temporal difference learning, generalizing from examples, relationship to

dynamic programming.

Unit-5
Analytical Learning-1- Introduction, learning with perfect domain
theories: PROLOG-EBG, remarks on explanation-based learning,
explanation-based learning of search control knowledge.

Analytical Learning-2-Using prior knowledge to alter the search

objective, using prior knowledge to augment search operators.

Combining Inductive and Analytical Learning – Motivation,

inductive-analytical approaches to learning, using prior knowledge
to initialize the hypothesis.
All expressions in first order logic are composed of:
– constants – e.g. bob, 23, a
– variables – e.g. X,Y,Z
– predicate symbols – e.g. female, father , predicates take on the values True or False only
– function symbols – e.g. age – functions can take on any constant as a value
– connectives – e.g. ∧, ∨, ¬, → (or ←)
– quantifiers – e.g. ∀, ∃
A term is
– any constant – e.g. bob
– any variable – e.g X
– any function applied to any term – e.g. age(bob)
A literal is any predicate or negated predicate applied to any terms – e.g. f emale(sue), ¬f ather(X,Y)
– A ground literal is a literal that contains no variables – e.g. female(sue )
– A positive literal is a literal that doesn’t contain a negated predicate – e.g. female(sue)
– A negative literal is a literal that contains a negated predicate – e.g ¬father(X,Y)
 First-Order Horn Clauses
learning the simple target concept Daughter (x, y), defined over pairs of people x and y.
The value of Daughter(x, y) is True when x is the daughter of y , and False otherwise.
Suppose each person in the data is described by the attributes : Name, Mother, Father, Male, Female.
each training example will consist of the description of two people in terms of these attributes , along with the value
of the target attribute Daughter .
(Name1 = Sharon, Mother1 = Louise, Father1 = Bob, Male1 = False, Female1 = True,
Name2 = Bob, Mother2 = Nora, Father2 = Victor, Male2 = True, Female2 = False,
Daughter1,2 = True)
very specific rule

General Rule
First-order Horn clauses may also refer to variables in the preconditions that do not occur in the post
conditions.

It is also possible to use the same predicates in the rule post -conditions and preconditions, enabling the
description of recursive rules.
FOIL Algorithm
 the outer loop corresponds to a variant of the SEQUENTIAL-COVERING al gorithm that is, it learns new rules one at
a time, removing the positive examples covered by the latest r ule before attempting to learn the next rule. Each iteration through
FOIL'S outer loop adds a new rule to its disjunctive hypothesis, Learned rules.
The inner loop corresponds to a variant of our earlier LEARN-ONE-RULE algorithm , extended to accommodate
first-order rules.
FOIL seeks only rules that predict when the target literal is Tru e, whereas our earlier algorithm would seek both rules that
predict when it is True and rules that predict when it is False.
Also, FOIL performs a simple hill climbing search rather than a beam search (equivalently, it uses a beam of width one).
Differences between FOIL and earlier algorithms.
1. In its general-to-specific search to 'learn each new rule, FOIL employs different detailed steps to generate candidate
specializations of the rule.
2. FOIL employs a PERFORMANCE measure, Foil-Gain, that differs from the entropy measure shown for
LEARN-ONE-RULE

Where
po - number of +ve bindings of rule R,
no - number of -ve bindings of R,
P1- number of +ve bindings of rule R‘(R+L),
n1 -is the number of -ve bindings of R'
t -is the number of +ve bindings of rule R that are still covered after adding
literal L to R.
 Generating Candidate Specializations in FOIL
The general-to-specific search in FOIL begins with the most general rule
GrandDaughter(x, y) <-
To specialize this initial rule, the above procedure generates the following literals as candidate additions to the rule preconditions:
Equal ( x , y ) , Female(x), Female(y), Father(x, y), Father(y, x), Father(x, z), Father(z, x), Father(y, z), Father(z,
y), and the negations of each of these literals (e.g., ¬ Equal(x, y)).
Now suppose that among the above literals FOIL greedily selects Father (y, z) as the most promising, leading to the more
specific rule
GrandDaughter(x, y) <- Father(y, z)
In generating candidate literals to further specialize this rule, FOIL will now
consider all of the literals mentioned in the previous step, plus the additional literals
Female(z), Equal(z, x), Equal(z, y), Father(z, w),
Father(w, z), and their negations.
If FOIL at this point were to select the literal Father(z, x) and on the next iteration select the literal Female(y) , this would
lead to the following rule, which covers only positive examples and hence terminates the search for further specializations of the
rule.

At this point, FOIL will remove all positive examples covered by this new rule. If additional positive examples remain to be
covered, then it will begin yet another general-to-specific search for an additional rule.
 Example
learn a set of rules for the target literal GrandDaughter(x, y)
Training data :
use the convention that P(x, y) can be read as "The P of x is y ."
1. GrandDaughter(Victor, Sharon)
2. Father(Sharon, Bob)
3. Father(Tom, Bob)
4. Female(Sharon)
5. Father(Bob, Victor)

To select the best specialization of the current rule, FOIL considers each distinct way in which the rule variables can bind to constants in the
training examples. For example, in the initial step when the rule is GrandDaughter(x, y) <-
The rule variables x and y are not constrained by any preconditions and may therefore bind in any combination to the four constants Victor,
Sharon, Bob, and Tom.
We will use the notation {x/Bob, y/Shar on} to denote a particular variable binding; that is, a substitution mapping each variable to a constant.
Given the four possible constants , there are 16 possible variable bindings for this initial rule.
The binding { xlvictor, ylSharon} corresponds to a positive example binding, because the training data includes the assertion
GrandDaughter(Victor, Sharon).
The other 15 bindings allowed by the rule (e.g., the binding {x/Bob, y/Tom}) constitute negative evidence for the rule in the current example,
because no corresponding assertion can be found in the training data.