Analytical Learning

• Inductive learning methods as neural network

and decision tree learning require a certain
number of training examples to achieve a given
levelof generalizationaccuracy, as reflected in
the theoretical bounds and experimental results.
• Analytical learning uses prior knowledge and
deductive reasoning toaugment the information
provided by the training examples, so that it is
not subject to these same bounds. This chapter
considers an analytical learning method called
explanation-based learning.

•In explanation-based learning, prior

knowledge is used to analyze or explain, how
each observed training example satisfies the
target concept.
• INTRODUCTION:
Decision tree learning,neural network
learning, inductive logic programming, and
genetic algorithms are all examples of
inductive methods.
• The key practical limit on these inductive
learners isthat they perform poorly when
insufficient data is available.

Explanation-based learning uses prior

knowledge to analyze, or explain each ,
training example in order to infer which
example features are relevant to the target
function and which are irrelevant. These
explanation enable it togeneralize more
accurately than inductive systems that rely on
the data alone.

Explanation-based learning uses prior

knowledge to reduce the complexity of the
hypothesis space to be searched, thereby
reducing sample complexity and improving
generalization accuracy of the learner.
• [Link] task of learning to play chess.

Suppose we would like our chess program to

learn to recognize important classes of game
positions, such as the target concept
"chessboard positions in which black will lose

its queen within two moves".

 Fig. Shows a positive training example of this target concept. Inducuve
learning methods could, of course, be employed to learn this target.
However, because the chessboard is fairly complex (there are 32 pieces
that may be on any of 64 squares), and because the particular patterns
that capture this concept are fairly subtle (involving the relative
positions of various pieces on the board), we would have to provide
thousands of training examples similar to the one concept.

FIGURE 11.1

A positive example of the target concept "chess positions in

which black will lose its queen within two moves." Note the
white knight is simultaneously attacking both the black king and
queen. Black must therefore move its king, enabling white to
capture its queen.

•Most people would be willing tosuggest a

general hypothesis for the target concept,
such as "board positions in which the black
king and queen are simultaneously attacked,"
andwould not even consider the (equally
consistent) hypothesis "board positions in

which fourwhite pawns are still in their

original locations."
 The answer appears to be that people rely

heavily onexplaining, or analyzing, the

example in terms of their prior
training
knowledge about the legal moves of chess.
• Ex. "positions which the queen will be lost
in

in two moves," most people would give an

explanation similar to the following: "Because

white's knight is attacking both the king and
queen, black must move out of check, thereby
allowing the knight tocapture the queen."

• The importance of such explanations is that

they provide the information needed to
rationally generalize from the details of the
training example to a correct general
hypothesis.

•Features of the training example that are

mentioned by the explanation are relevant to
the target concept and should be included
the general hypothesis others are not.
prior knowledge about the legal rules of
chess: knowledge of which moves are legal for

the knight and other pieces, the fact that

players must alternate moves in the game,
and the fact that to win the game one player
must capture his opponent's king.
Prior knowledge it is possible in principle to
calculate the optimal chess move for any
board position.

Explanation-based learning algorithm called PROLOG-EBG.

1.1 Inductive and Analytical Learning Problems

The essential difference between analytical and inductive learning

methods is that they assume two different formulations of the learning
problem:

In inductive learning, the learner is given a hypothesis space H from

which it must select an output hypothesis, and a set of training examples
D= ((x\,f (x~)). (
.,.(x,, f x,))}wheref s the target value forthe
(xi)i

instance xi. The desired output of the learner is a hypothesis h from H

that is consistent with these training examples.

In analytical learning, the input to the learner includes the same

hypothesis space H and trainingexamples D as forinductive [Link]
addition, the learner is provided an additional input: A domain theory B
consisting of background knowledge that can be used to explain observed
[Link] desired output of ,the learner is a hypothesis h
from H that is consistent with both the training examples D and the
domain theory B.
 chess exampleeach instance xiwould describe aparticula
chess position,and f (xi)would be True when xi is a positiu
for which black will lose its queen within two moves,and

False otherwise. We might define the hypothesis space H to

consist of sets of Horn clauses (if-then rules), where the
predicates used by the rules refer to the positions or relative
positions of specific pieces on the board.

The domain theory B would consist of a formalization of the

rules of chess, describing the legal moves,the fact that
players must take turns, and the fact that the game is won

when one player captures her opponent's king.

• Analytical learning, the learner must output a

hypothesis that is consistent with both the training
data and the domain theory. We say that
hypothesis h is consistentwith domain theory B
provided B does not entail the negation of h (i.e., B-
h).

• This additional constraint that the output hypothesis

must be consistent with B reduces the ambiguity
faced by the learnerwhen the data alone cannot
resolve among allhypotheses in [Link] net effect,
provided the domain theory iscorrect, is to increase
the accuracy of the output hypothesis.