Introduction: The candidate elimination algorithm keeps two lists of hypotheses consistent with the training data:
(i) The list of most specific hypotheses S and,
(ii) The list of most general hypotheses G. This is enough to derive the whole version space VS.
Steps:
4. Output {G,S}
Step (a) Positive examples
If X is positive:
Step (b) Negative examples
If X is negative:
The candidate elimination algorithm is guaranteed to converge to the right hypothesis provided the following:
a) No errors exist in the examples
b) The target concept is included in the hypothesis space H
If there exists errors in the examples:
a) The right hypothesis would be inconsistent and thus eliminated.
b) If the S and G sets converge to an empty space we have evidence that the true concept lies outside space H.