Real AdaBoost, and a logistic comparison

Section of Ensembles, random forests, and boosting, part of Statistical learning

Type	Section
Taught in	Ensembles, random forests, and boosting
Part	Statistical learning

AdaBoost as written asks each learner for a label in \{-1,+1\}. A probability p_t(x) carries more information than that label, and throwing it away is the step that fails when the learner is already able to say how sure it is. Real AdaBoost keeps the probability and converts it to the same half-logit that minimises exponential loss,

f_t(x)=\frac12\log\frac{p_t(x)}{1-p_t(x)}.

There is no separate vote \alpha_t, because the magnitude of f_t(x) already records the confidence at that x. The weight update is the exponential-loss factor itself,

w_{t+1,i}=\frac{w_{t,i}\,e^{-y_i f_t(x_i)}}{Z_t}, \qquad Z_t=\sum_i w_{t,i}\,e^{-y_i f_t(x_i)}.

The ensemble adds the scores and then takes the sign, f(x)=\operatorname{sign}\bigl(\sum_{t=1}^T f_t(x)\bigr).

A loss-based view lets the loss change while sequential fitting stays. With the score convention p=\sigma(2f), where \sigma is the logistic function, logistic negative log-likelihood and exponential loss have the same unrestricted population minimiser. Binomial deviance is twice the negative log-likelihood relative to a saturated model. The constant factor changes neither minimiser. The derivation below uses negative log-likelihood, without that factor two. Let p(x)=\tau_1(x) and Y'=(Y+1)/2\in\{0,1\}, so Y' is the 0/1 label used in logistic regression. The log-likelihood of one case is Y'\log p+(1-Y')\log(1-p). Substitute p=1/(1+e^{-2f}), so 1-p=1/(1+e^{2f}). Minus that log-likelihood becomes

-\ell(Y,p) =Y'\log\bigl(1+e^{-2f}\bigr)+(1-Y')\log\bigl(1+e^{2f}\bigr).

If Y'=1, then Y=1 and the expression is \log(1+e^{-2Yf}). If Y'=0, then Y=-1 and it is \log(1+e^{2f})=\log(1+e^{-2Yf}). Both cases are therefore

-\ell\bigl(Y,p(x)\bigr)=\log\bigl(1+e^{-2Y f(x)}\bigr).

The population minimisers agree. Both losses are minimised by half the conditional log odds, so with enough data a procedure that truly minimises either loss estimates the same f^*. The finite-sample paths differ, because the losses grow differently as the margin becomes more negative, and the stagewise weights follow the loss that is being minimised.

AdaBoost reweights the training cases at every round. A weak round, one with \varepsilon_t near 1/2, receives a small vote \alpha_t=\frac12\log((1-\varepsilon_t)/\varepsilon_t), and the next round faces a weighted problem on which the previous learner scores exactly 1/2.

Plot the losses against the margin yf, where y\in\{-1,+1\} is the correct label and f is the score before the threshold at 0 converts it to a label. A positive margin is a correct classification. A negative margin is a mistake, and a loss used for training should charge it. Squared error (y-f)^2 equals (1-yf)^2 when y\in\{-1,+1\}, because y^2=1. As a function of a real-valued score it is a parabola in the margin, minimised at yf=1, so a more confident correct call, with yf>1, is penalised more rather than less. Exponential loss grows exponentially as the margin falls below zero, so the fit concentrates on the worst mistakes. When the Bayes error is not near zero, some of those mistakes are unavoidable under any classifier, and concentrating on them fits noise. Binomial deviance, the logistic negative log-likelihood above, grows only linearly in the negative margin, so it is the milder penalty in that regime. Hinge loss is zero once the margin exceeds 1, and linear below that. Both exponential and logistic losses extend to more than two classes. The algorithms that minimise them by adding a weak learner, usually a tree, along the gradient of the training loss are collected under the name gradient boosting. In those programs the penalty on tree size and the limit on depth are tuning choices, selected by cross-validation or by a validation set. They are not consequences of the population minimiser.

Training classification error and training exponential loss are different criteria. A one-dimensional simulation can drive the training error to zero while the exponential loss is still moving, and the final observation weights concentrate on the points the early rounds found difficult.

Real AdaBoost, and a logistic comparison

Used in

See also