Alpha-NML Universal Predictors

Inspired by Sibson’s alpha-mutual information, we introduce a new parametric class of universal predictors. This class interpolates two well-known predictors, the mixture estimator, that includes the Laplace and the Krichevsky-Trofimov predictors, and the Normalized Maximum Likelihood (NML) estimator. We point out some advantages of this class of predictors and study its performance in terms of known regret measures under logarithmic loss, in particular for the well-studied case of discrete memoryless sources.

I. Introduction

Universal prediction, see e.g. [1], refers to the problem of estimating the next symbols of a sequence given its past, and evaluating the confidence of such an estimate, when the true model of the source is any of the models belonging to a certain class. This problem found applications in a wide range of areas, such as compression [2], [3], gambling [4] and machine learning [5], [6].