Generalization bounds for averaged classifiers

Yoav Freund, Yishay Mansour, Robert E. Schapire

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, that is, the hypothesis that minimizes the training error, our algorithm predicts with a weighted average of all hypotheses, weighted exponentially with respect to their training error. We show that the prediction of this algorithm is much more stable than the prediction of an algorithm that predicts with the best hypothesis. By allowing the algorithm to abstain from predicting on some examples, we show that the predictions it makes when it does not abstain are very reliable. Finally, we show that the probability that the algorithm abstains is comparable to the generalization error of the best hypothesis in the class.

Original languageEnglish (US)
Pages (from-to)1698-1722
Number of pages25
JournalAnnals of Statistics
Volume32
Issue number4
DOIs
StatePublished - Aug 1 2004

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Averaging
  • Bayesian methods
  • Classification
  • Ensemble methods
  • Generalization bounds

Fingerprint Dive into the research topics of 'Generalization bounds for averaged classifiers'. Together they form a unique fingerprint.

Cite this