Consistent Algorithms
The Halving algorithm predicts by majority vote among the hypotheses that remain viable.
Prediction as a Vote
The Halving algorithm treats prediction as a competition among hypotheses. At any round, several hypotheses remain viable. Each hypothesis predicts a label for the new example, and the algorithm selects the label supported by more of the surviving hypotheses. After the true label arrives, every hypothesis that disagrees with that label is removed.
The algorithm does not first choose one permanently trusted hypothesis. It uses the current collection of viable hypotheses and lets their votes determine the next prediction.
A Round of Halving
Eight hypotheses vote on one example
Suppose the current hypothesis class contains eight surviving hypotheses. Five predict label 0 for the incoming example, and three predict label 1.
Count the votes: Label 0 has five votes, while label 1 has three votes.
Make the prediction: The Halving algorithm predicts label 0 because it has the larger vote.
Observe the true label: If the true label is 1, the prediction was a mistake. If the true label is 0, the prediction was correct.
Filter the hypotheses: Only hypotheses predicting the true label remain. With true label 1, the three hypotheses predicting 1 survive and the five predicting 0 are removed.
The surviving class has three hypotheses when the true label is 1. The prediction is made before the true label is used for filtering.
What do you think happens?
In the worked example, what happens to the five hypotheses that voted for label 0 when the true label is 1?
Reveal answer
Answer: They are removed because they disagree with the true label.
The update uses the true label, not the algorithm's own prediction. Every hypothesis satisfying h(x_t) = y_t remains, and every hypothesis disagreeing with the observed label is removed.
Version-Space Filtering
The version space at round t, written V_t, is the set of hypotheses consistent with the examples observed before round t. Once the new instance x_t arrives, the algorithm predicts before seeing its true label y_t. After y_t is revealed, the update keeps exactly those hypotheses in V_t whose prediction on x_t matches y_t.
Why Mistakes Halve the Class
Suppose the Halving algorithm predicts label 0 because at least as many current hypotheses predict 0 as predict 1. If the true label is 1, the majority side was wrong. Every hypothesis on that incorrect side is removed during the update. Because that side contained at least half of the current hypotheses, a mistake removes at least half of the current hypothesis class.
M_Halving(H) ≤ log2(|H|)The bound follows from repeated halving. Each mistake removes at least half of the hypotheses that remain. For a finite hypothesis class H, the total number of mistakes is therefore bounded by log2(|H|). The bound concerns mistakes made by the Halving algorithm over the finite class.
Applying the mistake bound
A finite hypothesis class contains 16 hypotheses. Use the Halving mistake bound.
Identify the class size: Here, |H| is 16.
Apply the bound: The bound is M_Halving(H) ≤ log2(|H|), so the relevant quantity is log2(16).
Evaluate the logarithm: Because repeated halving takes 4 halvings to go from 16 to 1, log2(16) is 4.
The Halving algorithm makes at most 4 mistakes under this bound.
ERM and Consistent Selection
An ERM hypothesis is any hypothesis consistent with all past examples. In online learning, the Consistent algorithm uses this idea round by round: it chooses any hypothesis from the current version space V_t, then uses that hypothesis to make the next prediction.
The order matters. First, the instance arrives. Next, the Consistent algorithm selects a hypothesis from V_t and predicts using h(x_t). Only after that prediction does it receive y_t. The update keeps the hypotheses in V_t whose predictions on x_t match y_t.
Tracing Incorrect Results
When a recorded result is incorrect, trace the round in order rather than looking only at the final prediction. Check that the instance arrived before the prediction, that the selected hypothesis came from V_t, that the prediction used h(x_t), and that the update compared each hypothesis with the true label y_t.
Filtering with the algorithm's prediction instead of the true label
The update must use the observed true label y_t, not the algorithm's own prediction.
Fix:
Keep only hypotheses satisfying h(x_t) = y_t.Selecting a hypothesis outside the current version space
The Consistent algorithm chooses its hypothesis from V_t, which contains hypotheses consistent with all examples observed before round t.
Fix:
Restrict the selection to the current version space.Using the true label before making the prediction
The prediction is made before the true label is received.
Fix:
Process x_t, select a hypothesis, predict, and only then use y_t for updating.Tracking only the prediction and not the hypothesis set
The key state change is the membership of the hypothesis class. Future votes depend on the updated version space.
Fix:
After every observed label, explicitly identify which hypotheses remain.
Practice Trace
A current version space contains six hypotheses. On the next instance, four hypotheses predict 1 and two predict 0. The Halving algorithm predicts 1, but the true label is 0. State the prediction, identify which hypotheses are removed, and state how many hypotheses remain.
Hints
- Start by identifying the majority vote.
- The observed true label, not the prediction, determines which hypotheses survive.
- Remove every hypothesis that predicts differently from the true label.
Practice trace result
A current version space contains six hypotheses: four predict 1 and two predict 0. The true label is 0.
Prediction: The algorithm predicts 1 because four of the six hypotheses vote for 1.
Mistake: The true label is 0, so the majority prediction was incorrect.
Update: The four hypotheses predicting 1 are removed. The two hypotheses predicting 0 remain.
Two hypotheses remain, so the mistake removed at least half of the current class.
Key Takeaways
- Halving predicts the label receiving the majority vote among the currently viable hypotheses.
- After the true label arrives, hypotheses that disagree with it are removed from the version space.
- When Halving makes a mistake, the incorrect majority side contains at least half of the current hypotheses, so at least half are eliminated.
- For a finite hypothesis class H, the mistake bound is M_Halving(H) ≤ log2(|H|).
- The Consistent algorithm chooses any ERM hypothesis from V_t and updates the version space using the true label.
Key Takeaways
- The Halving algorithm makes predictions by majority vote among surviving hypotheses.
- The true observed label determines which hypotheses remain consistent.
- Each Halving mistake removes at least half of the current hypothesis class.
- The finite-class mistake bound is M_Halving(H) ≤ log2(|H|).
- The Consistent algorithm selects an ERM hypothesis from the current version space and updates that space after receiving the true label.