Instance-Based Learning (IBL)
1
General Description
• IBL methods learn by simply storing the presented training data.
• When a new query instance is encountered, a set of similar related
instances is retrieved from memory and used to classify the new
query instance.
• IBL approaches can construct a different approximation to the
target function for each distinct query. They can construct local
rather than global approximations.
• Advantage: IBL Methods are particularly well suited to problems in
which the target function is very complex, but can still be described
by a collection of less complex local approximations.
• Disadvantage I: The cost of classifying new instances can be high
(since most of the computation takes place at this stage).
• Disadvantage II: Many IBL approaches typically consider all
attributes of the instances ==> they are very sensitive to the curse
of dimensionality!
• The curse of dimensionality in instance-based learning is the problem where, as
the number of features increases, data points become uniformly distant, making
it harder to find meaningful nearest neighbors and increasing computation costs
2
3
K-NEAREST NEIGHBOR LEARNING
• The most basic instance-based method is the k-NEAREST
NEIGHBOR algorithm.
• The nearest neighbors of an instance are defined in terms of the
standard Euclidean distance.
• More precisely, let an arbitrary instance x be described by the
feature vector
• where ar (x) denotes the value of the rth attribute of instance x.
• Then the distance between two instances xi and xj is defined to be
d(xi, xj), where
• In nearest-neighbor learning the target function may be either
discrete-valued or real-valued.
4
5
K-NEAREST NEIGHBOR LEARNING
Training algorithm:
• For each training example (x, f (x)), add the example to the list
training examples
Classification algorithm:
• Given a query instance xq to be classified,
• Let xl . . .xk denote the k instances from training examples
that are nearest to xq
• Return
where ∂(a, b) = 1 if a = b and where 6(a, b) = 0 otherwise.
k-NEAREST NEIGHBOR. A set of positive and negative training examples is
shown on the left, along with a query instance x, to be classified. The 1-
NEAREST NEIGHBOR algorithm classifies x, positive, whereas 5-NEAREST 6
NEIGHBOR classifies it as negative
Distance-Weighted NEAREST NEIGHBOR Algorithm
One obvious refinement to the k-NEAREST NEIGHBOR algorithm is to weight the
contribution of each of the k neighbors according to their distance to the query point xq, giving
greater weight to closer neighbors.
For example, in the algorithm, which approximates discrete-valued target functions, we might
weight the vote of each neighbor according to the inverse square of its distance from xq.
This can be accomplished by replacing the final line of the algorithm by
To accommodate the case where the query point xq, exactly matches one of the training
instances xi and the denominator d(xq, xi)2 is therefore zero, we assign f(xq) to be f (xi) in this
case. If there are several such training examples, we assign the majority classification among
them.
We can distance-weight the instances for real-valued target functions in a similar fashion,
replacing the final line of the algorithm in this case by
10
Remarks on k-NN
• k-NN can be used for regression instead of classification.
• k-NN is robust to noise and, it is generally quite a good
classifier.
• k-NN’s disadvantage is that it uses all attributes to classify
instances
• Solution 1: weigh the attributes differently (use cross-
validation to determine the weights)
• Solution 2: eliminate the least relevant attributes (again,
use cross-validation to determine which attributes to
eliminate)
11
Faced this situation before?
• Oops the car stopped.
– What could have gone wrong?
• Aah.. Last time it happened, there was no petrol.
– Is there petrol?
• Yes.
– Oh but wait I remember the tyre was punctured (ban
bocor)
• This is the normal thought process of a human
when faced with a problem which is similar to a
problem he/she had faced before.
13
So what?
• Reuse the solution experience when faced
with a similar problem.
• This is Case Based Reasoning (CBR)!
– memory-based problem-solving
– re-using past experiences
• Experts often find it easier to relate stories
about past cases than to formulate rules
14
CBR Cycle
15
Two big tasks of CBR
• Classification tasks (good for CBR)
– Diagnosis - what type of fault is this?
– Prediction / estimation - what happened when
we saw this pattern before?
• Synthesis tasks (harder for CBR)
– Engineering Design
– Planning
– Scheduling
17
Example
18
Example
19
Lazy versus Eager Learning
Aspect Lazy Learners Eager Learners
Minimal processing; store Build a generalized model
Training Process
data during training
When Learning Happens At prediction time At training time
Typically slow due to Fast, as the model is pre-
Prediction Speed
distance calculations built
Generally slower due to
Training Speed Fast
model-building
High, as all training data Lower, as only the model
Memory Usage
is stored is stored
k-Nearest Neighbors (k-
Decision Trees, Naive
Examples NN), Case-Based
Bayes, Neural Networks
Reasoning (CBR)
Flexible with complex Fast predictions, compact
Advantages
patterns, quick to train model, robust to noise
Risk of
Slow prediction, memory-
overfitting/underfitting,
Disadvantages intensive, sensitive to
retraining needed for new
noise
data 20
Population Chromosomes could be:
• Bit strings (0101 ... 1100)
population • Real numbers (43.2 -33.1 ... 0.0 89.2)
• Permutations of element (E11 E3 E7 ... E1 E15)
• Lists of rules (R1 R2 R3 ... R22 R23)
• Program elements (genetic programming)
• ... any data structure ...
GENETIC ALGORITHMS
29
Learning Sets Of Rules
• Introduction
• Sequential Covering Algorithm
• Learning First-Order Rules
(FOIL Algorithm)
Introduction
• GOAL: Learning a target function as a set of IF-THEN rules
• BEFORE: Learning with decision trees
• Learning the decision tree
• Translate the tree into a set of IF-THEN rules (for each leaf one rule)
• OTHER POSSIBILITY: Learning with genetic algorithms
• Each set of rule is coded as a bit vector
• Several genetic operators are used on the hypothesis space
• TODAY AND HERE:
• First: Learning rules in propositional form
• Second: Learning rules in first-order form (Horn clauses which include
variables)
• Sequential search for rules, one after the other
36
Example
IF (Outlook = Sunny) ∧ (Humidity = High) THEN PlayTennis = No
IF (Outlook = Sunny) ∧ (Humidity = Normal) THEN PlayTennis = Yes
An example of first-order rule sets
target concept: Ancestor
IF Parent(x,y) THEN Ancestor(x,y)
IF Parent(x,y)∧ Parent(y,z) THEN Ancestor(x,z)
Here we use the predicate Parent(x, y) to indicate that y is
the mother or father of x, and the predicate Ancestor(x, y)
to indicate that y is an ancestor of x related by an
arbitrary number of family generations.
Learn-One-Rule:
This method is used in the sequential learning algorithm for
learning the rules. It returns a single rule that covers at least
some examples (as shown in Fig 1). However, what makes
it really powerful is its ability to create relations among the
attributes given, hence covering a larger hypothesis space.
For example:
IF Mother(y, x) and Female(y), THEN Daughter(x, y). Here,
any person can be associated with the variables x and y
Learn-One-Rule Algorithm
The Learn-One-Rule algorithm follows a greedy searching
paradigm where it searches for the rules with high accuracy
but its coverage is very low. It classifies all the positive
examples for a particular instance. It returns a single rule that
covers some examples
Learn-One-Rule:
Learn-One-Rule:
Learn-One-Rule:
Sequential Learning Algorithm uses this algorithm, improving on it and
increasing the coverage of the hypothesis space. It can be modified to accept
an argument that specifies the target value of interest.
Sequential Covering Algorithm
• Goal of such an algorithm:
Learning a disjunctive set of rules, which defines a preferably good classification of
the training data
• Principle:
Learning rule sets based on the strategy of learning one rule,
removing the examples it covers, then iterating this process.
• Requirement for the Learn-One-Rule method:
• As Input it accepts a set of positive and negative training examples
• As Output it delivers a single rule that covers many of the positive examples and
maybe a few of the negative examples
• Required: The output rule has a high accuracy but not necessarily a high
coverage
• Procedure:
• Learning set of rules invokes the Learn-One-Rule method on all of the available
training examples
• Remove every positive example covered by the rule
• Eventually short the final set of the rules: more accurate rules can be considered
first
• Greedy search:
• It is not guaranteed to find the smallest or best set of rules that covers the
training example. 42
Sequential Covering Algorithm
Sequential Covering Algorithm
44
• Learn-One-Rule
Learning Rule Sets: Summary
• Key dimension in the design of the rule learning algorithm
• Here sequential covering: learn one rule, remove the positive examples
covered, iterate on the remaining examples
• ID3 simultaneous covering the entire set
• Which one should be preferred?
• Key difference: choice at the most primitive step in the search
ID3: chooses among attributes by comparing the partitions of the data
they generated
CN2: chooses among attribute-value pairs by comparing the subsets of
data they cover
• Number of choices: learn n rules each containing k attribute-value tests in
their precondition
CN2: n*k primitive search steps
ID3: fewer independent search steps
• If the data is plentiful, then it may support the larger number of
independent decisions
• If the data is scarce, the sharing of decisions regarding preconditions of
different rules may be more effective
46
Learning Rule Sets: Summary
• CN2: general-to-specific (cf. Find-S specific-to-general):the direction of the
search in LEARN-ONE-RULE.
• Advantage: there is a single maximally general hypothesis from which
to begin the search <=> there are many specific ones
• GOLEM: choosing several positive examples at random to initialise
and to guide the search. The best hypothesis obtained through
multiple random choices is the selected one
• CN2: generate then test
• Find-S, CANDIDATE-ELIMINATION are example-driven
• Advantage of the generate and test approach: each choice in the
search is based on the hypothesis performance over many examples,
the impact of noisy data is minimized
47
Dimension Sequential Covering (CN2) Simultaneous Covering (ID3)
Learns the entire set of rules
Learns one rule at a time, covering
Learning Process simultaneously through a single
examples and removing them iteratively
decision tree search
Fewer independent decisions,
Makes many independent decisions,
as each decision node applies
Independent Decisions with each rule requiring separate
to multiple rules based on
attribute-value test decisions
attribute values
Works better when data is plentiful, More effective with limited
Data Dependency supporting numerous independent data, sharing decision
decisions preconditions across rules
Searches from general to specific in Often follows specific-to-
Search Direction LEARN-ONE-RULE, starting with a general approaches in
maximally general hypothesis algorithms like FIND-S
Example-driven: hypotheses are
Generate-and-test: hypotheses are refined based on individual
Search Type generated first and tested against training examples in FIND-S,
training data in LEARN-ONE-RULE CANDIDATE-ELIMINATION, AQ,
etc.
Less robust to noise, as it
More robust, as decisions are based on
Noise Robustness adjusts based on individual
multiple training examples
examples
Examples of Algorithms CN2, LEARN-ONE-RULE ID3, decision tree learnin
48
May not require post-pruning
Uses post-pruning to remove
as rules are refined through the
Post-Pruning preconditions that do not improve rule
entire dataset rather than
performance on pruning data
individual instances
- Relative frequency: rule accuracy
based on proportion of correctly
classified examples Primarily uses entropy to guide
Rule Performance - m-estimate of accuracy: adjusts for rule accuracy, similar to ID3-
Evaluation 𝒏𝒄+𝒎𝒑
prior probability p 𝒏+𝒎 based algorithms
- Entropy: measures uniformity and is
used for ID3-type algorithms
Chooses among alternative
Compares attribute-value pairs, focusing
Choice of Attributes attributes, comparing partitions
on data subsets covered by each pair
generated by these attributes
Examples of Algorithms CN2, LEARN-ONE-RULE ID3, decision tree learning
49
LEARNING FIRST-ORDER RULES:
First-Order Horn Clauses
• To see the advantages of first-order representations over
propositional (variable free) representations, 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:
50
LEARNING FIRST-ORDER RULES:
Before getting into the FOIL Algorithm, let us understand the
meaning of first-order rules and the various terminologies
involved in it.
First-Order Logic:
All expressions in first-order logic are composed of the following
attributes:
[Link] — e.g. tyler, 23, a
[Link] — e.g. A, B, C
[Link] symbols — e.g. male, father (True or False values
only)
[Link] symbols — e.g. age (can take on any constant as a
value)
[Link] — e.g. ∧, ∨, ¬, →, ←
[Link] — e.g. ∀, ∃
51
LEARNING FIRST-ORDER RULES:
Term: It can be defined as any constant, variable or function
applied to any term. e.g. age(bob)
Literal: It can be defined as any predicate or negated predicate
applied to any terms. e.g. female(sue), father(X, Y)
It has 3 types:
Ground Literal — a literal that contains no variables. e.g.
female(sue)
Positive Literal — a literal that does not contain a negated
predicate. e.g. female(sue)
Negative Literal — a literal that contains a negated predicate.
e.g. father(X,Y)
52
LEARNING FIRST-ORDER RULES:
53
LEARNING FIRST-ORDER RULES:
54
LEARNING FIRST-ORDER RULES:
55
LEARNING FIRST-ORDER RULES:
56
Cover all positive examples
Avoid all negative examples
LEARNING FIRST-ORDER RULES:
• Working of the Algorithm:
• In the algorithm, the inner loop is used to generate a new best rule. Let us
consider an example and understand the step-by-step working of the
algorithm.
58
LEARNING FIRST-ORDER RULES:
59
LEARNING FIRST-ORDER RULES:
60
Analytical learning
Overview
• As discussed earlier, inductive learning methods require a
certain number of training examples to generalize accurately.
• Analytical learning stems from the idea that when not
enough training examples are provided, it may be possible to
“replace” the “missing” examples by prior knowledge and
deductive reasoning.
• Explanation-Based Learning is a particular type of analytical
approach which uses prior knowledge to distinguish the
relevant features of the training examples from the
irrelevant, so that examples can be generalized based on
logical rather than statistical reasoning.
Inductive and Analytical Learning Problems
• The inductive and analytical learning assume two different
formulations of the learning problem.
• In inductive learning
• Given:
• Instances
• Hypothesis
• Target concept
• Training examples of target concept
• Determine: hypothesis consistent with the training examples
• In analytical learning
• Given:
• Instances
• Hypothesis
• Training examples of target concept
• Domain theory fro explaining examples
• Determine: hypothesis consistent with the training examples and the
domain theory.
Intuition about Explanation-Based Learning I
• Figure 11.1 of [Mitchell, p.308] represents a
positive example of the target concept: “chess
position in which black will lose its queen
within two moves”.
• Inductive learning could eventually learn this
concept with a large number (thousands?) of
such examples.
• However, that is not what human beings do:
they learn from a restricted number of
examples: they can even learn quite a lot from
the single example in Figure 11.1.
Intuition about Explanation-Based Learning II
• From the single board on Figure 11.1, humans
can suggest the general hypothesis: “board
positions in which the black king and queen are
simultaneously attacked”. They would not even
consider the (equally consistent) hypothesis
“board positions in which four white pawns are
still in their original position”!
• They do so, because they rely heavily on
explaining or analyzing the example in terms of
their prior knowledge about the legal moves of
chess.
• Explanation-Based-Learning attempts to learn in
the same fashion.
Analytical Learning: A Definition
• Given a hypothesis space H a set of training examples D and
a domain theory B consisting of background knowledge that
can be used to explain observed training examples, the
desired output of an analytical learner is a hypothesis h from
H that is consistent with both the training examples D and
the domain theory B.
• Explanation-Based-Learning works by generalizing not from
the training examples themselves, but from their
explanation.
Learning with Perfect Domain Theories:
Prolog-EBG
• Assume domain theory is correct (error-free)
• Allow us to assume explanation = proof
• Prolog-EBG is the algorithm that works under this assumption
• This assumption holds in chess and other search problems.
Learning with Perfect Domain Theories:
Prolog-EBG
• Prolog-EBG(TargetConcept, TrainingExamples, DomainTheory)
• LearnedRules <-- { }
• Pos <-- the positive examples from TrainingExamples
• for each PositiveExample in Pos that is not covered by
LearnedRules, do
1. Explain: Explanation <-- an explanation (proof) in terms of the
DomainTheory that PositiveExample satisfies the TargetConcept
2. Analyze: SufficientConditions <-- the most general set of features of
PositiveExample sufficient to satisfy the TargetConcept according to the
Explanation
3. Refine: LearnedRules <-- LearnedRules + NewHornClause, where
NewHornClause is of the form:
TargetConcept <-- SufficientConditions
• Return LearnedRules
An Analytical Learning problem: SafeToStack(x,y)
Explanation of a Training Example
Computing the Weakest Preimage of 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.
Regression Algorithm
Regression Algorithm
Summary of Prolog-EBG
• Prolog-EBG produces justified general hypotheses.
• The explanation of how the examples satisfy the target
concept determines which examples attributes are relevant:
those mentioned in the explanation.
• Regressing the target concept to determine its weakest
preimage allows deriving more general constraints on the
value of the relevant features.
• Each learned Horn Clause corresponds to a sufficient
condition for satisfying the target concept.
• The generality of the learned Horn clauses depend on the
formulation of the domain theory and on the sequence in
which the training data are presented.
• Prolog-EBG implicitly assumes that the domain theory is
correct and complete.
Different Perspectives on Explanation-Based-
Learning (EBL)
• EBL as theory-guided generalization of examples: EBL
generalizes rationally from examples.
• EBL as example-guided reformulation of theories: EBL can be
viewed as a method for reformulating the domain theory
into a more operational form.
• EBL as “just” restating what the learner already knows: EBL
proceeds by reformulating knowledge and this can
sometimes be seen as an important kind of learning (the
difference between knowing how to play chess and knowing
how to play chess well, for example!)
EBL of Search Control Knowledge
• Given EBL’s restriction to domains with a correct and complete domain
theory, an important class of application is in speeding up complex search
problems by learning how to control search.
• Two well-known systems employ EBL in such a way: PRODIGY and SOAR.
• In PRODIGY, the questions that need to be answered during the search
problem are: “Which subgoals should be solved next?” and “Which operator
should be considered for solving this subgoal?”. PRODIGY learns concepts
such as “the set of states in which subgoal A should be solved before subgoal
B”.
• SOAR learns by explaining situations in which its current strategy leads to
inefficiencies. More generally, SOAR uses a variant of EBL called chunking to
extract the general conditions under which the same explanation applies.
• SOAR has been applied in a great number of problem domain and has also
been proposed as a psychologically plausible model of human learning
processes.
Problems associated with applying EBL to
Learning Search Control
• In many cases, the number of control rules that must be
learned is very large. As the system learns more and more
control rules to improve its search, it must pay a larger and
larger cost at each step to match this set of rules against the
current search state.
• In many cases, it is intractable to construct the explanations
for the desired target concept.