Maximum Entropy competes with Maximum Likelihood

Armen AllahverdyanOpenReview 2020 · OpenReview

TL;DR

This paper investigates the limits and applicability of the Maximum Entropy (MAXENT) method for estimating unknown probabilities, particularly in sparse data regimes. By framing the problem within a Bayesian decision theory framework, the authors demonstrate that MAXENT can outperform regularized Maximum Likelihood (ML) estimators when specific prior information, such as rank correlations, is available.

What Problem Does This Paper Address?

Estimating unknown probability distributions from data is a fundamental problem in many fields, from statistical physics to machine learning. The Maximum Entropy (MAXENT) method is a powerful, non-parametric tool for this task, offering a principled way to infer distributions based on observed constraints. However, a systematic understanding of MAXENT's limitations and when it truly excels, especially compared to more traditional methods like Maximum Likelihood (ML), has been lacking. Specifically, the paper aims to answer:

  • Which constraints derived from noisy data are most effective for MAXENT?
  • When does MAXENT lead to overfitting?
  • How does MAXENT compare to other estimators, particularly regularized ML and Bayesian estimators?

Methods

The authors tackle these questions by employing a Bayesian decision theory framework. This involves:

  • Assuming a prior: They assume that the unknown probabilities are drawn from a Dirichlet distribution (or a mixture of Dirichlet distributions), which is a standard choice for non-informative priors over probability simplexes.
  • Defining a loss function: The Kullback-Leibler (KL) divergence is used as the metric to evaluate the quality of an estimator. The goal is to minimize the average KL divergence over both the data and the prior distribution.
  • Comparing estimators: They compare MAXENT with various constraints against:
  • The trivial estimator (uniform distribution).
  • The Bayesian estimator (posterior mean derived from the Dirichlet prior).
  • The regularized Maximum Likelihood (ML) estimator, which is a parametric estimator that shrinks the ML estimate towards a uniform distribution.

They explore different MAXENT constraints, including:

  • No constraints (leading to a uniform distribution).
  • Constraints based on the first moment (mean).
  • Constraints based on the first and second moments.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Simulated data: The performance of the estimators is evaluated through extensive numerical simulations, where probability distributions are generated from Dirichlet priors, and then samples are drawn from these distributions.
  • Real-world data: A real-world example of pre-election presidential polling data is used in Appendix A to illustrate the application of MAXENT to categorical data.

Key Insights and Ideas

  • MAXENT thrives on specific prior information: While MAXENT is often seen as "unsupervised" or "non-parametric," this paper shows it performs best when guided by specific prior knowledge. This prior information can be about the deterministic nature of probabilities or, more importantly, about rank correlations between the random quantity and its probabilities.
  • Overfitting is a real concern: Adding more constraints to MAXENT, especially when derived from noisy data, can lead to poorer performance (overfitting). This is particularly evident in sparse data regimes.
  • Affine symmetry matters: Constraints that lead to affine-invariant probabilities (meaning the inferred probabilities don't change if the underlying variable is linearly transformed) tend to yield better MAXENT estimators. This suggests that constraints that respect certain symmetries of the problem are more robust.
  • MAXENT can beat regularized ML: Under specific conditions (like prior rank correlations), MAXENT can outperform even optimally regularized ML estimators, which are often considered strong baselines. This is a significant finding, as ML estimators are generally more widely used and understood.
  • Bayesian estimators are robust but parametric: The Bayesian estimator, derived from the posterior mean, is shown to be consistently meaningful even for very small sample sizes. However, it is parametric, meaning its form depends on the specific prior chosen, which might not always be available in practice.

Key Results

  • Sparse data applicability: MAXENT is shown to be applicable in sparse data regimes (M < n, where M is sample size and n is number of outcomes), but it requires specific prior information.
  • MAXENT vs. Regularized ML: In scenarios with prior rank correlations between the random quantity and its probabilities, MAXENT estimators can achieve a smaller average KL-distance than optimally regularized ML estimators (Tables III and IV). For instance, in Table IV, MAXENT with constraints (19) or (19)+(22) performs better than regularized ML even for large sample sizes (M=241, n=60).
  • Overfitting demonstration: Table II illustrates overfitting, where adding a second constraint to MAXENT degrades performance for small sample sizes (M=9 to M=15), but becomes beneficial for larger M (M≥25).
  • Categorical data application: Appendix A demonstrates that MAXENT can be applied to categorical data by using frequency encoding, and its predictions can align well with Bayesian estimators.

Limitations and Future Work

  • Categorical data encoding: The paper acknowledges that applying MAXENT to categorical data requires a specific encoding of categories into numerical values. The choice of encoding can influence the results, and an open problem is to explore various encoding schemes and their impact on MAXENT estimators.
  • Affine symmetry analysis: While numerical evidence suggests that estimators with higher affine symmetry perform better, a formal analytical understanding of this relationship is still lacking.
  • Prior availability: The paper highlights that both Bayesian and regularized ML estimators are parametric and depend on prior information, which is often unavailable in practice. Understanding the sensitivity of these estimators to prior variations is an ongoing area of interest.
  • Minimum entropy principle: The paper touches upon the minimum entropy principle as a heuristic for avoiding overfitting, but its theoretical origin and broader implications are still under investigation.

Summary updated

Abstract

Maximum entropy (MAXENT) method has a large number of applications in theoretical and applied machine learning, since it provides a convenient non-parametric tool for estimating unknown probabilities. The method is a major contribution of statistical physics to probabilistic inference. However, a systematic approach towards its validity limits is currently missing. Here we study MAXENT in a Bayesian decision theory set-up, i.e. assuming that there exists a well-defined prior Dirichlet density for unknown probabilities, and that the average Kullback-Leibler (KL) distance can be employed for deciding on the quality and applicability of various estimators. These allow to evaluate the relevance of various MAXENT constraints, check its general applicability, and compare MAXENT with estimators having various degrees of dependence on the prior, {\it viz.} the regularized maximum likelihood (ML) and the Bayesian estimators. We show that MAXENT applies in sparse data regimes, but needs specific types of prior information. In particular, MAXENT can outperform the optimally regularized ML provided that there are prior rank correlations between the estimated random quantity and its probabilities.
BibTeX
@misc{allahverdyan2020maximum,
  author = {Armen Allahverdyan},
  title = {{Maximum Entropy competes with Maximum Likelihood}},
  year = {2020},
  url = {https://openreview.net/forum?id=_OGAW_hznmG},
  howpublished = {OpenReview},
}
Figure