Skip to content

Latest commit

 

History

History
57 lines (51 loc) · 3.28 KB

1995-a-decision-theoretic-generalization-of-on-line-learning-and-an-application-to-boosting.md

File metadata and controls

57 lines (51 loc) · 3.28 KB
title authors fieldsOfStudy meta_key numCitedBy reading_status ref_count tags urls venue year
A decision-theoretic generalization of on-line learning and an application to boosting
Y. Freund
R. Schapire
Computer Science
1995-a-decision-theoretic-generalization-of-on-line-learning-and-an-application-to-boosting
13363
TBD
46
gen-from-ref
other-default
paper
EuroCOLT
1995

semanticscholar url

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

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 Rn. 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.

Paper References

  1. Boosting a weak learning algorithm by majority
  2. Boosting Decision Trees
  3. How to use expert advice
  4. An Experimental and Theoretical Comparison of Model Selection Methods
  5. Data filtering and distribution modeling algorithms for machine learning
  6. Tight worst-case loss bounds for predicting with expert advice
  7. What Size Net Gives Valid Generalization?
  8. The weighted majority algorithm
  9. Solving Multiclass Learning Problems via Error-Correcting Output Codes
  10. Game theory, on-line prediction and boosting
  11. Boosting Performance in Neural Networks
  12. Bagging, Boosting, and C4.5
  13. Bias, Variance , And Arcing Classifiers
  14. A game of prediction with expert advice
  15. An analog of the minimax theorem for vector payoffs.
  16. Approximate methods for sequential decision making using expert advice
  17. Learning Sparse Perceptrons
  18. Universal Portfolios
  19. Some special vapnik-chervonenkis classes
  20. An Introduction to Computational Learning Theory
  21. Consumption and Portfolio Policies With Incomplete Markets and Short‐Sale Constraints - the Finite‐Dimensional Case
  22. Contributions to the theory of games
  23. Using experts for predicting continuous outcomes
    1. APPROXIMATION TO RAYES RISK IN REPEATED PLAY
  25. Aggregating strategies
  26. Experiments with a New Boosting Algorithm