Version Space
The version space is therefore a collection of ERM hypotheses, not necessarily a single hypothesis.
The Candidate Set Before Prediction
In online learning, the learner receives examples one round at a time. Before round t, it has already seen the earlier examples and can use them to eliminate hypotheses that disagree with those examples. The remaining hypotheses form the version space, written as V_t. The central question is not simply which hypothesis is correct, but which hypotheses are still consistent with everything observed so far.
ERM as Consistency
An ERM hypothesis is any hypothesis consistent with all past examples. In the online-learning setting, this means that an ERM hypothesis agrees with every labeled example received before the current round.
The version space is therefore a collection of ERM hypotheses, not necessarily a single hypothesis. Every member has survived all consistency checks performed so far. If several hypotheses remain, the Consistent algorithm may choose any one of them for the next prediction.
A Round of the Consistent Algorithm
The Consistent algorithm follows a strict order. First, the new instance x_t arrives. Next, the algorithm chooses any hypothesis from the current version space V_t. It uses that hypothesis to predict h(x_t). Only after the prediction does it receive the true label y_t. The algorithm then keeps the hypotheses in V_t whose predictions on x_t match y_t.
Tracing Candidate Elimination
Consider a generated illustration with three hypotheses: hA, hB, and hC. Initially, before any examples have been observed, all three are candidates. Thus V_1 contains hA, hB, and hC. Suppose the first instance is x_1, and the true label is y_1. If hB predicts a label different from y_1 while hA and hC match y_1, the update removes hB and leaves V_2 containing hA and hC.
Two Online-Learning Rounds
Track the version space when V_1 contains hA, hB, and hC. On the first example, hA and hC agree with the true label while hB disagrees. On the second example, hA disagrees while hC agrees.
- 1Round 1: receive x_1
The algorithm receives the instance before making a prediction. It chooses a hypothesis from V_1, which contains hA, hB, and hC.
- 2Round 1: receive y_1
After the prediction, the true label arrives. The update keeps hA and hC because their predictions on x_1 match y_1. It removes hB.
- 3Before round 2
The updated version space is V_2 = {hA, hC}. Both remaining hypotheses are consistent with the first labeled example.
- 4Round 2: receive x_2 and y_2
The algorithm selects from V_2. After the true label for x_2 arrives, hA is removed because it disagrees with y_2, while hC remains.
After the two updates, the version space is V_3 = {hC}. The set has shrunk because each update retains only hypotheses that agree with the newly revealed true label.
Selecting the Prediction Hypothesis
At the start of a round, the algorithm does not update the version space using the current example's true label, because that label has not yet been revealed. It first selects any hypothesis from V_t and predicts with that hypothesis. The selection must come from the current version space; using a hypothesis already eliminated by an earlier example would violate the Consistent algorithm's rule.
Finding the First Incorrect Step
When a traced result is incorrect, locate the first point where it stops following the algorithm. There are three main checks. The instance must arrive before the prediction. The selected hypothesis must belong to V_t, and the prediction must be h(x_t). After the true label arrives, the update must compare every hypothesis's prediction on x_t with y_t and retain only the matching hypotheses.
Common mistake Using the true label before making the prediction
What it looks likeChoosing a hypothesis only after seeing y_t for the current instance
Why it failsThe true label is received only after the prediction.
Do this insteadReceive x_t, choose from V_t, predict, then receive y_t and update.
Common mistake Selecting a hypothesis that is not in V_t
What it looks likeUsing hB after an earlier labeled example has already removed hB
Why it failsThe Consistent algorithm chooses from the current version space.
Do this insteadCheck the version space immediately before the round and select one of its members.
Common mistake Updating with the selected hypothesis only
What it looks likeRemoving or retaining candidates based only on the hypothesis used for the prediction
Why it failsThe update filters the hypotheses in V_t by comparing each one with y_t.
Do this insteadEvaluate every hypothesis in V_t on x_t and keep exactly those whose predictions match y_t.
Common mistake Comparing with the wrong label
What it looks likeFiltering candidates using a previous round's label instead of y_t
Why it failsThe current update must use the true label for the current instance.
Do this insteadMatch each hypothesis's prediction on x_t against the newly received y_t.
Practice the Round Trace
Suppose the current version space is V_t = {hA, hB}. The new instance x_t arrives. The algorithm selects hA and predicts with hA(x_t). Afterward, the true label y_t is revealed. On x_t, hA disagrees with y_t and hB agrees with y_t. What is the updated version space before the next round, and which hypothesis was used for the prediction?
Hints
- Separate the prediction stage from the update stage.
- The prediction uses the selected hypothesis before y_t is revealed.
- The update retains every hypothesis in V_t whose prediction matches y_t.
Practice Answer
V_t contains hA and hB. The algorithm predicts with hA, then the true label shows that hA disagrees and hB agrees.
- 1Prediction
The prediction was made using hA because hA was selected from V_t before the true label arrived.
- 2Update
The update checks both members of V_t. It removes hA because hA(x_t) disagrees with y_t and keeps hB because hB(x_t) matches y_t.
The updated version space is {hB}, and hA was the hypothesis used for the prediction.
Round-by-Round Checklist
- 1Identify V_t as the hypotheses consistent with all examples observed before round t.
- 2Receive x_t before making the prediction.
- 3Choose any hypothesis from V_t.
- 4Predict using that hypothesis on x_t.
- 5Receive the true label y_t after the prediction.
- 6Keep only the hypotheses in V_t whose predictions on x_t match y_t.
- 7Use the resulting set as the version space for the next round.
Key Takeaways
- An ERM hypothesis is consistent with every past example.
- V_t contains the hypotheses consistent with examples observed before round t.
- The Consistent algorithm selects any member of V_t to predict on x_t.
- After y_t is revealed, the update keeps only hypotheses whose predictions on x_t match y_t.
- To debug an incorrect trace, check the round order, hypothesis selection, prediction, and update in that order.