A weak classifier must respond to the current weights
A classifier that gets most training examples right may repeatedly miss the same difficult cases. Simply copying its vote does not repair those mistakes. Boosting changes the distribution on the training sample, then asks for a classifier that is useful under that new distribution.
The word “weak” therefore needs a quantitative contract at every round. An initial advantage on uniformly weighted data is not enough to justify a theorem about all later reweightings. We will derive a finite-sample AdaBoost guarantee with that condition stated explicitly.
Fix the sample, the score and the tie rule
Definition 12.1.1
(Binary weighted training problem)
Fix a nonempty sample , where . A weak classifier returns either or . At round , are weights summing to one, and its weighted error is
The indicator is 1 when its bracketed condition holds and 0 otherwise. Start with and score . After weighted votes, . Predict if , and otherwise. The training margin of example is .
A positive margin means a correct prediction. A zero margin is a tie: our rule classifies a positive label correctly and a negative label incorrectly. The proof will use the safe implication that an incorrect prediction has margin at most zero, rather than assert an equivalence. The score is a weighted vote, not a calibrated class probability.
Choose a vote by minimizing its normalization factor
Suppose the current weak classifier has . For a candidate vote weight , consider
Correct predictions have ; wrong predictions have . Differentiate: . Its zero gives
All logarithms in this lesson are natural. Both terms of are positive and , so this is the unique global minimum for the chosen direction . It does not claim to find the globally best entire ensemble. Because , the vote weight is positive and the minimizing is below 1.
Normalize the new example weights by
The formula preserves positive weights summing to one. It increases the mass on mistakes and decreases the mass on correct predictions. For these minimizing votes, the same update can be written exactly as
Consequently the previously wrong examples have total new mass exactly , as do the previously correct examples. The next weak learner must find a new advantage under these changed weights.
Define the exceptional rounds instead of dividing by zero
If , all training examples are correct because all their weights are positive. The weak classifier already supplies a zero-training-error answer. To retain the previous ensemble too, choose the finite coefficient , add this vote and stop. Every new margin is .
The logarithmic formula is not evaluated at zero error. Its limiting coefficient is infinite; the corresponding infimum is not attained by a finite coefficient. Our finite stopping vote guarantees correct training signs, not zero exponential loss.
If , the positive-edge premise has failed. At exactly , the optimal coefficient is 0 and is 1, giving no progress. If the hypothesis class permits negating , error above can be replaced by ; negation is an extra class assumption, and it does not help an exactly balanced classifier. The procedure below reports a missing edge rather than promise one.
BOOST(sample, max_rounds):
require sample is nonempty and labels are -1 or +1
D[i] = 1 / m for each example i
F[i] = 0 for each example i
votes = empty list
for each round up to max_rounds:
h = WEAK_LEARN(D)
error = sum D[i] over examples with h(x[i]) != y[i]
if error == 0:
alpha = 1 + max_i abs(F[i])
append (alpha, h) to votes
return votes with status PERFECT_TRAINING_FIT
if error >= 1/2:
return votes with status NO_POSITIVE_EDGE
alpha = (1/2) * ln((1-error) / error)
Z = 2 * sqrt(error * (1-error))
append (alpha, h) to votes
for each example i:
F[i] = F[i] + alpha * h(x[i])
D[i] = D[i] * exp(-alpha * y[i] * h(x[i])) / Z
return votes with status ROUND_LIMIT
Returned votes define the score on any input through their classifiers. stores current scores on the training examples for the stopping test. We do not require the weak learner to minimize weighted error exactly; the following theorem requires a suitable error bound on what it returns.
Worked example 12.1.2
(Stopping on a perfect weak classifier)
Let the labels be and the current scores . The tie rule predicts on a zero score, so the ensemble is wrong on examples , and . Suppose the next weak classifier equals on every training example, so . The finite stopping rule gives . The new scores are , with margins : all are at least , so every training prediction is correct. A coefficient of would give scores and margin on the first example, so that mistake would survive.
Worked example 12.1.3
(A classifier at exactly one half)
Take four equally weighted examples and a classifier that errs on examples and only, so . Then , and : the weights do not change and the vote adds nothing to . Negating gives a classifier that errs on examples and , again with weighted error , so negation does not rescue an exactly balanced classifier. A weak learner that returns such a classifier has no positive edge, which is the status NO_POSITIVE_EDGE of the procedure.
Telescoping the weights exposes the training objective
Theorem 12.1.4
(Training error is bounded by a product of normalizers)
For completed rounds with ,
The middle expression is the empirical exponential loss.
Proof
(Recover every final weight from the uniform initial weights)
Repeated substitution in the update gives
Sum over and use to obtain the equality in the theorem. For a misclassified example, the stated tie rule gives , hence . For a correctly classified example its error indicator is 0, no larger than its positive exponential term. Sum these pointwise inequalities and divide by .
Proof X-ray
What the telescoping proof uses and what it does not
The proof has two independent halves. The first is an identity. Unrolling from multiplies in one factor per round, and because the exponents combine into the margin, while the normalizers pile up in the denominator. Since the final weights sum to one, the exponential average must equal exactly; no property of how the weak classifiers were chosen is needed for this equality. The second half is a pointwise inequality, and it is the only place the tie rule is used: a mistake forces margin at most zero, hence . The inequality is one-sided; it does not say that a mistake has margin exactly zero or that correct points contribute little. The edge assumption never enters this proof. It enters only afterwards, when each is shown to be below one.
Theorem 12.1.5
(A uniform positive edge gives exponential decay)
Suppose each of these adaptive rounds satisfies , for one fixed . Then
The premise is under every current distribution , not merely under the initial uniform distribution.
Proof
(Bound each factor, then multiply)
Let . Then . For , ; on this square-root domain it gives . Multiply factors and apply the previous theorem. If a perfect weak classifier occurs, the separately proved finite stopping rule already gives zero training error.
For a finite sample, a strict bound below forces zero mistakes, because the number of mistakes is an integer. It suffices to complete positive-error rounds with the promised edge. This is a conditional guarantee: an implementation cannot create that edge by assuming it, and contradictory labels at one input may prevent it.
Common mistake
(A bound equal to does not exclude a mistake)
For , a training-error bound of exactly is compatible with one mistake, because one mistake among examples is a training error of . Only the strict inequality forces the integer number of mistakes below one. When choosing , require , not merely .
Work three adaptive rounds exactly
Worked example 12.1.6
(A fixed three-classifier class on four training inputs)
Use the following predictions; the table specifies only the training inputs and makes no claim about unseen labels:
| Example | Label | |||
|---|---|---|---|---|
| 1 | +1 | +1 | +1 | −1 |
| 2 | +1 | +1 | +1 | −1 |
| 3 | −1 | −1 | +1 | −1 |
| 4 | −1 | +1 | −1 | −1 |
Break the first weighted-error tie in favor of . The successive choices each minimize error in this small class at their round:
| Round | Current weights | Chosen error | Vote weight |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
In round one, only example 4 is wrong and receives half the new mass. Round two corrects it but misclassifies example 3, whose new weight becomes . This makes , wrong only on examples 1,2, useful at the third round despite its initial error of .
After one and two rounds the ensemble each makes one mistake, though the mistaken example changes. After three rounds all margins are positive:
The normalizers are , , , so the exponential loss after round three is . Actual training error is 0, well below this bound. The product objective decreases even when the observed zero-one error stays unchanged for a round.
Common mistake
(The objective falls every round; the mistake count need not)
In the three-round example the exponential-loss bound is after one round and after two, while the training error is after both: only the identity of the mistaken example changes. The theorem bounds the final error by the product of the and says nothing about each intermediate round, so expecting the mistake count to decrease monotonically is not justified.
Counterexample mode
An initial edge does not persist for a copied classifier
Immediately after an ordinary update, the same classifier's previous mistakes have new total weight . Calling it again without changing its predictions therefore gives weighted error exactly , not the earlier smaller error.
In the three-round example, has initial error , but error under . Its 75% uniform accuracy alone cannot justify repeated positive-edge rounds. Reweighting creates a new learning problem, not a promise that the last hypothesis remains weakly successful there.
State what the bound does and does not establish
All quantities above are measured on the fixed training sample. No sampling assumption or test distribution entered the proof. A population error conclusion needs a separate generalization argument; zero training error is not that argument. Similarly, decreasing exponential loss does not assert a strict decrease of observed zero-one error at every round.
For rounds, evaluating and updating example weights costs beyond the weak learner's own cost, assuming constant-time classifier evaluations and arithmetic. Store the weights/scores and the returned classifiers/vote coefficients. Exact positive normalization is the mathematical model here; finite-precision implementations need to preserve its intended distribution rather than silently treat numerical underflow as evidence of zero weighted error.
Solved exercises
Quick check
(Reweight a quarter-error classifier: start with four equal weights and a classifier wrong only on example 4. Derive the new weights using the two-case update. What weighted error does that unchanged classifier have under the new distribution?)
Use for the mistake and for the others.
Solution · Answer
. The wrong example gets ; each correct example gets . These sum to one. Its unchanged wrong set still consists of example 4, now of mass . The original positive edge therefore cannot simply be reused.
Quick check
(Distinguish objective progress from a changed mistake set: in the three-round example, explain why round two's ensemble is wrong on example 3 and correct on example 4. What are its training error and exponential-loss bound after two rounds?)
Compare the margins of examples 3 and 4.
Solution · Answer
The second vote exceeds the first . On example 3 the first classifier is correct but the second wrong, so the margin is . On example 4 it is . Examples 1 and 2 are correct under both. Training error is still , and the exponential-loss bound is . The bound can decrease while the error count stays the same.
Quick check
(Use the integer mistake count carefully: for and a guaranteed adaptive edge of at least in every completed positive-error round, give a sufficient number of rounds for the proved bound to force no training mistakes. Why is a strict bound below useful?)
Solve for .
Solution · Answer
Need , so rounds suffice. The bound is then strictly below ; even one mistake would give training error at least . At a bound merely equal to , one mistake would not be excluded. The conclusion still depends on finding the promised edge at every round.
Quick check
(A classifier has weighted error under the current weights. Give and , and the new total weight on its mistakes.)
Use and .
Solution · Answer
and . By the two-case update each mistake receives , so the mistakes together receive , and the correct examples together receive the other .