PaperlayerView exact revision on arXiv

Source-linked AI summary

A more robust boosting algorithm

Yoav Freund

arXiv:0905.2138v1stat.ML

TL;DR

AdaBoost and related boosting methods are sensitive to label noise, and convex-potential boosting can be defeated by random label noise. This paper presents Robustboost, a boosting algorithm motivated by large margins and using a changing, nonconvex potential; the authors report evidence that it is more robust to label noise than AdaBoost and Logitboost.

  • Problem

    AdaBoost performance deteriorates rapidly under random label noise, and convex-potential boosting algorithms can be defeated by such noise.

    Source: §1 · p. 1

  • Method

    Robustboost is a boosting algorithm based on Boost-by-Majority and Brownboost, with a nonconvex potential that changes during boosting.

    Source: §1 · p. 1

  • Results

    The authors present evidence that Robustboost is more robust to label noise than either Logitboost or AdaBoost.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The authors suggest that, after learning an approximate classifier, down-weighting examples far from the decision boundary regardless of label may be beneficial.

    Source: §6 · p. 8

    The analysis fixes the base classifiers, assumes the weak learner picks the smallest weighted-error classifier, and focuses on training mistakes.

    Source: §2 · p. 2

Abstract

from arXiv · show

We present a new boosting algorithm, motivated by the large margins theory for boosting. We give experimental evidence that the new algorithm is significantly more robust against label noise than existing boosting algorithm.

1. Introduction

AdaBoost’s resistance to overfitting has been explained through large margins, but its sensitivity to label noise motivates a more robust boosting method. Robustboost uses a nonconvex potential that changes during boosting and is based on Boost-by-Majority and Brownboost.

1. Introduction

  • AdaBoost often avoids overfitting: test error can continue to fall after training error reaches zero, with large margins and likelihood maximization offered as explanations.The large-margins account focuses on test classification error, whereas the logistic-regression account focuses on maximizing conditional likelihood.Source: §1 · p. 1
  • AdaBoost’s performance deteriorates rapidly with random label noise, while Logitboost bounds example weights and is described as better able to tolerate noise.AdaBoost assigns unbounded large weights to mislabeled examples; Logitboost’s bounded weights decrease their penalty.Source: §1 · p. 1
  • Long and Servedio (2008) prove that boosting algorithms based on convex potential functions can be defeated by random label noise.The convex potentials are minimized using gradient descent.Source: §1 · p. 1
  • Robustboost is presented as significantly more robust to label noise than either AdaBoost or Logitboost, using a changing, nonconvex potential based on Boost-by-Majority and Brownboost.The paper says it will present experimental evidence for this robustness.Source: §1 · p. 1

2. Learning Linear Discriminators under noise

The section frames noisy linear discrimination as a challenge for potential-based boosting: large negative margins can make noisy examples dominate the objective. Robustboost is introduced as a non-convex, changing-potential alternative claimed to be more robust to label noise.

2. Learning Linear Discriminators under noise

  • The setup fixes the base classifiers and represents examples through their outputs, reducing learning to finding a weight vector for a linear discriminator.The section focuses on minimizing training mistakes; finding the minimum-error linear classifier on non-separable data is NP-hard.Source: §2 · p. 2
  • Adaboost assigns potential exp(−m), while Logitboost’s potential is approximately −m for m ≪ 0, so the former penalizes badly misclassified examples more heavily.The section notes that the potentials and weights assigned to mislabeled examples by Adaboost are much larger than Logitboost’s.Source: §2 · pp. 2–3
  • Adaboost and Logitboost minimize convex margin potentials that upper-bound the error step function, using gradient descent on the average potential.The average-potential derivative with respect to a base-rule weight is interpreted as a margin-dependent weighted correlation.Source: §2 · pp. 2–3
  • With independent label flips, some clean examples with large positive margins become noisy examples with large negative margins, shifting the potential-minimization objective.Moving away from the original separator can increase those negative margins and lower their potential contributions.Source: §2 · p. 3
  • Robustboost uses a non-convex potential that changes during boosting and is presented as more robust to label noise than Adaboost or Logitboost.The paper also reports experimental evidence of greater robustness on the classification problem suggested by Long and Servedio.Source: §2 · p. 3

3. The large margins theory

The section uses large-margin theory to connect training margins with generalization error and shifts the boosting objective from minimizing mistakes to improving normalized margins. It also notes that maximizing the minimum margin alone has not consistently reduced generalization error in prior experiments.

3. The large margins theory

  • The margin bound links generalization error to the fraction of training examples with normalized margin at most θ, alongside a term depending on the number of base rules and training-set size.The supplied passage identifies these quantities but does not provide the bound’s full expression.Source: §3 · p. 3
  • Increasing θ raises the bound’s first term toward 1, while decreasing θ toward 0 makes its second term grow sharply.Thus choosing θ involves a trade-off between the two terms.Source: §3 · p. 4
  • Prior experiments maximizing the minimum margin found that this did not tend to decrease generalization error, challenging that explanation for Adaboost’s behavior.The section contrasts this evidence with the account that Adaboost decreases the bound by increasing the threshold with zero training examples below it.Source: §3 · p. 4
  • Large-margin theory motivates minimizing the number of training examples whose normalized margins fall below a positive threshold θ, rather than only minimizing training mistakes.For non-separable data, the section says useful bounds require margins above θ for most, but not all, training examples.Source: §3 · p. 4

4. Robustboost

Robustboost adapts Brownboost to minimize a margin-based cost rather than training error, using a non-convex, changing potential and bounded score variance.

4. Robustboost

  • BBM uses a finite horizon and gives up on examples with very negative margins, producing a non-convex potential with decreasing slope at both margin extremes.Its iteration count is set in advance using an error goal.Source: §4 · p. 4
  • Brownboost makes BBM adaptive by assigning larger weights to more accurate base classifiers and terminating when its time variable reaches a preset horizon.As the target error approaches zero, Brownboost becomes equivalent to Adaboost.Source: §4 · p. 4
  • Robustboost adapts Brownboost to minimize a margin-based cost, keeping score variance bounded through a mean-reverting drift.The drift pushes examples toward zero in the underlying process.Source: §4 · p. 4
  • Robustboost runs over 0 ≤ t ≤ 1, with θ setting the goal margin and σf controlling the final potential’s step slope.The paper sets σf = 0.1 to avoid numerical instability near t = 1; the potential there approximates the margin-error function.Source: §4 · pp. 4–5, Figure 2 · p. 5

Robustboost

  • The algorithm normalizes example weights, selects a weak classifier, and updates scores and its hypothesis until t reaches 1.The error goal ε is searched so the algorithm terminates in a reasonable number of iterations and determines ρ.Source: Robustboost · p. 5, §4 · p. 5

5. Experiments

Across two synthetic label-noise problems, Robustboost outperformed Adaboost and Logitboost. The experiments also examine why it succeeds and whether its large-margin predictions are trustworthy.

5.1. The Long/Servedio problem

  • The Long–Servedio experiment used 10 datasets of 800 training examples and compared training error with error against uncorrupted labels.The distribution has three example types, and adding 10% label noise severely degrades Adaboost and Logitboost.Source: §5.1 · p. 6
  • On Long–Servedio, Logitboost’s large-margin examples and pullers separate at a minimal-potential solution, while penalizers remain roughly random and contribute about 25% training error.The paper attributes this to sparse penalizers’ inability to pull the solution away from the direction of the pullers and large-margin examples.Source: §5.1 · pp. 6–7
  • On Long–Servedio, Robustboost downweights large-margin examples and mislabeled pullers, allowing many penalizers to be classified correctly after 200 iterations.It avoids the incorrect minima that trap Adaboost and Logitboost by ignoring examples with large negative margins.Source: §5.1 · p. 7

5.2. The Mease/Wyner problem

  • The Mease–Wyner problem uses a synthetic distribution whose target rule cannot be exactly represented by a finite number of the tested base classifiers.Experiments used 2,000 training and 2,000 test examples, with noise levels q = 0.1 and q = 0.2%.Source: §5.2 · p. 7

5. Experiments

  • Robustboost performed better than Logitboost, which outperformed Adaboost, on both synthetic problems; its advantage over Logitboost recurred in all 15 Mease–Wyner repeats.On Long–Servedio, Robustboost’s error against clean labels was about 1.0% despite 10% noise in the training data.Source: §5.1 · p. 6, §5.2 · pp. 7–8

5.2. The Mease/Wyner problem

  • For Mease–Wyner test examples outside the low-margin region |score| < θ, Robustboost’s predictions are reported as very trustworthy.The reported table separates the low-margin fraction from the error rate on the remaining examples against uncorrupted labels.Source: §5.2 · p. 8

6. conclusions

The authors report evidence that Robustboost is more robust to label noise than Adaboost and Logitboost, while noting that more experiments are needed to verify the claim. They also suggest that down-weighting examples far from the decision boundary, regardless of label, may be beneficial after learning an approximate classifier.

6. conclusions

  • Robustboost is reported to be more robust against label noise than either Logitboost or Adaboost.The authors say more experiments using synthetic and real-world datasets are needed to verify this claim.Source: §6 · p. 8
  • Further experiments using synthetic and real-world datasets are needed to verify Robustboost’s reported noise-robustness advantage.Source: §6 · p. 8
  • After learning an approximate classifier, it may be beneficial to down-weight examples far from the decision boundary regardless of their label.Source: §6 · p. 8
Loading 0905.2138v1…