A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting. Freund, Y. A. S. Journal of Computer and System Sciences, 55(1):119--139, 1997. abstract bibtex 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 weightupdate rule of Littlestone and Warmuth [15] 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 R 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.
@Article{Freund1997,
Title = {A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting},
Author = {Freund, Y. AND Schapire, R. E.},
Journal = {Journal of Computer and System Sciences},
Year = {1997},
Number = {1},
Pages = {119--139},
Volume = {55},
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 weightupdate rule of Littlestone and Warmuth [15] 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 R 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.},
Booktitle = {Journal of Computer and System Sciences},
Keywords = {Lab reading (Ali)},
Review = {- Machine learning algorithm. Fast.
- Take a bunch of weak classifiers (could just be slightly better than chance)
- Feed in sample data and see how they classify things. If they're correct, weigh them higher
- Classify based on the entire combined weaker classifiers},
Timestamp = {2011.02.17}
}
Downloads: 0
{"_id":"LAXSbCwYNZwuXHy8b","bibbaseid":"freund-adecisiontheoreticgeneralizationofonlinelearningandanapplicationtoboosting-1997","downloads":0,"creationDate":"2017-09-14T16:34:36.458Z","title":"A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting","author_short":["Freund, Y. A. S."],"year":1997,"bibtype":"article","biburl":"https://raw.githubusercontent.com/jfslin/jfslin.github.io/master/jf2lin.bib","bibdata":{"bibtype":"article","type":"article","title":"A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting","author":[{"propositions":[],"lastnames":["Freund"],"firstnames":["Y.","AND","Schapire"],"suffixes":[]}],"journal":"Journal of Computer and System Sciences","year":"1997","number":"1","pages":"119--139","volume":"55","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 weightupdate rule of Littlestone and Warmuth [15] 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 R 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.","booktitle":"Journal of Computer and System Sciences","keywords":"Lab reading (Ali)","review":"- Machine learning algorithm. Fast. - Take a bunch of weak classifiers (could just be slightly better than chance) - Feed in sample data and see how they classify things. If they're correct, weigh them higher - Classify based on the entire combined weaker classifiers","timestamp":"2011.02.17","bibtex":"@Article{Freund1997,\n Title = {A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting},\n Author = {Freund, Y. AND Schapire, R. E.},\n Journal = {Journal of Computer and System Sciences},\n Year = {1997},\n Number = {1},\n Pages = {119--139},\n Volume = {55},\n\n 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 weightupdate rule of Littlestone and Warmuth [15] 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 R 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.},\n Booktitle = {Journal of Computer and System Sciences},\n Keywords = {Lab reading (Ali)},\n Review = {- Machine learning algorithm. Fast. \n\n- Take a bunch of weak classifiers (could just be slightly better than chance)\n- Feed in sample data and see how they classify things. If they're correct, weigh them higher\n- Classify based on the entire combined weaker classifiers},\n Timestamp = {2011.02.17}\n}\n\n","author_short":["Freund, Y. A. S."],"key":"Freund1997","id":"Freund1997","bibbaseid":"freund-adecisiontheoreticgeneralizationofonlinelearningandanapplicationtoboosting-1997","role":"author","urls":{},"keyword":["Lab reading (Ali)"],"downloads":0},"search_terms":["decision","theoretic","generalization","line","learning","application","boosting","freund"],"keywords":["lab reading (ali)"],"authorIDs":[],"dataSources":["iCsmKnycRmHPxmhBd"]}