The Mixture Approach to Universal Model Selection
We build a model selection algorithm which has a mean Kullback risk upper bounded by the mean risk for the best model applied to half the sample augmented by an explicit penalty term of order one over the sample size. This estimator is not a \true" selection rule, but instead an adaptive convex combination of the models: this mixture approach is inspired by the context tree weighting method of information theory by Willems, Shtarkov and Tjalkens [6, 7], which is a \universal" data compression algorithm for stationary binary sources. Our algorithm is \universal" with respect to the statistical mean Kullback risk in the sense that it is almost optimal for any exchangeable sample distribution. We give an application to the estimation of a probability measure by adaptive histograms. We detail a factorised computation of the mixture which weights M models performing a number of operations of order log(M), when the subdivisions underlying the histograms have nested cells. The end of the paper shows that in the case of a dense family of models, a true selection rule can be built in a second step. We give an upper bound for the mean square Hellinger distance of the estimator from the sample distribution, which tends to zero at the optimal rate, up to an explicit multiplicative constant, in the case when the square Hellinder distance and the Kullback divergence are comparable.