Learning the Experts for Online Sequence Prediction
  Online sequence prediction is the problem of predicting the next element of a
sequence given previous elements. This problem has been extensively studied in
the context of individual sequence prediction, where no prior assumptions are
made on the origin of the sequence. Individual sequence prediction algorithms
work quite well for long sequences, where the algorithm has enough time to
learn the temporal structure of the sequence. However, they might give poor
predictions for short sequences. A possible remedy is to rely on the general
model of prediction with expert advice, where the learner has access to a set
of $r$ experts, each of which makes its own predictions on the sequence. It is
well known that it is possible to predict almost as well as the best expert if
the sequence length is order of $\log(r)$. But, without firm prior knowledge on
the problem, it is not clear how to choose a small set of {\em good} experts.
In this paper we describe and analyze a new algorithm that learns a good set of
experts using a training set of previously observed sequences. We demonstrate
the merits of our approach by applying it on the task of click prediction on
the web.
