Can a version space contain infinitely many hypotheses?

Yes. Its definition does not require a finite hypothesis space.

Does adding an example enlarge the classical version space?

No. With H fixed, additional consistency constraints can only preserve or shrink it.

Can surviving hypotheses disagree on new data?

Yes. Agreement on observed examples does not imply agreement everywhere.

AI Glossary / Graphs and symbolic AI / Intermediate

Version space

Definition

A version space is the set of hypotheses within a chosen hypothesis space that are consistent with all the training examples observed so far. In classical concept learning, consistency means predicting every observed label correctly. As new labeled examples arrive, hypotheses that disagree with them are removed, leaving the explanations that have not yet been ruled out.

What it means

The learner need not immediately choose one explanation. Several hypotheses can fit the same observations but disagree about unseen cases. The version space makes that remaining uncertainty explicit.
Its contents depend on both the data and the allowed hypothesis language. If the true rule is not expressible in that language, no amount of data can put it into the version space. If labels conflict or contain noise, insisting on exact consistency can eventually leave no hypothesis at all. The classical construction is therefore clearest under a noiseless, realizable learning assumption.

How it works

Begin with a hypothesis space H. For every new example, retain only hypotheses whose prediction matches its label. Symbolically, the version space is the subset of H satisfying all observed constraints.
Explicitly listing every hypothesis is often impractical. In suitable ordered hypothesis spaces, a candidate-elimination approach represents the remaining set through maximally general and maximally specific boundaries. Positive and negative examples update those boundaries differently. The representation must preserve every consistent hypothesis between them, not just one favored rule. Predictions on new cases can be certain within the model when all remaining hypotheses agree, or unresolved when they disagree.

Three practical examples

A concept-learning lesson can maintain all simple classification rules consistent with a small labeled dataset.
An interactive rule-learning prototype can identify an example on which surviving rules disagree and request its label.
A debugging exercise can inspect why the consistent hypothesis set became empty after a new training example.

Think of it this way

Think of keeping a list of plausible explanations and crossing out any explanation contradicted by new evidence. The remaining list records what the evidence has not settled. The analogy is limited because the initial list may exclude the true explanation, and an erroneous observation can wrongly eliminate a useful hypothesis.

Worked example

Consider an original classification task with objects described by color, red or blue, and shape, round or square. Restrict the hypothesis space to exactly six rules: accept every object; accept no object; accept red objects; accept round objects; accept objects that are both red and round; and accept objects that are red or round.
Initially, all six hypotheses remain. Observe a positive red round object. Every rule except accept-none predicts positive, so five survive.
Next observe a negative blue square object. Accept-everything is inconsistent and is removed. The four remaining rules are red, round, red-and-round, and red-or-round. All four accept the first example and reject the second.
Now observe a negative red square object. The red rule and red-or-round rule predict positive for it, so both are eliminated. The version space now contains exactly two hypotheses: round and red-and-round.
These two agree on red round, red square, and blue square objects. They disagree on blue round: round predicts positive, while red-and-round predicts negative. The existing evidence therefore does not justify a unique prediction for that case within this hypothesis space.
If a newly labeled blue round object is positive, the conjunction rule is eliminated and only round remains. If it is negative instead, round is eliminated and only red-and-round remains. Either label resolves the disagreement, assuming it is trustworthy.
At the two-hypothesis stage, round is the more general rule because it accepts everything the conjunction accepts and also blue round objects. It forms the general boundary, while red-and-round forms the specific boundary in this restricted example.
Finally, suppose a later example labels a red round object negative despite the earlier positive label for the identical feature combination. No deterministic rule over just these two features can satisfy both labels. The version space becomes empty. Possible explanations include a labeling error or an omitted feature; simply choosing another survivor is impossible because none remain.

Illustrative case study

In a fictional rule-learning workshop, a team uses a small feature language to infer which sample items require a special processing step. Several rules initially fit all examples, so the team chooses a new example specifically to distinguish them.
When two identical feature descriptions receive conflicting labels, the team reviews the records and considers whether a missing attribute affects the decision. It does not silently discard inconvenient data. This fictional case illustrates transparent uncertainty management rather than a deployed classification result.

Common misconceptions and mistakes

A version space is not a probability distribution over hypotheses. Equal membership does not imply equal probability or equal credibility unless an additional model supplies that interpretation.
Do not assume that a single surviving hypothesis must be the real-world truth. It is unique only relative to the selected hypothesis space and observed labels. Do not treat an empty space as proof that learning is impossible; it may reveal noise, contradictory labels, or an overly restrictive representation. Finally, exact consistency is different from minimizing average training error.

Business use

The concept is useful for explaining why evidence can leave several plausible rules and why the choice of features and hypothesis language matters. It can also motivate targeted data collection: examples that separate surviving hypotheses may be more informative than repeated examples on which they all agree.
For practical use, state how inconsistent labels are handled and avoid claiming certainty beyond the model. Preserve the observations responsible for eliminating a hypothesis so reviewers can trace the reasoning. If noise is expected, consider a learning formulation that explicitly accommodates it.

Check your understanding

After the negative red square example, why is a blue round object informative?

Answer: The two surviving rules predict different labels for it. Its label can distinguish them.

Related terms

Learn next

Next, repeat the example after removing the round rule from the initial hypothesis space. Track what happens when blue round is later labeled positive. Explain why correct new evidence can empty a restricted version space even when the underlying classification rule is simple.

Hypothesis space

Sources

Primary sources: Poole and Mackworth, Artificial Intelligence: Foundations of Computational Agents, Version-Space Learning: https://www.cs.ubc.ca/~poole/aibook/html1e/ArtInt_192.html ; Mitchell, Machine Learning, concept-learning treatment: https://www.cs.cmu.edu/~tom/files/MachineLearningTomMitchell.pdf . The six-rule hypothesis space and elimination trace are original.

Previous: Verification and validation Next: Version space learning