Real AdaBoost With Confidence-Rated Weak Rules

From Binary Votes to Confidence-Rated Scores

Discrete AdaBoost assigns each example a weak-rule vote in \(\{-1,+1\}\), then chooses one scalar coefficient for that rule. Real AdaBoost instead allows the rule to report a confidence that varies across regions of the predictor space. A region with a strong weighted majority can receive a larger score than one with a narrow majority; regions favoring opposite classes receive scores with opposite signs.

Let the training data be \((x_i,y_i)\), \(i=1,\ldots,n\), with labels \(y_i\in\{-1,+1\}\). At round \(t\), let \(D_t(i)\geq 0\) be the current example weights, normalized so that \(\sum_{i=1}^nD_t(i)=1\). A real-valued weak rule supplies a score \(g_t(x)\). The ensemble score after \(T\) rounds is \(F_T(x)=\sum_{t=1}^T g_t(x)\), and its binary prediction is based on the sign of \(F_T(x)\).

The score formula is the inverse hyperbolic tangent of \(r(x)\). Equivalently, if a region has positive and negative weighted class masses \(W_+\) and \(W_-\), its confidence is \(r=(W_+-W_-)/(W_++W_-)\), provided \(W_++W_->0\). Substitution gives \(g=\frac12\log(W_+/W_-)\) when both masses are positive. The score is therefore a log-odds quantity, not the raw confidence \(r\).

Deriving the Real-Valued Update

Suppose a candidate weak rule divides the inputs into regions and assigns one constant score \(g_j\) on each region \(A_j\). Define the current weighted class masses in a region by

The weighted exponential loss contributed by \(A_j\) is \(W_{j,+}e^{-g_j}+W_{j,-}e^{g_j}\). The first term is the contribution of positive examples, whose loss decreases as the score increases; the second is the contribution of negative examples, whose loss decreases as the score decreases.

To prove the result, write \(L_j(g)=W_{j,+}e^{-g}+W_{j,-}e^g\). Its first and second derivatives are

Strict positivity of the second derivative makes any stationary point the unique global minimizer. Solving \(L_j'(g)=0\) gives \(e^{2g}=W_{j,+}/W_{j,-}\), hence \(g_j^*=\frac12\log(W_{j,+}/W_{j,-})\). At this score, \(W_{j,+}e^{-g_j^*}=\sqrt{W_{j,+}W_{j,-}}\) and \(W_{j,-}e^{g_j^*}=\sqrt{W_{j,+}W_{j,-}}\). Adding the two terms gives the stated minimum. \(\square\)

Applying this calculation separately in each region yields a score function \(g_t\). The normalized example-weight update and its normalizing factor are

Thus examples that the score handles poorly receive more weight relative to those it handles well. Since \(Z_t\) is the weighted exponential loss of the chosen rule, a smaller value means a larger reduction in that round’s normalized exponential loss.

How a Round Compares With Discrete AdaBoost

In discrete AdaBoost, a weak rule \(h(x)\in\{-1,+1\}\) receives a single coefficient \(\alpha\), so its score is \(g(x)=\alpha h(x)\). If its weighted error is \(\varepsilon=\sum_iD_t(i)\mathbf{1}\{y_i\ne h(x_i)\}\), and \(0<\varepsilon<1\), the round’s loss as a function of \(\alpha\) is

Differentiating and setting the derivative to zero gives \(\alpha=\frac12\log((1-\varepsilon)/\varepsilon)\), and substitution gives \(Z=2\sqrt{\varepsilon(1-\varepsilon)}\). For Real AdaBoost, each region gets its own score based on its two weighted class masses. A constant binary vote is a special case of a real score, but real scores need not have the same magnitude in every region.

The round factors also connect the sequence of real-valued updates to training error. Start with \(D_1(i)=1/n\), and define \(F_T(x)=\sum_{t=1}^Tg_t(x)\). Repeatedly applying the update gives

This identity follows by induction: it holds at \(T=0\) with an empty product equal to \(1\); multiplying the expression at round \(T-1\) by \(e^{-y_i g_T(x_i)}/Z_T\) gives the expression at round \(T\). Since the weights sum to one, rearrangement yields \(\frac1n\sum_i e^{-y_iF_T(x_i)}=\prod_{t=1}^TZ_t\).

Zero-Mass Regions and Practical Interpretation

The finite-score formula requires both class masses in a region to be positive. If exactly one mass is zero and the other is positive, there is no finite minimizing score: the loss decreases toward zero as the score tends without bound in the direction of the class with positive mass. If both masses are zero, the region contributes zero loss for every finite score. These are distinct cases; an empty region does not have a score forced by the loss.

Common Mistake

A common mistake is to treat Real AdaBoost’s confidence \(r\), score \(g\), and class probability as interchangeable. They are not. The confidence \(r\) lies between \(-1\) and \(1\), while the associated score is a log-odds transformation that can be any real number; neither quantity should automatically be reported as a probability. Another error is to apply \(\frac12\log(W_+/W_-)\) when a mass is zero. The derivation requires two positive masses, and the correct boundary behavior depends on whether one mass or both masses vanish.

The central contrast is that discrete AdaBoost uses one vote magnitude for a weak rule, whereas Real AdaBoost can fit different signed magnitudes across regions. Both updates reweight examples through the exponential loss, but the real-valued rule uses local weighted class balance to decide how strongly each region contributes to the ensemble score.