Lesson5.9. Candidate Elimination Algorithm
Consider the following dataset:
Training Dataset
A person named Aldo Enjoys sport under the given
conditions.
Concept
The concept to learn is when does a person Aldo enjoy
sports.
The answer is Boolean : Yes – enjoys sport or No – doesn’t
enjoy sport.
Hypothesis Space
The actual space in which we search is huge. So let us
restrict to a hypothesis representation of the search space with only the
attributes in the training dataset. The easiest way to represent is by taking the
conjunction of all the attributes.
That is,
<sunny, warm, normal, strong, warm, same, yes>
is a hypothesis represented by <x,c(x)>. Here c(x) is ‘yes’.
We say that if it is,
Sunny and warm and normal and strong and warm and same,
then Aldo enjoys sports.
Notations
We assume the following notations as before:
0 – most specific and implies that the attribute
should have no value.
Attribute name – the given attributes in the table. Eg. sunny
? – the most generic where the attribute can take any
value
G - General set - Can have multiple g
Consistent
A hypothesis h is said to be consistent on x if
h(x) = c(x) for the training set x
A hypothesis h is consistent on a dataset D, if
h(x) = c(x) for all x in D
Version Space
The goal is to find all the consistent hypotheses on D.
That is, find all hypothesis in hypothesis space H that are consistent with
dataset D. This set is termed the Version Space.
Algorithm Overview
Goal
Create two sets G and S.
G = Set of all general hypotheses consistent with D
S = Set of all specific hypotheses consistent with D
Step 1 : Initialise
G_0 = Most General Hypotheses
= <?, ?, ?,
?, ?, ?>
S_0 = Most Specific Hypotheses
= <0, 0, 0,
0, 0, 0>
G_0 and S_0 – the 0 mentions the number of instances
already looked in the dataset.
Step 2: Perform Step 3 for all the instances in the training dataset
Step 3: Check if it is a positive label or negative label
That is, EnjoySport = Yes is positive
Perform Step 3.1., if the example is positive and Step
3.2 for negative examples
Step 3.1. The instance(x) is positive.
Step 3.1.1.
Check G
Take the
hypothesis(g) in G one by one and if it is inconsistent with x, remove the g
from G
Step
3.1.2. Check S
Take
the hypothesis(s) in S one by one and check with x.
If
s is inconsistent with x,
-
Remove s from S
-
Find all the minimal generalizations of s such that:
o
They are consistent with x. Note that the generalization
must be minimum.
o
They(s) are less general than some hypothesis in G.
o
Insert them in S
-
Check the hypothesis in S. If any hypothesis is more
general than another hypothesis remove the hypothesis.
Step 3.2. The instance(x) is negative. (Note: We swap G and S wrt step 3.1)
Step 3.2.1.
Check S
Take the
hypothesis(s) in S one by one and if it is inconsistent with x, remove the s
from S
Step
3.2.2. Check G
Take
the hypothesis(g) in G one by one and check with x.
If
g is inconsistent with x,
-
Remove g from G
-
Find all the minimal specifications of g such that:
o
They(g) are consistent with x. Note that the generalization
must be minimum.
o
They are more general than some hypothesis in S.
o
Insert them in G
-
Check the hypothesis in G. If any hypothesis is less
general than another hypothesis remove the hypothesis.
Minimal Generalization:
0 is replaced with specific attribute value
or
specific attribute value is replaced with ?
Eg. <0,0> is replaced with <warm, same>
or
<warm, same> may be replaced with <warm, ?>
The Algorithm(as in Tom Michell)
Example – Step by Step Explanation
Initial:
G_0 = Most General Hypotheses
= {<?, ?, ?,
?, ?, ?>}
S_0 = Most Specific Hypotheses
= {<0, 0, 0,
0, 0, 0>}
Positive Instance 1 : <sunny, warm, normal, strong, warm, same>
Check G_0
When we pass <sunny, warm, normal, strong, warm,
same> in the hypothesis <?, ?, ?, ?, ?, ?>, the result is “Yes” and so
x is consistent with g in G.
G_1 = {<?, ?, ?, ?, ?, ?>}
Check S_0
Remove inconsistent s
When we pass <sunny, warm, normal, strong, warm,
same> in the hypothesis <0, 0, 0, 0, 0, 0>, the result is “No” and so x
is inconsistent with s in S. Here there is only one ‘s’ in S.
S = {} after removing s
Add consistent and less general s
s=<0, 0, 0, 0, 0, 0> and minimal generalization is
making 0 into a specific value that is consistent with x=<sunny, warm,
normal, strong, warm, same>.
The number of minimal generalizations possible is very
huge.
[For the example in lesson5.8, the minimal generalization of <0,0> are
Minimal generalization =
{ <warm, 0>, <cold, 0>,
<0,rural>, <0,urban>
}
Let x = <warm, rural>. It is does not fit the minimal generalization and so we make it a little more general, by changing 1 feature in every hypothesis.
Next_minimal_generalization = {
<warm, rural>, <warm, urban>,
<cold, rural>, <cold, urban>
}
Next_Minimal generalization that fits sample =
{ <warm, rural>
}
]
So s=<sunny, warm, normal, strong, warm, same>
Also, s=<sunny, warm, normal, strong, warm, same>
is less general than g=<?, ?, ?, ?, ?, ?>
Insert s in S
S_1 = {<sunny, warm, normal, strong, warm, same>}
Summary
G_1 = {<?, ?, ?, ?, ?, ?>}
S_1 = {<sunny, warm, normal, strong, warm, same>}
Positive Instance 2 : <sunny, warm, high, strong, warm, same>
Check G_2
When we pass <sunny, warm, high, strong, warm, same>
in the hypothesis <?, ?, ?, ?, ?, ?>, the result is “Yes” and so x is
consistent with g in G.
G_2 = {<?, ?, ?, ?, ?, ?>}
Check S_2
Remove inconsistent s
When we pass x=<sunny, warm, high, strong, warm,
same> in the hypothesis s=<sunny, warm, normal, strong, warm, same>, the
result is “No” and so x is inconsistent with s in S. Here there is only one ‘s’
in S.
S = {} after removing s
Add consistent and less general s
s=<sunny, warm, normal, strong, warm, same> and
minimal generalization is making specific value to ? that is consistent with x=<sunny,
warm, high, strong, warm, same>.
So s=<sunny, warm, ?, strong, warm, same>
Also, s=<sunny, warm, ?, strong, warm, same> is
less general than g=<?, ?, ?, ?, ?, ?>
Insert s in S
S_1 = {<sunny, warm, ?, strong, warm, same>}
Summary
G_2 = {<?, ?, ?, ?, ?, ?>}
S_2 = {<sunny, warm, ?, strong, warm, same>}
Negative Instance 3 : <rainy, cold, high, strong, warm, change>
Check S_3
When we pass <rainy, cold, high, strong, warm, change>
in the hypothesis <sunny, warm, ?, strong, warm, same>, we see the first
attribute should be “sunny” to get an “yes”, but the training set has “rainy”.
Like this we can check for all attributes. So the result when passed through
the hypothesis is “No” and this is a negative instance and so x is consistent
with s in S.
S_3 = {<sunny, warm, ?, strong, warm, same>}
Check G_3
G_2 = {<?, ?, ?, ?, ?, ?>} and it is inconsistent
with x cause checking<rainy, cold, high, strong, warm, change> in q will
return ‘yes’. But it is a negative instance.
G_3 = {} after removing g
Minimal specializations of g that are consistent are {
<sunny, ?, ?, ?, ?, ?>, <?, warm, ?, ?, ?, ?>, <?, ?, normal, ?,
?, ?>, <?, ?, ?, weak, ?, ?>, <?,
?, ?, ?, cold, ?>, <?, ?, ?, ?, ?, same> }.
This is because we assume 2 possible values for each
attribute. If there was a third value like ‘medium’ for attribute ‘humidity’,
we would have included <?, ?, medium, ?, ?, ?>.
[For the example in lesson5.8, the minimal specializations
of <?,?> are
Minimal specialization =
{<warm, ?>, <cold, ?>, <?,urban>,
<?,rural>}
Reason : All that pass in <warm, urban> will
pass in <warm,?> and <?, ?>
But all that pass in <warm, ?> will not pass in
<warm, urban>. So <warm, ?> next minimal generalization of <?,
?>
If <cold, rural> is a negative example, then we
remove the inconsistent h{<warm, ?>, <cold, ?>, <?,urban>,
<?,rural>}. The inconsistent h has the attribute name in it as
cold or urban.
Further Explanation:
Here are the minimal specializations:
<warm,
?> (specializing the first feature to 'warm' while leaving the second
feature general)
<cold,
?> (specializing the first feature to 'cold' while leaving the second
feature general)
<?,
rural> (leaving the first feature general and specializing the second
feature to 'rural')
<?,
urban> (leaving the first feature general and specializing the second
feature to 'urban')
These are the most specific hypotheses that can be obtained from <?,?> by replacing one ? with a specific value from the corresponding feature's domain
]
Consistent_G_3 = { <sunny, ?, ?, ?, ?, ?>, <?,
warm, ?, ?, ?, ?>, <?, ?, normal, ?, ?, ?>, <?, ?, ?, strong, ?,
?> , <?, ?, ?, ?, cold, ?>, <?, ?, ?, ?, ?, same> }
S_3 = {<sunny, warm, ?, strong, warm, same>}
Checking h >= s
That is, an ‘x’ that gives ‘yes’ in s should not give ‘no’ in h.
<sunny, ?, ?, ?, ?, ?> is more general than <sunny,
warm, ?, strong, warm, same>
<?, warm, ?, ?, ?, ?> is more general than <sunny,
warm, ?, strong, warm, same>
Reasoning
Let x = <sunny, warm, high, strong, warm, same>
h=<?, ?, normal, ?, ?, ?> is less general than s=<sunny,
warm, ?, strong, warm, same>
x is yes in s, but 'no' in h
Let x = <sunny, warm, normal, strong, warm, same>
h=<?, ?, ?, weak, ?, ?> is less general than s=<sunny,
warm, ?, strong, warm, same>
x gives 'no' in h, but 'yes' in s
<?, ?, ?, ?, cold, ?> is less general than <sunny,
warm, ?, strong, warm, same>
<?, ?, ?, ?, ?, same> is more general than <sunny,
warm, ?, strong, warm, same>
G_3 = {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?,
?, ?, ?>, <?, ?, ?, ?, ?, same> }
Inside G_3, no hypothesis is less than another.
Summary
G_3 = {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?,
?, ?, ?>, <?, ?, ?, ?, ?, same> }
S_3 = {<sunny, warm, ?, strong, warm, same>}
Positive Instance 4 : <sunny, warm, high, strong, cool, change>
Check G_4
Check if <sunny, warm, high, strong, cool, change> is consistent with every hypothesis in the set {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?, ?, ?, ?>, <?, ?, ?, ?, ?, same> }.
<sunny, warm, high, strong, cool, change> consistent with <sunny, ?, ?, ?, ?, ?>
<sunny, warm, high, strong, cool, change> consistent with <?, warm, ?, ?, ?, ?>
<sunny, warm, high, strong, cool, change> is not consistent with <?, ?, ?, ?, ?, same>
G_4 = {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?, ?, ?, ?>}
Check S_4
S_3 = {<sunny, warm, ?, strong, warm, same>}
Remove inconsistent s
When we pass x=<sunny, warm, high, strong, cool, change> in the hypothesis s=<sunny, warm, ?, strong, warm, same>, the
result is “No” and so x is inconsistent with s in S. Here there is only one ‘s’
in S.
S = {} after removing s
Add consistent and less general s
s = <sunny, warm, ?, strong, warm, same>
Minimal Generalization = {}
s=<sunny, warm, ?, strong, warm, same> and
minimal generalization is making specific value to ? that is consistent with x=<sunny,
warm, high, strong, cool, change>.
How to get minimal generalization
Comparing s and x:
The first
attribute is the same: sunny.
The second
attribute is the same: warm.
The third
attribute differs (? in s can cover high in x).
The fourth
attribute is the same: strong.
The fifth
attribute differs: warm in s should be generalized to ? to cover cool in x.
The sixth
attribute differs: same in s should be generalized to ? to cover change in x.
The minimal generalization of s to cover x would be:
s = <sunny, warm, ?, strong, ?, ?>
Also, s=<sunny, warm, ?, strong, ?, ?> is
less general than
Insert s in S
S_4 = {<sunny, warm, ?, strong, ?, ?>}
Summary
G_4 = {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?, ?, ?, ?>}
S_4 = {<sunny, warm, ?, strong, ?, ?>}
Final Output
G = {<sunny, ?, ?, ?, ?, ?> , <?, warm, ?, ?, ?, ?>}
S = {<sunny, warm, ?, strong, ?, ?>}
Comments
Post a Comment