《A decision-theoretic generalization of on-line learning and an application to boosting》.pdf

A Desicion.Theoretic Generalization of On-Line Learning and an Application to Boosting YoavFreund Robert E. Schapire ATT Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974-0636 {yoav,schapire}@ Abstract. We consider the problem ofdynamically apportionlngresources 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 con- siderably 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 algo- rithm which does not require prior knowledge about the performance of the weak learning algorithm. 1 Introduction A gambler, frustrated by persistent horse-racing losses and envious of his friends winnings, decides to allow a group of his fellow gamblers to make bets on his behalf. He decides he will wager a fixed sum of money in every race, but that he will apportion his money among his friends based on how well they are doing. Certainly, if he knew psychically ahead of time which of his friends would win the most, he would naturally have that friend h