🌟 10.

3 Learning Rule Sets — Ultra Simple Summary

Rule-learning means creating IF–THEN rules from data.

There are 5 main differences in how algorithms learn rules:

⭐ 1. Sequential vs Simultaneous Covering

 Sequential (CN2, AQ): Learn one rule, remove covered

examples, then learn the next.

 Simultaneous (ID3): Learn all rules at once through a decision

tree.

📌 Sequential = many small decisions; Simultaneous = fewer decisions.

⭐ 2. General-to-Specific vs Specific-to-General

 General → Specific: Start with very general rule, then add

conditions.

 Specific → General: Start with very specific rules, then remove

conditions.

📌 General-to-specific is simpler because there is only one most-general

rule.

⭐ 3. Generate-and-Test vs Example-Driven

 Generate-and-test: Make many candidate rules → test → pick

best.

 Example-driven: Update rules based on each example.

📌 Generate-and-test is more noise-resistant.

⭐ 4. Rule Post-Pruning

After learning a rule, remove unnecessary conditions to avoid overfitting.

📌 Makes rules simpler and more accurate on new data.

⭐ 5. How to Measure Rule Quality

Three ways:
 1. Relative Frequency:
Accuracy = correct matches / total matches

2. m-Estimate:
Adds prior probability, useful when few examples.

3. Entropy:
Measures purity; lower entropy = better rule.

Learning Rule Sets: Example-Based Methods

(VTU 5–10 Marks Answer)

Example-based methods are rule-learning approaches in which rules are

created or modified directly in response to individual training
examples. Instead of generating all possible candidate rules first, these
methods let each example guide the search for the correct rule.

These methods are also called example-driven rule learning.

✅ Key Characteristics

1. Example-guided search

o The learning algorithm looks at one training example at a

time.

o It adjusts or builds rules so that they correctly classify this

example.

2. Incremental learning

o Rules are updated whenever a new example is seen.

o The rule gradually becomes more accurate.

3. Local corrections

o Each example causes a local change to the rule

(generalization or specialization).

4. Higher risk of noise sensitivity

o A single noisy or incorrect example can lead to wrong rule

updates.

5. Efficient search

o They explore only rules connected to the examples being

processed
 (unlike generate-and-test methods, which consider all possible
rules).

⭐ Important Example-Based Algorithms

1. FIND-S

 Starts with the most specific rule.

 Generalizes when it sees a positive example not covered by the

rule.

 Entire search is driven by positive examples.

2. Candidate-Elimination Algorithm

 Maintains version space with S (specific boundary) and G

(general boundary).

 Each new example updates these boundaries.

 Very example-driven.

3. AQ Algorithm

 Uses a single positive example as a seed.

 Searches only rules consistent with that example.

 Learns separate rule sets for each target value.

4. CIGOL (ILP)

 Uses inverse resolution guided by examples.

 Example-driven approach to learning first-order rules.

⭐ Advantages

 Efficient and fast

 Focuses on meaningful rules guided by examples

 Requires less hypothesis exploration

 Produces rules directly related to actual data

⭐ Disadvantages

 Sensitive to noisy examples

  May miss good rules not connected to the chosen examples

 Final rule quality depends on the order of examples

 Less robust than generate-and-test methods like CN2

⭐ Exam-Ready Short Summary

Example-based methods learn rule sets by refining rules in response

to individual training examples. Each example drives the
specialization or generalization of the rule. Algorithms like FIND-S,
Candidate-Elimination, AQ, and CIGOL follow this approach. These
methods are efficient but more sensitive to noisy data because they rely
heavily on single examples.

Example-Based Rule-Based (Generate-and-

Feature
Methods Test) Methods

Learned by looking at one Learned by generating many

How rules are
training example at a rule candidates and testing
learned
time them

Example-driven Hypothesis-driven (rules

Guidance (examples tell how to generated first, then data is
modify rules) checked)

Search Incremental: rules change Broad search: many rules are

process step-by-step created and then evaluated

Uses individual
Uses whole dataset to test
Use of data examples to update
rule performance
rules

More sensitive (one

Sensitivity to Less sensitive (evaluates on
wrong example can
noise many examples)
mislead)

Slower, because many rules

Speed Faster and more efficient
must be tested

Computational
Low Higher
cost

Depends heavily on
Rule quality More stable and accurate rules
example order

Flexibility Rules change frequently Rules remain fixed once

 Example-Based Rule-Based (Generate-and-
Feature
Methods Test) Methods

based on new examples chosen

CN2, Sequential Covering,

Typical FIND-S, Candidate-
Beam Search, ID3-based rule
algorithms Elimination, AQ, CIGOL
learning

🌟 FOIL Algorithm (First-Order Inductive Learner) – Simple

Explanation

FOIL (First Order Inductive Learning) is used to learn first-order rules

(rules with variables) instead of simple propositional rules.

✔ FOIL = Sequential Covering + First-Order Logic

It is basically the Sequential Covering algorithm, but extended to

first-order representation.

⭐ What FOIL Learns

 FOIL learns a set of first-order rules.

 Each rule is similar to a Horn clause, but with two differences:

1. FOIL rules are more restricted

 FOIL does NOT allow function symbols (like age(x)).

 This makes the search simpler.

2. FOIL rules are more expressive

 FOIL allows negated literals in the rule body.

Example:

 IF Parent(x, y) AND ¬Male(x) THEN Daughter(x, y)

🌟 Structure of FOIL Algorithm

FOIL works using two loops:

✔ 1. Outer Loop – Learn one rule at a time (Sequential Covering)

 FOIL collects all positive examples (Pos) and negative examples

(Neg).

 It learns one rule that covers some positive examples.

 Removes the positive examples covered by this rule.

 Repeats until no positive examples remain.

This is exactly like Sequential Covering.

✔ 2. Inner Loop – Construct one rule using hill climbing

Inside the inner loop:

Step 1: Start with the most general rule

IF THEN Target(x, y)

(no conditions yet)

Step 2: Add one literal at a time

FOIL generates many candidate literals:

 Example: Parent(x, y), Female(x), Brother(y, z), NOT Male(x), etc.

Step 3: Choose the best literal

Use FOIL-Gain (a performance measure) to select the literal that:

 Removes the largest number of negative examples

 Keeps as many positive examples as possible

Step 4: Continue adding literals

Stop when:

 The rule covers zero negative examples

Then the rule is ready.

⭐ FOIL-Gain

 FOIL uses a special metric called Foil-Gain, not entropy.

 Because:
 o FOIL uses variable bindings

o FOIL only predicts positive class

🌟 Complete FOIL Algorithm in Simple Words

1. Separate training examples into

Pos = positive examples
Neg = negative examples

2. While Pos is not empty:

o Start a new rule: IF THEN Target

o NewRuleNeg = all negative examples

o While NewRuleNeg is not empty:

 Generate all possible literals

 Choose the best literal using FOIL-Gain

 Add literal to rule body

 Remove negative examples now rejected by the rule

o Add the finished rule to the hypothesis

o Remove the positive examples covered by the rule

3. Return all learned rules.

🌟 Why FOIL Uses Hill Climbing?

 FOIL adds the best literal at each step.

 It does not maintain multiple search paths (like beam search).

 It only keeps one best rule at every step → this is hill climbing.

Advantages:

 Fast

 Simple

 Works well in many ILP problems

⭐ Very Simple Example (Short)

Target:

Daughter(x, y)

Possible predicates:

 Parent(x, y)

 Female(x)

 Male(x)

FOIL learns:

Rule 1:

IF Parent(y, x) AND Female(x)

THEN Daughter(x, y)

This rule is:

 General

 Works for all persons

 Avoids negatives

 Uses variables → first-order rule

🌟 Final Exam-Ready Summary

FOIL (First Order Inductive Learner) extends sequential covering to first-

order logic. It learns a set of first-order rules similar to Horn clauses, but
without function symbols and allowing negated literals. FOIL has two
loops: the outer loop learns one rule at a time by removing covered
positive examples, and the inner loop uses a hill-climbing search to add
literals that increase FOIL-Gain until no negative examples are covered.
FOIL is widely used in inductive logic programming.

🌟 FOIL’s Information Gain Formula (You can write it or skip)

FOIL uses the FOIL-Gain metric:

[
FOIL - Gain= p × log ⁡2
( P1
P 1+ N 1) (
− log ⁡2
P0
P0 + N 0 )]
Where:

 P0 , N 0= positives/negatives before adding the literal

 P1 , N 1 = positives/negatives after adding the literal

  p= number of positive examples still covered

(You do NOT need to compute it in an exam—just mention it.)

5. Explanation-Based Learning (EBL) – VTU Answer

Definition

Explanation-Based Learning (EBL) is a learning method in which the

system learns a general rule by explaining a single training example using
prior knowledge (domain theory).
EBL does not depend on many examples; instead, it depends on logical
explanation of why the example satisfies the target concept.

EBL identifies the relevant features used in the explanation and

generalizes them into a reusable rule.

⭐ Key Points (from textbook)

According to the textbook section on “Explanation-Based Learning”

BAI702-module-2-textbook

✔ EBL begins with one training example of a target concept.

✔ It uses domain knowledge to construct a logical explanation proving
the example is correct.
✔ From this explanation, the system keeps only relevant literals and
removes irrelevant details.
✔ It generalizes the explanation to create a general rule for future
predictions.
✔ The final rule is often much simpler and uses only the essential
conditions.

⭐ Process of EBL (from textbook)

1. Input

o A single positive example

 o A domain theory (set of rules already known)

2. Explanation

o A proof is constructed to show why the example is an instance

of the concept.

3. Generalization

o Replace specific constants by variables

o Remove irrelevant conditions not used in the explanation

4. Output

o A general Horn-clause-like rule that can classify new

examples

⭐ Case Study (From textbook style)

Learning the concept: Safe-To-Stack(x, y)

(An example consistent with the style of examples in the uploaded

textbook.)

Given

A robot must learn when it is safe to stack block A on block B.

Training Example:

SafeToStack(BlockA, BlockB) = True

Domain Theory (Background Knowledge):

 A block can be safely stacked only if the supporting block is wider.

 The lower block must be stable.

 The upper block must be smaller.

Step 1: Explanation

The robot explains the example using the domain theory:

 Width(BlockB) > Width(BlockA)

 Stable(BlockB)

 Therefore SafeToStack(BlockA, BlockB)

These are the relevant conditions.

Step 2: Remove irrelevant facts

(color, weight, material → all ignored since not used in explanation)

Step 3: Replace constants with variables

Generalized rule:

IF Width(Y) > Width(X) AND Stable(Y)

THEN SafeToStack(X, Y)

This becomes the final learned rule

EBL has successfully generalized from one example using its explanation.

⭐ Why EBL is useful (VTU points)

 Learns from very few examples

 Produces compact rules

 Depends on domain theory, not statistical frequency

 Efficient when explanation structure is available

 Good for logical, relational learning tasks

🌟 Explanation-Based Learning (EBL) of Search Control Knowledge

— Simple Answer

What is it?

EBL of search control knowledge means:

👉 The system learns rules that help it search faster

👉 It does this by explaining why a successful solution worked
👉 Then it generalizes that explanation into rules that guide future
searches

So the system learns how to avoid bad paths and choose good
actions during planning.

🌟 Process (Very Simple)

1. Start with a successful example

The system is given a solved problem (a plan that worked).

2. Explain why the solution worked

It uses domain knowledge to explain:

  Why each step was important

 Why this path leads to the goal

3. Keep only important parts

Remove details that do not matter.

4. Generalize

Replace actual names → variables

Make a general rule that applies in many situations.

5. Save the rule

This becomes search-control knowledge.

6. Use the rule to guide future planning

The planner now:

 Tries good actions first

 Avoids useless branches

 Reaches goal faster

🌟 Inductive–Analytical Approaches to Learning (Simple

Explanation)

Inductive–Analytical learning is a hybrid learning method that

combines:

✔ Inductive Learning (learning from examples)

✔ Analytical Learning (learning using prior knowledge or domain

theory)

This approach uses the strengths of both to produce a more powerful

learning system.

🌟 Why Combine Them?

Because:

 Induction works well when you have lots of data but no prior theory

 Analysis (EBL) works well when you have good theory but few
examples

👉 Hybrid learning solves problems where neither induction nor

analysis alone is enough.
🌟 How Inductive–Analytical Learning Works

The process is simple:

1. Start with a Weak Domain Theory

The system has some basic background knowledge, but it may be:

 incomplete

 incorrect

 too shallow

This theory helps guide the learning process.

2. Use Analytical Learning (EBL) to Explain Examples

The system:

 takes an example

 explains why it fits the target concept

 identifies important features

 removes irrelevant details

 forms a general rule

But the rule may not be perfect because the theory is weak.

3. Use Inductive Learning to Improve the Rule

Now induction helps by:

 adjusting the rule

 correcting mistakes

 adding missing conditions

 handling noisy or imperfect data

Induction refines what analysis produces.

4. Produce a Better Final Hypothesis

Final learned rules are:

 more accurate

 more general

 learned faster

 more robust to noise

 guided by knowledge and data

🌟 Why Inductive–Analytical Learning Is Useful

✔ Can learn even when domain theory is incomplete

✔ Can handle noise (from induction)

✔ Needs fewer examples (from analysis)

✔ Produces meaningful, human-understandable rules

✔ Faster learning because theory guides the process

✔ More accurate because data corrects the theory

🌟 Simple Example

Task: Learn what makes a fruit "ripe".

Domain Theory (Weak):

 “Ripe fruits are soft” (but this is incomplete)

Example Data:

 Mango is ripe → soft + yellow + sweet

 Banana is ripe → soft + yellow

 Papaya is ripe → soft + orange

Analytical Learning:

Uses theory: finds “softness” important.

Inductive Learning:

From the examples, learns that color also matters.

Hybrid Rule Learned:

IF soft AND (yellow OR orange)

THEN fruit is ripe

This rule is better than either method alone.

1. Inductive Learning (Data-Driven Learning)

Learns by observing many examples and finding patterns.

 Depends on training data

 Learns general rules from specific examples

 Works even without background knowledge

 Examples: Decision Trees, Neural Networks

👉 Learns bottom-up (from examples to rules).

2. Analytical Learning (Explanation-Based Learning – EBL)

Learns by reasoning using prior knowledge (domain theory).

 Needs strong background knowledge

 Learns from very few examples (even one)

 Uses logical explanation to generalize

 Example: EBL

👉 Learns top-down (from theory to rules).

🌟 Comparison Table (Very Simple)

Inductive
Feature Analytical Learning
Learning

Basis Data Logic / Domain Theory

❌ No (even one
Needs many examples? ✔ Yes
example)

Needs strong background

❌ No ✔ Yes
knowledge?

Learning Style Bottom-up Top-down

❌ Sensitive to wrong
Handles noise? ✔ Yes
theory

Type of reasoning Statistical Logical

 Inductive
Feature Analytical Learning
Learning

Analytical Learning Using Perfect Domain Theories — Simple

Explanation

Analytical learning means learning by using reasoning + prior

knowledge instead of using many examples.

A perfect domain theory means:

 All rules in the domain are correct

 The theory is complete

 No errors

 Can always correctly explain any positive example

So when a domain theory is perfect, analytical learning becomes very

efficient → it can learn from one example.

🌟 How It Works (Easy Steps)

Step 1 → Give a Positive Example

Example:
“SafeToStack(A, B) is TRUE.”

Step 2 → Use Perfect Domain Theory

The system uses its correct domain rules to prove the example is true.

Step 3 → Extract Relevant Parts

It picks only the conditions used in the proof.

Step 4 → Remove Irrelevant Details

Anything not used in the proof is removed.

Step 5 → Generalize

Replace constants → variables

(Example: A → X, B → Y)
Step 6 → Output a General Rule

The final rule applies to all future situations.

🌟 NEAT DIAGRAM (Draw this in exam)

+---------------------------+

| Positive Example |

| (E.g., SafeToStack(A,B))|

+--------------+------------+

+---------------------------+

| Perfect Domain Theory |

| (Correct and complete set |

| of rules) |

+--------------+------------+

+---------------------------+

| Explanation / Proof |

| - Why the example is true |

| - Identify used rules |

+--------------+------------+

+---------------------------+

| Remove Irrelevant Info |

| Keep only essential facts |

+--------------+------------+

|
 v

+---------------------------+

| Generalization |

| Replace constants → vars |

+--------------+------------+

+---------------------------+

| Learned Rule |

| (General, reusable rule) |

+---------------------------+

This is the standard analytical-learning (EBL) pipeline under a perfect

domain theory.

🌟 Example (Very Simple)

Given Perfect Theory:

IF Width(Y) > Width(X) AND Stable(Y)

THEN SafeToStack(X, Y)

Example Given:

SafeToStack(A, B)

Explanation:

 B is wider than A

 B is stable

Generalize:

IF Width(Y) > Width(X) AND Stable(Y)

THEN SafeToStack(X, Y)

(This is the same rule → because the domain theory was perfect.)

⭐ Final VTU Answer (Short & Perfect)

Analytical learning using perfect domain theories refers to learning
that relies entirely on correct and complete prior knowledge. The learner
explains why a given example satisfies the target concept using the
domain theory, extracts only those conditions that were essential in the
explanation, removes irrelevant details, and generalizes the explanation
by replacing constants with variables. Because the domain theory is
perfect, the explanation is always correct, and the learned rule is logically
sound. Analytical learning can learn from very few examples since most of
the knowledge comes from the domain t
Module 3

1. Explain the concept of Ensemble Learning. Discuss Boosting

and Bagging methods in detail with suitable examples.

⭐ Ensemble Learning (Simple Explanation)

Ensemble Learning is a technique where multiple models (weak or

strong) are combined to produce better accuracy than any single
model.

👉 “Many weak learners combine to form one strong learner.”

Ensemble learning reduces:

 Error

 Variance

 Overfitting

⭐ Why Ensemble Learning Works?

Because different models make different mistakes.

When combined:

✔ Errors cancel out

✔ Predictions become more stable

⭐ Types of Ensemble Learning

1. Bagging (Bootstrap Aggregating)

2. Boosting

3. Stacking

4. Random Forest (Bagging-based)

⭐ 1. Bagging (Bootstrap Aggregating)

Bagging reduces variance and avoids overfitting.

✓ How It Works (step-by-step)

1. Create many subsets from the training set using bootstrap

sampling
→ Sampling with replacement

2. Train a separate model on each subset

3. Combine the predictions

o For classification → majority voting

o For regression → average

✓ Why It Works?

 Each model sees a different portion of the data

 Their mistakes are uncorrelated

 Combining them improves stability

⭐ Bagging Example (Simple)

Suppose you want to classify emails as spam or not spam.

1. Generate 10 bootstrap datasets

2. Train 10 decision trees

3. For a new email:

o If 7 trees say “spam”

o Final output = spam (majority vote)

Random Forest = Bagging + feature randomness

⭐ 2. Boosting

Boosting reduces bias by focusing on mistakes made by previous models.

✓ How It Works (step-by-step)

1. Start with equal weights for all samples

2. Train a weak learner (e.g., a small tree)

3. Increase the weights of the samples that were misclassified

4. Train the next learner focusing more on difficult samples

5. Combine all weak learners

 o Using weighted voting or weighted sum

⚡ Boosting builds models sequentially — one after the other

Each model corrects the errors of the previous one.

⭐ Boosting Example (Simple)

Example: Predicting whether a customer will buy a product.

1. Train a weak classifier

→ Misclassifies 20% of customers

2. Increase weight on these misclassified customers

3. Train second classifier

4. Repeat for several rounds

5. Final decision = weighted majority vote

⭐ Popular Boosting Algorithms

 AdaBoost (Adaptive Boosting)

 Gradient Boosting

 XGBoost

 LightGBM

⭐ Differences Between Bagging and Boosting

Feature Bagging Boosting

Parallel (independent Sequential (depends on previous

Training
models) model)

Goal Reduce variance Reduce bias

Focus Treats samples equally Focuses on misclassified samples

Combinatio
Majority vote / average Weighted vote
n

Overfitting Less prone More prone (if not regulated)

Example Random Forest AdaBoost, Gradient Boosting

⭐ Diagram (Simple for Exam)

Ensemble Learning

--------------------------------------------

| |

Bagging Boosting

(Parallel Models) (Sequential Models)

| |

Bootstrap Samples Increase weight of

Train Models misclassified samples

Combine by Voting Combine by Weighted Vote

⭐ Final VTU-Ready Answer (Short & Crisp)

Ensemble Learning is a method of improving predictive performance by

combining multiple models. It reduces error, improves stability, and gives
higher accuracy compared to individual models.

Bagging (Bootstrap Aggregating) creates multiple training subsets using

sampling with replacement, trains separate models on each subset, and
combines their predictions (majority vote or average). It reduces variance
and is used in Random Forests.

Boosting trains models sequentially. Each new model focuses more on

the samples misclassified by the earlier models. All weak learners are
combined using weighted voting. It reduces bias and produces highly
accurate predictors. AdaBoost and Gradient Boosting are popular
examples.

🌳 What is Random Forest? (Simple Explanation)

Random Forest is an ensemble learning method that builds many

decision trees and combines their predictions.

👉 It is basically Bagging + Random Feature Selection.

How it works:

1. Create many bootstrap samples (sampling with replacement)

2. Train one decision tree on each sample

 3. At each tree split → choose a random subset of features

4. Combine predictions of all trees

o Classification → majority vote

o Regression → average

Why it works?

 Reduces overfitting

 Reduces variance

 Gives stable and accurate results

🌟 Simple Example

Predict if a customer will buy a product.

 100 different decision trees are trained

 For a new customer:

o 60 trees say “Buy”

o 40 say “Not Buy”

👉 Final output = Buy (majority vote)

⭐ Difference Between Random Forest, Bagging, and Boosting

Here is a very clear and easy comparison:

✔ 1. Random Forest vs Bagging

Feature Bagging Random Forest

Data sampling Bootstrap samples Bootstrap samples

All features allowed for Random subset of features

Features used
each tree split used at each split

Diversity
Less More (due to randomness)
between trees

Overfitting Can still overfit Much lower overfitting

👉 Random Forest = Bagging + Random feature selection

✔ 2. Random Forest vs Boosting

Feature Random Forest Boosting

Parallel (independent Sequential (one after

Model training
trees) another)

Treats all samples Focuses on misclassified

Error focus
equally samples

Goal Reduce variance Reduce bias

Stability Very stable Can overfit (if not controlled)

Speed Faster Slower due to sequential steps

Example AdaBoost, Gradient Boosting,

Random Forest
algorithms XGBoost