Weak Learners, Edges, And Signed Margins

From Classification Errors to Signed Quantities

In binary classification, a rule either agrees or disagrees with the observed label. Counting disagreements is useful, but it hides a distinction: two rules can have the same error rate while making errors on examples with very different importance. A signed quantity records agreement directly and can be averaged under whichever distribution matters for the analysis.

This tutorial develops two related quantities. The edge summarizes a rule’s average signed agreement with the label under a specified distribution. The signed margin records agreement for an individual observation, either for one rule or for a weighted ensemble. The distribution must always be stated: an edge under the population distribution is not generally the same as an edge under AdaBoost’s current weights on the training sample.

Definition: Let $(X,Y)$ have distribution $D$, where $X$ takes values in a measurable instance space $\mathcal X$ and $Y\in\{-1,+1\}$. A binary rule is a measurable function $h:\mathcal X\to\{-1,+1\}$. Its signed agreement on an observation is $Yh(X)$, and its edge under $D$ is $$ \operatorname{edge}_D(h)=E_D[Yh(X)]. $$ The rule’s error probability is $R_D(h)=P_D(h(X)\ne Y)$.

The sign convention is deliberate. If a rule is correct, $Yh(X)=+1$; if it is incorrect, $Yh(X)=-1$. Thus the edge averages correct and incorrect predictions with opposite signs. Since $Yh(X)$ always lies in $\{-1,+1\}$, every edge lies between $-1$ and $+1$. A positive edge means the rule is correct more often than not under the specified distribution; zero edge means its error probability is one half.

Theorem: For every binary rule $h$ and distribution $D$, $$ \operatorname{edge}_D(h)=1-2R_D(h). $$ In particular, $\operatorname{edge}_D(h)>0$ if and only if $R_D(h)<1/2$.

Proof. Let $C$ be the event $\{h(X)=Y\}$. On $C$, $Yh(X)=1$; on its complement, $Yh(X)=-1$. Therefore $$ E_D[Yh(X)]=P_D(C)-P_D(C^c). $$ Because $P_D(C)=1-R_D(h)$ and $P_D(C^c)=R_D(h)$, substitution gives $$ E_D[Yh(X)]=(1-R_D(h))-R_D(h)=1-2R_D(h). $$ The stated sign equivalence follows directly. $\square$

Worked Example: Population Edge From a Discrete Distribution

Suppose $X$ takes values $a,b,c$ with probabilities $0.5,0.3,0.2$, respectively. The labels are $Y=+1$ at all three points. A rule predicts $+1$ at $a$ and $b$, and $-1$ at $c$. Calculate its error probability and edge.

The rule is correct at $a$ and $b$, whose total probability is $0.5+0.3=0.8$. It is incorrect at $c$, with probability $0.2$. Thus $R_D(h)=0.2$. The edge, calculated directly from signed agreement, is $$ \operatorname{edge}_D(h)=(0.5)(+1)+(0.3)(+1)+(0.2)(-1)=0.6. $$ The identity gives the same value: $1-2(0.2)=0.6$. The rule’s edge is positive because its population error is below one half.

Edges Under AdaBoost’s Weighted Distribution

AdaBoost evaluates a weak rule using weights on the training examples. To define this precisely, fix a labeled sample $(x_1,y_1),\ldots,(x_n,y_n)$, with $y_i\in\{-1,+1\}$. At round $t$, let $D_t(i)\ge 0$ be the weight assigned to example $i$, with $\sum_{i=1}^n D_t(i)=1$. These weights define a probability distribution on the index set $\{1,\ldots,n\}$. The weighted error and edge of a rule $h$ are $$ \varepsilon_t(h)=\sum_{i=1}^n D_t(i)\mathbf{1}\{h(x_i)\ne y_i\}, \qquad \operatorname{edge}_{D_t}(h)=\sum_{i=1}^n D_t(i)y_i h(x_i). $$

The same agreement argument applies because the weights are probabilities. Consequently, $\operatorname{edge}_{D_t}(h)=1-2\varepsilon_t(h)$. Here the distribution is on the fixed sample, not on new draws from the population. A rule can therefore have positive edge under $D_t$ and nonpositive edge under the population distribution, or the reverse. The weights also matter: a training example with larger $D_t(i)$ contributes more to both the weighted error and the edge.

Worked Example: A Positive Edge Only Under the Round Weights

Consider four training examples with weights $D_t=(0.05,0.15,0.30,0.50)$. A rule misclassifies examples 2 and 3 and correctly classifies examples 1 and 4. Compute its weighted error and edge, and compare them with the unweighted sample error.

The weights sum to $0.05+0.15+0.30+0.50=1$. The weighted error is the total weight on the two mistakes: $$ \varepsilon_t(h)=0.15+0.30=0.45. $$ The weighted edge is $$ \operatorname{edge}_{D_t}(h) =(0.05)(+1)+(0.15)(-1)+(0.30)(-1)+(0.50)(+1) =0.05-0.15-0.30+0.50=0.10. $$ Equivalently, $1-2(0.45)=0.10$. The unweighted sample error is $2/4=0.50$, so the unweighted edge is $1-2(0.50)=0$. This rule has a positive edge under the round weights even though its unweighted training edge is zero. That difference comes from the weights: the correctly classified fourth example alone has weight $0.50$.

A weak-rule condition makes the quantifiers explicit. For a class $\mathcal H$ of binary rules, a distribution $Q$ on examples, and a number $\gamma>0$, the class has edge at least $\gamma$ under $Q$ if some $h\in\mathcal H$ satisfies $\operatorname{edge}_Q(h)\ge\gamma$. A uniform weak-learning condition requires this for every distribution $Q$ under consideration, with the same positive $\gamma$. In AdaBoost’s sample-based setting, the distributions of interest are the round-dependent weights $D_t$. Merely finding a rule with positive edge for one particular $D_t$ is not the same as satisfying a condition uniformly over all such distributions.

Signed Margins for Rules and Ensembles

The signed agreement $yh(x)$ is the individual margin of a single binary rule: it is $+1$ for a correct prediction and $-1$ for an incorrect one. For an ensemble, the score can take more than two values, so the margin also records how strongly the weighted votes favor the observed label.

Definition: Let $h_1,\ldots,h_M$ be binary rules and let $\alpha_1,\ldots,\alpha_M\ge 0$, with $A=\sum_{r=1}^M\alpha_r>0$. The ensemble score is $F(x)=\sum_{r=1}^M\alpha_r h_r(x)$. Its normalized signed margin at $(x,y)$ is $$ m_F(x,y)=\frac{yF(x)}{A} =\frac{y\sum_{r=1}^M\alpha_r h_r(x)}{\sum_{r=1}^M\alpha_r}. $$ The score-based classifier predicts $+1$ when $F(x)\ge 0$ and $-1$ when $F(x)<0$.

Because each $yh_r(x)$ is either $-1$ or $+1$, and the normalized coefficients $\alpha_r/A$ are nonnegative and sum to one, the margin lies in $[-1,1]$. A positive margin means the ensemble score has the sign of the label; a negative margin means its sign is opposite. A zero margin is a tie. Under the stated tie convention, a zero-margin observation with label $-1$ is misclassified, while one with label $+1$ is classified correctly. Thus a nonpositive margin marks a boundary or an error, but is not exactly the error event when ties occur.

Theorem: For any distribution $Q$ on labeled examples and any nonnegative ensemble weights with $A>0$, the ensemble’s average normalized margin is the coefficient-weighted average of the component edges under that same distribution: $$ E_Q[m_F(X,Y)] =\sum_{r=1}^M\frac{\alpha_r}{A}\operatorname{edge}_Q(h_r). $$

Proof. By the definition of $m_F$, the finite sum defining $F$, and linearity of expectation, $$ E_Q[m_F(X,Y)] =E_Q\left[\frac{Y\sum_{r=1}^M\alpha_r h_r(X)}{A}\right] =\frac{1}{A}\sum_{r=1}^M\alpha_r E_Q[Yh_r(X)]. $$ For each $r$, the expectation $E_Q[Yh_r(X)]$ is $\operatorname{edge}_Q(h_r)$. Replacing these expectations and using $A=\sum_{r=1}^M\alpha_r$ gives the result. $\square$

Worked Example: Computing Ensemble Margins and Edges

There are three equally likely examples with labels $(+1,-1,+1)$. Rule $h_1$ predicts $(+1,+1,-1)$, and rule $h_2$ predicts $(+1,-1,+1)$. Give the rules weights $\alpha_1=2$ and $\alpha_2=1$. Compute the normalized margins and verify the average-margin identity.

The total weight is $A=2+1=3$. At the first example, $F(x_1)=2(+1)+1(+1)=3$, so $m_F(x_1,y_1)=(+1)(3)/3=1$. At the second, $F(x_2)=2(+1)+1(-1)=1$; since $y_2=-1$, its margin is $(-1)(1)/3=-1/3$. At the third, $F(x_3)=2(-1)+1(+1)=-1$, so its margin is $(+1)(-1)/3=-1/3$. The margins are therefore $1,-1/3,-1/3$. The score-based classifier is correct on the first example and incorrect on the other two.

Under the uniform distribution, $h_1$ has signed agreements $+1,-1,-1$, hence edge $(1-1-1)/3=-1/3$. Rule $h_2$ is correct on all three examples, so its edge is $1$. The coefficient-weighted edge is $$ \frac{2}{3}\left(-\frac{1}{3}\right)+\frac{1}{3}(1) =-\frac{2}{9}+\frac{3}{9}=\frac{1}{9}. $$ The average margin is $\bigl(1-1/3-1/3\bigr)/3=1/9$, as the theorem states.

Why the Distribution Must Stay Visible

An edge is not an intrinsic property of a rule alone. It is a property of a rule and a distribution. The population edge $E_D[Yh(X)]$ averages over the data-generating distribution. The round-$t$ edge $\sum_iD_t(i)y_i h(x_i)$ averages over a probability distribution on the observed training examples. These quantities answer different questions, even if the same notation for signed agreement appears in both.

Similarly, the average-margin identity uses one fixed distribution $Q$ for every component rule. It cannot be applied by taking the $r$th edge under a different distribution $D_r$ and calling the result the ensemble’s average margin under a single distribution. If the averaging distributions differ, the expectation calculation in the proof no longer factors into the stated sum.

Common Mistake

A common error is to say, “The rule has edge $0.2$,” without stating whether this is a population edge, a uniform empirical edge, or an AdaBoost round-specific weighted edge. Another is to interpret positive edge under $D_t$ as evidence that the rule has positive population edge. Neither conclusion follows: the first leaves the quantity ambiguous, and the second confuses a distribution on training indices with the distribution of future observations.

The correction is to name the distribution every time an edge is reported and to show how it is formed. For AdaBoost, give the weights $D_t(i)$ and calculate the weighted error or signed-agreement sum. For a population statement, specify $D$ and interpret the expectation under that distribution. A positive training edge is a statement about weighted training performance; population performance requires its own analysis.

Key takeaway: Signed agreement is $Yh(X)$; edge is its expectation under a named distribution. A round-dependent AdaBoost edge uses weights on training examples. An ensemble’s normalized signed margin measures example-specific agreement, and its average equals the coefficient-weighted component edges only when those edges are evaluated under the same distribution.

Check Your Understanding

Use the definitions and keep the distribution explicit in each answer.

A binary rule has error probability $0.35$ under $D$. What is its edge under $D$, and what does the sign mean?
Why can a rule have positive edge under $D_t$ but zero edge under the unweighted empirical distribution on the same sample?
For an ensemble with nonnegative coefficients summing to $A>0$, what does a negative normalized margin say about its score and the observed label?
Why must all component edges in the average-margin identity be evaluated under the same distribution?
Under the tie convention in this tutorial, can a zero-margin example be correctly classified? Give the label for which this happens.