Online Learning Fundamentals
In online learning, the ERM idea is applied repeatedly.
Learning One Example at a Time
Online learning makes a prediction round by round. At round t, the algorithm receives an instance x_t, chooses a hypothesis that fits the examples it has already seen, and uses that hypothesis to predict. The true label y_t arrives only after the prediction. The algorithm then uses that label to decide which hypotheses remain possible for later rounds.
The order of events is essential: receive x_t, select from the current version space, predict, receive y_t, and then update the version space.
The Version Space Across Rounds
The version space V_t is the set of hypotheses consistent with the examples observed before round t. It represents the hypotheses that have not yet been ruled out by the available labeled examples. After the true label for the current example is received, the algorithm keeps only the hypotheses whose prediction on x_t matches y_t. The surviving set becomes the version space used for a later round.
The diagram uses a generated abstract example. It starts with three possible hypotheses. The first labeled example removes h₂, leaving h₁ and h₃. The second labeled example removes h₁, leaving only h₃. The important idea is not the particular hypothesis names; it is that each new label can shrink the set of hypotheses that remain consistent.
ERM as Historical Consistency
An ERM hypothesis is any hypothesis consistent with all past examples.
In online learning, the ERM idea is applied repeatedly. At a particular round, a hypothesis is acceptable as an ERM hypothesis if it agrees with every labeled example received before that round. The algorithm does not need to select one hypothesis that agrees with future labels, because those labels have not arrived yet.
The Consistent Algorithm Loop
The Consistent algorithm chooses any hypothesis from V_t to make the prediction at round t. Once x_t arrives, the chosen hypothesis produces h(x_t). The true label y_t is then received. The update keeps only the hypotheses in V_t whose predictions on x_t equal y_t. In symbolic form, the retained hypotheses are those satisfying h(x_t) = y_t.
- 1Receive the current instance x_t.
- 2Choose any hypothesis h_t from the current version space V_t.
- 3Predict using h_t(x_t).
- 4Receive the true label y_t.
- 5Keep the hypotheses in V_t that satisfy h(x_t) = y_t.
A Two-Round Trace
Filtering Abstract Hypotheses
Suppose the initial version space is V₁ = {h₁, h₂, h₃}. At round 1, the received instance is x₁, and the true label is y₁. Assume h₁(x₁) = y₁, h₂(x₁) differs from y₁, and h₃(x₁) = y₁. At round 2, the received instance is x₂, and h₁(x₂) differs from y₂ while h₃(x₂) = y₂.
- 1Round 1 selection
The algorithm may choose any one hypothesis from V₁. For this generated trace, choose h₂. The choice is allowed because h₂ is in the current version space before the prediction.
- 2Round 1 prediction
The prediction is h₂(x₁). The true label is not used until after this prediction.
- 3Round 1 update
Compare every hypothesis in V₁ with y₁. Hypotheses h₁ and h₃ match y₁, while h₂ does not. Therefore the next version space is V₂ = {h₁, h₃}.
- 4Round 2 selection
The algorithm must choose from V₂, not from the original V₁. For this generated trace, choose h₁.
- 5Round 2 update
The round-2 label removes h₁ because h₁(x₂) differs from y₂. Hypothesis h₃ remains because h₃(x₂) = y₂.
The version spaces are V₁ = {h₁, h₂, h₃}, V₂ = {h₁, h₃}, and V₃ = {h₃}. The example illustrates that selection uses the current version space, while updating filters that same space using the newly received label.
The version space is a set. The selected hypothesis is one member of that set. The prediction uses the selected hypothesis, while the later update checks every hypothesis in the current version space.
Finding the First Incorrect Step
When a recorded result is incorrect, locate the first point where it stops following the Consistent algorithm. Check whether the instance arrived before the prediction, whether the selected hypothesis came from V_t, whether the prediction used h(x_t), whether the true label was handled after the prediction, and whether the update compared each hypothesis with y_t.
Common mistake Selecting a hypothesis that is not in the current version space
What it looks likeChoosing from the original hypothesis set after earlier labels have already removed some hypotheses.
Why it failsThe Consistent algorithm chooses from V_t, which contains only hypotheses consistent with examples observed before round t.
Do this insteadWrite down the current V_t before making the selection, then choose from that set.
Common mistake Using the true label to make the prediction
What it looks likeComputing a prediction after looking at y_t.
Why it failsThe true label is received only after the prediction.
Do this insteadSeparate the prediction step from the label-receipt step.
Common mistake Updating only the selected hypothesis
What it looks likeKeeping or removing h_t without checking the other members of V_t.
Why it failsThe update keeps all hypotheses in V_t satisfying h(x_t) = y_t.
Do this insteadCompare every hypothesis in V_t with the received true label.
Common mistake Comparing predictions with the wrong label or wrong instance
What it looks likeFiltering with an earlier label or with a prediction on a different instance.
Why it failsThe update must compare each hypothesis's prediction on the current x_t with the current y_t.
Do this insteadLabel the current pair explicitly as x_t and y_t before filtering.
For each round, record five items in order: the current instance, the version space before prediction, the selected hypothesis, the prediction and received label, and the filtered version space. This makes the first incorrect step visible instead of hiding several operations in one line.
Practice the Round Order
A current version space is V_t = {h₁, h₂}. The current instance x_t arrives. The algorithm selects h₂ and predicts h₂(x_t). Afterward, the true label y_t arrives. Hypothesis h₁ agrees with y_t on x_t, while h₂ does not. What is the updated version space, and at which step would an error occur if the algorithm kept h₂ because it was the selected hypothesis?
Hints
- The update checks every hypothesis in V_t, not only the selected one.
- Keep a hypothesis only when its prediction on x_t equals y_t.
Practice Result
Using the stated predictions, determine the updated version space.
- 1Check h₁
h₁ agrees with y_t on x_t, so h₁ remains.
- 2Check h₂
h₂ does not agree with y_t on x_t, so h₂ is removed.
- 3Locate the error
Keeping h₂ because it was selected confuses prediction selection with version-space updating. The update must test every hypothesis against the true label.
The updated version space is {h₁}. The incorrect result arises during version-space updating, not merely because h₂ was selected for the prediction.
The Round-by-Round Checklist
- 1An ERM hypothesis is consistent with all examples observed so far.
- 2V_t contains the hypotheses consistent with examples observed before round t.
- 3The Consistent algorithm chooses any hypothesis from V_t and predicts with h_t(x_t).
- 4The true label y_t arrives after the prediction.
- 5The update keeps every hypothesis satisfying h(x_t) = y_t.
- 6To debug an incorrect result, find the first violation of the required round order or consistency test.
Key Takeaways
- An ERM hypothesis is any hypothesis consistent with all past labeled examples.
- The version space V_t is the set of hypotheses still consistent before round t.
- The Consistent algorithm selects one hypothesis from V_t, predicts on x_t, receives y_t, and filters V_t.
- The update retains hypotheses whose prediction on x_t matches y_t.
- Incorrect results can be traced by checking instance arrival, hypothesis selection, prediction, label handling, and updating in order.