Concepts / Theorem 21.11

Theorem 21.11

For the finite-class case, each hypothesis is treated as an expert.

  • Programming

The Proof Bridge

Theorem 21.11 supplies the bridge between a finite hypothesis class and an analysis of competing experts. Suppose the hypothesis class is finite and write it as H = {h_1, ..., h_d}. The proof can then treat every hypothesis as one expert. Each expert advises on the current input, and the analysis tracks the cost of that advice.

represented asrepresented asrepresented asH{h_1, ..., h_d}Expert h_1h_1(x_t), v_t,1Expert h_2h_2(x_t), v_t,2Expert h_dh_d(x_t), v_t,d
How does each hypothesis in a finite class become an expert that provides a prediction and incurs a cost?

Expert Advice and Cost

At round t, expert h_i gives the advice h_i(x_t). Its cost is v_t,i = |h_i(x_t) - y_t|. Thus, the proof records two connected pieces of information for every expert: the prediction made on the current input and the cost of that prediction relative to y_t.

givescompared withdeterminesExpert h_iAdviceh_i(x_t)y_tobserved valueCostv_t,i = |h_i(x_t) - y_t|
What advice does each expert give, what cost does it incur, and how are those values tracked for a round?

Reading One Expert's Record

For a particular round t, suppose expert h_2 gives advice h_2(x_t), and the observed value is y_t.

Advice: Record the expert's prediction as h_2(x_t).

Cost: Compare that advice with y_t. The recorded cost is v_t,2 = |h_2(x_t) - y_t|.

Interpretation: The expert is represented not only by its prediction, but also by the cost associated with that prediction.

For each round, the expert record pairs h_2(x_t) with v_t,2.

Weighted Prediction

The Weighted-Majority prediction combines the experts' advice rather than using only one hypothesis. If expert h_i has weight w_i^(t) at round t, the combined prediction is p_t = ∑ i w_i^(t) h_i(x_t). The weights determine how the individual pieces of advice contribute to the prediction.

contributescontributescontributesh_1(x_t)weighted by w_1^(t)p_tweighted combinationh_2(x_t)weighted by w_2^(t)h_d(x_t)weighted by w_d^(t)
How do the experts' weighted predictions combine to determine the Weighted-Majority prediction?

Following the Prediction Step

Consider the finite collection H = {h_1, h_2, h_3} at round t. Each hypothesis supplies advice on x_t, and each advice has a corresponding weight.

Collect advice: The three experts provide h_1(x_t), h_2(x_t), and h_3(x_t).

Apply weights: The advice is paired with w_1^(t), w_2^(t), and w_3^(t), respectively.

Combine: The Weighted-Majority prediction is formed as p_t = ∑ i w_i^(t) h_i(x_t), with the sum taken over the experts in the finite class.

The prediction p_t is produced by combining the weighted advice of all three represented hypotheses.

Contribution to Theorem 21.10

The proof of Theorem 21.10 begins with the simpler finite-class case. Writing H as {h_1, ..., h_d} makes every hypothesis an expert. The Weighted-Majority Algorithm then combines their advice, and Theorem 21.11 supplies the expert interpretation needed to track their costs. The analysis can therefore relate the algorithm's loss to the costs of the competing experts.

represent each hypothesis as an expertgivecombineincursupports analysisrelate to algorithm lossFinite HH = {h_1, ..., h_d}Experts h_1, ..., h_dTheorem 21.11Expert adviceh_i(x_t)Weighted-Majorityp_tTheorem 21.10proof uses the finite-classanalysisExpert costsv_t,i
How does applying the finite-class expert setup and Theorem 21.11 provide the step needed to prove Theorem 21.10?

Common Misreadings

  • Treating the algorithm as if it selected one hypothesis and ignored the others.

    The Weighted-Majority prediction combines the advice supplied by the finite collection of experts.

    Fix: Represent every hypothesis as an expert and form p_t from the weighted advice h_i(x_t).

  • Confusing an expert's advice with its cost.

    The advice is h_i(x_t), whereas the cost is v_t,i = |h_i(x_t) - y_t|.

    Fix: Record the prediction and then calculate or track its associated cost separately.

  • Describing Theorem 21.11 as the entire proof of Theorem 21.10.

    The source states that the proof uses both the Weighted-Majority Algorithm and Theorem 21.11.

    Fix: Describe Theorem 21.11 as the bridge that enables the finite-class hypothesis analysis to be treated as an expert analysis.

The finite-class setup is specifically the case in which H can be written as a finite list {h_1, ..., h_d}. The expert representation described here depends on having that finite collection available for the initial part of the proof.

Check Your Understanding

EASY

Suppose H = {h_1, h_2, h_3}. Describe what must be recorded at round t for expert h_2, and explain how h_2 contributes to the Weighted-Majority prediction.

Hints
  • Start with the expert's advice on x_t.
  • Use y_t to identify the expert's cost.
  • Include the weight w_2^(t) when describing the combined prediction.

What do you think happens?

Before reading the explanation, what is the role of writing H as {h_1, ..., h_d}?

  • It identifies each hypothesis as an expert for the finite-class analysis.
  • It removes the need to track expert costs.
  • It makes the algorithm choose only h_1.
  • It replaces expert advice with the observed value y_t.
Reveal answer

Answer: It identifies each hypothesis as an expert for the finite-class analysis.

This representation lets the proof apply the Weighted-Majority perspective and relate the algorithm's loss to the costs of the competing hypotheses.

Key Takeaways

  • In the finite-class case, write H as {h_1, ..., h_d} and treat each hypothesis as an expert.
  • Expert h_i advises h_i(x_t) at round t.
  • The cost of that advice is v_t,i = |h_i(x_t) - y_t|.
  • Weighted-Majority forms p_t by combining the experts' advice with weights w_i^(t).
  • Theorem 21.11 provides the finite-class expert interpretation used with Weighted-Majority in the proof of Theorem 21.10.

Related Topics

  • Weighted-Majority Algorithm
  • Theorem 21.10