|| Jai Sri Gurudev||

Sri Adichunchanagiri Shikshana Trust(R)

SJB INSTITUTE OF TECHNOLOGY

BGS Health & Education City, Dr. Vishnuvardhan Road, Kengeri, Bengaluru–560060
An Autonomous Institute affiliated to Visvesvaraya Technological University, Belagavi
Affiliated to Visvesvaraya Technological University, Belagavi & Approved by AICTE, New Delhi, Certified by ISO 9001-2015
Accredited by NBA & NAAC, New Delhi with ‘A+’ Grade, Recognized by UGC, New Delhi with 2(f) and 12(B)

Study Material
Course Name: Machine Learning-2 (ML-2)

Course Code: BAI702

Module – 2

By

Faculty Name: Mrs. Chetana Patil

Semester: 7th ‘A’

Department of Artificial Intelligence and Machine Learning

Aca. Year: ODD SEM /2025-26

[BAI702,Machine learning]

CHAPTER 10: LEARNING SET OF RULES

10.2 SEQUENTIAL COVERING ALGORITHMS
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.
A subroutine LEARN-ONE-RULE that t 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.

This output 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 routine for learning a single rule, one obvious approach to
learning a set of rules is to invoke LEARN-ONE-RULE 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.

 This sequential covering algorithm is one of the most widespread approaches to

learning disjunctive sets of rules.
 It reduces the problem of learning a disjunctive set of rules to a sequence of simpler
problems.
 It performs a greedy search, formulating a sequence of rules without backtracking.
 It is not guaranteed to find the smallest or best set of rules that cover the training
examples.

Dept of AIML, pg. 1

[BAI702,Machine learning]

10.2.1 General to Specific Beam Search

 One effective approach to implementing LEARN-ONE-RULE is to 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.

 The search begins by considering the most general rule precondition possible, then
greedily adding the attribute test that most improves rule performance measured over
the training [Link] this test has been added, the process is repeated by greedily
adding a second attribute test, and so on

 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.
 The general-to-specific search suggested above for the LEARN-ONE-RULE algorithm
is a greedy depth-first search with no backtracking.
 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 eachstep, 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.

Dept of AIML, pg. 2

[BAI702,Machine learning]

Learn one rule:

Dept of AIML, pg. 3

[BAI702,Machine learning]

10.4 LEARNING FIRST-ORDER RULES

10.4.1 First-Order Horn Clauses
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:

(Namel = Sharon, Motherl = Louise, Fatherl = Bob,

Malel = False, Female1 = True,
Name2 = Bob, Mother2 = Nora, Father2 = Victor,
Male2 = True, Female2 = False, Daughterl.2 = True)
where the subscript on each attribute name indicates which of [Link] persons is being
described the result would be a collection of very specific rules such as
IF (Father1 = Bob) ∧ (Name2 = Bob) ∧ (Femalel = True)
THEN daughter1,2 = True

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

Dept of AIML, pg. 4

[BAI702,Machine learning]

10.5 LEARNING SETS OF FIRST-ORDER RULES: FOIL

FOIL program is the natural extension of these earlier algorithms to first-order representations.

RULES

 The literals are not permitted to contain function symbols this reduces the complexity
of the hypothesis space search.
 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.

FOIL Algorithm

Dept of AIML, pg. 5

[BAI702,Machine learning]

The two most substantial differences between FOIL and SEQUENTIAL algorithm

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

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

where L1.. . Ln, are literals forming the current rule preconditions and where P(x1, x2, . . . ,
xk) is the literal that forms the rule head, or postconditions. FOIL generates candidate
specializations of this rule by considering new literals L n+1 that fit one of the following forms:
 Q(vl, . . . , v,), where Q is any predicate name occurring in Predicates and where the vi
are either new variables or variables already present in the rule. At least one of the vi in
the created literal must already exist as a variable in the rule.
 Equal(xj, xk), where xi and xk are variables already present in the rule.
 The negation of either of the above forms of literals.

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

10.6 INDUCTION AS INVERTED DEDUCTION

Inductive logic programming is based on the simple observation that induction is just the
inverse of deduction.

Dept of AIML, pg. 6

[BAI702,Machine learning]

Induction is, in fact, the inverse operation of deduction, and cannot be conceived to exist
without the corresponding operation, so that the question of relative importance cannot arise.
Who thinks of asking whether addition or subtraction is the more important process in
arithmetic? But at the same time much difference in
difficulty may exist between a direct and inverse operation; it must be allowed that inductive
investigations are of a far higher degree of difficulty and complexity than any questions of
deduction.. . . (Jevons 1874)

 This formulation subsumes the common definition of learning as finding some general
concept that matches a given set of training examples (which corresponds to the special
case where no background knowledge B is available).
 By incorporating the notion of background information B, this formulation allows a
more rich definition of when a hypothesis may be said to "fit" the data. Up until now,
we have always determined whether a hypothesis. (e.g., neural network) fits the data
based solely on the description of the hypothesis and data, independent of the task
domain under study.
 By incorporating background information B, this formulation invites learning methods
that use this background information to guide the search for h, rather than merely
searching the space of syntactically legal hypotheses. The inverse resolution procedure
described in the following section uses background knowledge in this fashion.

Inductive logic programing has several practical difficulties.

 The requirement ∨ (xi, f (xi)) ∈D) (B∧h ∧xi) t f (xi) does not naturally accommodate
noisy training data. The problem is that this expression does not allow for the possibility
that there may be errors in the observed description of the instance xi or its target value
f (xi). Such errors can produce an inconsistent set of constraints on h. Unfortunately,
most formal logic frameworks completely lose their ability to distinguish between truth
and falsehood once they are given inconsistent sets of assertions.
 The language of first-order logic is so expressive, and the number of hypotheses that
satisfy (V(xi , f (xi)) ∈ D) (B ∧ h ∧ xi) t f (xi) is SO large, that the search through the
space of hypotheses is intractable in the general case. Much recent work has sought
restricted forms of first-order expressions, or additional second-order knowledge, to
improve the tractability of the hypothesis space search.

Dept of AIML, pg. 7

[BAI702,Machine learning]

10.7 INVERTING RESOLUTION

The resolution rule is a sound and complete rule for deductive inference in first-order logic. It
is easiest to introduce the resolution rule in propositional form, though it isreadily extended
to first-order representations. Let L be an arbitrary propositional literal, and let P and R be
arbitrary propositional clauses. The resolution rule is

Given two clauses C1 and C2, the resolution operator first identifies a literal L that occurs as a
positive literal in one of these two clauses and as a negative literal in the other. It then draws
the conclusion given by the above formula. It is easy to invert the resolution operator to form
an inverse entailment operator O(C, C1) that performs inductive inference.

Dept of AIML, pg. 8

[BAI702,Machine learning]

Dept of AIML, pg. 9