UNIT-5

1.1 LEARNING SETS OF RULES

In many cases it is useful to learn the target function represented as a set of if-then rules
that jointly define the function. One way to learn sets of rules is to first learn a decision tree,
then translate the tree into an equivalent set of rules-one rule for each leaf node in the tree. A
second method, is to use a genetic algorithm that encodes each rule set as a bit string and uses
genetic search operators to explore this hypothesis space.
In this chapter we explore a variety of algorithms that directly learn rule sets and that differ from
these algorithms in two key respects. First, they are designed to learn sets of first-order rules that
contain variables. This is significant because first-order rules are much more expressive than
propositional rules. Second, the algorithms discussed here use sequential covering algorithms
that learn one rule at a time to incrementally grow the final set of rules.
As an example of first-order rule sets, consider the following two rules that jointly describe the
target concept Ancestor. Here we use the predicate Parent(x, y) to indicate that y is the mother
or father of x, and the predicate Ancestor(x, y) to indicate that y is an ancestor of related by an
arbitrary number of family generations.
IF Parent (x, y) THEN Ancestor(x,y)
IF Parent(x, z) ˄ Ancestor(z, y) THEN Ancestor(x, y)
Note these two rules compactly describe a recursive function that would be very difficult to
represent using a decision tree or other propositional representation. One way to see the
representational power of first-order rules is to consider the general purpose programming
language PROLOG. In PROLOG, programs are sets of first-order rules such as the two shown
above (rules of this form are also called Horn clauses). In fact, when stated in a slightly different
syntax the above rules form a valid PROLOG program for computing the Ancestor relation. In
this light, a general purpose algorithm capable of learning such rule sets may be viewed as an
algorithm for automatically inferring PROLOG programs from examples. In this chapter we
explore learning algorithms capable of learning such rules, given appropriate sets of training
examples.

1.2 SEQUENTIAL COVERING ALGORITHMS

Here we consider a family of algorithms for learning rule sets based on the strategy of learning
one rule, removing the data it covers, then iterating this process. Such algorithms are called
sequential covering algorithms. To elaborate, imagine we have a subroutine LEARN-ONE-
RULE that accepts a set of positive and negative training examples as input, then outputs a
single rule that covers many of the positive examples and few of the negative examples. We
require that this input rule have high accuracy, but not necessarily high coverage. By high
accuracy, we mean the predictions it makes should be correct. By accepting low coverage, we
mean it need not make predictions for every training example.
Given this LEARN-ONE-RULE subroutine for learning a single rule, one obvious approach to
learning a set of rules is to invoke LEARN-ONE-RULE on all the available training examples,
remove any positive examples covered by the rule it learns, then invoke it again to learn a second
rule based on the remaining training examples. This procedure can be iterated as many times as
desired to learn a disjunctive set of rules that together cover any desired fraction of the positive
examples. This is called a sequential covering algorithm because it sequentially learns a set of
rules that together cover the full set of positive examples. The final set of rules can then be sorted
so that more accurate rules will be considered first when a new instance must be classified. A
prototypical sequential covering algorithm is described in Table 10.1.

1.2.1 General to Specific Beam Search

One effective approach to implementing LEARN-ONE-RULE organize the hypothesis space
search in the same general fashion as the ID3 algorithm, but to follow only the most promising
branch in the tree at each step. As illustrated in the search tree of Figure 10.1, the search begins
by considering the most general rule precondition possible (the empty test that matches every
instance), then greedily adding the attribute test that most improves rule performance measured
over the training examples. Once this test has been added, the process is repeated by greedily
adding a second attribute test, and so on. Like ID3, this process grows the hypothesis by greedily
adding new attribute tests until the hypothesis reaches an acceptable level of performance.
Unlike ID3, this implementation of LEARN-ONE –RULE follows only a single descendant at
each search step-the attribute-value pair yielding the best performance-rather than growing a
subtree that covers all possible values of the selected attribute. This approach to implementing
LEARN-ONE-RULE performs a general-to-specific search through the space of possible rules in
search of a rule with high accuracy, though perhaps incomplete coverage of the data. As in
decision tree learning, there are many ways to define a measure to select the "best" descendant.
To follow the lead of ID3 let us for now define the best descendant as the one whose covered
examples have the lowest entropy (recall Equation 3.31).
The general-to-specific search suggested above for the LEARN-ONE-RULE algorithm is a
greedy depth-first search with no backtracking. As with any greedy search, there is a danger that
a suboptimal choice will be made at any step. To reduce this risk, we can extend the algorithm to
perform a beam search; that is, a search in which the algorithm maintains a list of the k best
candidates at each step, rather than a single best candidate. On each search step, descendants
(specializations) are generated for each of these k best candidates, and the resulting set is again
reduced to the k most promising members. Beam search keeps track of the most promising
alternatives to the current top-rated hypothesis, so that all of their successors can be considered at
each search step. This general to specific beam search algorithm is used by the CN2 program
described by Clark and Niblett(1989). The algorithm is described in Table 10.2.

A few remarks on the LEARN-ONE-RULE algorithm of Table 10.2 are in order. First, note that
each hypothesis considered in the main loop of the algorithm is a conjunction of attribute-value
constraints. Each of these conjunctive hypotheses corresponds to a candidate set of preconditions
for the rule to be learned and is evaluated by the entropy of the examples it covers. The search
considers increasingly specific candidate hypotheses until it reaches a maximally specific
hypothesis that contains all available attributes. The rule that is output by the algorithm is the
rule encountered during the search whose PERFORMANCE is greatest-not necessarily the final
hypothesis generated in the search. The postcondition for the output rule is chosen only in the
final step of the algorithm, after its precondition (represented by the variable Best_hypothesis)
has been determined. The algorithm constructs the rule postcondition to predict the value of the
target attribute that is most common among the examples covered by the rule precondition.
Finally, note that despite the use of beam search to reduce the risk, the greedy search may still
produce suboptimal rules. However, even when this occurs the SEQUENTIALCOVERING
algorithm can still learn a collection of rules that together cover the training examples, because it
repeatedly calls LEARN-ONE-RULE on the remaining uncovered examples.

1.3 LEARNING FIRST-ORDER RULES

In the previous sections we discussed algorithms for learning sets of propositional (i.e., variable-
free) rules. In this section, we consider learning rules that contain Variables - in particular,
learning first-order Horn theories. Our motivation for considering such rules is that they are
much more expressive than propositional rules. Inductive learning of first-order rules or theories
is often referred to as Inductive Logic Programming (or LP for short), because this process can
be viewed as automatically inferring PROLOG programs from examples. PROLOG is a
general purpose, Turing-equivalent programming language in which programs are expressed as
collections of Horn clauses.

1.3.1 First-Order Horn Clauses

To see the advantages of first-order representations over propositional (variable-free)
representations, consider the task of 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. Hence, 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. For
example, the following is a positive example in which Sharon is the daughter of Bob:
Although it is correct, this rule is so specific that it will rarely, if ever, be useful in classifying
future pairs of people. The problem is that propositional representations offer no general way to
describe the essential relations among the values of the attributes. In contrast, a program using
first-order representations could learn the following general rule:
IF Father(y, x) ˄ Female(y), THEN Daughter(x, y)
where x and y are variables that can be bound to any person. First-order Horn clauses may also
refer to variables in the preconditions that do not occur in the postconditions. For example, one
rule for GrandDaughter might be
IF Father(y, z) ˄ Mother(z, x) ˄ Female(y)
THEN GrandDaughter(x, y)
Note the variable z in this rule, which refers to the father of y, is not present in the rule
postconditions. Whenever such a variable occurs only in the preconditions, it is assumed to be
existentially quantified; that is, the rule preconditions are satisfied as long as there exists at least
one binding of the variable that satisfies the corresponding literal. It is also possible to use the
same predicates in the rule postconditions and preconditions, enabling the description of
recursive rules. For example, the two rules at the beginning of this chapter provide a recursive
definition of the concept Ancestor (x, y). ILP learning methods such-as those described below
have been demonstrated to learn a variety of simple recursive functions, such as the above
Ancestor function, and functions for sorting the elements of a list, removing a specific element
from a list, and appending two lists.

1.4 LEARNING SETS OF FIRST-ORDER RULES: FOIL

A variety of algorithms has been proposed for learning first-order rules, or Horn clauses.
In this section we consider a program called FOIL (Quinlan 1990) that employs an approach
very similar to the SEQUENTIAL-COVERING and LEARNING-ONE-RULE algorithms of
the previous section. In fact, the FOIL program is the natural extension of these earlier
algorithms to first-order representations. Formally, the hypotheses learned by FOIL are sets of
first-order rules, where each rule is similar to a Horn clause with two exceptions. First, the rules
learned by FOIL are more restricted than general Horn clauses, because the literals are not
permitted to contain function symbols (this reduces the complexity of the hypothesis space
search). Second, FOIL rules are more expressive than Horn clauses, because the literals
appearing in the body of the rule may be negated. FOIL has been applied to a variety of problem
domains. For example, it has been demonstrated to learn a recursive definition of the
QUICKSORT algorithm and to learn to discriminate legal from illegal chess positions.
The FOIL algorithm is summarized in Table 10.4. Notice the outer loop corresponds to a
variant of the SEQUENTIAL-COVER algorithm discussed earlier; that is, it learns new rules
one at a time, removing the positive examples covered by the latest rule before attempting to
learn the next rule. The inner loop corresponds to a variant of our earlier LEARN-ONE-RULE
algorithm, extended to accommodate first-order rules. Note also there are a few minor
differences between FOIL and these earlier algorithms. In particular, FOIL seeks only rules that
predict when the target literal is True, 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
hillclimbing search rather than a beam search (equivalently, it uses a beam of width one). The
hypothesis space search performed by FOIL is best understood by viewing it hierarchically.
Each iteration through FOIL'S outer loop adds a new rule to its disjunctive hypothesis, Learned-
Rules. The effect of each new rule is to generalize the current disjunctive hypothesis (i.e., to
increase the number of instances it classifies as positive), by adding a new disjunct. Viewed at
this level, the search is a specific-to-general search through the space of hypotheses, beginning
with the most specific empty disjunction and terminating when the hypothesis is sufficiently
general to cover all positive training examples. The inner loop of FOIL performs a finer -grained
search to determine the exact definition of each new rule. This inner loop searches a second
hypothesis space, consisting of conjunctions of literals, to find a conjunction that will form the
preconditions for the new rule. Within this hypothesis space, it conducts a general-to-specific,
hill-climbing search, beginning with the most general preconditions possible (the empty
precondition), then adding literals one at a time to specialize the rule until it avoids all negative
examples.

The two most substantial differences between FOIL and our earlier SEQUENTIAL-COVER and
LEARN-ONE-RULE algorithm follow from the requirement that it accommodate first-order
rules. These differences are:
1. In its general-to-specific search to 'learn each new rule, FOIL employs different detailed steps
to generate candidate specializations of the rule. This difference follows from the need to
accommodate variables in the rule preconditions.
2. FOIL employs a PERFORMANCE measure, Foil-Gain, that differs from the entropy
measure shown for LEARN-ONE-RULE shown in Table 10.2. This difference follows from the
need to distinguish between different bindings of the rule variables and from the fact that FOIL
seeks only rules that cover positive
examples.

1.4.1 Generating Candidate Specializations in FOIL

To generate candidate specializations of the current rule, FOIL generates a variety of new
literals, each of which may be individually added to the rule preconditions. More precisely,
suppose the current rule being considered is
1.4.2 Guiding the Search in FOIL
To select the most promising literal from the candidates generated at each step, FOIL considers
the performance of the rule over the training data. In doing this, it considers all possible bindings
of each variable in the current rule. To illustrate this process, consider again the example in
which we seek to learn a set of rules for the target literal GrandDaughter(x, y). For illustration,
assume the training data includes the following simple set of assertions, where we use the
convention that P(x, y) can be read as "The P of x is y ."
GrandDaughter(Victor, Sharon) Father(Sharon, Bob) Father(Tom, Bob)
Female(Sharon) Father(Bob, Victor)
1.4.3 Learning Recursive Rule Sets

1.4.4 Summary of FOIL

To summarize, FOIL extends the sequential covering algorithm of CN2 to handle the case of
learning first-order rules similar to Horn clauses. To learn each rule FOIL performs a general-to-
specific search, at each step adding a single new literal to the rule preconditions. The new litera l
may refer to variables already mentioned in the rule preconditions or postconditions, and may
introduce new variables as well. At each step, it uses the Foil-Gain function of Equation (10.1)
to select among the candidate new literals. If new literals are allowed to refer to the target
predicate, then FOIL can, in principle, learn sets of recursive rules. While this introduces the
complexity of avoiding rule sets that result in infinite recursion, FOIL has been demonstrated to
successfully learn recursive rule sets in several cases. In the case of noise-free training data,
FOIL may continue adding new literals to the rule until it covers no negative examples. To
handle noisy data, the search is continued until some tradeoff occurs between rule accuracy,
coverage, and complexity. FOIL uses a minimum description length approach to halt the growth
of rules, in which new literals are added only when their description length is shorter than the
description length of the training data they explain. The details of this strategy are given in
Quinlan (1990). In addition, FOIL post-prunes each rule it learns, using the same rule post-
pruning strategy used for decision trees.
1.5 INDUCTION AS INVERTED DEDUCTION
1.6 INVERTING RESOLUTION
A general method for automated deduction is the resolution rule introduced by Robinson
(1965). The resolution rule is a sound and complete rule for deductive inference in first-order
logic. Therefore, it is sensible to ask whether we can invert the resolution rule to form an inverse
entailment operator. The answer is yes, and it is just this operator that forms the basis of the
CIGOL program introduced by Muggleton and Buntine (1988).
1.7 ANALYTICAL LEARNING
Inductive learning methods such as neural network and decision tree learning require a
certain number of training examples to achieve a given level of generalization accuracy, as
reflected in the theoretical bounds and experimental results discussed in earlier chapters.
Analytical learning uses prior knowledge and deductive reasoning to augment 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 (EBL). In explanation-
based learning, prior knowledge is used to analyze, or explain, how each observed training
example satisfies the target concept. This explanation is then used to distinguish the relevant
features of the training example from the irrelevant, so that examples can be generalized based
on logical rather than statistical reasoning. Explanation-based learning has been successfully
applied to learning search control rules for a variety of planning and scheduling tasks.
Inductive learning methods generalize from observed training examples by identifying features
that empirically distinguish positive from negative training examples. Decision tree learning,
neural network learning, inductive logic programming, and genetic algorithms are all examples
of inductive methods that operate in this fashion. The key practical limit on these inductive
learners is that they perform poorly when insufficient data is available. Theoretical analysis
shows that there are fundamental bounds on the accuracy that can be achieved when learning
inductively from a given number of training examples. Can we develop learning methods that
are not subject to these fundamental bounds on learning accuracy imposed by the amount of
training data available?
Yes, if we are willing to reconsider the formulation of the learning problem itself. One way is to
develop learning algorithms that accept explicit prior knowledge as an input, in addition to the
input training data. Explanation-based learning is one such approach. It 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 explanations enable it to generalize more
accurately than inductive systems that rely on the data alone. Inductive logic programming
systems such as CIGOL also use prior background knowledge to guide learning. However, they
use their background knowledge to infer features that augment the input descriptions of
instances, thereby increasing the complexity of the hypothesis space to be searched. In contrast,
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. To capture the intuition underlying explanation-based learning, consider
the task of learning to play chess. In particular, 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." Figure 11.1 shows a positive
training example of this target concept. Inductive learning methods could, of course, be
employed to learn this target concept. 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 in Figure 1 1.1 to expect
an inductively learned hypothesis to generalize correctly to new situations.
What is interesting about this chess-learning task is that humans appear to learn such target
concepts from just a handful of training examples! In fact, after considering only the single
example shown in Figure 1 1.1, most people would be willing to suggest a general hypothesis for
the target concept, such as "board positions in which the black king and queen are
simultaneously attacked," and would not even consider the (equally consistent) hypothesis
"board positions in which four white pawns are still in their original locations." How is it that
humans can generalize so successfully from just this one example? The answer appears to be that
people rely heavily on explaining, or analyzing, the training example in terms of their prior
knowledge about the legal moves of chess. If asked to explain why the training example of
Figure 11.1 is a positive example of "positions in which the queen will be lost 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 to
capture 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 (e.g., the
position of the white knight, black king, and black queen) are relevant to the target concept and
should be included in the general hypothesis. In contrast, features of the example that are not
mentioned by the explanation (e.g., the fact that there are six black pawns on the board) can be
assumed to be irrelevant details.

1.8 LEARNING WITH PERFECT DOMAIN THEORIES: PROLOG-EBG

We consider explanation-based learning from domain theories that are perfect, that is,
domain theories that are correct and complete. A domain theory is said to be correct if each of its
assertions is a truthful statement about the world. A domain theory is said to be complete with
respect to a given target concept and instance space, if the domain theory covers every positive
example in the instance space. Put another way, it is complete if every instance that satisfies the
target concept can be proven by the domain theory to satisfy it. Notice our definition of
completeness does not require that the domain theory be able to prove that negative examples do
not satisfy the target concept. However, if we follow the usual PROLOG convention that
unprovable assertions are assumed to be false, then this definition of completeness includes full
coverage of both positive and negative examples by the domain theory. The reader may well ask
at this point whether it is reasonable to assume that such perfect domain theories are available to
the learner. After all, if the learner had a perfect domain theory, why would it need to learn?
There are two responses to this question.
 First, there are cases in which it is feasible to provide a perfect domain theory. Our earlier
chess problem provides one such case, in which the legal moves of chess form a perfect
domain theory from which the optimal chess playing strategy can (in principle) be
inferred. Furthermore, although it is quite easy to write down the legal moves of chess
that constitute this domain theory, it is extremely difficult to write down the optimal
chess-playing strategy. In such cases, we prefer to provide the domain theory to the
learner and rely on the learner to formulate a useful description of the target concept (e.g.,
"board states in which I am about to lose my queen") by examining and generalizing
from specific training examples.
 Second, in many other cases it is unreasonable to assume that a perfect domain theory is
available. It is difficult to write a perfectly correct and complete theory even for our
relatively simple SafeToStack problem.
A more realistic assumption is that plausible explanations based on imperfect domain
theories must be used, rather than exact proofs based on perfect knowledge.
Nevertheless, we can begin to understand the role of explanations in learning by
considering the ideal case of perfect domain theories.
This section presents an algorithm called PROLOG-EBG(Kedar-Cabelli and McCarty 1987) that
is representative of several explanation-based learning algorithms. PROLOG-EBG is a
sequential covering algorithm. In other words, it operates by learning a single Horn clause rule,
removing the positive training examples covered by this rule, then iterating this process on the
remaining positive examples until no further positive examples remain uncovered. When given a
complete and correct domain theory, PROLOG-EBG is guaranteed to output a hypothesis (set of
rules) that is itself correct and that covers the observed positive training examples. For any set of
training examples, the hypothesis output by PROLOG-EBG constitutes a set of logically
sufficient conditions for the target concept, according to the domain theory. PROLOG-EBG is a
refinement of the EBG algorithm introduced by Mitchell et al. (1986) and is similar to the EGGS
algorithm described by DeJong and Mooney (1986).
The explanation for the current training example is shown in Figure 11.2. Note the bottom of
this figure depicts in graphical form the positive training example SafeToStack (Obj1 , 0bj2)
from Table 11.1. The top of the figure depicts the explanation constructed for this training
example. Notice the explanation, or proof, states that it is SafeToStack Obj1 on 0bj2 because
Obj1 is Lighter than Obj2. Furthermore, Obj1 is known to be Lighter, because its Weight can be
inferred from its Density and Volume, and because the Weight of 0bj2 can be inferred from the
default weight of an Endtable. The specific Horn clauses that underlie this explanation are
shown in the domain theory of Table 1 1.1. Notice that the explanation mentions only a small
fraction of the known attributes of Obj1and 0bj2 (i.e., those attributes corresponding to the
shaded region in the figure). While only a single explanation is possible for the training example
and domain theory shown here, in general there may be multiple possible explanations.
In such cases, any or all of the explanations may be used. While each may give rise to a
somewhat different generalization of the training example, all will be justified by the given
domain theory. In the case of PROLOG-EBG, the explanation is generated using a backward
chaining search as performed by PROLOG. PROLOGEBG, like PROLOG, halts once it finds
the first valid proof.
1.9 REINFORCEMENT LEARNING
Reinforcement learning addresses the question of how an autonomous agent that senses
and acts in its environment can learn to choose optimal actions to achieve its goals. This very
generic problem covers tasks such as learning to control a mobile robot, learning to optimize
operations in factories, and learning to play board games. Each time the agent performs an
action in its environment, a trainer may provide a reward or penalty to indicate the desirability of
the resulting state. For example, when training an agent to play a game the trainer might provide
a positive reward when the game is won, negative reward when it is lost, and zero reward in all
other states. The task of the agent is to learn from this indirect, delayed reward, to choose
sequences of actions that produce the greatest cumulative reward. This chapter focuses on an
algorithm called Q learning that can acquire optimal control strategies from delayed rewards,
even when the agent has no prior knowledge of the effects of its actions on the environment.
Reinforcement learning algorithms are related to dynamic programming algorithms frequently
used to solve optimization problems. Consider building a learning robot. The robot, or agent,
has a set of sensors to observe the state of its environment, and a set of actions it can perform to
alter this state. For example, a mobile robot may have sensors such as a camera and sonars, and
actions such as "move forward" and "turn." Its task is to learn a control strategy, or policy, for
choosing actions that achieve its goals. For example, the robot may have a goal of docking onto
its battery charger whenever its battery level is low. This chapter is concerned with how such
agents can learn successful control policies by experimenting in their environment. We assume
that the goals of the agent can be defined by a reward function that assigns a numerical value-an
immediate payoff-to each distinct action the agent may take from each distinct state. For
example, the goal of docking to the battery charger can be captured by assigning a positive
reward (e.g., +l00) to state-action transitions that immediately result in a connection to the
charger and a reward of zero to every other state-action transition. This reward function may be
built into the robot, or known only to an external teacher who provides the reward value for each
action performed by the robot. The task of the robot is to perform sequences of actions, observe
their consequences, and learn a control policy. The control policy we desire is one that, from any
initial state, chooses actions that maximize the reward accumulated over time by the agent. This
general setting for robot learning is summarized in Figure 13.1. As is apparent from Figure 13.1,
the problem of learning a control policy to maximize cumulative reward is very general and
covers many problems beyond robot learning tasks. In general the problem is one of learning to
control sequential processes. This includes, for example, manufacturing optimization problems
in which a sequence of manufacturing actions must be chosen, and the reward to be maximized
is the value of the goods produced minus the costs involved. It includes sequential scheduling
problems such as choosing which taxis to send for passengers in a large city, where the reward to
be maximized is a function of the wait time of the passengers and the total fuel costs of the taxi
fleet. In general, we are interested in any type of agent that must learn to choose actions that alter
the state of its environment and where a cumulative reward function is used to define the quality
of any given action sequence. Within this class of problems we will consider specific settings,
including settings in which the actions have deterministic or nondeterministic outcomes, and
settings in which the agent has or does not have prior knowledge about the effects of its actions
on the environment.
1.9 Q LEARNING
1.10 TEMPORAL DIFFERENCE LEARNING