skip to content

AdaBoost

3 roadmaps3 questions

Misclassified examples get heavier weights before the next stump is fitted, and each stump votes with a weight set by its own error. Interviewers ask what loss this is quietly minimising.

on this pageshow

explore

questions

3

In AdaBoost, what happens to the example weights and the learner's vote weight after each round?

level: middleimportance: must knowfreq 70%

answer

  1. the training set does not stay the same
  2. mistakes get louder, hits get quieter
  3. vote weight comes from weighted error
  4. half a log of (1-e) over e
  5. errors end up holding half the weight

basics

~20 s

AdaBoost scales misclassified examples' weights up and correct ones down, then renormalises, so the next weak learner targets current mistakes. That learner's vote weight is 0.5 * ln((1 - e) / e), where e is its weighted error.

solid answer

~40 s

AdaBoost keeps a weight distribution over the training rows, starting uniform at `1/N`. Each round it fits a weak learner (classically a one-split decision stump) to minimise weighted error `e`, then gives that learner a vote weight `alpha = 0.5 * ln((1 - e) / e)` — large when `e` is small, zero at `e = 0.5`. It then multiplies every misclassified row's weight by `exp(alpha)` and every correct row's by `exp(-alpha)` and renormalises, which always leaves the misclassified set holding exactly half the total weight. The next stump therefore sees a reweighted problem in which the current ensemble's mistakes matter most. The final prediction is `sign(sum_t alpha_t * h_t(x))`, so weak rounds with high error contribute little to the vote.

code

python · 16 lines
python
import math

y = [1, 1, 1, 1, 1, -1, -1, -1, -1, -1]   # true labels, coded -1 / +1
h = [1, 1, -1, -1, -1, -1, -1, -1, -1, -1]  # stump: wrong on rows 2, 3, 4
w = [0.1] * 10                            # round-1 weights, uniform

err = sum(w[i] for i in range(10) if h[i] != y[i]) / sum(w)
alpha = 0.5 * math.log((1 - err) / err)

w = [w[i] * math.exp(-alpha * y[i] * h[i]) for i in range(10)]
z = sum(w)
w = [round(x / z, 4) for x in w]

print(round(err, 2), round(alpha, 4))   # 0.3 0.4236
print(w)                                # wrong rows 0.1667, right rows 0.0714
print(round(sum(w[i] for i in range(10) if h[i] != y[i]), 4))   # 0.5

go deeper

for a junior

Be ready to state the loop in order: fit a stump, measure its weighted error, give it a vote, raise the weight of the rows it missed, repeat. Knowing that misclassified rows get heavier is the minimum here.

for a middle

You are expected to write the alpha formula, explain why it is zero at error 0.5 and grows as error falls, and describe the exp(alpha) / exp(-alpha) multipliers plus renormalisation without prompting.

for a senior

Show you can reason about the update numerically — what a 0.30 error implies, why the misclassified set ends up at half the mass, and what an ensemble whose alphas are all near zero is telling you about the base learner.

for a principal

Frame the update as the mechanism by which boosting spends capacity on bias, and be ready to say what it costs: a sequential, hard-to-parallelise fit whose behaviour is dictated entirely by how the weight distribution evolves.

## The setup AdaBoost (adaptive boosting) builds a binary classifier as a **weighted vote of many simple classifiers**, added one at a time. Encode labels as `y in {-1, +1}` and let each weak learner `h_t(x)` also return `-1` or `+1`. The two quantities that move between rounds are easy to mix up, so name them clearly: - **Example weights** `w_1 ... w_N` — one per training row, a distribution summing to 1. They say how much each row matters *right now*. - **Vote weight** `alpha_t` — one per round, the say that round's learner gets in the final ensemble. At the start every row is equally important: `w_i = 1/N`. ## One round, in order 1. **Fit** a weak learner `h_t` that minimises **weighted** error on the current weights. A decision stump does this by searching one feature and one threshold. 2. **Measure** its weighted error `e_t = sum of w_i over the rows it gets wrong` (the weights already sum to 1, so this is directly a fraction between 0 and 1). 3. **Score** the learner: `alpha_t = 0.5 * ln((1 - e_t) / e_t)`. 4. **Reweight**: `w_i <- w_i * exp(-alpha_t * y_i * h_t(x_i))`. Because `y_i * h_t(x_i)` is `+1` when correct and `-1` when wrong, that means multiply wrong rows by `exp(alpha_t)` and right rows by `exp(-alpha_t)`. 5. **Renormalise** by the sum `Z_t` so the weights are a distribution again. Repeat for `T` rounds and predict `H(x) = sign(sum_t alpha_t * h_t(x))`. ## Why alpha has that shape `alpha_t` is a half log-odds of being right. It is **monotonically decreasing in the error**: - `e = 0.5` gives `alpha = 0`: a coin flip earns no vote and, since `exp(0) = 1`, leaves the weights untouched. - `e = 0.3` gives `alpha = 0.5 * ln(0.7 / 0.3) = 0.424`. - `e = 0.1` gives `alpha = 1.099` — a much better stump shouts much louder. - `e > 0.5` gives a **negative** alpha, which is the ensemble voting *against* that learner; it is equivalent to flipping its output, and most descriptions simply require every weak learner to beat chance so this never arises. ## The worked example Ten rows, weights `0.1` each, and a stump that gets three of them wrong, so `e = 0.30` and `alpha = 0.4236`. The multipliers are `exp(alpha) = 1.5275` for the wrong rows and `exp(-alpha) = 0.6547` for the right ones. Before normalising, the wrong rows carry `0.30 * 1.5275 = 0.458` and the right ones `0.70 * 0.6547 = 0.458`. They are **equal, and this is not a coincidence**: the alpha formula is exactly the value that rebalances the two groups. After dividing by `Z = 0.9165` each wrong row sits at `1/6 = 0.1667` and each right row at `1/14 = 0.0714`, and the three wrong rows together hold precisely half the distribution. So a useful one-line summary of the update: **after every round, the examples the round got wrong own 50% of the weight.** That is what makes the next stump attack them. ## Why this converges The normalising constant is `Z_t = 2 * sqrt(e_t * (1 - e_t))`, which is less than 1 whenever `e_t` differs from 0.5. Writing `e_t = 0.5 - g_t`, the training error of the ensemble is bounded by the product of the `Z_t`, which shrinks like `exp(-2 * sum of g_t^2)`. In words: as long as every round is *some* fixed amount better than chance on its own weighted problem, training error falls exponentially in the number of rounds. This is the formal content of "boosting a weak learner into a strong one", and it is why boosting is framed as a **bias-reduction** procedure — each round buys accuracy the current ensemble does not have. ## Confusions worth avoiding - **Weights are not votes.** A row's weight controls how much the *next* learner cares about it; alpha controls how much a *learner* counts at prediction time. - **Nothing is refitted.** Earlier stumps and their alphas are frozen; only the weight distribution and the growing sum change. - **Correct rows change too.** Their absolute weight shrinks; even under renormalisation their share falls. - **Reweighting is not random resampling.** Where a base learner cannot accept weights, an implementation may draw a sample with probability proportional to the weights as a stand-in, but the algorithm itself is deterministic reweighting of the full training set.

  • What does AdaBoost do when a weak learner's weighted error comes out at exactly 0.5?
    Its vote weight is `0.5 * ln(1) = 0`, so it contributes nothing to the final sum, and the weight multipliers are both `exp(0) = 1`, so the distribution is unchanged. The round is wasted. If the error goes above 0.5 the alpha turns negative, which is the ensemble voting against that learner — mathematically the same as flipping its output.
  • Why renormalise the weights at the end of every round?
    It keeps them a probability distribution, so the next round's weighted error is directly a number between 0 and 1 and is comparable across rounds. The normalising constant is `Z = 2 * sqrt(e * (1 - e))`, and the product of those constants over all rounds bounds the ensemble's training error — so the normaliser is not just bookkeeping.
  • Are earlier weak learners ever revisited or refitted as boosting proceeds?
    No. Each stump and its alpha are fixed the moment they are added; the ensemble only grows. That is what makes boosting a stagewise procedure rather than a joint optimisation, and it is why the only state carried forward is the weight distribution.

It is a study group that, after each mock exam, re-drills the questions the group just got wrong and skims the ones it aced — and gives the sharpest member the loudest voice in the final answer.

saying these in an interview costs you the question

  • Says every weak learner gets an equal vote in the ensemble
  • Confuses a row's example weight with the learner's vote weight
  • Claims only misclassified rows change weight, correct ones stay put
  • Thinks AdaBoost refits or discards earlier learners each round
  • Describes boosting as fitting independent learners in parallel

context

resolving links…

open as a page

In AdaBoost, why is a one-split decision stump the standard weak learner?

level: juniorimportance: should knowfreq 50%

basics

~20 s

Boosting supplies accuracy through many rounds, so it needs a high-bias, low-variance base learner only slightly better than chance. A stump, one feature and one threshold, is the cheapest such learner and refits fast each reweighted pass.

open as a page

Why does AdaBoost's exponential loss make it fragile to mislabelled rows and outliers?

level: seniorimportance: should knowfreq 55%

basics

~20 s

Exponential loss penalises a wrong prediction exponentially in how wrong it is, so a mislabelled row that can never be fit gains weight every round. Tens of rounds later a few such rows can own most of the distribution.

open as a page