Bayesian Properties of Normalized Maximum Likelihood and its Fast Computation

Abstract—The normalized maximized likelihood (NML) pro-vides the minimax regret solution in universal data compression, gambling, and prediction, and it plays an essential role in the minimum description length (MDL) method of statistical modeling and estimation. Here we show that when the sample space is finite, a generic condition on the linear independence of the component models implies that the normalized maximum likelihood has an exact Bayes-like representation as a mixture of the component models, even in finite samples, though the weights of linear combination may be both positive and negative. This addresses in part the relationship between MDL and Bayes modeling. The representation also has the practical advantage of speeding the calculation of marginals and conditionals required for coding and prediction applications. Index Terms—universal coding, universal prediction, minimax regret, Bayes mixtures I