Weighted-Majority Algorithm
Weighted-Majority is the chapter's first important online-learning algorithm.
Decisions Before Labels
Imagine that examples arrive one at a time, exactly when a prediction is needed. The learner cannot first collect a complete training set and postpone every decision. It must predict, discover the correct label, and then use that new information when the next example arrives. This timing is the central setting of online learning.
| PAC learning | Online learning |
|---|---|
| The learner first receives a batch of training examples. | The learner predicts each example before its true label is known. |
| The learner learns a hypothesis from the batch. | The learner observes the label after predicting. |
| The learner predicts labels for new examples afterward. | The observed example can become training information for later rounds. |
The key difference is the order in which training, prediction, and feedback occur.
One Round in Order
Weighted-Majority can be read as a repeated decision process. Suppose there are d experts and a planned horizon of T rounds. At the start of a round, every expert has an unnormalized weight. The learner first turns those weights into a probability distribution by dividing each weight by the total of all weights. It then chooses an expert according to that distribution. Afterward, it observes the costs assigned to all experts, pays the distribution-weighted cost for the round, and updates every expert's weight. The next round begins with the updated weights.
From Weights to Advice
Prediction with expert advice represents the learner's choice as a distribution over experts. If expert i has current unnormalized weight w̃_i, the learner divides it by the total Z of all current unnormalized weights. The resulting values are probabilities, so their total is 1. The learner therefore relies more strongly on experts with larger current weights, without having to select one expert deterministically in every description of the method.
Normalizing Two Expert Weights
Suppose two experts enter a round with unnormalized weights 2 and 1.
- 1Add the weights
The normalization total is 3.
- 2Divide each weight by the total
The first expert receives probability 2 divided by 3, and the second receives probability 1 divided by 3.
- 3Interpret the distribution
The learner gives the first expert twice as much probability as the second expert for this round.
The distribution over experts is 2/3 for the first expert and 1/3 for the second expert.
The current distribution determines the learner's averaged cost for the round. This is different from simply reporting the cost of one fixed expert: the learner's cost is weighted by how strongly the learner relied on each expert.
Costs and Future Influence
After the costs arrive, expert i's unnormalized weight is multiplied by exp(-eta v_t,i), where v_t,i is that expert's cost on the round. Costs lie between 0 and 1. A larger cost therefore produces a smaller multiplicative factor than a smaller cost. Costly advice loses more relative weight, while less costly advice retains more of its weight. The parameter eta controls the update expression and is set using the number of experts d and the planned number of rounds T.
Different Costs, Different Updates
Two experts begin a round with weights 2 and 1. The first expert receives a larger cost than the second expert.
- 1Keep the entering weights
The first expert starts with more influence, but that does not guarantee it will keep more influence.
- 2Apply the multiplicative factors
The first expert is multiplied by exp(-eta times its larger cost). The second is multiplied by exp(-eta times its smaller cost).
- 3Compare relative retention
Because the first cost is larger, its multiplicative factor is smaller. It loses more relative weight than the second expert.
- 4Normalize next time
At the next round, both updated weights are divided by their new total to form the new distribution.
The expert with the larger cost has less relative influence in the next prediction than it would have had if both costs were equal.
Realizable and Unrealizable Settings
Online binary classification is studied under realizable and unrealizable assumptions. In the realizable case, the analysis allows a hypothesis that correctly explains every observed example. In the unrealizable case, every available hypothesis eventually makes mistakes on the sequence. This distinction changes what the learner is being compared against: perfect explanation is available in the realizable setting, while the learner must reason about unavoidable mistakes in the unrealizable setting.
The Chapter Progression
Weighted-Majority is the chapter's first important online-learning algorithm. The progression then moves to online-learning problems with convex loss functions and finally to the Perceptron algorithm. The Perceptron is presented as an example of using surrogate convex loss functions in the online-learning model.
| Topic | Role in the progression |
|---|---|
| Weighted-Majority | Introduces an online algorithm that adjusts reliance on experts. |
| Convex loss functions | Extends the study to online-learning problems whose loss function is convex. |
| Perceptron | Shows the use of surrogate convex loss functions in the online-learning model. |
These topics form a progression within the study of online learning.
Unknown Time Horizons
The update parameter eta is chosen using the number of experts d and the planned number of rounds T. That creates a problem when the total number of rounds is not known in advance. The doubling trick removes this dependence by organizing the run into progressively extended time periods and restarting the algorithm for those periods. The learner therefore does not need one final round count before the run begins.
Implementation Checkpoints
Common mistake Using the cost vector before making the current prediction.
What it looks likeAn implementation updates weights as soon as a cost is available and then uses those updated weights for the same round's prediction.
Why it failsThe intended order is normalization, prediction, cost observation, and then weight update.
Do this insteadUse the costs to affect the next round, not the prediction that occurred before those costs were observed.
Common mistake Treating the learner's cost as the cost of one selected expert.
What it looks likeThe implementation reports only the cost assigned to the expert with the largest weight.
Why it failsThe learner pays the distribution-weighted cost, which is an average determined by the current distribution.
Do this insteadCombine each expert's cost with the probability assigned to that expert.
Common mistake Normalizing at the wrong point.
What it looks likeThe implementation normalizes once and never forms a new distribution after the cost update.
Why it failsUpdated unnormalized weights must be used to form the next choice distribution.
Do this insteadAfter updating, use the new total when normalization is needed for the next prediction.
Common mistake Inspecting only the final distribution while debugging.
What it looks likeA final value differs from expectation, but the entering weights and the update factors were never checked.
Why it failsA mismatch in an earlier checkpoint propagates to every later value.
Do this insteadCompare entering weights, normalization, cost-weighted loss, and post-cost update in that order.
Debug one round as four checkpoints: the weights entering the round, the normalization total, the cost-weighted loss, and the post-cost update. The first checkpoint that differs from the intended algorithm identifies where later values began to diverge.
Practice the Trace
Two experts enter a round with unnormalized weights 4 and 2. First, describe the probability distribution used for the prediction. Then suppose the first expert receives a larger cost than the second. Without calculating a numerical exponential, explain which expert loses more relative weight and what changes in the next round.
Hints
- Add the entering weights to find the normalization total.
- Divide each weight by that total.
- Compare exp(-eta times the larger cost) with exp(-eta times the smaller cost).
What do you think happens?
After the costs are observed, should the learner update the weights before or after calculating the current round's prediction?
Reveal answer
After the prediction
The learner first normalizes the entering weights and makes the prediction. It then observes costs, pays the distribution-weighted cost, and updates weights for the next round.
Key Takeaways
- 1Online learning predicts before observing the true label, while PAC learning separates batch training from later prediction.
- 2Weighted-Majority normalizes current expert weights into a distribution before predicting.
- 3The learner's cost is distribution-weighted rather than automatically equal to the cost of one expert.
- 4A larger expert cost produces a smaller exponential multiplicative factor and reduces that expert's future relative influence.
- 5The doubling trick uses progressively extended periods when the total number of rounds is unknown.
At a glance
- Online learning requires a prediction before the current label is known; the revealed label can inform later rounds.
- Weighted-Majority represents reliance on experts with a normalized distribution over their current weights.
- Each expert's cost changes its unnormalized weight through an exponential multiplicative update.
- Correct tracing follows normalization, prediction, cost observation, and update in that order.
- The doubling trick handles an unknown total number of rounds by using progressively extended time periods.