Conditional smoothing improves prediction from training batches
Batch Universal Prediction via Conditional Additive Smoothing
Information Theory
Summary
Predicting sequences from unknown sources is hard, especially when you have some training examples first. The authors study a method called conditional additive smoothing that adjusts predictions based on a batch of training sequences. They analyze how well this method works for simple binary memoryless and Markov sources, showing how the best adjustments depend on the training size and source properties. They also introduce a new way to measure prediction quality related to a concept called Rényi mutual information.
What this means in practice
- •For language model developers: Enhance sequence prediction accuracy by tuning smoothing parameters based on training batch size for simpler language model components.
- •For data compression engineers: Improve adaptive compression schemes by using conditional additive smoothing to better estimate source distributions from training data batches.
A theory result. No direct application yet.
Authors
Marco Bondaschi, Michael Gastpar
Abstract
Modern language models motivate renewed interest in universal prediction problems in which a predictor can exploit previously observed data before predicting a fresh sequence. We study an idealized version of this setting by introducing \emph{batch regret}: a conditional analogue of classical average regret in which a predictor observes a batch of $n$ training sequences and is then evaluated on an independent test sequence generated by the same unknown source. Additive smoothing estimators, which add a bias to the observed token frequencies before predicting the next token, played a fundamental role as a simple prediction strategy with almost-optimal average regret for memoryless and Markov sources. Their equivalent under batch regret are the conditional additive smoothing estimators, which estimate the conditional distribution of the test sequence given the training batch. In this work, we study their asymptotical batch regret for binary memoryless and first-order Markov sources. For binary memoryless sources, we show how the optimal bias of the estimator, and consequently the corresponding batch regret, change as a function of the training batch size $n$, by extending the Poisson-based analysis of Krichevsky. For binary Markov sources with positive transitions, we characterize the leading coefficient of batch regret and its dependence on whether the initial law is known, free, or stationary. Finally, we introduce a Rényi analogue of batch regret and identify the corresponding optimal predictors as conditional $α$-NML estimators, thereby giving an operational interpretation to a conditional version of Sibson's $α$-mutual information.