Machine Learning II BAI702
Module 2
PART A — Learning Sets of Rules
1. Why learn rules?
Imagine you are a detective. Each case file (training example) contains facts and an outcome.
Your job is to write simple IF–THEN statements that explain the outcome. These statements are
“rules”. A collection of rules is a “rule set”.
Definitions (quick revision):
Rule: An IF (conditions) THEN (prediction) statement.
Rule set: A collection of rules. Many rule learners treat the full model as an OR of rules
(Rule1 OR Rule2 OR …).
Conjunctive rule: Conditions are combined using AND.
Disjunctive rule set: Multiple rules combined using OR.
2. Sequential Covering
Story: You have many “positive” examples to catch, and you want to avoid “negative”
examples. Sequential covering works like fishing with nets. You throw one net (learn one
accurate rule). Then you remove the positives caught by that net, and throw another net for the
remaining positives. Repeat until you cannot find a useful new rule.
Definition:
Sequential covering: Learn one rule at a time; remove the (correctly covered) positive
examples; repeat.
Annotated diagram you can redraw:
ALL EXAMPLES (Pos + Neg)
|
v
(1) LEARN ONE RULE R1 (high accuracy)
|
v
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
(2) REMOVE POSITIVES COVERED BY R1
|
v
(3) POSITIVES LEFT?
| YES | NO
v v
LEARN R2 STOP → FINAL RULE SET
(repeat)
Exam memory:
Greedy and fast: not guaranteed to find the globally best/smallest rule set.
Final model acts like OR of learned rules (disjunctive set).
3. Learning ONE rule: General → Specific search
Story: To craft one good rule, we start with a rule that matches everything (very general). Then
we keep adding conditions to make it more specific until it becomes accurate enough. Think of
tightening a filter.
Definition:
General-to-specific search: Start from the most general rule (no conditions) and add
conditions to specialize it.
Annotated specialization sketch:
MOST GENERAL
IF TRUE THEN Predict (e.g., Yes)
|
v add best condition
IF Humidity=High THEN No
|
v add another condition
IF Humidity=High AND Wind=Strong THEN No
MOST SPECIFIC
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
What changes as you add conditions?
Coverage decreases (rule matches fewer examples).
Accuracy tends to increase (rule becomes more precise).
4. Beam Search (CN2 style) — keeping multiple good options
Story: If we always pick the single best-looking condition early (pure greedy search), we might
make a wrong early choice and get stuck. Beam search reduces this risk by keeping the top k
candidate partial rules at each step. Then it expands all of them and again keeps only the top k.
Definition:
Beam search: Maintain the best k hypotheses at each depth; expand them; keep best k again.
Beam width k=2 (annotated):
Level 0:
[ TRUE ]
Level 1 (keep best 2):
[ Humidity=High ] [ Wind=Strong ]
Level 2 (expand both, keep best 2 again):
[ Humidity=High AND Wind=Weak ]
[ Wind=Strong AND Outlook=Sunny ]
5. How do we score a rule? (Performance measures)
Story: When you try different candidate conditions, you need a score to decide which condition
is best. Different learners use different scores. Three important ones in this module: Relative
frequency (simple accuracy), m-estimate (accuracy with prior), and entropy (purity of covered
examples).
5.1 Relative Frequency (simple accuracy)
If a rule matches n examples and is correct on nc of them, its relative-frequency accuracy is
nc/n.
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
Accuracy = nc / n
Example: rule matches n=20, correct nc=15 → accuracy = 15/20 = 0.75
5.2 m-estimate (accuracy with a “prior” to avoid overconfidence)
Beginner intuition: If a rule matches only a few examples, its accuracy can look artificially high.
The m-estimate blends the observed accuracy with a prior probability p. Parameter m controls
how strongly we trust the prior (bigger m → more conservative).
m-estimate = (nc + m·p) / (n + m)
Where:
n = number of matched examples
nc = number correctly predicted
p = prior probability of predicted class
m = strength of prior
Solved numerical example:
Given n=4, nc=3, p=0.2, m=10:
m-estimate = (3 + 10*0.2) / (4 + 10)
= (3 + 2) / 14
= 5/14
= 0.357
5.3 Entropy (purity of the covered set)
Entropy measures how mixed the class labels are among the examples that a rule covers. A
perfectly pure set (all positives or all negatives) has entropy 0.
Entropy(S) = - Σ p_i log2(p_i)
Example: 8 positives, 2 negatives → p+=0.8, p-=0.2
Entropy = -(0.8 log2 0.8 + 0.2 log2 0.2) ≈ 0.72
Visual intuition:
Pure: ++++++++ (low entropy)
Mixed: +++---- (high entropy)
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
6. From propositional rules to first-order rules (ILP)
Story: Propositional rules work with fixed attributes (like Father1=Bob). They fail when the
concept is truly relational, like family relationships or chemical structures. First-order rules
introduce variables (x, y, z) so that one rule can apply to many entities.
Definitions:
First-order rule: A rule with variables and predicates (relations).
Predicate: A relation that is True/False, e.g., Parent(x,y), Female(x).
Horn clause: A clause with at most one positive literal; PROLOG programs are sets of Horn
clauses.
Example (general, first-order):
Daughter(x,y) :- Father(y,x), Female(x).
Meaning: x is daughter of y if y is father of x and x is female.
7. FOIL: Learning first-order rules using sequential covering
Story: FOIL is like sequential covering, but for first-order rules. It learns one rule at a time to
predict the target predicate as True. Inside each rule, it keeps adding one literal at a time until
the rule stops covering negative examples (or until a stopping criterion is met for noisy data).
FOIL structure (two loops):
OUTER LOOP (many rules → OR):
While positive examples remain:
Learn ONE rule
Remove positives covered by this rule
INNER LOOP (one rule → AND):
Start with: Target(...) :- TRUE
Repeat:
add the best literal to improve the rule
until rule avoids negatives
Definition:
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
Literal: A predicate (or its negation) used in the rule body, e.g., Father(y,z), Female(x), -
Equal(x,y).
7.1 FOIL-Gain (how FOIL chooses the next literal)
Beginner intuition: FOIL asks, “If I add this literal, does my rule become cleaner?” Cleaner
means: keep positives but remove negatives. FOIL-Gain measures the improvement in
information (purity) after adding a literal.
FoilGain(L,R) = t * [ log2( p1/(p1+n1) ) - log2( p0/(p0+n0) ) ]
Where:
p0, n0 = positive/negative bindings BEFORE adding literal L
p1, n1 = positive/negative bindings AFTER adding literal L
t = number of positive bindings of R that remain covered after adding L
Solved numerical example:
Before: p0=10, n0=10 → purity=10/20=0.5 → log2= -1
After: p1=8, n1=2 → purity= 8/10=0.8 → log2≈-0.322
t=8
Gain = 8 * [(-0.322) - (-1)] = 8 * 0.678 = 5.42
7.2 Recursive rule sets (FOIL can learn recursion)
If the target predicate is allowed to appear in the rule body, FOIL can learn recursive definitions.
Example: Ancestor. One rule covers direct parent; the second rule uses recursion to cover multi-
generation ancestors.
Ancestor(x,y) :- Parent(x,y).
Ancestor(x,y) :- Parent(x,z), Ancestor(z,y).
8. Induction as inverted deduction (idea + resolution)
Story: Deduction is what you do in math: Rules + facts → conclusion. Induction is learning:
facts + conclusions → rules. The chapter explains that one way to learn rules is to invert
deductive operators like resolution.
Definitions:
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
Deduction: Using existing rules to derive conclusions.
Induction: Inferring rules/hypotheses so that they explain the observed conclusions.
Propositional resolution (deduction):
(P ∨ L) , (¬L ∨ R) ⇒ (P ∨ R)
Inverse resolution (induction idea):
Given (P ∨ R) and one parent clause, infer the missing parent clause.
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
PART B — Analytical Learning / Explanation-Based Learning
9. Why analytical learning?
Story: Sometimes you don’t want to learn by statistics from many examples. Instead, you
already have knowledge about how the world works (domain theory). You explain why a single
example is positive using that knowledge, then generalize the explanation into a rule. This is
explanation-based learning (EBL).
Definitions:
Domain theory (B): Background knowledge (rules) used to explain examples.
Explanation: A proof (or reasoning chain) showing why the example satisfies the target
concept.
EBL: Learning by generating and generalizing explanations.
10. PROLOG-EBG (the EBL algorithm in this module)
PROLOG-EBG is a sequential covering algorithm for analytical learning. It processes positive
examples. For each uncovered positive example, it: (1) builds a proof using the domain theory,
(2) identifies which example facts mattered in the proof, (3) generalizes to the weakest sufficient
conditions, and (4) stores the resulting Horn clause as a learned rule.
PROLOG-EBG steps (story version):
1) Explain: build an explanation/proof using the domain theory
2) Analyze: find what facts are truly needed (relevant features)
3) Generalize: compute weakest preimage (most general sufficient conditions)
4) Refine: add a new Horn clause rule to LearnedRules
10.1 Explanation tree (SafeToStack example intuition)
In the textbook’s SafeToStack example, the system explains that stacking is safe because x is
lighter than y; lighter depends on weights; weight depends on volume and density. This forms a
proof tree. Only the facts used in the proof are considered relevant.
Annotated explanation chain:
SafeToStack(x,y)
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
|
v (rule: SafeToStack ← Lighter)
Lighter(x,y)
|
v (rule: Lighter ← Weight(x)<Weight(y))
Weight(x) < Weight(y)
|
v
Volume(x)*Density(x) < Weight(y)
|
v
Type(y)=Endtable (if y is an Endtable, assume Weight(y)=5 in the example)
11. Weakest preimage / Regression
Beginner meaning: “What is the most general set of conditions that still guarantees the
explanation works?” Instead of keeping the exact numbers from the example (like Volume=2),
we keep the general relationships (Weight = Volume×Density, and Weight < 5).
Definitions:
Weakest preimage: The most general conditions that are sufficient to prove the target
concept (using the same explanation).
Regression: The step-by-step backward procedure that computes the weakest preimage by
replacing a conclusion with the premises of the rule used to prove it.
Regression sketch (backward reasoning):
Start: SafeToStack(x,y)
Regress: replace with conditions from proof rule
End: Volume(x,v), Density(x,d), Equal(w, v*d), LessThan(w, 5), Type(y,Endtable)
This final conjunction becomes the body of the learned Horn clause.
12. Quick comparison (very exam-friendly)
Think of Chapter 10 methods as learning patterns from data, and Chapter 11 methods as
learning from explanations using prior knowledge.
Soumya L N,[Link],CSE(AI & ML)
Machine Learning II BAI702
Remember these contrasts:
Inductive rule learning (CN2/FOIL): search many candidate rules; pick the best by a metric;
works with noise.
Explanation-based learning (PROLOG-EBG): build a proof using domain theory; generalize
proof; needs correct/complete domain theory (ideal case).
Soumya L N,[Link],CSE(AI & ML)