Performance guarantees for regularized maximum entropy density estimation

ISBN:

Call Number:

URL:

Keywords:

Abstract:

The authors consider the problem of estimating an unknown probability distribution from samples using the principle of maximum entropy (maxent). To alleviate overfitting with a very large number of features, they propose applying the maxent principle with relaxed constraints on the expectations of the features. By convex duality, this turns out to be equivalent to finding the Gibbs distribution minimizing a regularized version of the empirical log loss. They prove nonasymptotic bounds showing that, with respect to the true underlying distribution, this relaxed version of maxent produces density estimates that are almost as good as the best possible. These bounds are in terms of the deviation of the feature empirical averages relative to their true expectations, a number that can be bounded using standard uniform-convergence techniques. In particular, this leads to bounds that drop quickly with the number of samples and that depend very moderately on the number or complexity of the features. The authors also derive and prove convergence for both sequential-update and parallel-update algorithms. Finally, they briefly describe experiments on data relevant to the modeling of species’ geographical distributions.

Notes:

ELECTRONIC FILE - Zoology

Book title: Learning theory: proceedings of the 17th Annual Conference on Computational Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004. 654 pp.
Series: Lecture Notes in Computer Science, Vol. 3120
Subseries: Lecture Notes in Artificial Intelligence