Candidate Elimination Algorithm in Machine Learning
Candidate Elimination Algorithm is used to find the set of consistent hypothesis, that is Version spsce.
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):
Example | Size | Color | Shape | Class/Label |
1 | Big | Red | Circle | No |
2 | Small | Red | Triangle | No |
3 | Small | Red | Circle | Yes |
4 | Big | Blue | Circle | No |
5 | Small | Blue | Circle | Yes |
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.