MODULE 2
INTRODUCTION
• Learning target functions as if-then rules helps jointly define the
function.
• One approach: learn a decision tree, then convert it into an
equivalent set of rules (one per leaf node).
• Another approach: use a genetic algorithm that encodes rules as bit
strings and applies genetic search operators.
• The chapter focuses on algorithms that directly learn first-order rules
containing variables.
• First-order rules are more expressive than propositional rules.
• Uses sequential covering algorithms to learn one rule at a time,
incrementally building the rule set.
Cont.
• Example of first-order rule sets: defines the target concept Ancestor.
• Predicates used:
• Parent(x, y): y is the mother or father of x.
• Ancestor(x, y): y is an ancestor of x over any number of generations.
• Rules:
• IF Parent(x, y) THEN Ancestor(x, y)
• IF Parent(x, z) ∧ Ancestor(z, y) THEN Ancestor(x, y)
• These rules compactly describe a recursive function difficult to express with decision
trees or propositional logic.
• First-order rules are more expressive and can represent concepts in Prolog (Horn
clauses).
• In Prolog, such rules form a valid program for computing the Ancestor relation.
• Learning algorithms can infer such Prolog-style rules automatically from training
examples.
Sequential covering algorithms
• Sequential covering algorithms are a family of rule-learning methods
that work by repeatedly learning one rule at a time, removing the
examples it covers, and then continuing the process until most of the
positive training examples are covered.
• This strategy is also called a “separate-and-conquer” approach.
Learn-One-Rule
• At the core of this approach is a subroutine called Learn-One-Rule,
which takes positive and negative training examples as input and
produces a single rule that correctly classifies many positive
examples and few negative ones.
• The rule must have high accuracy, meaning its predictions are correct,
but it does not need to cover all examples, so low coverage is
acceptable.
Process of sequential covering
• The process begins by applying Learn-One-Rule to the full training set.
Once a rule is found, the positive examples covered by it are removed
from the dataset.
• The algorithm is then applied again to learn another rule from the
remaining examples.
• This procedure is repeated until the set of rules collectively covers the
desired fraction of positive examples.
• The resulting rules are then ordered so that more accurate ones are
applied first when classifying new instances.
Cont.
• Sequential covering reduces the complex task of learning a large
disjunctive rule set into smaller, simpler problems where each rule is
conjunctive.
• It performs in a greedy manner by adding rules without
backtracking, which makes it efficient though not always guaranteed
to find the most optimal set.
• This approach is widely used in rule-based learning systems because
of its simplicity and effectiveness.
Cont.
• To design Learn-One-Rule, the key requirement is that it should
produce a rule with high accuracy, even if it does not cover all
positive examples.
• In practice, different algorithms have been developed to generate
such rules, and research has explored many variations.
• Initially, these methods focus on learning propositional rules, but they
can also be extended to learn more expressive first-order Horn
clauses.
Algorithm
Learning First-Order Rules
Cont.
PROLOG-EBG
⮚ PROLOG-EBG (Kedar-Cabelli and McCarty 1987) is representative of
several explanation-based learning algorithms.
⮚ the PROLOG-EBG algorithm is a sequential covering algorithm that
considers the training data incrementally.
⮚ For each new positive training example that is not yet covered by a
learned Horn clause, it forms a new Horn clause by:
(1) explaining the new positive training example,
(2) analyzing this explanation to determine an appropriate
generalization
(3) refining the current hypothesis by adding a new Horn clause
rule to cover this positive example, as well as other similar
instances.
Algorithm
Example
Given:
⮚ Instance space X: Each instance describes a pair of objects represented by the
predicates Type, Color, Volume, Owner, Material, Density, and On.
⮚ Hypothesis space H: Each hypothesis is a set of Horn clause rules. The head of
each Horn clause is a literal containing the target predicate SafeToStack.
⮚ The body of each Horn clause is a conjunction of literals based on the same
predicates used to describe the instances, as well as the predicates LessThan,
Equal, GreaterThan, and the functions plus, minus, and times.
For example, the following Horn clause is in the hypothesis space:
Target concept: SafeToStack(x,y)
⮚ the example Horn clause hypothesis shown in the table asserts that it is
SafeToStack any object x on any object y, if the Volume of x is LessThan the
Volume of y
Step1:Explain the Training Example
⮚ faced in generalizing the training example is "of the many features that happen
to be true of the current training example, which ones are generally relevant to
the target concept?'
⮚ The explanation, or proof, states that it is SafeToStack Objl on 0bj2 because Objl
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 explanation mentions only a small fraction of the known attributes of Obj1
and 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.
⮚ For example, the explanation of Figure 11.2 refers to the Density of
Obj1, but not to its Owner.
⮚ Therefore, the hypothesis for SafeToStack(x,y) should include density(x,
0.3), but not Owner(x, Fred).
⮚ By collecting the features mentioned in the leaf nodes of the explanation
in Figure and substituting variables x and y for Objl and Obj2, we can
form a general rule that is justified by the domain theory:
⮚ The body of the above rule includes each leaf node in the proof tree,
except for the leaf nodes "Equal(0.6, times(2,0.3)" and
"LessThan(0.6,5)."
⮚ We omit these two because they are by definition always satisfied,
independent of x and y.
Step2:Analyze The Explanation
⮚ PROLOG-EBG computes the weakest preimage of the target concept with
respect to the explanation,using a general procedure called regression
(Waldinger 1977).
⮚ The regression procedure operates on a domain theory represented by
an arbitrary set of Horn clauses.
⮚ It works iteratively backward through the explanation, first computing
the weakest preimage of the target concept with respect to the final
proof step in the explanation, then computing the weakest preimage of
the resulting expressions with respect to the preceding step, and so on.
⮚ The procedure terminates when it has iterated over all steps in the
explanation, yielding the weakest precondition of the target concept
with respect to the literals at the leaf nodes of the explanation.
Definition: The weakest preimage of a conclusion C with respect to a proof P
is the most general set of initial assertions A, such that A entails C
according to P.
⮚ The frontier of regressed expressions created at each step by the regression
procedure is shown underlined in italics.
⮚ The process begins at the root of the tree , with the frontier initialized to the
general target concept SafeToStack(x,y).
⮚ The first step is to compute the weakest preimage of this frontier expression with
respect to the final (top-most) inference rule in the explanation. The rule in this
case is , so the resulting weakest preimage is
Lighter(x, y).
⮚ The process now continues by regressing the new frontier {Lighter(x, y)}, through
the next Horn clause in the explanation, resulting in the regressed expressions
{Weight(x, wx), LessThan(wx, wy), Weight(y, wy)}.
⮚ This indicates that the explanation will hold for any x and y such that the weight
wx of x is less than the weight wy of y.
⮚ The regression of this frontier back to the leaf nodes of the explanation continues
in this step-by-step fashion, finally resulting in a set of generalized literals for the
leaf nodes of the tree.
⮚ This final set of literals, shown at the bottom of the above fig forms the body of
the final rule.
⮚ The heart of the regression procedure is the algorithm that at each step regresses the
current frontier of expressions through a single Horn clause from the domain theory.
⮚ This algorithm is described and illustrated in Table above. The illustrated example in
this table corresponds to the bottommost single regression step of Figure above.
⮚ As shown in the table, the REGRESS algorithm operates by finding a substitution that
unifies the head of the Horn clause rule with the corresponding literal in the frontier,
replacing this expression in the frontier by the rule body, then applying a unifying
substitution to the entire frontier.
⮚ The final Horn clause rule output by PROLOG-EBG is formulated as follows: The clause
body is defined to be the weakest preconditions calculated by the above procedure.
⮚ The clause head is the target concept itself, with each substitution from each
regression step applied to it.
⮚ This substitution is necessary in order to keep consistent variable names between the
head and body of the created clause, and to specialize the clause head when the
explanation applies to only a special case of the target concept.
⮚ As noted earlier, for the current example the final rule is
Step3:Refine The Current Hypothesis
⮚ The current hypothesis at each stage consists of the set of Horn clauses
learned thus far.
⮚ At each stage, the sequential covering algorithm picks a new positive
example that is not yet covered by the current Horn clauses, explains this
new example, and formulates a new rule‘ according to the procedure
described above.
⮚ Notice only positive examples are covered in the algorithm as we have
defined it, and the learned set of Horn clause rules predicts only positive
examples.
⮚ A new instance is classified as negative if the current rules fail to predict
that it is positive.
⮚ This is in keeping with the standard negation-as-failure approach used
in Horn clause inference systems such as PROLOG.
INDUCTIVE-ANALYTICAL APPROACHES TO
LEARNING
Cont.
Cont.
Cont.
Cont.
KBANN Algorithm
Learn the target concept cup
Network constructed from the cup domain
theory
TANGENTDROP Algorithm
EXAMPLE
Cont.
Cont.
Cont.
EXAMPLE
EBNN ALGORITHM
ERANN ALGORITHM
DIAGRAM
STEPS OF EBANN ALGORITHM
Cont.
Cont.
Cont.