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.

Inductive Learning

• Analyzing words into their linguistic components (morphemes).

• Morphemes are the smallest meaningful units of language.

• Ambiguity: More than one alternatives

flies flyVERB+PROG

flyNOUN+PLU

adam adam+ACC - the man (accusative)

adam+P1SG - my man

ada+P1SG+ACC - my island (accusative)

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)

Lexical Processing

• The purpose of lexical processing is to determine meanings of individual words.

• Basic methods is to lookup in a database of meanings – lexicon

• We should also identify non-words such as punctuation marks.

• Word-level ambiguity -- words may have several meanings, and the correct one

cannot be chosen based solely on the word itself.

– bank in English

• Solution -- resolve the ambiguity on the spot by POS tagging (if possible) or passon

the ambiguity to the other levels.

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.

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.

Knowledge Representation for NLP

• 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

Forms of Learning

Several classification of learning systems are possible based on the above components as

follows:

Goal/Task/Target Function:

Prediction: To predict the desired output for a given input based on previous input/output

pairs. E.g., to predict the value of a stock given other inputs like market index, interest

rates etc.

Categorization: To classify an object into one of several categories based on features of

the object. E.g., a robotic vision system to categorize a machine part into one of the

categories, spanner, hammer etc based on the parts’ dimension and shape.

Clustering: To organize a group of objects into homogeneous segments. E.g., a satellite

image analysis system which groups land areas into forest, urban and water body, for

better utilization of natural resources.

Planning: To generate an optimal sequence of actions to solve a particular problem. E.g.,

an Unmanned Air Vehicle which plans its path to obtain a set of pictures and avoid

enemy anti-aircraft guns.

Models:

• Propositional and FOL rules

• Decision trees

• Linear separators

• Neural networks

• Graphical models

• Temporal models like hidden Markov models

Learning Rules:

Learning rules are often tied up with the model of learning used. Some common rules are

gradient descent, least square error, expectation maximization and margin maximization.

Version 1 CSE IIT, Kharagpur

Experiences:

Learning algorithms use experiences in the form of perceptions or perception action pairs

to improve their performance. The nature of experiences available varies with

applications. Some common situations are described below.

Supervised learning: In supervised learning a teacher or oracle is available which

provides the desired action corresponding to a perception. A set of perception action pair

provides what is called a training set. Examples include an automated vehicle where a set

of vision inputs and the corresponding steering actions are available to the learner.

Unsupervised learning: In unsupervised learning no teacher is available. The learner only

discovers persistent patterns in the data consisting of a collection of perceptions. This is

also called exploratory learning. Finding out malicious network attacks from a sequence

of anomalous data packets is an example of unsupervised learning.

Active 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.

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.

UNIT IV

LEARNING

Introduction to Learning

Machine Learning is the study of how to build computer systems that adapt and improve

with experience. It is a subfield of Artificial Intelligence and intersects with cognitive

science, information theory, and probability theory, among others.

Classical AI deals mainly with deductive reasoning, learning represents inductive

reasoning. Deductive reasoning arrives at answers to queries relating to a particular

situation starting from a set of general axioms, whereas inductive reasoning arrives at

general axioms from a set of particular instances.

Classical AI often suffers from the knowledge acquisition problem in real life

applications where obtaining and updating the knowledge base is costly and prone to

errors. Machine learning serves to solve the knowledge acquisition bottleneck by

obtaining the result from data by induction.

Machine learning is particularly attractive in several real life problem because of the

following reasons:

• Some tasks cannot be defined well except by example

• Working environment of machines may not be known at design time

• Explicit knowledge encoding may be difficult and not available

• Environments change over time

• Biological systems learn

Recently, learning is widely used in a number of application areas including,

• Data mining and knowledge discovery

• Speech/image/video (pattern) recognition

• Adaptive control

• Autonomous vehicles/robots

• Decision support systems

• Bioinformatics

• WWW

Formally, a computer program is said to learn from experience E with respect to some

class of tasks T and performance measure P, if its performance at tasks in T, as measured

by P, improves with experience E.

Thus a learning system is characterized by:

• task T

• experience E, and

• performance measure P