Online Learning Fundamentals
An ERM hypothesis is any hypothesis consistent with all past examples.
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.
- Receive the current instance x_t.
- Choose any hypothesis h_t from the current version space V_t.
- Predict using h_t(x_t).
- Receive the true label y_t.
- Keep 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₂.
Round 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.
Round 1 prediction: The prediction is h₂(x₁). The true label is not used until after this prediction.
Round 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₃}.
Round 2 selection: The algorithm must choose from V₂, not from the original V₁. For this generated trace, choose h₁.
Round 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.
Selecting a hypothesis that is not in the current version space
The Consistent algorithm chooses from V_t, which contains only hypotheses consistent with examples observed before round t.
Fix:
Write down the current V_t before making the selection, then choose from that set.Using the true label to make the prediction
The true label is received only after the prediction.
Fix:
Separate the prediction step from the label-receipt step.Updating only the selected hypothesis
The update keeps all hypotheses in V_t satisfying h(x_t) = y_t.
Fix:
Compare every hypothesis in V_t with the received true label.Comparing predictions with the wrong label or wrong instance
The update must compare each hypothesis's prediction on the current x_t with the current y_t.
Fix:
Label 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.
Check h₁: h₁ agrees with y_t on x_t, so h₁ remains.
Check h₂: h₂ does not agree with y_t on x_t, so h₂ is removed.
Locate 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
- An ERM hypothesis is consistent with all examples observed so far.
- V_t contains the hypotheses consistent with examples observed before round t.
- The Consistent algorithm chooses any hypothesis from V_t and predicts with h_t(x_t).
- The true label y_t arrives after the prediction.
- The update keeps every hypothesis satisfying h(x_t) = y_t.
- To 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.