Adversarial search

https://drive.google.com/file/d/0B8bQtt5J_O0vNjVGNzV0djJlTWc/edit?usp=sharing

Intelligent Agents

https://drive.google.com/file/d/0B8bQtt5J_O0vOS1veFQxUW5PLUU/edit?usp=sharing

Explanation Based Learning (EBL)

Humans appear to learn quite a lot from one example.
Basic idea: Use results from one examples problem solving effort next time around.
An EBL accepts 4 kinds of input:

A training example

-- what the learning sees in the world.

A goal concept

-- a high level description of what the program is supposed to learn.

A operational criterion

-- a description of which concepts are usable.

A domain theory

-- a set of rules that describe relationships between objects and actions in a domain.

From this EBL computes a generalisation of the training example that is sufficient not only to describe the goal concept but also satisfies the operational criterion.
This has two steps:

Explanation

-- the domain theory is used to prune away all unimportant aspects of the training example with respect to the goal concept.

Generalisation

-- the explanation is generalised as far possible while still describing the goal concept.

Information Extraction

Extracting the information for the following fields

• sales forecasting

• industrial process control

• customer research

• data validation

• risk management

• target marketing

Because of their adaptive and non-linear nature they have also been used in a number of

control system application domains like,

• process control in chemical plants

• unmanned vehicles

• robotics

• consumer electronics

Probabilistic Language Processing

Using logic to represent and reason we can represent knowledge about the world with

facts and rules, like the following ones:

bird(tweety).

fly(X) :- bird(X).

We can also use a theorem-prover to reason about the world and deduct new facts about

the world, for e.g.,

?- fly(tweety).

Yes

However, this often does not work outside of toy domains - non-tautologous certain

rules are hard to find.

A way to handle knowledge representation in real problems is to extend logic by using

certainty factors.

 In other words, replace

 IF condition THEN fact

with

IF condition with certainty x THEN fact with certainty f(x)

Unfortunately cannot really adapt logical inference to probabilistic inference, since the

latter is not context-free.

Replacing rules with conditional probabilities makes inferencing simpler.

Replace

smoking -> lung cancer

or

lotsofconditions, smoking -> lung cancer

with

P(lung cancer | smoking) = 0.6

Uncertainty is represented explicitly and quantitatively within probability theory, a

formalism that has been developed over centuries.

A probabilistic model describes the world in terms of a set S of possible states - the

sample space. We don’t know the true state of the world, so we (somehow) come up with

a probability distribution over S which gives the probability of any state being the true

one. The world usually described by a set of variables or attributes.

Consider the probabilistic model of a fictitious medical expert system. The ‘world’ is

described by 8 binary valued variables:

Review of Probability Theory

The primitives in probabilistic reasoning are random variables. Just like primitives in

Propositional Logic are propositions. A random variable is not in fact a variable, but a

function from a sample space S to another space, often the real numbers.

For example, let the random variable Sum (representing outcome of two die throws) be

defined thus: Sum(die1, die2) = die1 +die2

Each random variable has an associated probability distribution determined by the

underlying distribution on the sample space

Continuing our example : P(Sum = 2) = 1/36,

P(Sum = 3) = 2/36, . . . , P(Sum = 12) = 1/36

Conditional probability is defined as:

It means for any value x of A and any value y of B

Grammar Induction

All objects described are fixed or unique

"John is a student" student(john)

Here John refers to one unique person.

Objects described can be unique or variables to stand for a unique object

"All students are poor"

ForAll(S) [student(S) -> poor(S)]

Here S can be replaced by many different unique students.

This makes programs much more compact:

eg. ForAll(A,B)[brother(A,B) -> brother (B,A)] replaces half the possible statements about brothers

• Temporal => Represents truth over time.

• Modal => Represents doubt

• Higher order logics => Allows variable to represent many relations between objects

• Non-monotonic => Represents defaults

Given clauses C1 and C2, a clause C is a RESOLVENT of C1 and C2, if

1. There is a subset C1' = {A1, .., Am} of C1 of literals of the same sign, say

positive, and a subset C2' = {B1, .., Bn} of C2 of literals of the opposite sign, say

negative,

2. There are substitutions s1 and s2 that replace variables in C1' and C2' so as to

have new variables,

3. C2'' is obtained from C2 removing the negative signs from B1 .. Bn

4. There is an Most General Unifier s for the union of C1'.s1 and C2''.s2

and C is

((C1 - C1').s1 UNION (C2 - C2').s2).s

In symbols this Resolution inference rule becomes:

{C1, C2}

Let L be a list containing the initial state (L= the fringe)

Loop

if L is empty return failure

Node   select (L)

if Node is a goal

then return Node

(the path from initial state to Node)

else generate all successors of Node, and

merge the newly generated states into L

End Loop

Semantic Analysis

• Assigning meanings to the structures created by syntactic analysis.

• Mapping words and structures to particular domain objects in way consistent with

our knowledge of the world.

• Semantic can play an import role in selecting among competing syntactic analyses

and discarding illogical analyses.

– I robbed the bank -- bank is a river bank or a financial institution

• We have to decide the formalisms which will be used in the meaning

representation.

Ambiguity and Disambiguation

• Which knowledge representation will be used depends on the application --

Machine Translation, Database Query System.

• Requires the choice of representational framework, as well as the specific

meaning vocabulary (what are concepts and relationship between these concepts

-- ontology)

• Must be computationally effective.

• Common representational formalisms:

– first order predicate logic

– conceptual dependency graphs

– semantic networks

– Frame-based representations

Discourse Understanding

• Discourses are collection of coherent sentences (not arbitrary set of sentences)

• Discourses have also hierarchical structures (similar to sentences)

• anaphora resolution -- to resolve referring expression

– Mary bought a book for Kelly. She didn’t like it.

• She refers to Mary or Kelly. -- possibly Kelly

• It refers to what -- book.

– Mary had to lie for Kelly. She didn’t like it.

• Discourse structure may depend on application.

– Monologue

– Dialogue

– Human-Computer Interaction

Augmented Grammars

Parts-of-Speech (POS) Tagging

• Each word has a part-of-speech tag to describe its category.

• Part-of-speech tag of a word is one of major word groups (or its subgroups).

– open classes -- noun, verb, adjective, adverb

– closed classes -- prepositions, determiners, conjuctions, pronouns, particples

• POS Taggers try to find POS tags for the words.

•duck is a verb or noun? (morphological analyzer cannot make decision).

• A POS tagger may make that decision by looking the surrounding words.

– Duck! (verb)

– Duck is delicious for dinner. (noun)

Semantic Interpretation

Semantics: The meanings of the atomic symbols of the logic, and the rules for

determining the meanings of non-atomic expressions of the logic. It specifies what facts

in the world a sentence refers to. Hence, also specifies how you assign a truth value to a

sentence based on its meaning in the world. A fact is a claim about the world, and may be

true or false.

There are a number of logical systems with different syntax and semantics. We list below

a few of them.

Syntactic Processing

• Parsing -- converting a flat input sentence into a hierarchical structure that

corresponds to the units of meaning in the sentence.

• There are different parsing formalisms and algorithms.

• Most formalisms have two main components:

– grammar -- a declarative representation describing the syntactic structure

of sentences in the language.

– parser -- an algorithm that analyzes the input and outputs its structural

representation (its parse) consistent with the grammar specification.

• CFGs are in the center of many of the parsing mechanisms. But they are

complemented by some additional features that make the formalism more suitable

to handle natural languages.

UNIT V - artificial Intelligence, Communication,

UNIT V

APPLICATIONS

Communication

Natural Language Processing (NLP) is the process of computer analysis of input provided

in a human language (natural language), and conversion of this input into a useful form of

representation.

The field of NLP is primarily concerned with getting computers to perform useful and

interesting tasks with human languages. The field of NLP is secondarily concerned with

helping us come to a better understanding of human language.

• The input/output of a NLP system can be:

– written text                                                               

– speech

The following language related information are useful in NLP:

• Phonology – concerns how words are related to the sounds that realize them.

• Morphology – concerns how words are constructed from more basic meaning units called morphemes. A morpheme is the primitive unit of meaning in a language.

• Syntax – concerns how can be put together to form correct sentences and determines what structural role each word plays in the sentence and what phrases are subparts of other phrases.

• Semantics – concerns what words mean and how these meaning combine in sentences to form sentence meaning. The study of context-independent meaning.

UNIT V

APPLICATIONS

Communication

Natural Language Processing (NLP) is the process of computer analysis of input provided

in a human language (natural language), and conversion of this input into a useful form of

representation.

The field of NLP is primarily concerned with getting computers to perform useful and

interesting tasks with human languages. The field of NLP is secondarily concerned with

helping us come to a better understanding of human language.

• The input/output of a NLP system can be:

– written text                                                               

– speech

The following language related information are useful in NLP:

• Phonology – concerns how words are related to the sounds that realize them.

• Morphology – concerns how words are constructed from more basic meaning units called morphemes. A morpheme is the primitive unit of meaning in a language.

• Syntax – concerns how can be put together to form correct sentences and determines what structural role each word plays in the sentence and what phrases are subparts of other phrases.

• Semantics – concerns what words mean and how these meaning combine in sentences to form sentence meaning. The study of context-independent meaning.

• Pragmatics – concerns how sentences are used in different situations and how use affects the interpretation of the sentence.

• Discourse – concerns how the immediately preceding sentences affect the interpretation of the next sentence. For example, interpreting pronouns and interpreting the temporal aspects of the information.

• World Knowledge – includes general knowledge about the world. What each language user must know about the other’s beliefs and goals.

Communication as action

• We will mostly concerned with written text (not speech).

• To process written text, we need:

– lexical, syntactic, semantic knowledge about the language

– discourse information, real world knowledge

• To process spoken language, we need everything required to process written text, plus the challenges of speech recognition and speech synthesis.

There are two components of NLP.

• Natural Language Understanding

– Mapping the given input in the natural language into a useful representation.

– Different level of analysis required

morphological analysis,

syntactic analysis,

semantic analysis,

discourse analysis.

• Natural Language Generation

– Producing output in the natural language from some internal representation.

– Different level of synthesis required,

deep planning (what to say),

syntactic generation

• NL Understanding is much harder than NL Generation. But, still both of them are hard.

The difficulty in NL understanding arises from the following facts:

• Natural language is extremely rich in form and structure, and very ambiguous.

– How to represent meaning,

– Which structures map to which meaning structures.

• One input can mean many different things. Ambiguity can be at different levels.

– Lexical (word level) ambiguity -- different meanings of words

– Syntactic ambiguity -- different ways to parse the sentence

– Interpreting partial information -- how to interpret pronouns

– Contextual information -- context of the sentence may affect the meaning of that sentence.

• Many input can mean the same thing.

• Interaction among components of the input is not clear.

Neural Networks

Artificial neural networks are among the most powerful learning models. They have the

versatility to approximate a wide range of complex functions representing multidimensional

input-output maps. Neural networks also have inherent adaptability, and can

perform robustly even in noisy environments.

An Artificial Neural Network (ANN) is an information processing paradigm that is

inspired by the way biological nervous systems, such as the brain, process information.

The key element of this paradigm is the novel structure of the information processing

system. It is composed of a large number of highly interconnected simple processing

elements (neurons) working in unison to solve specific problems. ANNs, like people,

learn by example. An ANN is configured for a specific application, such as pattern

recognition or data classification, through a learning process. Learning in biological

systems involves adjustments to the synaptic connections that exist between the neurons.

This is true of ANNs as well. ANNs can process information at a great speed owing to

their highly massive parallelism.

Neural networks, with their remarkable ability to derive meaning from complicated or

imprecise data, can be used to extract patterns and detect trends that are too complex to

be noticed by either humans or other computer techniques. A trained neural network can

be thought of as an "expert" in the category of information it has been given to analyse.

This expert can then be used to provide projections given new situations of interest and

answer "what if" questions. Other advantages include:

1. Adaptive learning: An ability to learn how to do tasks based on the data given for

training or initial experience.

2. Self-Organisation: An ANN can create its own organisation or representation of

the information it receives during learning time.

3. Real Time Operation: ANN computations may be carried out in parallel, and

special hardware devices are being designed and manufactured which take

advantage of this capability.

4. Fault Tolerance via Redundant Information Coding: Partial destruction of a

network leads to the corresponding degradation of performance. However, some

network capabilities may be retained even with major network damage.

Biological Neural Networks

Much is still unknown about how the brain trains itself to process information, so theories

abound. In the human brain, a typical neuron collects signals from others through a host

of fine structures called dendrites. The neuron sends out spikes of electrical activity

through a long, thin stand known as an axon, which splits into thousands of branches. At

the end of each branch, a structure called a synapse converts the activity from the axon

into electrical effects that inhibit or excite activity from the axon into electrical effects

that inhibit or excite activity.

Artificial Neural Networks

Artificial neural networks are represented by a set of nodes, often arranged in layers, and

a set of weighted directed links connecting them. The nodes are equivalent to neurons,

while the links denote synapses. The nodes are the information processing units and the

links acts as communicating media.

Instance based learning

In a nutshell, the variable elimination procedure repeats the following steps.

1. Pick a variable Xi

2. Multiply all expressions involving that variable, resulting in an expression f over a

number of variables (including Xi)

3. Sum out Xi, i.e. compute and store

For the multiplication, we must compute a number for each joint instantiation of all variables in f, so complexity is exponential in the largest number of variables participating in one of these multiplicative subexpressions.

If we wish to compute several marginals at the same time, we can use Dynamic Programming to avoid the redundant computation that would be involved if we used variable elimination repeatedly.

Exact inferencing in a general Bayes net is a hard problem. However, for networks with

some special topologies efficient solutions inferencing techniques. We discuss one such technque for a class of networks called Poly-trees.

Statistical learning methods

Definition:

The problem is to learn a function mapping examples into two classes: positive and

negative. We are given a database of examples already classified as positive or negative.

Concept learning: the process of inducing a function mapping input examples into a

Boolean output.

Examples:

  Classifying objects in astronomical images as stars or galaxies

  Classifying animals as vertebrates or invertebrates

Class of Tasks: Predicting poisonous mushrooms

Performance: Accuracy of classification

Experience: Database describing mushrooms with their class

Knowledge to learn: Function mapping mushrooms to {0,1} where 0:not-poisonous and

1:poisonous

Representation of target knowledge: conjunction of attribute values.

Learning mechanism: candidate-elimination

Representation of instances:

Features:

• color {red, brown, gray}

• size {small, large}

• shape {round,elongated}

• land {humid,dry}

• air humidity {low,high}

• texture {smooth, rough}

Input and Output Spaces:

X : The space of all possible examples (input space).

Y: The space of classes (output space).

An example in X is a feature vector X.

For instance: X = (red,small,elongated,humid,low,rough)

X is the cross product of all feature values.

Only a small subset of instances is available in the database of examples.

Learning with complete data and hidden variables

we must state some formal definitions:

Definition 1: Let X be some set of objects, with elements noted as x. Thus,X = {x}.

Definition 2: A fuzzy set A in X is characterized by a membership function mA(x) which maps each point in X onto the real interval [0.0, 1.0]. As mA(x) approaches 1.0, the "grade of membership" of x in A increases.

Definition 3: A is EMPTY iff for all x, mA(x) = 0.0.

Definition 4: A = B iff for all x: mA(x) = mB(x) [or, mA = mB].

Definition 5: mA' = 1 - mA.

Definition 6: A is CONTAINED in B iff mA <= mB.

Definition 7: C = A UNION B, where: mC(x) = MAX(mA(x), mB(x)).

Definition 8: C = A INTERSECTION B where: mC(x) = MIN(mA(x),mB(x)).

Reinforcement learning:

In reinforcement learning a teacher is available, but the teacher instead of directly providing the desired action corresponding to a perception, return reward and punishment to the learner for its action corresponding to a perception.

Examples include a robot in a unknown terrain where its get a punishment when its hits

an obstacle and reward when it moves smoothly.

In order to design a learning system the designer has to make the following choices

based on the application.

Active Reinforcement learning:

Here not only a teacher is available, the learner has the freedom to ask

the teacher for suitable perception-action example pairs which will help the learner to

improve its performance.

Consider a news recommender system which tries to learn an users preferences and categorize news articles as interesting or uninteresting to the user.

The system may present a particular article (of which it is not sure) to the user and ask

whether it is interesting or not.

Passive Reinforcement learning:

By instantiating subsets of the variables, we can break loops in the graph. Unfortunately, when the cutset is large, this is very slow. By instantiating only a subset of values of the cutset, we can compute lower bounds on the probabilities of interest. Alternatively, we can sample the cutsets jointly, a technique known as block Gibbs sampling.

Generalization in Reinforcement Learning

Example to generalize Reinforcement Learning

Training Examples:

D : The set of training examples.

D is a set of pairs { (x,c(x)) }, where c is the target concept. c is a subset of the universe

of discourse or the set of all possible instances.

Example of D:

((red,small,round,humid,low,smooth), poisonous)

((red,small,elongated,humid,low,smooth), poisonous)

((gray,large,elongated,humid,low,rough), not-poisonous)

((red,small,elongated,humid,high,rough), poisonous)

Hypothesis Representation

Any hypothesis h is a function from X to Y h: X   Y

We will explore the space of conjunctions.

Special symbols:

  ? Any value is acceptable

  0 no value is acceptable

Consider the following hypotheses:

(?,?,?,?,?,?): all mushrooms are poisonous

(0,0,0,0,0,0): no mushroom is poisonous

Hypotheses Space:

The space of all hypotheses is represented by H

Let h be a hypothesis in H.

Let X be an example of a mushroom.

if h(X) = 1 then X is poisonous, otherwise X is not-poisonous

Our goal is to find the hypothesis, h*, that is very “close” to target concept c.

A hypothesis is said to “cover” those examples it classifies as positive.