A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

Yoav Freund, Robert E. Schapire

Research output: Contribution to journalArticle

7890 Scopus citations

Abstract

In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone-Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in ℝn. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.

Original languageEnglish (US)
Pages (from-to)119-139
Number of pages21
JournalJournal of Computer and System Sciences
Volume55
Issue number1
DOIs
StatePublished - Aug 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting'. Together they form a unique fingerprint.

  • Cite this