Recent Results in On-line Prediction and Boosting
The successful design of practical algorithms for solving a class of problems very often depends on the existence of a formal model where algorithmical ideas can be developed, analyzed, and compared. In the case of machine learning, a number of such formal models have been proposed in the past. Some of them have been successful in generating elegant mathematical results but, on the other hand, they have had a rather limited impact on the practical side. In this paper, we suggest that the on-line prediction model is a good source of interesting algorithmic ideas with a great potential for new applications. To this end, we will describe a simple algorithm based on “multiplicative weights,” we will analyze this algorithm within the on-line prediction model, and finally we will show some of its variants and applications.