Prerequisite: Version Space in Machine Learning

The Candidate Elimination Algorithm computes the version space containing all hypotheses from H that are consistent with an observed sequence of training examples.

It begins by initializing the version space to the set of all hypotheses in H, that is, by initializing the G boundary set to contain the most general hypotheses in H

G ← {<?,?,?,?,?,?,?>}

And initializing the S boundary set to contain the most specific hypothesis.

S← {<0,0,0,0,0,0,0>}

These two boundary sets delimit the entire hypothesis space because every other hypothesis in H is both more general than Sand more specific than G0.

As each training example is considered, the S and G boundary sets are generalized and specialized, respectively to eliminate from the version space any hypothesis found inconsistent with the new training example.

After all the examples have been processed, the computed version space contains all the hypotheses consistent with these examples and hypotheses.

The Candidate Elimination Algorithm goes as follows -

  1. Initialize G to the set of maximally general hypotheses in H.
  2. Initialize S to the set of maximally specific hypotheses in H.
  3. For each training example d
    1. If d is a positive example
    2. Remove from G any hypothesis that does not include.
    3. For each hypothesis s in S that does not include d, remove s from S.
    4. Add to S all minimal generalizations h of s such that h includes d, and
    5. Some member of G is more general than h
      1. Remove from S any hypothesis that is more general than another hypothesis in S.
  4. For each training example d
    1. If d is a negative example
    2. Remove from S any hypothesis that does not include.
    3. For each hypothesis g in G that does not include d
    4. Remove g from G
  5. Add to G all minimal generalizations h of g such that
    1. h does not include d and
    2. Some member of S is more specific than h
  6. Remove from G any hypothesis that is less general than another hypothesis in G.
  7. If G or S, ever becomes empty, data not consistent (with H).