TY - GEN
T1 - A decision-theoretic generalization of on-line learning and an application to boosting
AU - Freund, Yoav
AU - Schapire, Robert E.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
PY - 1995
Y1 - 1995
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84983110889&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84983110889&partnerID=8YFLogxK
U2 - 10.1007/3-540-59119-2_166
DO - 10.1007/3-540-59119-2_166
M3 - Conference contribution
AN - SCOPUS:84983110889
SN - 9783540591191
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 23
EP - 37
BT - Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
A2 - Vitanyi, Paul
PB - Springer Verlag
T2 - 2nd European Conference on Computational Learning Theory, EuroCOLT 1995
Y2 - 13 March 1995 through 15 March 1995
ER -