The LIST-THEN-ELIMINATION algorithm

The LIST-THEN-ELIMINATE algorithm first initializes the version space to contain all hypotheses in H and then eliminates any hypothesis found inconsistent with any training example.

1.  VersionSpace c a list containing every hypothesis in H

2.  For each training example, (x, c(x))

remove from VersionSpace any hypothesis h for which h(x) ≠ c(x)

3.  Output the list of hypotheses in VersionSpace

 The LIST-THEN-ELIMINATE Algorithm

• List-Then-Eliminate works in principle, so long as version space is finite.
• However, since it requires exhaustive enumeration of all hypotheses in practice it is not feasible.