Details

Autor(en) / Beteiligte

• Cesa-Bianchi, Nicol
• Freund, Yoav
• Helmbold, David P.
• Warmuth, Manfred K.

Titel

On-line prediction and conversion strategies

Ist Teil von

• Machine learning, 1996, Vol.25 (1), p.71-110

Erscheinungsjahr

1996

Quelle

SpringerLINK Contemporary (Konsortium Baden-Württemberg)

Beschreibungen/Notizen

• We study the problem of deterministically predicting boolean values by combining the boolean predictions of several experts. Previous on-line algorithms for this problem predict with the weighted majority of the experts' predictions. These algorithms give each expert an exponential weight beta super(m) where beta is a constant in [0, 1) and m is the number of mistakes made by the expert in the past. We show that it is better to use sums of binomials as weights. In particular, we present a deterministic algorithm using binomial weights that has a better worst case mistake bound than the best deterministic algorithm using exponential weights. The binomial weights naturally arise from a version space argument. We also show how both exponential and binomial weighting schemes can be used to make prediction algorithms robust against noise.