Theorem 21.11

Theorem 21.11 supplies the bridge between a finite hypothesis class and an analysis of competing experts.

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.

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.

What advice does each expert give, what cost does it incur, and how are those values tracked for a round?

Worked example

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.

1
Advice
Record the expert's prediction as h_2(x_t).
2
Cost
Compare that advice with y_t. The recorded cost is v_t,2 = |h_2(x_t) - y_t|.
3
Interpretation
The expert is represented not only by its prediction, but also by the cost associated with that prediction.

Result

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.

How do the experts' weighted predictions combine to determine the Weighted-Majority prediction?

Worked example

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.

1
Collect advice
The three experts provide h_1(x_t), h_2(x_t), and h_3(x_t).
2
Apply weights
The advice is paired with w_1^(t), w_2^(t), and w_3^(t), respectively.
3
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.

Result

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.

How does applying the finite-class expert setup and Theorem 21.11 provide the step needed to prove Theorem 21.10?

Before

H = {h_1, ..., h_d}

Analyze the finite hypothesis class directly.

The hypotheses are viewed as a finite collection.

After

H = {h_1, ..., h_d}

Expert h_i gives h_i(x_t)
Expert h_i has cost v_t,i
Weighted-Majority forms p_t from weighted advice

The same hypotheses are represented as competing experts whose advice and costs can be analyzed.

Common Misreadings

Common mistake
Treating the algorithm as if it selected one hypothesis and ignored the others.
What it looks like
Using only h_1(x_t) as the prediction without considering the other experts.
Why it fails
The Weighted-Majority prediction combines the advice supplied by the finite collection of experts.
Do this instead
Represent every hypothesis as an expert and form p_t from the weighted advice h_i(x_t).
Common mistake
Confusing an expert's advice with its cost.
What it looks like
```
Calling h_i(x_t) the cost of expert h_i.
```
Why it fails
The advice is h_i(x_t), whereas the cost is v_t,i = |h_i(x_t) - y_t|.
Do this instead
Record the prediction and then calculate or track its associated cost separately.
Common mistake
Describing Theorem 21.11 as the entire proof of Theorem 21.10.
What it looks like
Saying that Theorem 21.11 alone proves Theorem 21.10.
Why it fails
The source states that the proof uses both the Weighted-Majority Algorithm and Theorem 21.11.
Do this instead
Describe Theorem 21.11 as the bridge that enables the finite-class hypothesis analysis to be treated as an expert analysis.

Edge case

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.

Your attempt (not saved)

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 concepts

More concepts starting with T