ERM Hypothesis
An ERM hypothesis is any hypothesis consistent with all past examples.
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.
Start: Before the first round, all three listed hypotheses are in V₁.
Prediction: 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.
Update: 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.
Next 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
- Start round t with the current version space V_t.
- Receive the current instance x_t.
- Choose any hypothesis from V_t.
- Use the selected hypothesis to make the prediction h(x_t).
- Receive the true label y_t after the prediction.
- Keep 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.
Treating the selected hypothesis as the entire version space
V_t is a set of hypotheses. Selecting one hypothesis determines the prediction, but the update must consider every hypothesis in V_t.
Fix:
Keep the full current set visible, then filter every member according to whether its prediction on x_t matches y_t.Choosing a hypothesis that is not in V_t
The Consistent algorithm chooses its hypothesis from the current version space.
Fix:
Check membership in V_t before accepting the selected hypothesis.Using the true label before making the prediction
The true label is received only after the prediction.
Fix:
Place the prediction before receipt of y_t, and perform the filtering step afterward.Filtering with the wrong comparison
The update keeps only hypotheses whose prediction on the current instance matches the true label.
Fix:
For 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 |
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
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
- An ERM hypothesis is any hypothesis consistent with all past examples.
- V_t contains the hypotheses consistent with examples observed before round t.
- The Consistent algorithm chooses any hypothesis from V_t and uses it to predict on x_t.
- The true label y_t arrives after the prediction, and the update keeps only hypotheses h satisfying h(x_t) = y_t.
- To debug an incorrect result, check hypothesis selection, prediction, and version-space filtering in that order.
Key Takeaways
- 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.