Candidate Elimination Algorithm Concept and Example

Candidate Elimination Algorithm Concept:

Will use Version Space.
Consider both positive and negative result.
For positive example: tend to generalize specific hypothesis.
For Negative example: tend to make general hypothesis more specific.

Algorithm:

Initialize G & S as most General and specific hypothesis.
For each example e:

if e is +ve:

make specific hypothesis more general.

else:

Make a general hypothesis more specific.

Find the maximally general hypothesis and maximally specific hypothesis for the training examples given in the table using the candidate elimination algorithm.

Training Example:

Sky	Temp	Humidity	wind	water	Forecast	sport
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	cool	change	Yes

Step 1:
Initialize G & S as most General and specific hypothesis.

G ={'?', '?','?','?', '?','?'}

S = {'φ','φ','φ','φ','φ','φ'}

Step 2:
for each +ve example: make a specific hypothesis more general.

s = {'φ','φ','φ','φ','φ','φ'}

Take the most specific hypothesis as your 1st positive instance.

h={'sunny', 'warm','Normal', 'Strong', 'warm', 'same'}

General hypothesis will remain same: G ={'?', '?','?','?', '?','?'}

Step 3:
Compare with another positive instance for each attribute.
if (attribute value = hypothesis value) do nothing.
else
replace the hypothesis value with more general constraint '?'.

Since instance 2 is also positive so we will compare with it. In instance 2 attribute humidity is changing so we will generalize that attribute.

S={'sunny', 'warm','?', 'Strong', 'warm', 'same'}

General hypothesis will remain same: G ={'?', '?','?','?', '?','?'}

Step 4:
Instance 3 is negative so for each -ve example make general hypothesis more specific.
we will make the general hypothesis more specific by comparing all the attributes of the negative instance with the positive instance if attribute found different to create a dedicated set for the attribute.
G ={<'sunny', '?','?','?', '?','?'> , <'?', 'warm','?','?', '?','?'> , <'?', '?','Normal','?', '?','?'> , < '?', '?','?','?', '?','same'>}

Specific hypothesis will be same: S={'sunny', 'warm','?', 'Strong', 'warm', 'same'}

step 5:
Instance 4 is positive so repeat step 3:
S={'sunny', 'warm','?', 'Strong', '?', '?'}

Discard the general hypothesis set which is contradicting with a resultant specific hypothesis here humidity and forecast attribute is contradicting.
G ={<'sunny', '?','?','?', '?','?'> , <'?', 'warm','?','?', '?','?'> }

.:. Maximally specific and general hypothesis are:

S={'sunny', 'warm','?', 'Strong', '?', '?'}

G ={<'sunny', '?','?','?', '?','?'> , <'?', 'warm','?','?', '?','?'> }