Abstract

We advance probabilistic multiclass prediction on open-ended streams of items. In this setting, a predictor must emit items with probabilities, and adapt to significant non-stationarity, including new item appearances and frequency changes. The predictor is not given the set of items that it is to predict a priori, and moreover the totality of the items can grow unbounded: the space-limited predictor need only track the currently salient items and their probabilities. We develop Sparse Moving Average techniques (SMAs), including adaptations of sparse EMA as well as novel queue-based methods with dynamic per-item histories. For performance evaluation, to handle new items, we develop a bounded version of log-loss. Our findings, on a range of synthetic and real data streams, show that dynamic predictand-specific (per connection) parameters, such as learning rates, enhance both adaptation speed and stability.