Sat, 05 Jul 2008 00:17:48 BST CiteULike: AbnerCYH Schapire http://www.citeulike.org/user/AbnerCYH/author/Schapire CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/2269430 <i>Mach. Learn., Vol. 37, No. 3. (December 1999), pp. 297-336.</i> Improved Boosting Algorithms Using Confidence-rated Predictions Robert Schapire Yoram Singer doi:10.1023/A:1007614523901 Mach. Learn., Vol. 37, No. 3. (December 1999), pp. 297-336. 2008-01-21T17:16:45-00:00 1999 Mach. Learn. 0885-6125 37 3 297 336 Kluwer Academic Publishers algorithms kdd http://www.citeulike.org/user/AbnerCYH/article/2858063 <i>Machine Learning, Vol. 5, No. 2. (1 June 1990), pp. 197-227.</i><br /><br />This paper addresses the problem of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class islearnable (orstrongly learnable) if, given access to a source of examples of the unknown concept, the learner with high probability is able to output an hypothesis that is correct on all but an arbitrarily small fraction of the instances. The concept class isweakly learnable if the learner can produce an hypothesis that performs only slightly better than random guessing. In this paper, it is shown that these two notions of learnability are equivalent. The strength of weak learnability Robert Schapire doi:10.1007/BF00116037 Machine Learning, Vol. 5, No. 2. (1 June 1990), pp. 197-227. 2008-06-03T02:04:04-00:00 1990 Machine Learning 5 2 197 227 algorithms complexity kdd http://www.citeulike.org/user/AbnerCYH/article/2800472 <i>Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 119-139.</i><br /><br />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. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund Robert Schapire doi:10.1006/jcss.1997.1504 Journal of Computer and System Sciences, Vol. 55, No. 1. (August 1997), pp. 119-139. 2008-05-15T01:39:48-00:00 1997 Journal of Computer and System Sciences 55 1 119 139 algorithms kdd math stochastic http://www.citeulike.org/user/AbnerCYH/article/411634 <i>(2001)</i><br /><br />Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, this chapter overviews some of the recent work on boosting including analyses of AdaBoost's training error and generalization error; boosting's connection to game theory and linear programming; the relationship between boosting and logistic regression; extensions of AdaBoost for multiclass classification problems; methods of incorporating human knowledge... The boosting approach to machine learning: An overview R Schapire (2001) 2005-11-30T08:57:07-00:00 2001 algorithms game kdd stochastic