Back

Soft Margins for AdaBoost

Gunnar RätschT. OnodaKlaus-Robert Müller

article2001Machine-mediated learning1,389 citations

Explains why AdaBoost overfits on noisy data by linking its asymptotic behavior to hard-margin maximization, and proposes soft-margin regularization techniques via gradient descent and mathematical programming to prevent outliers from degrading classification performance.

Listen

Practical automated decision-making and predictive analytics often rely on machine learning ensemble methods, which combine multiple simple prediction models into a stronger, highly accurate composite model. A widely used ensemble method, AdaBoost, performs exceptionally well when training data is clean and separable. However, real-world data in operational settings is frequently contaminated with noise, such as mislabeled records, overlapping class profiles, and extreme outliers. In these noisy environments, traditional boosting methods often suffer from severe overfitting, memorizing noise and producing irregular, complex decision boundaries that degrade real-world classification accuracy.

The article demonstrates why standard boosting fails in the presence of noise and proposes regularized extensions that restore model robustness and generalization. Specifically, the article develops and evaluates soft-margin variations of boosting—including regularized AdaBoost and linear and quadratic programming boosting formulations—which allow the learning process to tolerate misclassifications on unreliable training data.

To establish these insights, the analysis presents both theoretical proofs and extensive empirical evaluations. The theoretical analysis models boosting as an asymptotic optimization process that enforces a hard margin by concentrating sample weights onto the single most difficult data points, mirroring the support vectors of support vector machines. The experimental evaluation compared standard AdaBoost, the proposed regularized algorithms, a single baseline classifier, and support vector machines across 13 benchmark datasets from standard repositories. The testing protocol utilized 100 independent splits per dataset with 200 combined base models, training over three million adaptive radial basis function networks and solving more than one hundred thousand optimization problems.

The findings provide strong evidence regarding the failure modes of standard boosting and the effectiveness of the proposed soft-margin solutions. First, standard AdaBoost asymptotically achieves a hard margin, focusing disproportionately on outliers and resulting in test error rates that are worse than a single baseline model across almost all noisy datasets, showing an average excess error of approximately 11.9% above the optimal benchmark. Second, the proposed regularized AdaBoost algorithm successfully counteracts overfitting, reducing the average excess error to just 1.7% and achieving the top classification performance in 26.0% of all benchmark trials. Third, regularized AdaBoost statistically outperformed standard AdaBoost in 10 out of 13 domains and surpassed support vector machines in 5 of 7 statistically differentiated comparisons. Finally, quadratic programming formulations of boosting outperformed linear programming variants because they favor evenly distributed model weights, which prevents single hypotheses from dominating the ensemble.

These results demonstrate that enforcing a hard margin on imperfect, real-world data is inherently flawed because an automated system should not treat every outlier or mislabeled data point with equal trust. Introducing regularization acts as a controlled level of mistrust, enabling systems to ignore corrupted data points while maintaining smooth and reliable decision boundaries. For organizations deploying predictive models, adopting soft-margin boosting reduces operational risk and improves classification accuracy over both standard boosting and fixed-kernel support vector machines without requiring manual filtering of noisy records.

For practical implementation, organizations working with noisy classification data should adopt regularized AdaBoost over standard AdaBoost or pure hard-margin ensemble methods. When tuning models, engineering teams should use cross-validation to select the regularization constant, balancing margin size against data mistrust. Future initiatives should extend these regularized, soft-margin boosting techniques to continuous regression problems and explore adaptive regularization operators tailored to specific operational noise characteristics.

The findings carry high confidence due to the thorough combination of theoretical proofs and extensive computational validation across multiple benchmark domains. Nevertheless, decision-makers should recognize that model performance depends on selecting an appropriate regularization parameter via cross-validation, and the empirical evaluations were primarily focused on binary classification using neural base learners.

Central Research Institute of Electric Power IndustryGMD FIRSTUniversity of Potsdamadaboost algorithmadaptive regularizationautomated systemsAdaBoostsoft marginmargin classifiers
Rätsch et al (2001).pdf
  • Paper: Stability and Generalization, Olivier Bousquet et al. (2002). This paper develops algorithmic stability bounds that formalize why regularized, soft-margin optimization techniques maintain strong generalization guarantees under data perturbations.
  • Paper: Greedy function approximation: A gradient boosting machine, Jerome H. Friedman (2001). This work generalizes boosting into a gradient-descent optimization framework in function space, introducing robust loss functions like Huber loss to tackle noisy data.
  • Paper: Boosting for transfer learning, Wenyuan Dai et al. (2007). This paper extends boosting reweighting mechanisms to transfer learning by actively downweighting misaligned or conflicting training instances from source distributions.
  • Paper: Online Passive-Aggressive Algorithms, Koby Crammer et al. (2003). This work applies linear and quadratic soft-margin slack penalties to online margin-based learning to achieve robust classification in noisy environments.
  • Paper: XGBoost: A Scalable Tree Boosting System, Tianqi Chen et al. (2016). This paper incorporates formal second-order regularized objective functions into large-scale tree boosting to control model complexity and prevent overfitting.
  • Paper: Predicting good probabilities with supervised learning, Alexandru Niculescu-Mizil et al. (2005). This study analyzes the severe probability-calibration distortions produced by maximum-margin boosted ensembles and provides post-processing calibration methods.
  • Paper: BART: Bayesian Additive Regression Trees, Hugh A. Chipman et al. (2008). This article develops a Bayesian approach to additive tree ensembles that relies on explicit regularization priors to prevent overfitting without hard-margin asymptotic behavior.
  • Paper: Learning From Noisy Labels With Deep Neural Networks: A Survey, Hwanjun Song et al. (2020). This survey provides a comprehensive taxonomy of modern loss adjustment, sample selection, and robust regularization methods developed to handle severe label noise.
Cover for Soft Margins for AdaBoost

Abstract

Recently ensemble methods like ADABOOST have been applied successfully in many problems, while seemingly defying the problems of overfitting.

ADABOOST rarely overfits in the low noise regime, however, we show that it clearly does so for higher noise levels. Central to the understanding of this fact is the margin distribution. ADABOOST can be viewed as a constraint gradient descent in an error function with respect to the margin. We find that ADABOOST asymptotically achieves a hard margin distribution, i.e. the algorithm concentrates its resources on a few hard-to-learn patterns that are interestingly very similar to Support Vectors. A hard margin is clearly a sub-optimal strategy in the noisy case, and regularization, in our case a “mistrust” in the data, must be introduced in the algorithm to alleviate the distortions that single difficult patterns (e.g. outliers) can cause to the margin distribution. We propose several regularization methods and generalizations of the original ADABOOST algorithm to achieve a soft margin. In particular we suggest (1) regularized ADABOOSTREG where the gradient decent is done directly with respect to the soft margin and (2) regularized linear and quadratic programming (LP/QP-) ADABOOST, where the soft margin is attained by introducing slack variables.

Extensive simulations demonstrate that the proposed regularized ADABOOST-type algorithms are useful and yield competitive results for noisy data.

Topics

adaboost algorithmadaptive regularizationautomated systemsbase learnersbinary classificationboostingcross validationdata pointsnoisy environmentoptimization

Keywords

AdaBoostsoft marginmargin classifiershard margin classificationmargin distributionssupport vector learningensemble learning methodslinear programmingbinary classificationquadratic optimization

Table of Contents

  • 1. Introduction
  • 2. Analysis of ADABOOST's learning process
  • 2.1. Algorithm
  • 2.2. Error function of ADABOOST
  • 2.3. ADABOOST as an annealing process
  • 2.4. Asymptotic analysis
  • 3. Hard margin and overfitting
  • 4. Improvements using a soft margin
  • 4.1. Margin vs. influence of a pattern
  • 4.2. Linear programming with slack variables
  • 4.3. Quadratic programming and the connection to support vector machines
  • 5. Experiments
  • 5.1. Experimental setup
  • 5.2. Experimental results
  • 6. Conclusion
  • Appendix
  • B. Proof of Theorem 3
  • C. Proof of Lemma 5
  • D. RBF nets with adaptive centers
  • Acknowledgments
  • Notes
  • References

Knowls

  1. Knowl 1 — Regularized AdaBoost Algorithm

    algorithm

    The AdaBoostReg\text{AdaBoost}_{\text{Reg}} algorithm modifies standard AdaBoost to construct a soft margin by penalizing patterns with high cumulative influence, preventing the ensemble from overfitting to noisy patterns or outliers.

    Input: Training examples Z=((x1,y1),…,(xl,yl))Z = ((x_1, y_1), \dots, (x_l, y_l)) where xi∈Xx_i \in \mathcal{X} and yi∈{−1,+1}y_i \in \{-1, +1\}, number of iterations TT, regularization constant C>0C > 0, influence exponent p≥1p \ge 1 (typically p=2p = 2), upper bound Γ\Gamma.
    Initialize: w1(zi)=1/lw_1(z_i) = 1/l for all i=1,…,li = 1, \dots, l, and cumulative influence μ0(zi)=0\mu_0(z_i) = 0.
    for t=1t = 1 to TT:
        1. Train base classifier with respect to weighted sample set {Z,wt}\{Z, w_t\} to obtain hypothesis ht:X→{−1,+1}h_t: \mathcal{X} \to \{-1, +1\}.
        2. Find hypothesis weight bt≥0b_t \ge 0 by minimizing the regularized potential functional:
           bt=argminbt≥0∑i=1lexp⁡(−12[ρ(zi,bt)+C∣bt∣μt(zi)p])b_t = \text{argmin}_{b_t \ge 0} \sum_{i=1}^l \exp\left( -\frac{1}{2} \left[ \rho(z_i, b^t) + C |b^t| \mu_t(z_i)^p \right] \right)
           where ρ(zi,bt)=yi∑r=1tbrhr(xi)\rho(z_i, b^t) = y_i \sum_{r=1}^t b_r h_r(x_i), ∣bt∣=∑r=1tbr|b^t| = \sum_{r=1}^t b_r, and μt(zi)=∑r=1tcrwr(zi)\mu_t(z_i) = \sum_{r=1}^t c_r w_r(z_i) with cr=br/∣bt∣c_r = b_r / |b^t|.
        3. if bt=0b_t = 0 or bt≥Γb_t \ge \Gamma, abort the loop.
        4. Update sample distribution wt+1(zi)w_{t+1}(z_i) for each i=1,…,li = 1, \dots, l:
           wt+1(zi)=1Ztexp⁡(−12[ρ(zi,bt)+C∣bt∣μt(zi)p])w_{t+1}(z_i) = \frac{1}{Z_t} \exp\left( -\frac{1}{2} \left[ \rho(z_i, b^t) + C |b^t| \mu_t(z_i)^p \right] \right)
           where ZtZ_t normalizes ∑i=1lwt+1(zi)=1\sum_{i=1}^l w_{t+1}(z_i) = 1.
    Output: Combined hypothesis f(x)=∑t=1Tctht(x)f(x) = \sum_{t=1}^T c_t h_t(x) with normalized weights ct=bt/∑r=1Tbrc_t = b_t / \sum_{r=1}^T b_r, giving classification f~(x)=sign(f(x))\tilde{f}(x) = \text{sign}(f(x)).

    The line search for btb_t has a unique minimum because the objective is strictly convex for bt>0b_t > 0 when base error is bounded below 1/21/2.

  2. Knowl 2 — Soft Margin Formulation and Exponential Loss Regularization in AdaBoost

    model/method

    To prevent AdaBoost from enforcing a hard margin on mislabeled points and outliers, a non-negative mistrust variable ζ(zi)\zeta(z_i) is introduced to relax the margin constraint ρ(zi,c)≥ϱ\rho(z_i, c) \ge \varrho into a soft margin condition:

    ρ~(zi,c):=ρ(zi,c)+Cζ(zi)≥ϱ\tilde{\rho}(z_i, c) := \rho(z_i, c) + C \zeta(z_i) \ge \varrho

    where ρ(zi,c)=yif(xi)=yi∑t=1Tctht(xi)\rho(z_i, c) = y_i f(x_i) = y_i \sum_{t=1}^T c_t h_t(x_i) is the classification margin of pattern zi=(xi,yi)z_i = (x_i, y_i), c=[c1,…,cT]c = [c_1, \dots, c_T] are hypothesis weights with ∑tct=1\sum_t c_t = 1, and C>0C > 0 is a regularization hyperparameter.

    The mistrust function is defined by the cumulative influence of pattern ziz_i over boosting steps:

    ζ(zi)=μt(zi)p,whereμt(zi)=∑r=1tcrwr(zi)\zeta(z_i) = \mu_t(z_i)^p, \quad \text{where} \quad \mu_t(z_i) = \sum_{r=1}^t c_r w_r(z_i)

    with p≥1p \ge 1 (typically p=2p=2).

    The regularized potential function optimized at step tt is:

    GReg(bt)=∑i=1lexp⁡(−12∣bt∣[ρ(zi,ct)+Cμt(zi)p])G_{\text{Reg}}(b^t) = \sum_{i=1}^l \exp\left( -\frac{1}{2} |b^t| \left[ \rho(z_i, c^t) + C \mu_t(z_i)^p \right] \right)

    where ∣bt∣=∑r=1tbr|b^t| = \sum_{r=1}^t b_r and ct=bt/∣bt∣c^t = b^t / |b^t|.

    For p=1p=1, the pattern weight update reduces to:

    wt+1(zi)=wt(zi)Ztexp⁡(btI(yi≠ht(xi))−Cμt(zi)∣bt∣)w_{t+1}(z_i) = \frac{w_t(z_i)}{Z_t} \exp\left( b_t I(y_i \ne h_t(x_i)) - C \mu_t(z_i) |b^t| \right)

    For p=2p=2, the pattern weight update is:

    wt+1(zi)=wt(zi)Ztexp⁡(btI(yi≠ht(xi))−Cμt(zi)2∣bt∣+Cμt−1(zi)2∣bt−1∣)w_{t+1}(z_i) = \frac{w_t(z_i)}{Z_t} \exp\left( b_t I(y_i \ne h_t(x_i)) - C \mu_t(z_i)^2 |b^t| + C \mu_{t-1}(z_i)^2 |b^{t-1}| \right)

    where ZtZ_t is the normalization factor ensuring ∑i=1lwt+1(zi)=1\sum_{i=1}^l w_{t+1}(z_i) = 1.

  3. Knowl 3 — Linear Programming Soft-Margin Boosting Algorithm

    algorithm

    The LPReg-AdaBoost\text{LP}_{\text{Reg}}\text{-AdaBoost} algorithm post-processes an ensemble of hypotheses generated by AdaBoost by solving a linear program that maximizes a soft margin via slack variables ξi\xi_i.

    Input: Labeled examples Z=((x1,y1),…,(xl,yl))Z = ((x_1, y_1), \dots, (x_l, y_l)), number of hypotheses TT, regularization constant C>0C > 0.
    1. Run AdaBoost to generate TT hypotheses h1,…,hTh_1, \dots, h_T.
    2. Compute the margin matrix M∈{−1,+1}l×TM \in \{-1, +1\}^{l \times T} with entries:
       Mi,t=yiht(xi)M_{i,t} = y_i h_t(x_i)
    3. Solve the linear program for weights c∈RTc \in \mathbb{R}^T, margin ϱ∈R\varrho \in \mathbb{R}, and slack variables ξ∈Rl\xi \in \mathbb{R}^l:
       Maximize ϱ−Cl∑i=1lξi\varrho - \frac{C}{l} \sum_{i=1}^l \xi_i
       subject to:
           ∑t=1TctMi,t≥ϱ−ξi\sum_{t=1}^T c_t M_{i,t} \ge \varrho - \xi_i for all i=1,…,li = 1, \dots, l
           ξi≥0\xi_i \ge 0 for all i=1,…,li = 1, \dots, l
           ct≥0c_t \ge 0 for all t=1,…,Tt = 1, \dots, T
           ∑t=1Tct=1\sum_{t=1}^T c_t = 1
    Output: Ensemble hypothesis f(x)=∑t=1Tctht(x)f(x) = \sum_{t=1}^T c_t h_t(x) with prediction f~(x)=sign(f(x))\tilde{f}(x) = \text{sign}(f(x)).

    The slack variables ξi\xi_i allow misclassified or noisy patterns to attain margins below ϱ\varrho. The parameter ν:=1/C∈[0,1]\nu := 1/C \in [0, 1] serves asymptotically as an upper bound on the fraction of margin errors and a lower bound on the fraction of support patterns.

  4. Knowl 4 — Quadratic Programming Soft-Margin Boosting Algorithm

    algorithm

    The QPReg-AdaBoost\text{QP}_{\text{Reg}}\text{-AdaBoost} algorithm determines ensemble weights by minimizing the ℓ2\ell_2-norm of unnormalized hypothesis weights together with penalized soft-margin slack variables, drawing an explicit equivalence to Support Vector Machine optimization.

    Input: Labeled examples Z=((x1,y1),…,(xl,yl))Z = ((x_1, y_1), \dots, (x_l, y_l)), number of hypotheses TT, regularization constant C>0C > 0.
    1. Run AdaBoost to obtain TT hypotheses h1,…,hTh_1, \dots, h_T.
    2. Compute the margin matrix M∈{−1,+1}l×TM \in \{-1, +1\}^{l \times T} where Mi,t=yiht(xi)M_{i,t} = y_i h_t(x_i).
    3. Solve the quadratic program for unnormalized weights b∈RTb \in \mathbb{R}^T and slack variables ξ∈Rl\xi \in \mathbb{R}^l:
       Minimize ∥b∥22+Cl∑i=1lξi\|b\|_2^2 + \frac{C}{l} \sum_{i=1}^l \xi_i
       subject to:
           ∑t=1TbtMi,t≥1−ξi\sum_{t=1}^T b_t M_{i,t} \ge 1 - \xi_i for all i=1,…,li = 1, \dots, l
           bt≥0b_t \ge 0 for all t=1,…,Tt = 1, \dots, T
           ξi≥0\xi_i \ge 0 for all i=1,…,li = 1, \dots, l
    Output: Ensemble hypothesis f(x)=∑t=1Tctht(x)f(x) = \sum_{t=1}^T c_t h_t(x) where ct=bt/∑r=1Tbrc_t = b_t / \sum_{r=1}^T b_r, with prediction f~(x)=sign(f(x))\tilde{f}(x) = \text{sign}(f(x)).

    Penalizing ∥b∥22\|b\|_2^2 encourages more uniform hypothesis weights across the ensemble, reducing ensemble complexity compared to the sparse solutions generated by linear programming.

  5. Knowl 5 — AdaBoost Margin Optimization as Constrained Gradient Descent

    theoretical result

    For an AdaBoost-type algorithm parameterized by ϕ∈(0,1)\phi \in (0, 1) (where ϕ=1/2\phi = 1/2 corresponds to standard AdaBoost), the training process performs constrained gradient descent on the exponential margin functional:

    G(bt,bt−1)=∑i=1lexp⁡(−ρ(zi,bt)+∣bt∣(12−ϕ))G(b^t, b^{t-1}) = \sum_{i=1}^l \exp\left( -\rho(z_i, b^t) + |b^t| \left( \frac{1}{2} - \phi \right) \right)

    where zi=(xi,yi)z_i = (x_i, y_i), ρ(zi,bt)=yi∑r=1tbrhr(xi)\rho(z_i, b^t) = y_i \sum_{r=1}^t b_r h_r(x_i), and ∣bt∣=∑r=1tbr|b^t| = \sum_{r=1}^t b_r.

    The updated pattern distribution wt+1w_{t+1} in iteration tt is exactly equal to the normalized negative gradient of G(bt+1,bt)G(b^{t+1}, b^t) with respect to the pattern margins ρ(zi,bt)\rho(z_i, b^t):

    wt+1(zi)=∂G(bt+1,bt)∂ρ(zi,bt)∑j=1l∂G(bt+1,bt)∂ρ(zj,bt)w_{t+1}(z_i) = \frac{\frac{\partial G(b^{t+1}, b^t)}{\partial \rho(z_i, b^t)}}{\sum_{j=1}^l \frac{\partial G(b^{t+1}, b^t)}{\partial \rho(z_j, b^t)}}

    Selecting the next base hypothesis hth_t to minimize the weighted training error ϵt=∑i=1lwt(zi)I(ht(xi)≠yi)\epsilon_t = \sum_{i=1}^l w_t(z_i) I(h_t(x_i) \ne y_i) corresponds to identifying the steepest descent direction in hypothesis space, while setting bt=log⁡(ϕ(1−ϵt)ϵt(1−ϕ))b_t = \log\left( \frac{\phi(1-\epsilon_t)}{\epsilon_t(1-\phi)} \right) performs the optimal line search step size.

  6. Knowl 6 — Soft-Max Annealing Property and Asymptotic Hard Margin in AdaBoost

    theoretical result

    The pattern weight distribution generated by an AdaBoost-type algorithm can be expressed as a soft-max function parameterized by the total hypothesis weight ∣bt∣=∑r=1tbr|b^t| = \sum_{r=1}^t b_r:

    wt+1(zi)=exp⁡(−12ρ(zi,ct)∣bt∣)∑j=1lexp⁡(−12ρ(zj,ct)∣bt∣)w_{t+1}(z_i) = \frac{\exp\left( -\frac{1}{2} \rho(z_i, c^t) |b^t| \right)}{\sum_{j=1}^l \exp\left( -\frac{1}{2} \rho(z_j, c^t) |b^t| \right)}

    where ct=bt/∣bt∣c^t = b^t / |b^t| and ρ(zi,ct)=yi∑r=1tcrhr(xi)∈[−1,1]\rho(z_i, c^t) = y_i \sum_{r=1}^t c_r h_r(x_i) \in [-1, 1].

    If the weighted base training errors are strictly bounded away from ϕ\phi such that ϵt≤ϕ−Δ\epsilon_t \le \phi - \Delta for some constant Δ>0\Delta > 0, then ∣bt∣|b^t| increases at least linearly with the iteration index tt (∣bt∣>γt|b^t| > \gamma t for a constant γ>0\gamma > 0).

    As ∣bt∣→∞|b^t| \to \infty, the parameter ∣bt∣|b^t| acts as an annealing parameter. The soft-max converges to the hard maximum operation:

    lim⁡∣bt∣→∞−1∣bt∣log⁡G(bt)=min⁡i=1,…,lρ(zi,ct)\lim_{|b^t| \to \infty} -\frac{1}{|b^t|} \log G(b^t) = \min_{i=1, \dots, l} \rho(z_i, c^t)

    Consequently, AdaBoost asymptotically concentrates all probability mass on the subset of patterns possessing the smallest margin, enforcing a hard margin classifier on the training set.

  7. Knowl 7 — Lower Bound on the Asymptotic Classification Margin for AdaBoost-Type Algorithms

    theoretical result

    For an AdaBoost-type algorithm with parameter ϕ∈(0,1)\phi \in (0, 1) running for TT iterations with weighted classification errors ϵ1,…,ϵT\epsilon_1, \dots, \epsilon_T satisfying max⁡tϵt<ϕ\max_{t} \epsilon_t < \phi, the training margin distribution satisfies for all θ∈[−1,1]\theta \in [-1, 1]:

    1l∑i=1lI(yif(xi)≤θ)≤(Φ1+θ2+Φ−1−θ2)T∏t=1Tϵt1−θ(1−ϵt)1+θ\frac{1}{l} \sum_{i=1}^l I(y_i f(x_i) \le \theta) \le \left( \Phi^{\frac{1+\theta}{2}} + \Phi^{-\frac{1-\theta}{2}} \right)^T \prod_{t=1}^T \sqrt{\epsilon_t^{1-\theta} (1 - \epsilon_t)^{1+\theta}}

    where Φ=ϕ1−ϕ\Phi = \frac{\phi}{1-\phi} and f(x)=∑t=1Tctht(x)f(x) = \sum_{t=1}^T c_t h_t(x) is the combined classifier.

    Asymptotically (T→∞T \to \infty), the minimal classification margin ϱ=min⁡iyif(xi)\varrho = \min_{i} y_i f(x_i) is bounded from below by:

    ϱ≥ln⁡(ϕϵ−1)+ln⁡((1−ϕ)(1−ϵ)−1)ln⁡(ϕϵ−1)−ln⁡((1−ϕ)(1−ϵ)−1)\varrho \ge \frac{\ln(\phi \epsilon^{-1}) + \ln((1-\phi)(1-\epsilon)^{-1})}{\ln(\phi \epsilon^{-1}) - \ln((1-\phi)(1-\epsilon)^{-1})}

    where ϵ=max⁡tϵt\epsilon = \max_t \epsilon_t, provided ϵ≤(1−ϱ)/2\epsilon \le (1-\varrho)/2 holds.

  8. Knowl 8 — Asymptotic Equalization of Class Margins and Support Patterns

    theoretical result

    In the learning process of an AdaBoost-type algorithm, the smallest margin of the positive training patterns and the smallest margin of the negative training patterns asymptotically converge to the exact same value:

    lim⁡t→∞min⁡i:yi=+1ρ(zi,ct)=lim⁡t→∞min⁡j:yj=−1ρ(zj,ct)\lim_{t \to \infty} \min_{i: y_i = +1} \rho(z_i, c^t) = \lim_{t \to \infty} \min_{j: y_j = -1} \rho(z_j, c^t)

    provided two conditions hold:

    1. The hypothesis weights are uniformly bounded from below and above: 0<γ<bt<Γ<∞0 < \gamma < b_t < \Gamma < \infty.
    2. The base learning algorithm can classify all instances into a single class s∈{−1,+1}s \in \{-1, +1\} whenever the total sample weight of class ss exceeds a fixed threshold δ∈(0,1)\delta \in (0, 1):

    ∑i:yi=sw(zi)>δ  ⟹  h(xi)=sfor all i=1,…,l\sum_{i: y_i = s} w(z_i) > \delta \implies h(x_i) = s \quad \text{for all } i = 1, \dots, l

    The subset of training patterns that asymptotically attain this shared minimal margin are called Support Patterns, forming an exact analogue to Support Vectors in separable Support Vector Machines.

  9. Knowl 9 — Generalization Error Comparison Across 13 Benchmark Datasets

    data/table

    The test error rates (mean ±\pm standard deviation over 100 random splits into roughly 60% training and 40% testing) for Single RBF network, standard AdaBoost (AB), AdaBoostReg\text{AdaBoost}_{\text{Reg}} (ABR; p=2p=2), LPReg-AdaBoost\text{LP}_{\text{Reg}}\text{-AdaBoost} (LPR-AB), QPReg-AdaBoost\text{QP}_{\text{Reg}}\text{-AdaBoost} (QPR-AB), and Support Vector Machine (SVM with RBF kernel) combining 200 base hypotheses:

    Dataset RBF AB ABR LPR-AB QPR-AB SVM
    Banana 10.8 ±\pm 0.6 12.3 ±\pm 0.7 10.9 ±\pm 0.4 10.7 ±\pm 0.4 10.9 ±\pm 0.5 11.5 ±\pm 0.7
    B. Cancer 27.6 ±\pm 4.7 30.4 ±\pm 4.7 26.5 ±\pm 4.5 26.8 ±\pm 6.1 25.9 ±\pm 4.6 26.0 ±\pm 4.7
    Diabetes 24.3 ±\pm 1.9 26.5 ±\pm 2.3 23.8 ±\pm 1.8 24.1 ±\pm 1.9 25.4 ±\pm 2.2 23.5 ±\pm 1.7
    German 24.7 ±\pm 2.4 27.5 ±\pm 2.5 24.3 ±\pm 2.1 24.8 ±\pm 2.2 25.3 ±\pm 2.1 23.6 ±\pm 2.1
    Heart 17.6 ±\pm 3.3 20.3 ±\pm 3.4 16.5 ±\pm 3.5 17.5 ±\pm 3.5 17.2 ±\pm 3.4 16.0 ±\pm 3.3
    Image 3.3 ±\pm 0.6 2.7 ±\pm 0.7 2.7 ±\pm 0.6 2.8 ±\pm 0.6 2.7 ±\pm 0.6 3.0 ±\pm 0.6
    Ringnorm 1.7 ±\pm 0.2 1.9 ±\pm 0.3 1.6 ±\pm 0.1 2.2 ±\pm 0.5 1.9 ±\pm 0.2 1.7 ±\pm 0.1
    F. Solar 34.4 ±\pm 2.0 35.7 ±\pm 1.8 34.2 ±\pm 2.2 34.7 ±\pm 2.0 36.2 ±\pm 1.8 32.4 ±\pm 1.8
    Splice 10.0 ±\pm 1.0 10.1 ±\pm 0.5 9.5 ±\pm 0.7 10.2 ±\pm 1.6 10.1 ±\pm 0.5 10.9 ±\pm 0.7
    Thyroid 4.5 ±\pm 2.1 4.4 ±\pm 2.2 4.6 ±\pm 2.2 4.6 ±\pm 2.2 4.4 ±\pm 2.2 4.8 ±\pm 2.2
    Titanic 23.3 ±\pm 1.3 22.6 ±\pm 1.2 22.6 ±\pm 1.2 24.0 ±\pm 4.4 22.7 ±\pm 1.1 22.4 ±\pm 1.0
    Twonorm 2.9 ±\pm 0.3 3.0 ±\pm 0.3 2.7 ±\pm 0.2 3.2 ±\pm 0.4 3.0 ±\pm 0.3 3.0 ±\pm 0.2
    Waveform 10.7 ±\pm 1.1 10.8 ±\pm 0.6 9.8 ±\pm 0.8 10.5 ±\pm 1.0 10.1 ±\pm 0.5 9.9 ±\pm 0.4
    Mean% 6.6 ±\pm 5.8 11.9 ±\pm 7.9 1.7 ±\pm 1.9 8.9 ±\pm 10.8 5.8 ±\pm 5.5 4.6 ±\pm 5.4
    Winner% 14.8 ±\pm 8.5 7.2 ±\pm 7.8 26.0 ±\pm 12.4 14.4 ±\pm 8.6 13.2 ±\pm 7.6 23.5 ±\pm 18.0

    'Mean%' measures the average percentage excess error relative to the best method across all 13 benchmarks. 'Winner%' is the Laplacian probability of having the lowest generalization error on a realization. AdaBoostReg\text{AdaBoost}_{\text{Reg}} achieves the best overall performance, significantly outperforming standard AdaBoost on 10 of the 13 datasets (95% t-test).

  10. Knowl 10 — Adaptive Radial Basis Function Base Classifier

    algorithm

    The base learning algorithm used in the boosting experiments is an adaptive Radial Basis Function (RBF) network whose centers μk\mu_k, widths σk\sigma_k, and output linear weights wkw_k are jointly adapted to minimize a regularized squared error function.

    Input: Training set Z=((x1,y1),…,(xl,yl))Z = ((x_1, y_1), \dots, (x_l, y_l)), number of RBF centers KK, regularization parameter λ\lambda (fixed to 10−610^{-6}), number of conjugate gradient iterations OO.
    Initialize: Compute initial centers μk\mu_k (k=1,…,Kk=1,\dots,K) using KK-means clustering. Set initial widths σk\sigma_k to the distance between μk\mu_k and the closest neighboring center μi\mu_i (i≠ki \ne k).
    for o=1o = 1 to OO:
        1. Compute optimal output weights in closed form:
           w=(GTG+2λlI)−1GTyw = \left( G^T G + \frac{2\lambda}{l} I \right)^{-1} G^T y
           where Gik=exp⁡(−∥xi−μk∥22σk2)G_{ik} = \exp\left( -\frac{\|x_i - \mu_k\|^2}{2\sigma_k^2} \right), y=[y1,…,yl]Ty = [y_1, \dots, y_l]^T, and II is the identity matrix.
        2. Compute gradients of E=12∑i=1l(yi−f(xi))2+λ2l∑k=1Kwk2E = \frac{1}{2} \sum_{i=1}^l (y_i - f(x_i))^2 + \frac{\lambda}{2l} \sum_{k=1}^K w_k^2 with respect to μk\mu_k and σk\sigma_k:
           ∂E∂μk=∑i=1l(f(xi)−yi)wkxi−μkσk2gk(xi)\frac{\partial E}{\partial \mu_k} = \sum_{i=1}^l (f(x_i) - y_i) w_k \frac{x_i - \mu_k}{\sigma_k^2} g_k(x_i)
           ∂E∂σk=∑i=1l(f(xi)−yi)wk∥μk−xi∥2σk3gk(xi)\frac{\partial E}{\partial \sigma_k} = \sum_{i=1}^l (f(x_i) - y_i) w_k \frac{\|\mu_k - x_i\|^2}{\sigma_k^3} g_k(x_i)
        3. Form conjugate direction vector vˉ\bar{v} via Fletcher-Reeves-Polak-Ribiere method.
        4. Perform line search to find step size δ\delta minimizing EE along vˉ\bar{v}, recomputing optimal ww via step 1 at every evaluation.
        5. Update μk\mu_k and σk\sigma_k using vˉ\bar{v} and δ\delta.
    Output: Optimized RBF hypothesis h(x)=sign(∑k=1Kwkexp⁡(−∥x−μk∥22σk2))h(x) = \text{sign}\left( \sum_{k=1}^K w_k \exp\left( -\frac{\|x - \mu_k\|^2}{2\sigma_k^2} \right) \right).

    When incorporated into AdaBoost, the squared loss is weighted by the sample distribution wt(zi)w_t(z_i).

Coverage note — No substantial contributed material was omitted; all key theoretical analyses, regularized boosting algorithms, base learner specifications, and empirical benchmarks are captured.

References

  1. 1.Bennett, K. (1998). Combining support vector and mathematical programming methods for induction. In B. Schölkopf, C. Burges, & A. Smola (Eds.), Advances in kernel methods—SV learning. Cambridge, MA: MIT Press.
  2. 2.Bennett, K. & Mangasarian, O. (1992). Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods and Software, 1, 23–34.
  3. 3.Bertoni, A., Campadelli, P., & Parodi, M. (1997). A boosting algorithm for regression. In W. Gerstner, A. Germond, M. Hasler, & J.-D. Nicoud (Eds.), LNCS, Vol. V: Proceedings ICANN’97: Int. Conf. on Artificial Neural Networks (pp. 343–348). Berlin: Springer.
  4. 4.Bishop, C. (1995). Neural Networks for Pattern Recognition. Oxford: Clarendon Press.
  5. 5.Boser, B., Guyon, I., & Vapnik, V. (1992). A training algorithm for optimal margin classifiers. In D. Haussler (Ed.), Proceedings COLT’92: Conference on Computational Learning Theory (pp. 144–152). New York, NY: ACM Press.
  6. 6.Breiman, L. (1996). Bagging predictors. Mechine Learning, 26(2), 123–140.
  7. 7.Breiman, L. (1997a). Arcing the edge. Technical Report 486, Statistics Department, University of California.
  8. 8.Breiman, L. (1997b). Prediction games and arcing algorithms. Technical Report 504, Statistics Department, University of California.
  9. 9.Breiman, L. (1998). Arcing classifiers. The Annals of Statistics, 26(3), 801–849.
  10. 10.Breiman, L. (1999). Using adaptive bagging to debias regressions. Technical Report 547, Statistics Department, University of California.
  11. 11.Cortes, C. & Vapnik, V. (1995). Support vector networks. Machine Learning, 20, 273–297.
  12. 12.Frean, M. & Downs, T. (1998). A simple cost function for boosting. Technical Report, Department of Computer Science and Electrical Engineering, University of Queensland.
  13. 13.Freund, Y. & Schapire, R. (1994). A decision-theoretic generalization of on-line learning and an application to boosting. In Proceedings EuroCOLT’94: European Conference on Computational Learning Theory. LNCS.
  14. 14.Freund, Y. & Schapire, R. (1996). Game theory, on-line prediction and boosting. In Proceedings COLT’86: Conf. on Comput. Learning Theory (pp. 325–332). New York, NY: ACM Press.
  15. 15.Friedman, J. (1999). Greedy function approximation. Technical Report, Department of Statistics, Stanford University.
  16. 16.Friedman, J., Hastie, T., & Tibshirani, R. (1998). Additive logistic regression: A statistical view of boosting. Technical Report, Department of Statistics, Sequoia Hall, Stanford University.
  17. 17.Frieß, T. & Harrison, R. (1998). Perceptrons in kernel feature space. Research Report RR-720, Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK.
  18. 18.Grove, A. & Schuurmans, D. (1998). Boosting in the limit: Maximizing the margin of learned ensembles. In Proceedings of the Fifteenth National Conference on Artifical Intelligence.
  19. 19.Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. J. Statistical Physics, 34, 975–986.
  20. 20.LeCun, Y., Jackel, L., Bottou, L., Cortes, C., Denker, J., Drucker, H., Guyon, I., Müller, U., Säckinger, E., Simard, P., & Vapnik, V. (1995). Learning algorithms for classification: A comparism on handwritten digit recognition. Neural Networks, 261–276.
  21. 21.Mangasarian, O. (1965). Linear and nonlinear separation of patterns by linear programming. Operations Research, 13, 444–452.
  22. 22.Mason, L., Bartlett, P. L., & Baxter, J. (2000a). Improved generalization through explicit optimization of margins. Machine Learning 38(3), 243–255.
  23. 23.Mason, L., Baxter, J., Bartlett, P. L., & Frean, M. (2000b). Functional gradient techniques for combining hypotheses. In A. J. Smola, P. Bartlett, B. Schölkopf, & C. Schuurmans (Eds.), Advances in Large Margin Classifiers. Cambridge, MA: MIT Press.
  24. 24.Moody, J. & Darken, C. (1989). Fast learning in networks of locally-tuned processing units. Neural Computation, 1(2), 281–294.
  25. 25.Müller, K.-R., Smola, A., Rätsch, G., Schölkopf, B., Kohlmorgen, J., & Vapnik, V. (1998). Using support vector machines for time series prediction. In B. Schölkopf, C. Burges, & A. Smola (Eds.), Advances in Kernel Methods—Support Vector Learning. Cambridge, MA: MIT Press.
  26. 26.Onoda, T., Rätsch, G., & Müller, K.-R. (1998). An asymptotic analysis of ADABOOST in the binary classification case. In L. Niklasson, M. Bodén, & T. Ziemke (Eds.), Proceedings ICANN’98: Int. Conf. on Artificial Neural Networks (pp. 195–200).
  27. 27.Onoda, T., Rätsch, G., & Müller, K.-R. (2000). An asymptotical analysis and improvement of ADABOOST in the binary classification case. Journal of Japanese Society for AI, 15(2), 287–296 (in Japanese).
  28. 28.Press, W., Flannery, B., Teukolsky, S., & Vetterling, W. (1992). Numerical Recipes in C (2nd ed.). Cambridge: Cambridge University Press.
  29. 29.Quinlan, J. (1992). C4.5: Programs for Machine Learning. Los Altos, CA: Morgan Kaufmann.
  30. 30.Quinlan, J. (1996). Boosting first-order learning. In S. Arikawa & A. Sharma (Eds.), LNAI, Vol. 1160: Proceedings of the 7th International Workshop on Algorithmic Learning Theory (pp. 143–155). Berlin: Springer.
  31. 31.Rätsch, G. (1998). Ensemble learning methods for classification. Master’s Thesis, Department of Computer Science, University of Potsdam, Germany (in German).
  32. 32.Rätsch, G., Onoda, T., & Müller, K.-R. (1998). Soft margins for ADABOOST. Technical Report NC-TR-1998-021, Department of Computer Science, Royal Holloway, University of London, Egham, UK.
  33. 33.Rätsch, G., Onoda, T., & Müller, K.-R. (1999). Regularizing ADABOOST. In M. Kearns, S. Solla, & D. Cohn (Eds.), Advances in Neural Information Processing Systems 11 (pp. 564–570). Cambridge, MA: MIT Press.
  34. 34.Rätsch, G., Schölkopf, B., Smola, A., Mika, S., Onoda, T., & Müller, K.-R. (2000). Robust ensemble learning. In A. Smola, P. Bartlett, B. Schölkopf, & D. Schuurmans (Eds.), Advances in Large Margin Classifiers(pp. 207–219). Cambridge, MA: MIT Press.
  35. 35.Rätsch, G., Warmuth, M., Mika, S., Onoda, T., Lemm, S., & Müller, K.-R. (2000). Barrier boosting. In Proceedings COLT’00: Conference on Computational Learning Theory (pp. 170–179). Los Altos, CA: Morgan Kaufmann.
  36. 36.Rokui, J. & Shimodaira, H. (1998). Improving the generalization performance of the minimum classification error learning and its application to neural networks. In Proc. of the Int. Conf. on Neural Information Processing (ICONIP) (pp. 63–66). Japan, Kitakyushu.
  37. 37.Schapire, R. (1999). Theoretical views of boosting. In Proceedings EuroCOLT’99: European Conference on Computational Learning Theory.
  38. 38.Schapire, R., Freund, Y., Bartlett, P., & Lee, W. (1997). Boosting the margin: A new explanation for the effectiveness of voting methods. In Proceedings ICML’97: International Conference on Machine Learning (pp. 322–330). Los Altos, CA: Morgan Kaufmann.
  39. 39.Schapire, R. & Singer, Y. (1998). Improved boosting algorithms using confidence-rated predictions. In Proceedings COLT’98: Conference on Computational Learning Theory (pp. 80–91).
  40. 40.Schölkopf, B. (1997). Support Vector Learning. R. Oldenbourg Verlag, Berlin.
  41. 41.Schölkopf, B., Smola, A., & Williamson, R. (2000). New support vector algorithms. Neural Computation. also NeuroCOLT TR–31–89, 12:1083–1121.
  42. 42.Schwenk, H. & Bengio, Y. (1997). AdaBoosting neural networks. In W. Gerstner, A. Germond, M. Hasler, & J.-D. Nicoud (Eds.), Proceedings ICANN’97: Int. Conf. on Artificial Neural Networks, Vol. 1327 of LNCS (pp. 967–972). Berlin: Springer.
  43. 43.Smola, A. J. (1998). Learning with kernels. Ph.D. Thesis, Technische Universität Berlin.
  44. 44.Smola, A., Schölkopf, B., & Müller, K.-R. (1998). The connection between regularization operators and support vector kernels. Neural Networks, 11, 637–649.
  45. 45.Tikhonov, A. & Arsenin, V. (1977). Solutions of Ill-Posed Problems. Washington, D.C.: W.H. Winston.
  46. 46.Vapnik, V. (1995). The Nature of Statistical Learning Theory. Berlin: Springer.
  47. 47.Weston, J. (1999). LOO-support vector machines. In Proceedings of IJCNN’99.
  48. 48.Weston, J., Gammerman, A., Stitson, M. O., Vapnik, V., Vovk, V., & Watkins, C. (1997). Density estimation using SV machines. Technical Report CSD-TR-97-23, Royal Holloway, University of London, Egham, UK.

Citation

MLA
Rätsch, G., et al. “Soft Margins for AdaBoost”. Machine Learning, vol. 42, no. 3, 2001, pp. 287–320, https://doi.org/10.1023/A:1007618119488.
APA
Rätsch, G., Onoda, T., & Müller, K.-R. (2001). Soft Margins for AdaBoost. Machine Learning, 42(3), 287–320. https://doi.org/10.1023/A:1007618119488
Chicago
Rätsch, G., T. Onoda, and K.-R. Müller. 2001. “Soft Margins for AdaBoost”. Machine Learning 42 (3): 287–320. https://doi.org/10.1023/A:1007618119488.
Harvard
Rätsch, G., Onoda, T. and Müller, K.-R. (2001) “Soft Margins for AdaBoost”, Machine Learning, 42(3), pp. 287–320. Available at: https://doi.org/10.1023/A:1007618119488.
Vancouver
1. Rätsch G, Onoda T, Müller K-R (2001) Soft Margins for AdaBoost. Machine Learning 42:287–320

BibTeX

@article{R_tsch_2001, title={Soft Margins for AdaBoost}, volume={42}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1007618119488}, DOI={10.1023/a:1007618119488}, number={3}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Rätsch, G. and Onoda, T. and Müller, K.-R.}, year={2001}, month=Mar, pages={287–320} }
Metadata:Crossref

Access the Paper

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

Open PDF