Boosting the margin: A new explanation for the effectiveness of voting methods

R. SchapireY. FreundPeter BarlettWee Sun Lee

article1997ICML3,114 citations

Explains why boosting continues to improve generalization error even after reaching zero training error by proving theoretical bounds based on the classification margin distribution rather than ensemble complexity.

Listen

The paper addresses a striking empirical puzzle in machine-learning experiments: voting methods such as boosting and bagging produce combined classifiers whose test error continues to fall, or at least does not rise, even after the training error has reached zero and the ensemble has grown to contain millions of nodes. Traditional theory based on Occam’s razor or bias-variance decomposition predicts that such growth should eventually degrade generalization, yet the opposite is observed on many benchmark problems.

The authors set out to explain this behavior by shifting attention from training error alone to the distribution of classification margins on the training set. A margin for an example is the difference between the total weight placed on the correct label and the largest weight placed on any single incorrect label by the weighted vote; a large positive margin signals a confident correct classification. They prove non-asymptotic upper bounds on generalization error that depend on the fraction of training examples whose margins fall below a chosen threshold, together with a measure of the complexity of the base-classifier family and the number of training examples, but not on the number of base classifiers themselves. The bounds hold for any voting method and apply whether the base-classifier space is finite or has finite VC-dimension.

The analysis shows that both bagging and boosting increase margins, but boosting does so more aggressively, driving almost all training margins well above zero even after the training error is already zero. Experiments on letter, satimage, vehicle and several synthetic data sets confirm that reductions in the mass of small-margin examples track improvements in test error across C4.5 trees, decision stumps, and error-correcting output coding. In contrast, bias-variance decompositions account reasonably for bagging yet fail to explain why boosting remains effective when base-classifier variance is low or even increases.

These results imply that the practical success of voting methods need not rest on keeping the final classifier simple; what matters is producing a large margin on most training points. The theory therefore supplies a qualitative account of the observed learning curves and suggests that algorithms explicitly aimed at margin maximization could yield further gains. At the same time, the quantitative bounds remain loose for the data-set sizes typical in practice, and they do not yet identify precisely when boosting will fail because base-classifier errors rise too quickly. Tighter margin-based bounds or alternative statistics that reliably predict test performance on real data therefore remain important open directions.

AT&T Labs—Research Australian Defence Force Academy Australian National University boosting neural networks support vector Boosting Margin Voting Method

Schapire et al (1997).pdf

Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). This paper establishes the foundational margin-maximization framework for optimal margin classifiers that the source paper adapts and applies to voting methods.
Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). This paper introduces the decision-theoretic generalization of on-line learning and AdaBoost, providing the boosting algorithms whose test error behavior the source paper explains via margins.
Paper: Experiments with a New Boosting Algorithm, Yoav Freund et al. (1996). This empirical study on AdaBoost highlights the surprising phenomenon of test error decreasing after zero training error, which the source paper investigates and explains using margin distribution.

Paper: Understanding deep learning requires rethinking generalization, Chiyuan Zhang et al. (2017). This paper extends the study of generalization and large capacity in classifiers, revisiting the puzzle of why models generalize well when fitting large training sets.
Paper: Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, P. Bartlett et al. (2002). This paper builds on margin and complexity analysis by deriving Rademacher and Gaussian complexity risk bounds that generalize performance guarantees for voting and margin-based classifiers.

Cover for Boosting the margin: A new explanation for the effectiveness of voting methods

Abstract

One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often is observed to decrease even after the training error reaches zero. In this paper, we show that this phenomenon is related to the distribution of margins of the training examples with respect to the generated voting classification rule, where the margin of an example is simply the difference between the number of correct votes and the maximum number of votes received by any incorrect label. We show that techniques used in the analysis of Vapnik’s support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error. We also show theoretically and experimentally that boosting is especially effective at increasing the margins of the training examples. Finally, we compare our explanation to those based on the bias-variance decomposition.

Topics

boosting neural networks support vector classification rules classification models svm

Keywords

Boosting Margin Voting Method Bagging AdaBoost Generalization Error Bias‑Variance Decomposition VC‑Dimension Support Vector Classifier Error‑Correcting Output Code

2.1. Finite base-classifier spaces.
2.3. Infinite base-classifier spaces.
5.3. *Boosting and variance reduction.*
APPENDIX A

Knowls

Knowl 1 — Margin-Based Generalization Bound for Finite Base Classifier Spaces
theoretical result
Let $\mathcal{D}$ be a probability distribution over an instance-label space $\mathcal{X} \times \{-1, +1\}$ , and let $S = \langle (x_1, y_1), \dots, (x_m, y_m) \rangle$ be a sample of $m$ training examples chosen independently at random according to $\mathcal{D}$ . Let $\mathcal{H}$ be a finite space of base classifiers mapping $\mathcal{X} \to \{-1, +1\}$ , and let $\mathcal{C}$ denote its convex hull, consisting of all weighted averages $f(x) = \sum_{h \in \mathcal{H}} a_h h(x)$ with $a_h \ge 0$ and $\sum_h a_h = 1$ .

For any confidence parameter $\delta > 0$ , with probability at least $1 - \delta$ over the random choice of the training sample $S$ , every combined classifier $f \in \mathcal{C}$ satisfies the following bound for all margin thresholds $\theta > 0$ :

$P_{(x, y) \sim \mathcal{D}}[yf(x) \le 0] \le P_{(x, y) \sim S}[yf(x) \le \theta] + O\left( \frac{1}{\sqrt{m}} \left( \frac{\log m \log |\mathcal{H}|}{\theta^2} + \log(1/\delta) \right)^{1/2} \right)$

where $P_{(x, y) \sim \mathcal{D}}[yf(x) \le 0]$ is the generalization error of the majority voting rule associated with $f$ , and $P_{(x, y) \sim S}[yf(x) \le \theta]$ is the fraction of training examples with margin at most $\theta$ . The bound does not depend on the number of base classifiers combined in $f$ , showing that voting many classifiers does not inherently cause overfitting if large margins are achieved.
Knowl 2 — AdaBoost Exponential Bound on the Training Margin Distribution
theoretical result
Let AdaBoost be executed on a binary training set $S = \langle (x_1, y_1), \dots, (x_m, y_m) \rangle$ with $y_i \in \{-1, +1\}$ for $T$ iterations. On each round $t \in \{1, \dots, T\}$ , AdaBoost trains a base classifier $h_t: \mathcal{X} \to \{-1, +1\}$ achieving weighted training error $\epsilon_t = P_{i \sim D_t}[y_i \neq h_t(x_i)]$ with respect to distribution $D_t$ , and assigns classifier weight $\alpha_t = \frac{1}{2} \ln((1 - \epsilon_t)/\epsilon_t)$ . The normalized combined function is $f(x) = \sum_{t=1}^T \alpha_t h_t(x) / \sum_{t=1}^T \alpha_t$ .

For any margin threshold $\theta \in \mathbb{R}$ , the fraction of training examples with margin at most $\theta$ is bounded by:

$P_{(x, y) \sim S}[yf(x) \le \theta] \le 2^T \prod_{t=1}^T \sqrt{\epsilon_t^{1-\theta}(1-\epsilon_t)^{1+\theta}}$

If the base learning algorithm generates classifiers that are consistently slightly better than random guessing, such that $\epsilon_t \le \frac{1}{2} - \gamma$ for some $\gamma > 0$ across all rounds $t$ , the bound simplifies to:

$P_{(x, y) \sim S}[yf(x) \le \theta] \le \left( \sqrt{(1 - 2\gamma)^{1-\theta} (1 + 2\gamma)^{1+\theta}} \right)^T$

For any $\theta < \gamma$ , the base term is strictly less than 1, implying that the proportion of training examples with margin below $\theta$ decreases exponentially fast to zero as the number of boosting iterations $T$ increases.
Knowl 3 — Margin-Based Generalization Bound for Base Classifiers with Bounded VC-Dimension
theoretical result
Let $\mathcal{D}$ be a distribution over $\mathcal{X} \times \{-1, +1\}$ , and let $S$ be a sample of $m$ training examples chosen i.i.d. from $\mathcal{D}$ . Let $\mathcal{H}$ be a base-classifier space mapping $\mathcal{X} \to \{-1, +1\}$ with Vapnik-Chervonenkis (VC) dimension $d$ , and let $\mathcal{C}$ be its convex hull. Assume $m \ge d \ge 1$ .

For any $\delta > 0$ , with probability at least $1 - \delta$ over the random draw of $S$ , every voting classifier $f \in \mathcal{C}$ satisfies, for all margin thresholds $\theta > 0$ :

$P_{(x, y) \sim \mathcal{D}}[yf(x) \le 0] \le P_{(x, y) \sim S}[yf(x) \le \theta] + O\left( \frac{1}{\sqrt{m}} \left( \frac{d \log^2(m/d)}{\theta^2} + \log(1/\delta) \right)^{1/2} \right)$

This nonasymptotic upper bound depends directly on the sample size $m$ , the VC-dimension $d$ of the base hypothesis class, and the margin threshold $\theta$ , while remaining independent of the number of base classifiers combined in the vote.
Knowl 4 — Definition of Classification Margin for Voting Classifiers
definition
Let $\mathcal{H}$ be a family of base classifiers, and let a combined voting classifier $f$ be defined as a normalized convex combination of classifiers in $\mathcal{H}$ with non-negative weights summing to 1.

For binary classification with labels $\mathcal{Y} = \{-1, +1\}$ where base classifiers map $h: \mathcal{X} \to \{-1, +1\}$ , the voting classifier is $f(x) = \sum_{h \in \mathcal{H}} a_h h(x)$ with $a_h \ge 0, \sum_h a_h = 1$ . The classification margin of an example $(x, y)$ is defined as:

$\text{margin}(f, x, y) = y f(x)$

The margin lies in the interval $[-1, 1]$ . An example is correctly classified by the majority vote rule if and only if its margin is positive ( $y f(x) > 0$ ), and larger positive values signify higher classification confidence.

For multiclass classification with $k$ classes $\mathcal{Y} = \{1, \dots, k\}$ , base classifiers are represented as mappings $h: \mathcal{X} \times \mathcal{Y} \to \{0, 1\}$ , where $h(x, y) = 1$ indicates that $y$ is considered a plausible label for $x$ . The combined function is $f(x, y) = \sum_{h \in \mathcal{H}} a_h h(x, y)$ with $a_h \ge 0, \sum_h a_h = 1$ , and the classifier predicts $\arg\max_{y \in \mathcal{Y}} f(x, y)$ . The multiclass margin of an example $(x, y)$ is defined as:

$\text{margin}(f, x, y) = f(x, y) - \max_{y' \neq y} f(x, y')$

This represents the difference between the total vote weight assigned to the correct label $y$ and the maximum vote weight assigned to any single incorrect alternative label $y'$ .
Knowl 5 — Multiclass Margin-Based Generalization Error Bounds
theoretical result
Let $\mathcal{D}$ be a distribution over $\mathcal{X} \times \mathcal{Y}$ where $\mathcal{Y} = \{1, \dots, k\}$ , and let $S$ be a random sample of $m$ training instances drawn i.i.d. from $\mathcal{D}$ . Let $\mathcal{H}$ be a class of base classifiers $h: \mathcal{X} \times \mathcal{Y} \to \{0, 1\}$ , and let $\mathcal{C}$ be the convex hull of $\mathcal{H}$ , where $f(x, y) = \sum_{h \in \mathcal{H}} a_h h(x, y)$ with $a_h \ge 0, \sum_h a_h = 1$ . The classification margin is $\text{margin}(f, x, y) = f(x, y) - \max_{y' \neq y} f(x, y')$ .

For any $\delta > 0$ , with probability at least $1 - \delta$ over the random draw of $S$ , every function $f \in \mathcal{C}$ satisfies, for all $\theta > 0$ :
1. If $\mathcal{H}$ is finite:
$P_{\mathcal{D}}[\text{margin}(f, x, y) \le 0] \le P_S[\text{margin}(f, x, y) \le \theta] + O\left( \frac{1}{\sqrt{m}} \left( \frac{\log(mk) \log |\mathcal{H}|}{\theta^2} + \log(1/\delta) \right)^{1/2} \right)$
1. If $\mathcal{H}$ has VC-dimension $d$ (with $m \ge d \ge 1$ ):
$P_{\mathcal{D}}[\text{margin}(f, x, y) \le 0] \le P_S[\text{margin}(f, x, y) \le \theta] + O\left( \frac{1}{\sqrt{m}} \left( \frac{d \log^2(mk/d)}{\theta^2} + \log(1/\delta) \right)^{1/2} \right)$
Knowl 6 — Uniform Convergence Generalization Bounds via Sloppy Covers
theoretical result
Let $\mathcal{F}$ be a family of real-valued functions defined on an instance space $\mathcal{X}$ . For a training set $S$ of size $m$ and positive constants $\theta$ and $\epsilon$ , a function class $\hat{\mathcal{F}}$ is defined to be an $\epsilon$ -sloppy $\theta$ -cover of $\mathcal{F}$ with respect to $S$ if for every $f \in \mathcal{F}$ there exists $\hat{f} \in \hat{\mathcal{F}}$ such that $P_{x \sim S}[|\hat{f}(x) - f(x)| > \theta] < \epsilon$ . Let $\mathcal{N}(\mathcal{F}, \theta, \epsilon, m)$ denote the maximum over all samples $S$ of size $m$ of the minimum cardinality of an $\epsilon$ -sloppy $\theta$ -cover of $\mathcal{F}$ with respect to $S$ .

For any distribution $\mathcal{D}$ over $\mathcal{X} \times \{-1, +1\}$ , any sample $S \sim \mathcal{D}^m$ , and any $\epsilon > 0, \theta > 0$ , the probability over the random draw of $S$ that there exists $f \in \mathcal{F}$ satisfying

$P_{(x, y) \sim \mathcal{D}}[yf(x) \le 0] > P_{(x, y) \sim S}[yf(x) \le \theta] + \epsilon$

is at most:

$2 \mathcal{N}(\mathcal{F}, \theta/2, \epsilon/8, 2m) \exp\left( -\frac{\epsilon^2 m}{32} \right)$
Knowl 7 — Margin Distribution Dynamics and Post-Zero Training Error Generalization in AdaBoost
empirical result
In empirical comparisons of AdaBoost, Bagging, and Error-Correcting Output Codes (ECOC) applied to decision trees (C4.5) on multiclass benchmarks (Letter, Satimage, and Vehicle), boosting demonstrates a distinctive margin-increasing behavior that explains why generalization error continues to decrease after training error reaches zero.

On the Letter dataset with C4.5, single-tree test error is 13.8%. After combining 5 trees, AdaBoost achieves 0% training error with an 8.4% test error. Continued boosting to 1000 trees further reduces test error to 3.1% (compared to 6.6% for Bagging after 1000 trees). Throughout iterations 5 to 1000, while the training 0-1 error remains constant at 0%, the empirical cumulative distribution of training margins shifts significantly toward larger positive values: at round 5, approximately 7.7% of training instances have a margin below 0.5, whereas by round 100, 0% of instances have a margin below 0.5.

Unlike Bagging (which often assigns maximal margin 1 to over half the instances while leaving many instances with small margins near 0), AdaBoost aggressively increases the margins of difficult, small-margin examples at the cost of reducing margins on examples that already possess large margins.

Knowl 8 — Bias-Variance Decomposition Analysis of Boosting vs. Bagging

data/table

Empirical evaluations on five synthetic benchmark datasets demonstrate that AdaBoost functions primarily by reducing bias, and does not require base classifiers to have high variance to succeed. In some problems, boosting substantially lowers generalization error while simultaneously increasing classifier variance.

Experiments evaluated C4.5 and single-node decision stumps under two standard definitions of bias and variance (Kong & Dietterich 1995; Breiman 1998) over 1000 runs on 10,000 test examples, with training sample sizes of 200 (Kong-Dietterich problem) or 300 (others):

		Kong and Dietterich definitions						Breiman definitions
		Stumps			C4.5			Stumps			C4.5
Dataset	Metric	Base	Boost	Bag	Base	Boost	Bag	Base	Boost	Bag	Base	Boost	Bag
Waveform	Bias	26.0	3.8	22.8	1.5	0.5	1.4	19.2	2.6	15.7	0.9	0.3	1.4
	Variance	5.6	2.8	4.1	14.9	3.7	5.2	12.5	4.0	11.2	15.5	3.9	5.2
	Error	44.7	19.6	39.9	29.4	17.2	19.7	44.7	19.6	39.9	29.4	17.2	19.7
Twonorm	Bias	2.5	0.6	2.0	0.5	0.2	0.5	1.3	0.3	1.1	0.3	0.1	0.3
	Variance	28.5	2.3	17.3	18.7	1.8	5.4	29.6	2.6	18.2	19.0	1.9	5.6
	Error	33.3	5.3	21.7	21.6	4.4	8.3	33.3	5.3	21.7	21.6	4.4	8.3
Threenorm	Bias	24.5	6.3	21.6	4.7	2.9	5.0	14.2	4.1	13.8	2.6	1.9	3.1
	Variance	6.9	5.1	4.8	16.7	5.2	6.8	17.2	7.3	12.6	18.8	6.3	8.6
	Error	41.9	22.0	36.9	31.9	18.6	22.3	41.9	22.0	36.9	31.9	18.6	22.3
Ringnorm	Bias	46.9	4.1	46.9	2.0	0.7	1.7	32.3	2.7	37.6	1.1	0.4	1.1
	Variance	-7.9	6.6	-7.1	15.5	2.3	6.3	6.7	8.0	2.2	16.4	2.6	6.9
	Error	40.6	12.2	41.4	19.0	4.5	9.5	40.6	12.2	41.4	19.0	4.5	9.5
Kong-Diet.	Bias	49.2	49.1	49.2	7.7	5.5	8.9	49.0	49.0	49.0	5.1	3.5	6.2
	Variance	0.2	0.2	0.2	7.2	6.6	4.3	0.4	0.3	0.5	9.8	8.5	6.9
	Error	49.5	49.3	49.5	14.9	12.1	13.1	49.5	49.3	49.5	14.9	12.1	13.1

For instance, on Ringnorm using decision stumps, AdaBoost reduces overall error from 40.6% to 12.2% by reducing bias from 46.9% to 4.1%, while variance increases from -7.9% to 6.6% (Kong-Dietterich) or from 6.7% to 8.0% (Breiman).

Knowl 9 — High-Dimensional Margin Geometry: Boosting vs. Support Vector Machines
model/method
Both Support Vector Machines (SVMs) and AdaBoost construct linear combinations of basis functions in a high-dimensional feature space $\mathbf{h}(x) = \langle h_1(x), \dots, h_T(x) \rangle$ parameterized by a weight vector $\boldsymbol{\alpha} = \langle \alpha_1, \dots, \alpha_T \rangle$ , but they optimize margins under different norm geometries and computational frameworks:
1. Support Vector Classifiers maximize the normalized $\ell_2$ -margin:
$\min_{(x, y) \in S} \frac{y(\boldsymbol{\alpha} \cdot \mathbf{h}(x))}{\|\boldsymbol{\alpha}\|_2}$

subject to $\|\mathbf{h}(x)\|_2 \le R$ . This is solved via quadratic programming over inner products (kernels).
1. AdaBoost maximizes the normalized $\ell_1$ -margin:
$\min_{(x, y) \in S} \frac{y(\boldsymbol{\alpha} \cdot \mathbf{h}(x))}{\|\boldsymbol{\alpha}\|_1}$

subject to $\|\mathbf{h}(x)\|_\infty = \max_t |h_t(x)| \le 1$ , by greedily minimizing an exponential loss $\sum_i \exp(-y_i \boldsymbol{\alpha} \cdot \mathbf{h}(x_i))$ . This corresponds to coordinate-wise descent (approximate linear programming), where base hypotheses explore one coordinate of the high-dimensional feature space at a time.
Knowl 10 — Overfitting via Majority Voting of Simple Functions
theoretical result
To counter the misconception that majority voting over base hypotheses acts universally as a variance-reducing "smoothing" operation that cannot increase complexity, consider a hypothesis class $\mathcal{H}$ consisting of single-point delta functions (predicting $+1$ on a single designated point $x_0 \in \mathcal{X}$ and $-1$ elsewhere, or $-1$ on $x_0$ and $+1$ elsewhere) together with the two constant functions ( $+1$ and $-1$ ).

The VC-dimension of $\mathcal{H}$ is exactly 2. However, for any training set $S$ of size $m$ with $m_+$ positive and $m_-$ negative instances, an unweighted majority vote over at most $2m$ functions from $\mathcal{H}$ ( $m$ single-point delta functions matching each training instance, plus $m_+$ constant $+1$ functions and $m_-$ constant $-1$ functions) achieves 0% training error while having generalization error close to random guessing on unseen points.

Margin analysis accurately predicts this failure: while the combined rule classifies the training set perfectly, every training instance receives a tiny margin of order $O(1/m)$ . For $\theta = O(1/m)$ , the margin generalization bound becomes vacuous ( $O(\sqrt{m})$ ), correctly explaining the severe overfitting.
Knowl 11 — Quantitative Bound Looseness and Inadequacy of Minimal Margin Maximization
limitation
The theoretical margin bounds on voting generalization error are nonasymptotic but loose, requiring training sample sizes $m$ in the tens of thousands before providing non-trivial quantitative guarantees on generalization error, despite qualitative alignment with empirical learning curves.

Furthermore, modifying voting algorithms to maximize only the minimal training margin (the single smallest margin $\min_i y_i f(x_i)$ via linear programming, as studied by Breiman, and Grove & Schuurmans) frequently increases generalization error compared to AdaBoost (for example, on the Ionosphere dataset). This demonstrates that generalization error depends on the overall distribution of margins across all training examples rather than purely the extreme minimum margin.

Coverage note — None was omitted; the knowls comprehensively cover the formal margin definitions (binary and multiclass), finite and VC generalization bounds, the sloppy cover framework, AdaBoost training margin convergence guarantees, empirical error/margin dynamics, bias-variance analysis and dataset experiments, norm-based comparison to SVMs, and the theoretical counterexample and limitations.

References

1.BARRON, A. R. (1993). Universal approximation bounds for superposition of a sigmoidal function. IEEE Trans. Inform. Theory 39 930–945.
2.BARTLETT, P. L. (1998). The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Trans. Inform. Theory 44 525–536.
3.BAUER, E. and KOHAVI, R. (1997). An empirical comparison of voting classification algorithms: bagging, boosting, and variants. Unpublished manuscript.
4.BAUM, E. B. and HAUSSLER, D. (1989). What size net gives valid generalization? Neural Computation 1 151–160.
5.BOSER, B. E., GUYON, I. M. and VAPNIK, V. N. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory 144–152. ACM, New York.
6.BREIMAN, L. (1996). Bagging predictors. Machine Learning 24 123–140.
7.BREIMAN, L. (1997). Prediction games and arcing classifiers. Technical Report 504, Dept. Statistics, Univ. California, Berkeley.
8.BREIMAN, L. (1998). Arcing classifiers (with discussion). Ann. Statist. 26 801–849.
9.BREIMAN, L., FRIEDMAN, J. H., OLSHEN, R. A. and STONE, C. J. (1984). Classification and Regression Trees. Wadsworth, Belmont, CA.
10.CORTES, C. and VAPNIK, V. (1995). Support-vector networks. Machine Learning 20 273–297.
11.DEVROYE, L. (1982). Bounds for the uniform deviation of empirical measures. J. Multivariate Anal. 12 72–79.
12.DIETTERICH, T. G. (1998). An experimental comparison of three methods for constructing ensembles of decision trees: bagging, boosting, and randomization. Unpublished manuscript.
13.DIETTERICH, T. G. and BAKIRI, G. (1995). Solving multiclass learning problems via error-correcting output codes. J. Artificial Intelligence Res. 2 263–286.
14.DONAHUE, M. J., GURVITS, L., DARKEN, C. and SONTAG, E. (1997). Rates of convex approximation in non-Hilbert spaces. Constr. Approx. 13 187–220.
15.DRUCKER, H. (1997). Improving regressors using boosting techniques. In Machine Learning: Proceedings of the Fourteenth International Conference 107–115. Morgan Kauffman, San Francisco.
16.DRUCKER, H. and CORTES, C. (1996). Boosting decision trees. Advances in Neural Information Processing Systems 8 479–485.
17.FREUND, Y. (1995). Boosting a weak learning algorithm by majority. Inform. Comput. 121 256–285.
18.FREUND, Y. and SCHAPIRE, R. E. (1996). Experiments with a new boosting algorithm. In Machine Learning: Proceedings of the Thirteenth International Conference 148–156. Morgan Kauffman, San Francisco.
19.FREUND, Y. and SCHAPIRE, R. E. (1996). Game theory, on-line prediction and boosting. In Proceedings of the Ninth Annual Conference on Computational Learning Theory 325–332.
20.FREUND, Y. and SCHAPIRE, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. System Sci. 55 119–139.
21.FREUND, Y. and SCHAPIRE, R. E. (1998). Adaptive game playing using multiplicative weights. Games and Economic Behavior. To appear.
22.FRIEDMAN, J. H. (1998). On bias, variance, 0/1-loss, and the curse-of-dimensionality. Available at http://stat.stanford.edu/~jhf.
23.GROVE, A. J. and SCHUURMANS, D. (1998). Boosting in the limit: maximizing the margin of learned ensembles. In Proceedings of the Fifteenth National Conference on Artificial Intelligence. AAAI Press, Meno Park, NJ.
24.JONES, L. K. (1992). A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. Ann. Statist. 20 608–613.
25.KOHAVI, R. and WOLPERT, D. H. (1996). Bias plus variance decomposition for zero-one loss functions. In Machine Learning: Proceedings of the Thirteenth International Conference 275–283. Morgan Kauffman, San Francisco.
26.KONG, E. B. and DIETTERICH, T. G. (1995). Error-correcting output coding corrects bias and variance. In Proceedings of the Twelfth International Conference on Machine Learning 313–321. Morgan Kauffman, San Francisco.
27.LEE, W. S., BARTLETT, P. L. and WILLIAMSON, R. C. (1996). Efficient agnostic learning of neural networks with bounded fan-in. IEEE Trans. Inform. Theory 42 2118–2132.
28.LEE, W. S., BARTLETT, P. L. and WILLIAMSON, R. C. (1998). The importance of convexity in learning with squared loss. IEEE Trans. Inform. Theory. To appear.
29.MACLIN, R. and OPITZ, D. (1997). An empirical evaluation of bagging and boosting. In Proceedings of the Fourteenth National Conference on Artificial Intelligence 546–551.
30.MERZ, C. J. and MURPHY, P. M. (1998). UCI repository of machine learning databases. Available at http://www.ics.uci.edu/~mlearn/MLRepository.html.
31.QUINLAN, J. R. (1996). Bagging, boosting, and C4.5. In Proceedings of the Thirteenth National Conference on Artificial Intelligence 725–730.
32.QUINLAN, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo.
33.SAUER, N. (1972). On the density of families of sets. J. Combin. Theory Ser. A 13 145–147.
34.SCHAPIRE, R. E. (1990). The strength of weak learnability. Machine Learning 5 197–227.
35.SCHAPIRE, R. E. (1997). Using output codes to boost multiclass learning problems. In Machine Learning: Proceedings of the Fourteenth International Conference 313–321. Morgan Kauffman, San Francisco.
36.SCHAPIRE, R. E. and SINGER, Y. (1998). Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory.
37.SCHWENK, H. and BENGIO, Y. (1998). Training methods for adaptive boosting of neural networks for character recognition. Advances in Neural Information Processing Systems 10 647–653. MIT Press.
38.SHAWE-TAYLOR, J., BARTLETT, P. L., WILLIAMSON, R. C. and ANTHONY, M. (1996). A framework for structural risk minimisation. In Proceedings of the Ninth Annual Conference on Computational Learning Theory 68–76.
39.SHAWE-TAYLOR, J., BARTLETT, P. L., WILLIAMSON, R. C. and ANTHONY, M. (1996). Structural risk minimization over data-dependent hierarchies. Technical Report NC-TR-96-053, Neurocolt.
40.TIBSHIRANI, R. (1996). Bias, variance and prediction error for classification rules. Technical Report, Univ. Toronto.
41.VAPNIK, V. N. (1995). The Nature of Statistical Learning Theory. Springer, New York.
42.VAPNIK, V. N. and CHERVONENKIS, A. YA. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16 264–280.

Citation

MLA

Bartlett, P., et al. “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods”. The Annals of Statistics, vol. 26, no. 5, 1998, https://doi.org/10.1214/AOS/1024691352.

APA

Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998). Boosting the margin: a new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5). https://doi.org/10.1214/AOS/1024691352

Chicago

Bartlett, P., Y. Freund, W. S. Lee, and R. E. Schapire. 1998. “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods”. The Annals of Statistics 26 (5). https://doi.org/10.1214/AOS/1024691352.

Harvard

Bartlett, P. et al. (1998) “Boosting the margin: a new explanation for the effectiveness of voting methods”, The Annals of Statistics, 26(5). Available at: https://doi.org/10.1214/AOS/1024691352.

Vancouver

1. Bartlett P, Freund Y, Lee WS, Schapire RE (1998) Boosting the margin: a new explanation for the effectiveness of voting methods. The Annals of Statistics. https://doi.org/10.1214/AOS/1024691352

BibTeX

@article{Bartlett_1998, title={Boosting the margin: a new explanation for the effectiveness of voting methods}, volume={26}, ISSN={0090-5364}, url={http://dx.doi.org/10.1214/AOS/1024691352}, DOI={10.1214/aos/1024691352}, number={5}, journal={The Annals of Statistics}, publisher={Institute of Mathematical Statistics}, author={Bartlett, Peter and Freund, Yoav and Lee, Wee Sun and Schapire, Robert E.}, year={1998}, month=Oct }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Boosting the margin: A new explanation for the effectiveness of voting methods

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Margin-Based Generalization Bound for Finite Base Classifier Spaces

Knowl 2 — AdaBoost Exponential Bound on the Training Margin Distribution

Knowl 3 — Margin-Based Generalization Bound for Base Classifiers with Bounded VC-Dimension

Knowl 4 — Definition of Classification Margin for Voting Classifiers

Knowl 5 — Multiclass Margin-Based Generalization Error Bounds

Knowl 6 — Uniform Convergence Generalization Bounds via Sloppy Covers

Knowl 7 — Margin Distribution Dynamics and Post-Zero Training Error Generalization in AdaBoost

Knowl 8 — Bias-Variance Decomposition Analysis of Boosting vs. Bagging

Knowl 9 — High-Dimensional Margin Geometry: Boosting vs. Support Vector Machines

Knowl 10 — Overfitting via Majority Voting of Simple Functions

Knowl 11 — Quantitative Bound Looseness and Inadequacy of Minimal Margin Maximization

References

Citation

BibTeX

Access the Paper