Candidate Elimination Algorithm Solved Example – 2

 

Candidate Elimination Algorithm in Machine Learning

Candidate Elimination Algorithm is used to find the set of consistent hypothesis, that is Version spsce.

Click Here for Python Program to Implement Candidate Elimination Algorithm to get Consistent Version Space

Video Tutorial of Candidate Elimination Algorithm Solved Example – 2

Algorithm:

For each training example d, do:
     If d is positive example
         Remove from G any hypothesis h inconsistent with d
         For each hypothesis s in S not consistent with d:
              Remove s from S
              Add to S all minimal generalizations of s consistent with d and having a generalization in G
              Remove from S any hypothesis with a more specific h in S
     If d is negative example
          Remove from S any hypothesis h inconsistent with d
          For each hypothesis g in G not consistent with d:
                Remove g from G
                Add to G all minimal specializations of g consistent with d and having a specialization in S
                Remove from G any hypothesis having a more general hypothesis in G

Solved Numerical Example – 2 (Candidate Elimination Algorithm):

ExampleSizeColorShapeClass/Label
1BigRedCircleNo
2SmallRedTriangleNo
3SmallRedCircleYes
4BigBlueCircleNo
5SmallBlueCircleYes

Solution:

S0: (0, 0, 0) Most Specific Boundary

G0: (?,  ?,  ?) Most Generic Boundary

The first example is negative, the hypothesis at the specific boundary is consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent hence we write all consistent hypotheses by removing one “?” at a time.

S1: (0, 0, 0)

G1: (Small, ?, ?), (?, Blue, ?), (?, ?, Triangle)

The second example is negative, the hypothesis at the specific boundary is consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent hence we write all consistent hypotheses by removing one “?” at a time.

S2: (0, 0, 0)

G2: (Small, Blue, ?), (Small, ?, Circle), (?, Blue, ?), (Big, ?, Triangle), (?, Blue, Triangle)

The third example is positive, the hypothesis at the specific boundary is inconsistent, hence we extend the specific boundary, and the consistent hypothesis at the generic boundary is retained and inconsistent hypotheses are removed from the generic boundary.

S3: (Small, Red, Circle)

G3: (Small, ?, Circle)

The fourth example is negative, the hypothesis at the specific boundary is consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent hence we write all consistent hypotheses by removing one “?” at a time.

S4: (Small, Red, Circle)

G4: (Small, ?, Circle)

The fifth example is positive, the hypothesis at the specific boundary is inconsistent, hence we extend the specific boundary, and the consistent hypothesis at the generic boundary is retained and inconsistent hypotheses are removed from the generic boundary.

S5: (Small, ?, Circle)

G5: (Small, ?, Circle)

Learned Version Space by Candidate Elimination Algorithm for given data set is:

S: G: (Small, ?, Circle)

Summary

This tutorial discusses the Candidate Elimination Algorithm to find the set of consistent hypotheses in Machine Learning. If you like the tutorial share with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published. Required fields are marked *