for Lifelong Open-Ended Probability Prediction
Sparse moving averages (SMAs) are designed for probabilistic prediction & learning on long open-ended streams of items. In these problems, change is paramount, thus 'moving' in the name 'moving average' (and 'averaging' to estimate probabilities here). The number of possibilities, targets of prediction, is large and possibly unbounded (open-ended), so we say the predictions are 'sparse', ie at any time point, a small subset of items (eg, up to 10s or 100s) get nonzero probabilities by the predictor. The predictor is not given the list of items it will observe before hand. Instead, it processes a long or an infinite stream of items, and repeats predicting, observing, and updating (learning) (this has been referred to as the prequential loop). The predictor has finite space and should be efficient in its updating and predicting. The frequency of items in the stream can change. For example, a currently frequent item may cease to appear again, and a new highly frequent item (event) can occur for the first time (and become the norm thereafter for some time). Thus the predictor tries to predict the currently salient items, those with a (recent) probability above a threshold. We develop and explore a number of SMAs for the task, learning-rate based ones such as sparse EMA and counting-based ones, and find that keeping predictand specific parameters, such as learning rates, can lead to a superior trade-off between plasticity and stability.
This open-ended prediction problem arises within Prediction Games, where concepts (structured patterns such as n-grams) predict one another (during every interpretation episode), and new concepts are generated from time to time, causing non-stationarities in existing predictions.
SMAs are applicable to other settings, such as continual personalization and behavior modeling, in particular when needing to predict from within a possibly large number of possibilities fast, and when there exist non-stationarities, e.g. when some aspects of the modeled behavior change.
Pointers: