Using and combining predictors that specialize

We study online learning algorithms that predict by combining the predictions of severrd subordinate prediction algorithms, sometimes crdled "experts ." These simple algorithms belong to the multiplicative weights family of algorithms. The performance of these algorithms degrades only logarithmically with the number of experts, making them particularly useful in applications where the number of experts is very large. However, in applications such as text categorization, it is often natural for some of the experts to abstain from making predictions on some of the instances. We show how to transform algorithms that assume that afl experts are atways awake to algorithms that do not require this assumption. We also show how to derive corresponding Ioss bounds. Our method is very generaf, and can be applied to a large family of online learning algori[hms. We also give applications to various prediction models including decision graphs and "switching" experts.