Version space & the candidate-elimination algorithm

Concept learning is search over a lattice

From L8.1, the space of concept descriptions is partially ordered by generality. The version space is the subset of that space still consistent with every training example seen so far — every hypothesis that labels each positive instance positive and each negative instance negative. As examples arrive, the version space shrinks.

The trick of candidate elimination (Mitchell) is to never enumerate the version space — just track its two boundaries:

• S — the set of most-specific hypotheses consistent with the data.
• G — the set of most-general hypotheses consistent with the data.

Every consistent concept lies between S and G. The two boundaries crawl toward each other:

• a positive example generalizes S (minimally, so S still covers it) and prunes any member of G that fails to cover it;
• a negative example specializes G (minimally, so G no longer covers it) and prunes any member of S that wrongly covers it.

When S == G == {one concept} the algorithm has provably found the unique consistent concept. When S and G become empty, the target is not expressible in the representation language.

Worked example

Describe weather by three attributes ⟨sky, temp, humidity⟩, where ? means “any value”. Start at the extremes: $S_0=⟨\varnothing ,\varnothing ,\varnothing ⟩$ (covers nothing), $G_0=⟨?,?,?⟩$ (covers everything).

1. + ⟨sunny,warm,high⟩ — S generalizes to exactly that instance: ⟨sunny,warm,high⟩.
2. + ⟨sunny,warm,low⟩ — S must now cover both, so the differing attribute (humidity) becomes ?: S = ⟨sunny,warm,?⟩.
3. − ⟨rainy,cold,high⟩ — G specializes to exclude this negative while still covering the positives. Two minimal specializations survive: ⟨sunny,?,?⟩ (it isn’t sunny) and ⟨?,warm,?⟩ (it isn’t warm).

Result: S = [⟨sunny,warm,?⟩], G = [⟨sunny,?,?⟩, ⟨?,warm,?⟩]. The version space is everything between them — the exercise below computes exactly this.