Tracking Margins Across Boosting Rounds

Why Track Margins, Not Just Errors?

A classification error rate records how many observations are classified incorrectly, but it does not describe how close the remaining observations are to the decision boundary. Boosting can substantially change those distances while leaving the number of errors unchanged. A margin histogram makes that change visible: it shows whether observations are moving away from the boundary, accumulating near it, or entering a low-margin tail.

The distinction matters on both the training sample and held-out data. A training margin distribution describes how the fitted ensemble behaves on the observations used to fit it. A held-out distribution describes its behavior on observations not used for fitting, provided those observations have genuinely been kept separate. Neither a favorable training histogram nor a favorable held-out snapshot alone explains every aspect of performance; the quantities and the sample on which they were calculated must be stated.

Margins and Round-by-Round Summaries

For binary classification, write the class label as $Y_i\in\{-1,+1\}$, and let $h_t(x)\in\{-1,+1\}$ be the prediction of the weak classifier added at round $t$. Suppose the cumulative classifier after $t$ rounds has positive coefficients $\alpha_1,\ldots,\alpha_t$, and define $A_t=\sum_{s=1}^t\alpha_s$. Its normalized signed margin on observation $i$ is

m_{i,t}=\frac{Y_i\sum_{s=1}^t\alpha_s h_s(X_i)}{A_t}.

A positive margin means the cumulative score has the correct sign; a negative margin means it has the wrong sign. A zero margin is a tie. Here, ties count as classification errors. Since each product $Y_i h_s(X_i)$ is either $-1$ or $+1$, each normalized margin lies in $[-1,1]$. If the next round has coefficient $\alpha_t>0$, then, for $t\geq2$,

m_{i,t}=\frac{A_{t-1}m_{i,t-1}+\alpha_tY_i h_t(X_i)}{A_t}.

Thus, a new margin is a weighted average of the old margin and the new signed prediction. It need not increase: the latest weak classifier can vote against an observation, and the normalization changes as the ensemble grows. A round-by-round comparison should therefore use the margins computed from the cumulative ensemble at each round, not just the prediction of the latest weak classifier.

Definition: For a sample of $n$ observations, the empirical margin distribution at round $t$ is summarized by $\widehat F_t(u)=n^{-1}\sum_{i=1}^n I(m_{i,t}\leq u)$. For a threshold $\eta>0$, the empirical low-margin tail proportion is $T_t(\eta)=n^{-1}\sum_{i=1}^n I(m_{i,t}\leq\eta)$. With the tie convention above, the empirical classification error is $E_t=n^{-1}\sum_{i=1}^n I(m_{i,t}\leq0)$.

The tail threshold $\eta$ must be specified: “the low-margin fraction” has no unique numerical value without one. The margin histogram is a graphical summary of the distribution; the tail proportion and error are exact threshold counts. If histogram bins straddle zero or $\eta$, the plotted bars may not reveal either count exactly.

Worked Example: A Tail Shrinks While the Error Rate Stays Fixed

Suppose six observations have round-3 margins, in order, $-1,-1/3,1/3,1/3,1,1$. At round 4, the new coefficient is one and the previous coefficient total is three, so the update is $m_{i,4}=(3m_{i,3}+Y_i h_4(X_i))/4$. Assume the new classifier predicts correctly on the first two observations and incorrectly on the remaining four. Their signed new predictions $Y_i h_4(X_i)$ are therefore $1,1,-1,-1,-1,-1$.

Applying the update observation by observation gives

\begin{aligned} m_{1,4}&=\{3(-1)+1\}/4=-1/2,\\ m_{2,4}&=\{3(-1/3)+1\}/4=0,\\ m_{3,4}&=\{3(1/3)-1\}/4=0,\\ m_{4,4}&=\{3(1/3)-1\}/4=0,\\ m_{5,4}&=\{3(1)-1\}/4=1/2,\\ m_{6,4}&=\{3(1)-1\}/4=1/2. \end{aligned}

This version of the update illustrates why the signed prediction for each observation must be included; the outcome is not determined by the previous margin alone. At threshold $\eta=0.4$, the round-3 tail contains the margins $-1,-1/3,1/3,1/3$, so $T_3(0.4)=4/6$. At round 4, the margins at or below $0.4$ are $-1/2,0,0,0$, giving $T_4(0.4)=4/6$. The error rate is $2/6$ at round 3 and $4/6$ at round 4: two of the initially positive margins have reached zero and count as errors under the stated convention. This calculation shows both why the update must be checked margin by margin and why a tail count cannot be read as an error count.

A simpler update can isolate the distinction. If the signed prediction is $+1$ for every observation and the coefficient ratio yields $m_{i,4}=(3m_{i,3}+1)/4$, then the same round-3 margins become $-1/2,0,1/2,1/2,1,1$. The first two observations remain errors: one has a negative margin and one has a zero margin. Both are in the $\eta=0.4$ tail, so $T_4(0.4)=2/6$, while the error rate is also $2/6$. In this case the tail falls from $4/6$ to $2/6$ without a change in classification error.

What a Low-Margin Tail Counts

For any fixed $\eta>0$, the tail $T_t(\eta)$ includes all observations with nonpositive margins as well as correctly classified observations whose positive margins are no larger than $\eta$. This yields an exact decomposition, not an approximation.

Result: For $\eta>0$, under the convention that $m_{i,t}\leq0$ is an error, $$ T_t(\eta)=E_t+\frac{1}{n}\sum_{i=1}^n I(0<m_{i,t}\leq\eta). $$ In particular, $E_t\leq T_t(\eta)$.

To verify the identity, partition the event $\{m_{i,t}\leq\eta\}$ into the disjoint events $\{m_{i,t}\leq0\}$ and $\{0<m_{i,t}\leq\eta\}$. Because $\eta>0$, these events cover every margin at most $\eta$, and they do not overlap. Summing their indicators over the sample and dividing by $n$ gives the displayed equality. The second term is nonnegative, which proves the inequality. Consequently, a smaller positive-threshold tail need not mean fewer errors: it may instead mean fewer correctly classified observations remain close to the boundary. Conversely, an unchanged error rate can accompany a substantial reduction in that near-boundary fraction. $\square$

Worked Example: Equal Error Rates, Different Margin Tails

Consider two ensembles evaluated on the same five observations. Their margins are, respectively, $(-0.4,0.02,0.08,0.30,0.70)$ and $(-0.8,0.20,0.25,0.50,0.80)$. Use $\eta=0.10$ and count ties as errors.

For the first ensemble, only $-0.4$ is nonpositive, so $E=1/5$. The margins at or below $0.10$ are $-0.4,0.02,0.08$, giving $T(0.10)=3/5$. The decomposition has one error and two correctly classified observations in the low-margin tail.

For the second ensemble, only $-0.8$ is nonpositive, so $E=1/5$ again. Only $-0.8$ is at or below $0.10$, giving $T(0.10)=1/5$. The classification error is identical, but the first ensemble has more correct predictions close to the boundary. The tail summary distinguishes these ensembles in a way the error rate does not.

How Much Can One Round Move a Margin?

The round update also gives a useful bound on individual changes. It applies to positive coefficients and normalized margins, and helps identify which observations could cross a chosen threshold in a single round.

Result: Suppose $m_{i,t-1}\in[-1,1]$, $A_{t-1}>0$, and $\alpha_t>0$. Set $\lambda_t=\alpha_t/A_t$. Then $$ |m_{i,t}-m_{i,t-1}|\leq 2\lambda_t. $$ For any threshold $\eta$, an observation can change whether its margin is at most $\eta$ only if its previous margin lies within $2\lambda_t$ of $\eta$.

To prove the bound, put $z_i=Y_i h_t(X_i)$, so $z_i\in\{-1,+1\}$. Since $A_t=A_{t-1}+\alpha_t$, the update can be rewritten as

m_{i,t}-m_{i,t-1} =\frac{\alpha_t}{A_t}(z_i-m_{i,t-1}) =\lambda_t(z_i-m_{i,t-1}).

Both $z_i$ and $m_{i,t-1}$ belong to $[-1,1]$, so $|z_i-m_{i,t-1}|\leq2$. Multiplication by $\lambda_t>0$ proves the first inequality. If the observation changes sides of $\eta$, then one of its old and new margins is at most $\eta$ and the other is greater than $\eta$. Thus $|m_{i,t-1}-\eta|\leq |m_{i,t-1}-m_{i,t}|\leq2\lambda_t$. This proves the crossing condition. $\square$

The result does not say that all margins move by the same amount or in the same direction. It says that a threshold count can change only through observations close enough to that threshold before the update. In particular, when $\lambda_t$ is small, a large change in a tail count requires many observations concentrated near its cutoff.

Worked Example: Locating Possible Crossings

Suppose $A_{t-1}=9$ and $\alpha_t=1$. Then $A_t=10$, $\lambda_t=1/10$, and every margin moves by at most $2/10=0.2$. For a tail threshold $\eta=0.30$, only observations with previous margins in $[0.10,0.50]$ can possibly change whether they belong to the tail.

For example, an observation at $m_{i,t-1}=0.05$ cannot leave the tail: even its largest permitted increase is $0.20$, so its new margin is at most $0.25<0.30$. An observation at $0.60$ cannot enter the tail: even its largest permitted decrease is $0.20$, leaving its margin at least $0.40>0.30$. An observation at $0.35$, by contrast, is close enough to cross; whether it does depends on its signed prediction $z_i$, not just on its old margin. The bound identifies possible crossings, not guaranteed ones.

Reading Training and Held-Out Histograms

A careful round-by-round comparison reports at least the sample, the round, the margin normalization, the error convention, and the tail threshold. For each round, useful numerical summaries include $E_t$, $T_t(\eta)$, and a few quantiles of the margin distribution. The histogram supplies shape: a pile-up near zero, a left tail of negative margins, or a broad movement toward larger positive values can all matter even when two rounds share the same error rate.

Worked Example: A Training Improvement Is Not a Held-Out Improvement

At round 10, suppose a training sample of 10 observations has two nonpositive margins and two additional margins in $(0,0.20]$. Its error is $2/10=0.20$, and its tail at $\eta=0.20$ is $4/10=0.40$. At round 20, suppose the training sample has one nonpositive margin and one additional margin in $(0,0.20]$. Then its error is $1/10=0.10$, and its tail is $2/10=0.20$. On these training summaries, both error and low-margin tail have fallen.

Now suppose a separate held-out sample of 10 observations has one nonpositive margin and two additional margins in $(0,0.20]$ at round 10. Its error is $1/10=0.10$, and its tail is $3/10=0.30$. At round 20, suppose it still has one nonpositive margin, but four additional margins in $(0,0.20]$. Its error remains $1/10=0.10$, while its tail rises to $5/10=0.50$. The held-out classification error has not changed, but more correctly classified observations are close to the boundary. A report that gives only training error would miss this contrast; a report that gives only held-out error would miss the tail change.

The held-out comparison is informative only if these observations were not used to choose rounds, tune the procedure, or otherwise fit the model. Repeatedly selecting a round because it looks best on the same nominally held-out sample makes that sample part of the selection process. The interpretation should therefore describe how the sample was used, not merely label it “held out.”

Common Mistakes and Practical Interpretation

Equating a low-margin tail with the error rate. For $\eta>0$, the tail includes errors and low-margin correct predictions. Use the exact decomposition rather than treating the two proportions as interchangeable.
Assuming margins must improve every round. The cumulative score and its normalization both change. Check the update for each observation or compare the actual round-wise distributions.
Ignoring ties. State whether a zero margin counts as an error. Under the convention here, it does; changing the convention changes the error count and the corresponding tail decomposition.
Reading exact counts from broad histogram bins. If a bin straddles zero or the chosen threshold, its height does not determine the count on either side. Calculate the threshold proportions from the margins.
Mixing training and held-out conclusions. State which observations produced each histogram. Training and held-out margin changes answer different descriptive questions.
Changing the threshold between rounds. A tail comparison is interpretable only when the same $\eta$ and margin normalization are used throughout.

Margin tracking complements classification error by showing the distribution of confidence, especially near the decision boundary. It does not replace error measurement, and a training-margin shift alone does not establish improved performance on new data. Read the two summaries together: first identify how many observations are errors, then inspect how much correctly classified mass remains close to zero.

Check Your Understanding

Use the margin convention and definitions in this tutorial.

For margins $(-0.2,0,0.05,0.4)$, calculate the error rate and the tail proportion at $\eta=0.10$.
Explain why two ensembles can have the same classification error but different tail proportions at a positive threshold.
If $\lambda_t=0.05$, how far can a normalized margin move in one round, and which previous margins can possibly cross the threshold $\eta=0.25$?
Why can a histogram with a bin spanning zero fail to reveal the exact classification error?
What information is needed before interpreting a round-wise difference between training and held-out margin histograms?