A decision-theoretic generalization of on-line learning and an application to boosting

Yoav Freund, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2122 Scopus citations

Abstract

We consider the problem of dynamically apportionlng 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 rule of Littlestone and Warmuth [10] 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 We also show how the weight-update rule can be used to derive a new boosting algorithm which does not require prior knowledge about the performance of the weak learning algorithm.

Original languageEnglish (US)
Title of host publicationComputational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
EditorsPaul Vitanyi
PublisherSpringer Verlag
Pages23-37
Number of pages15
ISBN (Print)9783540591191
DOIs
StatePublished - Jan 1 1995
Externally publishedYes
Event2nd European Conference on Computational Learning Theory, EuroCOLT 1995 - Barcelona, Spain
Duration: Mar 13 1995Mar 15 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume904
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd European Conference on Computational Learning Theory, EuroCOLT 1995
CountrySpain
CityBarcelona
Period3/13/953/15/95

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

    Freund, Y., & Schapire, R. E. (1995). A decision-theoretic generalization of on-line learning and an application to boosting. In P. Vitanyi (Ed.), Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings (pp. 23-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 904). Springer Verlag. https://doi.org/10.1007/3-540-59119-2_166