Prerequisite: Version Space in Machine Learning

The List-Then-Eliminate algorithm initializes the version space to contain all hypotheses in H, then eliminates the hypotheses that are inconsistent, from training examples.

The version space of hypotheses thus shrinks as more examples are observed until one hypothesis remains that is consistent with all the observed examples.

Presumably, this hypothesis is the desired target concept.

If the data available is insufficient, to narrow the version space to a single hypothesis, then the algorithm can output the entire set of hypotheses consistent with the observed data.

The List-Then-Eliminate algorithm can be applied whenever the hypothesis space “H” is finite.

It has many advantages, including the fact that it is guaranteed to output all hypotheses consistent with the training data.

It requires exhaustively enumerating all hypotheses in H — an unrealistic requirement for all but the most trivial hypothesis spaces.