ERM Hypothesis
The central distinction is between one selected ERM hypothesis and the whole version space. The selected hypothesis makes the next prediction; the version space contains every hypothesis that is still consistent with the examples observed so far.
A Choice Under Partial Information
In online learning, the algorithm must make a prediction before it knows the true label for the current instance. It therefore needs a hypothesis that agrees with every example it has already seen. An ERM hypothesis is any hypothesis consistent with all past examples. The Consistent algorithm applies this idea one round at a time: it selects a hypothesis from the current version space, uses it to predict, receives the true label, and then removes hypotheses that disagree with that label.
The central distinction is between one selected ERM hypothesis and the whole version space. The selected hypothesis makes the next prediction; the version space contains every hypothesis that is still consistent with the examples observed so far.
Version Space Across Rounds
The version space V_t is the set of hypotheses consistent with the examples observed before round t. At the beginning of round t, the Consistent algorithm chooses any hypothesis from V_t. After the algorithm receives the current instance x_t, predicts, and then receives the true label y_t, the next version space keeps only the hypotheses in V_t whose prediction on x_t equals y_t. In other words, the update filters the current set rather than selecting an unrelated new set of hypotheses.
Filtering a Version Space
Suppose a generated teaching example begins with V₁ = {hA, hB, hC}. On the first round, the current example causes hB to disagree with the received true label, while hA and hC agree.
- 1Start
Before the first round, all three listed hypotheses are in V₁.
- 2Prediction
The Consistent algorithm selects any one hypothesis from V₁ for the prediction. The other hypotheses remain candidates in the version space even though they were not selected.
- 3Update
After the true label is received, remove hB because its prediction on the current instance does not equal the true label. Keep hA and hC.
- 4Next round
The resulting version space is V₂ = {hA, hC}. It is the set available for the next round.
The update changes the whole candidate set from {hA, hB, hC} to {hA, hC}; it does not merely replace the single hypothesis used for prediction.
The Consistent Algorithm
- 1Start round t with the current version space V_t.
- 2Receive the current instance x_t.
- 3Choose any hypothesis from V_t.
- 4Use the selected hypothesis to make the prediction h(x_t).
- 5Receive the true label y_t after the prediction.
- 6Keep only the hypotheses in V_t whose prediction on x_t matches y_t.
Locating an Incorrect Result
When a recorded result is incorrect, trace the algorithm from the first step and identify the first point where it no longer follows the rule. There are three main checks. First, verify that the selected hypothesis came from V_t. Second, verify that the prediction was made by applying that hypothesis to x_t. Third, verify that the update compared each hypothesis's prediction on x_t with the true label y_t. An error in any of these steps can produce an incorrect result later in the round.
Common mistake Treating the selected hypothesis as the entire version space
What it looks likeThe algorithm selects hA from V_t, and the trace records only hA as the remaining candidate.
Why it failsV_t is a set of hypotheses. Selecting one hypothesis determines the prediction, but the update must consider every hypothesis in V_t.
Do this insteadKeep the full current set visible, then filter every member according to whether its prediction on x_t matches y_t.
Common mistake Choosing a hypothesis that is not in V_t
What it looks likeA trace uses hD even though hD was removed by an earlier example.
Why it failsThe Consistent algorithm chooses its hypothesis from the current version space.
Do this insteadCheck membership in V_t before accepting the selected hypothesis.
Common mistake Using the true label before making the prediction
What it looks likeThe trace first compares predictions with y_t and then reports the prediction.
Why it failsThe true label is received only after the prediction.
Do this insteadPlace the prediction before receipt of y_t, and perform the filtering step afterward.
Common mistake Filtering with the wrong comparison
What it looks likeA hypothesis is kept even though h(x_t) does not equal y_t.
Why it failsThe update keeps only hypotheses whose prediction on the current instance matches the true label.
Do this insteadFor each hypothesis in V_t, compare h(x_t) directly with y_t.
One Hypothesis or Many
| Object | Role | When it is used |
|---|---|---|
| ERM hypothesis | One hypothesis consistent with all past examples | Selected from the current version space to make the next prediction |
| Version space V_t | The set of hypotheses consistent with examples observed before round t | Used as the pool from which the prediction hypothesis is selected and as the set filtered after the true label arrives |
An ERM hypothesis is one member selected from the version space; the version space is the complete current set of consistent hypotheses.
The word any matters in the definition. If several hypotheses are consistent with all past examples, each is an ERM hypothesis under the definition used here. The Consistent algorithm may choose any hypothesis from V_t for its prediction. The update is different: it does not choose one surviving hypothesis. It retains all hypotheses whose predictions agree with the newly received true label.
Practice Trace
A generated trace begins with V₁ = {hA, hB}. The algorithm receives x₁ and selects hB. It predicts using hB(x₁). Afterward, the true label y₁ is received. The prediction of hA on x₁ matches y₁, but the prediction of hB on x₁ does not. What is the next version space, and which part of the trace should you inspect if the trace instead reports V₂ = {hB}?
Hints
- The selected hypothesis and the hypotheses retained after the update are different concepts.
- Apply the update rule to every hypothesis in V₁.
- The retained hypotheses are those whose prediction on x₁ equals y₁.
What do you think happens?
What should the next version space be in the practice trace?
Reveal answer
V₂ = {hA}. The update keeps hA because hA(x₁) matches y₁ and removes hB because hB(x₁) does not match y₁.
If the trace reports V₂ = {hB}, the first incorrect result is in the version-space update, specifically in the comparison between each hypothesis's prediction and y₁. The fact that hB was selected for the prediction does not make hB survive the update.
Key Takeaways
- 1An ERM hypothesis is any hypothesis consistent with all past examples.
- 2V_t contains the hypotheses consistent with examples observed before round t.
- 3The Consistent algorithm chooses any hypothesis from V_t and uses it to predict on x_t.
- 4The true label y_t arrives after the prediction, and the update keeps only hypotheses h satisfying h(x_t) = y_t.
- 5To debug an incorrect result, check hypothesis selection, prediction, and version-space filtering in that order.
At a glance
- An ERM hypothesis is any hypothesis consistent with all past examples.
- The version space is the complete set of hypotheses still consistent before the current round.
- The Consistent algorithm selects one hypothesis from that set, predicts, receives the true label, and then filters the set.
- Incorrect traces commonly come from using a hypothesis outside the current version space, reordering prediction and feedback, or applying the wrong update comparison.