Concepts / Consistent Algorithms

Consistent Algorithms

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.

  • Programming

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.

Version spacesurviving hypothesesLabel 0hypothesis votesPredictionmajority labelLabel 1hypothesis votespredict 0predict 1larger votelarger vote
How do the remaining hypotheses vote on a new example, and how does the majority vote determine the prediction?
Key point

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

Worked example

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.

  1. 1
    Count the votes

    Label 0 has five votes, while label 1 has three votes.

  2. 2
    Make the prediction

    The Halving algorithm predicts label 0 because it has the larger vote.

  3. 3
    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.

  4. 4
    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.

Result

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?

  • They remain because they formed the majority

  • They are removed because they disagree with the true label

  • They are changed to predict label 1

  • They are ignored until the next round

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.

h1predicts 0h2survives for y_t = 1h2predicts 1h1 and h3removedh3predicts 0disagreesmatchesdisagrees
Which hypotheses remain in the version space after the observed label, and which hypotheses are removed as inconsistent?

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.

Predicts 0at least halfTrue label 1prediction 0 is wrongPredicts 1less than or equal to halfRemoved hypothesespredict 0majority predictiondisagrees with true labelminority vote
When the majority prediction is wrong, how are the hypotheses split by their predicted labels, and why does the incorrect side contain at least half of them?
Formula

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.

|H|initial hypotheses|H| divided by 2after one mistake|H| divided by 4after two mistakeslog2(|H|)mistake boundone mistakeone mistakerepeated halving
How does repeatedly removing at least half of the remaining hypotheses lead to the mistake bound?
Worked example

Applying the mistake bound

A finite hypothesis class contains 16 hypotheses. Use the Halving mistake bound.

  1. 1
    Identify the class size

    Here, |H| is 16.

  2. 2
    Apply the bound

    The bound is M_Halving(H) ≤ log2(|H|), so the relevant quantity is log2(16).

  3. 3
    Evaluate the logarithm

    Because repeated halving takes 4 halvings to go from 16 to 1, log2(16) is 4.

Result

The Halving algorithm makes at most 4 mistakes under this bound.

ERM and Consistent Selection

Definition

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.

Instance x_tarrives firstV_tconsistent hypothesesERM hypothesischosen from V_tPrediction h(x_t)before y_tUpdated V_tmatches y_tuse current version spacechoose anyevaluate on x_tafter true label y_t
How does the Consistent algorithm choose an ERM hypothesis from the hypotheses that make no mistakes on the examples seen so far?

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.

  • Common mistake

    Filtering with the algorithm's prediction instead of the true label

    What it looks like

    Keeping every hypothesis that agrees with the predicted label

    Why it fails

    The update must use the observed true label y_t, not the algorithm's own prediction.

    Do this instead
    Keep only hypotheses satisfying h(x_t) = y_t.
  • Common mistake

    Selecting a hypothesis outside the current version space

    What it looks like

    Using a hypothesis that disagreed with an earlier observed example

    Why it fails

    The Consistent algorithm chooses its hypothesis from V_t, which contains hypotheses consistent with all examples observed before round t.

    Do this instead

    Restrict the selection to the current version space.

  • Common mistake

    Using the true label before making the prediction

    What it looks like

    Choosing a prediction after examining y_t

    Why it fails

    The prediction is made before the true label is received.

    Do this instead

    Process x_t, select a hypothesis, predict, and only then use y_t for updating.

  • Common mistake

    Tracking only the prediction and not the hypothesis set

    What it looks like

    Recording that the algorithm predicted 0 but not recording which hypotheses survived

    Why it fails

    The key state change is the membership of the hypothesis class. Future votes depend on the updated version space.

    Do this instead

    After every observed label, explicitly identify which hypotheses remain.

x_tinstance arrivesHypothesischosen from V_th(x_t)predictiony_ttrue label arrivesV_t updatekeep matching hypothesesbefore predictionevaluatethen receivecompare predictions
At which step can an incorrect result arise: selecting the prediction, filtering the version space, or updating the surviving hypotheses?

Practice Trace

EASY

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.
Worked example

Practice trace result

A current version space contains six hypotheses: four predict 1 and two predict 0. The true label is 0.

  1. 1
    Prediction

    The algorithm predicts 1 because four of the six hypotheses vote for 1.

  2. 2
    Mistake

    The true label is 0, so the majority prediction was incorrect.

  3. 3
    Update

    The four hypotheses predicting 1 are removed. The two hypotheses predicting 0 remain.

Result

Two hypotheses remain, so the mistake removed at least half of the current class.

Key Takeaways

  1. 1
    Halving predicts the label receiving the majority vote among the currently viable hypotheses.
  2. 2
    After the true label arrives, hypotheses that disagree with it are removed from the version space.
  3. 3
    When Halving makes a mistake, the incorrect majority side contains at least half of the current hypotheses, so at least half are eliminated.
  4. 4
    For a finite hypothesis class H, the mistake bound is M_Halving(H) ≤ log2(|H|).
  5. 5
    The Consistent algorithm chooses any ERM hypothesis from V_t and updates the version space using the true label.

At a glance

  • 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.

Related Topics

Related concepts

More concepts starting with C