MACHINE LEARNING
Consistent Hypothesis
Hypothesis h is consistent with a set of training examples D iff h(x) = c(x) for each
example in D.
Example to demonstrate the consistent hypothesis
Example Citations Size InLibrary Price Editions Buy
1 Some Small No Affordable One No
2 Many Big No Expensive Many Yes
h1 = (?, ?, No, ?, Many) Consistent hypothesis
h2 = (?, ?, No, ?, ?) Inconsistent hypothesis
Version space
Consider a binary classification problem. Let D be a set of training examples and
H a hypothesis space for the problem. The version space for the problem with
respect to the set D and the space H is the set of hypotheses from H consistent
with D; that is, it is the set
VSD;H = {h ∈ H ∶ h(x) = c(x) for all x ∈ D}
Hypothesis Space
ℎ1 …………ℎ𝑛
All hypothesis
Algorithm to Obtain Version Space
The algorithm that is used to obtain version space is called list then eliminate algorithm.
Step 1:make a list of every hypothesis in H
Step 2: remove inconsistent data from the list
Step 3: prepare a final list of all consistent hypothesis after considering all training data into account.
Hypothesis Space Version Space Training example D
H2 X1
H2
H1 H3 H1 H3 X2
H4 H4
X3
Let check for consistency for each hypothesis with all the training examples individually, i.e.,
If H1(X1)= C(X1)
H1(X2)= C(X2) Final Version Space
H1(X3)= C(X3)
X1
If H2(X1)= C(X1) If H4(X1)= C(X1) H1
H2(X2)≠ C(X2) H4(X2)= C(X2)
H1 X2
H2(X3)= C(X3) H4(X3)≠ C(X3)
H3
If H3(X1)= C(X1)
X3
H3(X2)= C(X2)
H3(X3)= C(X3)
Consider the following example to understand list then eliminate algorithm:
Here F1 & F2 are two attributes
F1 F2
A X
B Y
Instance Space: (A, X), (A, Y), (B, X), (B, Y) – 4 Examples
Hypothesis Space: (A, X), (A, Y), (A, ø), (A, ?), (B, X), (B, Y), (B, ø), (B, ?), (ø, X), (ø, Y), (ø, ø), (ø,
?), (?, X), (?, Y), (?, ø), (?, ?) – 16 Hypothesis
Semantically Distinct Hypothesis : (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y (?, ?),
(ø, ø) – 10
Version Space: (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y) (?, ?), (ø, ø)
Let us consider a training instance
F1 F2 TARGET
A X YES
A Y YES
Consistent Hypothesis are: (A, ?), (?, ?)
Problems: List-Then-Eliminate algorithm
1.The hypothesis space must be finite
2.Enumeration of all the hypothesis, rather inefficient
Candidate Elimination Algorithm
• The candidate elimination algorithm incrementally builds the version space given a hypothesis
space H and a set E of examples.
• The examples are added one by one; each example possibly shrinks the version space by removing
the hypotheses that are inconsistent with the example.
• The candidate elimination algorithm does this by updating the general and specific boundary for
each new example.
Salient Features for Candidate Elimination Algorithm
• Can be considered as an extended form of Find-S algorithm.
• Considers both positive and negative examples.
• Actually, positive examples are used here as Find-S algorithm (Basically they are generalizing from
the specification). Specific to general
• While the negative example is specified from generalize form.
General to specific
Terms Used:
•Concept learning: Concept learning is basically learning task of the machine (Learn by Train
data)
•General Hypothesis: Not Specifying features to learn the machine.
•G = {‘?’, ‘?’,’?’,’?’…}: depends on number of attributes.
•Specific Hypothesis: Specifying features to learn machine (Specific feature)
•S= {‘𝟇’,’𝟇’,’𝟇’…}: depends on number of attributes.
•Version Space: It is intermediate of general hypothesis and Specific hypothesis. It not only just
written one hypothesis but a set of all possible hypothesis based on training data-set.
Steps for execution of the algorithm:
1) Initialize both specific and general hypothesis depending on the numbers of attributes.
G = {‘?’, ‘?’,’?’,’?’…} and S= {‘𝟇’,’𝟇’,’𝟇’…}
2) For each example -----
if example is positive
move specific to general
else example is negative
move general to specific
Let us consider a problem of going outdoor for enjoyment
Six attributes
Sky Temperature Humidity Wind Water Forecast Enjoy Classification
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cold Change Yes
G = {‘?’, ‘?’,’?’,’?’, ’?’, ‘?’, ‘?’} and S= {‘𝟇’,’𝟇’,’𝟇’, ‘𝟇’, ‘𝟇’, ‘𝟇’}
Sky Temperature Humidity Wind Water Forecast Enjoy
Sunny Warm Normal Strong Warm Same Yes
S1= { ‘sunny’, ‘warm’,’ normal’, strong’, ‘warm’, ’same’}
G1 = {?, ?, ?, ? , ?, ?} +ve case so specific to general
This is the first hypothesis so we need to consider all attributes under specific and then make it to general one
Sky Temperature Humidity Wind Water Forecast Enjoy
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
+ ve case so specific to general
Compare the 2nd specific hypothesis to the 1st specific hypothesis
S2= { ‘sunny’, ‘warm’,’ ?’, strong’, ‘warm’, ’same’}
G2 = {?, ?, ?, ? , ?, ?}
Sky Temperature Humidity Wind Water Forecast Enjoy
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Negative case so general to specific
Now since it is a negative example so specific hypothesis S2 remains same and tinker with general hypothesis.
S2=S3= { ‘sunny’, ‘warm’,’ ?’, strong’, ‘warm’, ’same’}
To write the general hypothesis compare S3 with 3rd case mentioned in the table and find out the position
where attributes are changing. 5 question mark, attribute changes in 6th
G2 = {?, ?, ?, ? , ?, ?} position
G3 = {<‘sunny’?????>,<?warm????>,<?????Same>}
Attribute changes in 1st position followed One question mark, attribute changes in
by 5 question mark 2nd position followed by 4 question
mark
Sky Temperature Humidity Wind Water Forecast Enjoy
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cold Change Yes
+ve case so specific to general
Compare the 3rd specific hypothesis to the 4th case
S3= { ‘sunny’, ‘warm’,’ ?’, strong’, ‘warm’, ’same’}
S4= { ‘sunny’, ‘warm’,’ ?’, strong’, ‘?’, ’?’}
As we know for +ve case general
hypothesis remains same but in
G3 = {<‘sunny’?????>,<?warm????>,<?????Same>} G4 same is missing. It is because
observe S4 carefully and in S4
there is same missing so from G4
G4 = {<‘sunny’?????>,<?warm????>} also Same is removed.
