ML-II[BAI702] Module-
One of the most expressive and human readable representations for learned
hypotheses is sets of if-then rules. This chapter explores several algorithms for
learning such sets of rules. One important special case involves learning sets of rules
containing variables, called first-order Horn clauses. Because sets of first-order Horn
clauses can be interpreted as programs in the logic programming language PROLOG,
learning them is often called inductive logic programming (ILP). This chapter
examines several approaches to learning sets of rules, including an approach based on
inverting the deductive operators of mechanical theorem provers.
10.1 INTRODUCTION
Introduction to Learning Sets of Rules
• Human-Readable Representation: One of the most expressive and human-
readable ways to represent learned hypotheses is through a set of if-then rules.
• Methods for Learning Rule Sets: The sources mention several methods for
learning sets of rules:
◦ Translating a Decision Tree: A decision tree can be learned first, and then
converted into an equivalent set of rules, with one rule created for each leaf node.
◦ Using a Genetic Algorithm: A genetic algorithm can be used where each rule set
is encoded as an individual (e.g., a bit string) and the algorithm searches for the best
set.
◦ Directly Learning Rule Sets: The focus of this chapter is on algorithms that
learn rule sets directly. These algorithms differ from the above methods in two main
ways:
1. They are designed to learn first-order rules, which contain variables and
are much more expressive than propositional (variable-free) rules.
2. They typically use sequential covering algorithms, which learn one rule at a
time to incrementally build the final set of rules.
• First-Order Rules and Inductive Logic Programming (ILP):
◦ Learning sets of rules that contain variables is a special case known as learning
first-order Horn clauses.
1
ML-II[BAI702] Module-
2
◦ Because these rule sets can be interpreted as programs in the PROLOG language,
this field is often called Inductive Logic Programming (ILP). Learning these rules
is like automatically inferring PROLOG programs from examples.
◦ Expressive Power: First-order rules are very powerful. For example, the
concept of an Ancestor can be defined with two simple, recursive rules that would be
very difficult to represent with a decision tree or other propositional method:
▪ IF Parent(x, y) THEN Ancestor(x, y)
▪ IF Parent(x, z) AND Ancestor(z, y) THEN Ancestor(x, y)
• Practical Applications:
◦ First-order learning systems are particularly useful for problems where relational
assertions are important, which are difficult to describe using propositional
representations.
◦ Successful applications include:
▪ Learning to predict chemical bond fragmentation in a mass spectrometer.
▪ Identifying chemical substructures that cause mutagenic activity.
▪ Learning to design finite element meshes for analyzing stress in physical
structures.
10.2 SEQUENTIAL COVERING ALGORITHMS
1. Core Strategy and Algorithm
• Definition: Sequential covering algorithms learn a set of rules by iteratively
applying a simple strategy: learn one rule, remove the positive examples it covers, and
then repeat the process on the remaining data.
• Prototypical Algorithm (SEQUENTIAL-COVERING):
1. Start with an empty set of learned rules (Learned_rules).
2. Use a subroutine called LEARN-ONE-RULE on the available examples to
generate a single, high-accuracy rule.
3. As long as the performance of the generated rule is above a specified Threshold:
▪ Add the new rule to Learned_rules.
▪ Remove the positive examples that are correctly classified by this new rule
from the set of Examples.
▪ Call LEARN-ONE-RULE again on the reduced set of examples.
4. Once the loop terminates, sort the Learned_rules by their performance and return
the final set.
• Key Characteristics:
2
ML-II[BAI702] Module-
2
◦ This is one of the most widespread approaches for learning disjunctive (OR-ed)
sets of rules.
◦ It simplifies the problem by breaking it down into a sequence of smaller, simpler
problems of learning a single conjunctive (AND-ed) rule.
◦ The algorithm performs a greedy search without backtracking, meaning it is not
guaranteed to find the smallest or best possible set of rules.
2. The LEARN-ONE-RULE Subroutine
• Purpose: This subroutine is designed to find a single rule that has high accuracy
but not necessarily high coverage. It should cover many positive examples while
covering few negative ones.
• Implementation: General-to-Specific Beam Search:
◦ A common and effective implementation organizes the search similarly to the ID3
algorithm.
◦ It starts with the most general rule precondition possible (an empty test that
matches every instance).
◦ It then greedily adds attribute tests one at a time to make the rule more specific,
at each step choosing the test that most improves the rule's performance.
◦ Unlike ID3, which explores all branches of an attribute, this search typically
follows only the single most promising path at each step (a greedy depth-first search).
◦ To reduce the risk of making a suboptimal greedy choice, a beam search can be
used. This involves maintaining a list of the k best candidate rules at each step,
generating specialisations for all of them, and then selecting the new top k candidates
for the next step. The CN2 program uses this approach.
3. Variations on Sequential Covering Algorithms
• Learning Rules for a Single Class: A variation is to learn rules that only cover
positive examples. A "default" rule is then used to classify any instance not covered
by any learned rule as negative. This is useful when the positive class is rare (e.g.,
"patients likely to have twins") and corresponds to the "negation-as-failure" strategy
in PROLOG.
• The AQ Algorithm: The AQ family of algorithms predates CN2 and differs in a
few ways:
◦ It learns a disjunctive set of rules for each target value in turn.
3
ML-II[BAI702] Module-
2
◦ Its LEARN-ONE-RULE variant is "example-driven." It uses a single positive
example as a "seed" to guide the general-to-specific search for a new rule, only
considering attributes satisfied by that seed example.
• Performance Metrics for Guiding the Search: The PERFORMANCE metric is
crucial for guiding the search in LEARN-ONE-RULE. Common evaluation functions
include:
◦ Entropy: The negative entropy of the examples covered by the rule. This is used
by CN2 and rewards rules that cover a uniform set of examples (i.e., all positive or all
negative).
◦ Relative Frequency: The ratio of correctly classified examples to the total
number of examples a rule matches (nc/n). This is used by the AQ program.
◦ m-estimate of Accuracy: A smoothed accuracy estimate that is useful when data
is scarce. It is biased towards a prior probability p with a weighting factor m. is used
by CN2 and rewards rules that cover a uniform set of examples (i.e., all positive or all
negative).
◦ Relative Frequency: The ratio of correctly classified examples to the total
number of examples a rule matches (nc/n). This is used by the AQ program.
◦ m-estimate of Accuracy: A smoothed accuracy estimate that is useful when data
is scarce. It is biased towards a prior probability p with a weighting factor
A prototypical sequential covering algorithm is described in Table 10.1:
4
ML-II[BAI702] Module-
2
10.2.1 General to Specific Beam Search
1. Core Concept and Implementation
• Purpose: This search method is an effective way to implement the LEARN-ONE-
RULE subroutine, which is responsible for finding a single, high-accuracy rule.
• Search Direction: The search is general-to-specific. It begins with the most general
rule possible (i.e., one with an empty precondition that matches every instance) and
greedily adds attribute tests to make it more specific.
• Analogy to ID3: The process is organised in a similar fashion to the ID3 algorithm,
but with a key difference. Instead of growing an entire subtree for all possible values
of an attribute, this search typically follows only the single most promising branch
at each step. This is a greedy, depth-first search.
• Guiding the Search: At each step, the algorithm adds the attribute test that most
improves the rule's performance when measured over the training examples. The
sources suggest using entropy as the performance metric, similar to ID3, where the
best descendant is the one whose covered examples have the lowest entropy. The
LEARN-ONE-RULE algorithm in Table 10.2 defines PERFORMANCE as -Entropy
so that higher scores are better.
2. Beam Search to Reduce Risk
• Problem with Greedy Search: A simple greedy depth-first search is at risk of
making a suboptimal choice at any step, which could lead to a suboptimal final rule.
• Solution (Beam Search): To reduce this risk, the algorithm can be extended to
perform a beam search. Instead of tracking only the single best candidate rule, it
maintains a list of the k best candidates at each step.
• Beam Search Process:
1. At each step, generate all possible specialisations (descendants) for each of the k
best candidates.
2. Evaluate this entire new set of specialised rules.
3. Reduce the set back down to the k most promising members, which will be used
in the next step of the search.
• Benefit: This method keeps track of the most promising alternatives, allowing their
successors to be considered at each step, making the search more robust.
• Example Implementation: The CN2 program uses this general-to-specific beam
search algorithm. The detailed algorithm is presented in Table 10.2.
3. Details of the LEARN-ONE-RULE Algorithm (Table 10.2)
5
ML-II[BAI702] Module-
2
• Hypothesis Representation: Each hypothesis considered is a conjunction of
attribute-value constraints, which corresponds to the preconditions of the rule being
learned.
• Search Termination: The search for a single rule continues by adding constraints
until it reaches a maximally specific hypothesis (one that contains all available
attributes).
• Final Rule Selection: The algorithm does not necessarily output the final, most
specific hypothesis. Instead, it returns the rule encountered at any point during the
search that had the greatest PERFORMANCE score.
• Postcondition (Rule Head): The "then" part of the rule (the prediction or
postcondition) is determined only in the final step, after the best precondition
(Besthypothesis) has been found. It is set to predict the most frequent value of the
target attribute among the examples that match the chosen precondition.
• Interaction with SEQUENTIAL-COVERING: Even if the greedy beam search
produces a suboptimal rule, the outer SEQUENTIAL-COVERING algorithm can still
learn a complete and effective rule set because it will repeatedly call LEARN-ONE-
RULE on any positive examples that remain uncovered