Approximate Maximum A Posteriori Inference with Entropic Priors

Matthew D. HoffmanarXiv 2010 · OpenReview

Abstract

In many probabilistic modeling applications, it is desirable to fit multinomial distributions to observed data using a penalty term that encourages sparsity. For instance, in probabilistic latent audio source decomposition, one might assume that only a few latent sources are active at any given time. However, the standard heuristic of applying an $L_1$ penalty is ineffective for multinomial distributions because their parameters are constrained to sum to one. This report proposes an alternative approach: using an entropic prior to encourage low-entropy, sparse solutions. To overcome the lack of conjugacy between the entropic prior and the multinomial distribution, a simple iterative algorithm for Maximum A Posteriori (MAP) estimation is derived.

The Sparsity Paradox on the Simplex

In machine learning, sparsity is often achieved through $L_1$ regularization (Lasso), which penalizes the sum of the absolute values of the parameters. While this works well for linear regression, it fails for multinomial parameters $\theta$. Because $\theta$ represents a probability distribution, its elements are non-negative and must sum to one. Consequently, the $L_1$ norm of $\theta$ is always exactly 1, rendering the $L_1$ penalty mathematically constant and useless for inducing sparsity.

To address this, we turn to the entropic prior. Entropy is a natural measure of the "flatness" of a distribution. By penalizing high-entropy solutions, we reward "peaky" distributions where most of the probability mass is concentrated in a few categories. This effectively induces sparsity within the constraints of the simplex.

Methodology: Overcoming Non-Conjugacy

The primary challenge with entropic priors is that they are not conjugate to the multinomial distribution. This means there is no closed-form solution for the MAP estimate. Hoffman addresses this by introducing an auxiliary function $\ell$ that approximates the entropy term using a free parameter $\alpha$ and a scalar $\nu$.

The Iterative Algorithm

The proposed solution is a fixed-point iteration scheme. The algorithm alternates between two computationally inexpensive updates:

  1. Update Auxiliary Parameters ($\alpha$): Adjust the auxiliary parameters based on the current estimate of the multinomial parameters $\theta$.
  2. Update Multinomial Parameters ($\theta$): Re-estimate the distribution weights based on the observed data and the current state of $\alpha$.

As the constant $\nu$ increases, the auxiliary function more closely approximates the true entropic prior. By iterating these steps, the algorithm converges toward a local optimum of the sparse objective function. These updates resemble "weighted counts," making them easy to integrate into existing Expectation-Maximization (EM) frameworks with negligible computational overhead.

Key Theoretical Insights

  • Entropy as a Sparsity Proxy: While $L_1$ is the standard for unconstrained parameters, entropy is the mathematically appropriate sparsity measure for any parameter set constrained to a simplex.
  • Auxiliary Function Optimization: The paper demonstrates that difficult, non-conjugate priors can be managed by creating surrogate functions that are easier to differentiate and optimize.
  • Convergence: The report provides a mathematical proof that the system reaches a stationary point, yielding an approximate local optimum for the MAP estimate. When $\nu$ is sufficiently large, the auxiliary function perfectly recovers the original entropic prior.

Limitations and Future Directions

As a theoretical technical report, this work focuses on the derivation of the algorithm rather than empirical validation. Several areas remain for further exploration:

  • Local Optima: The iterative scheme is guaranteed to find a local optimum, but like many non-convex optimization problems, it may not reach the global maximum.
  • Convergence Trade-offs: There is an inherent trade-off between approximation accuracy and speed; higher values of $\nu$ improve the approximation but likely increase the number of iterations required for convergence.
  • Hyperparameter Selection: The report does not define a formal method for selecting the optimal strength of the sparsity prior ($a$) or the tightness of the approximation ($\nu$).

Conclusion

This proposed iterative scheme offers a computationally efficient path for inducing sparsity in multinomial models. By replacing the ineffective $L_1$ penalty with an entropic prior and solving the resulting non-conjugacy through auxiliary functions, Hoffman provides a practical tool for researchers working with latent component analysis and other simplex-constrained models.

Summary updated

Abstract

In certain applications it is useful to fit multinomial distributions to observed data with a penalty term that encourages sparsity. For example, in probabilistic latent audio source decomposition one may wish to encode the assumption that only a few latent sources are active at any given time. The standard heuristic of applying an L1 penalty is not an option when fitting the parameters to a multinomial distribution, which are constrained to sum to 1. An alternative is to use a penalty term that encourages low-entropy solutions, which corresponds to maximum a posteriori (MAP) parameter estimation with an entropic prior. The lack of conjugacy between the entropic prior and the multinomial distribution complicates this approach. In this report I propose a simple iterative algorithm for MAP estimation of multinomial distributions with sparsity-inducing entropic priors.
BibTeX
@misc{hoffman2010approximate,
  author = {Matthew D. Hoffman},
  title = {{Approximate Maximum A Posteriori Inference with Entropic Priors}},
  year = {2010},
  eprint = {1009.5761},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1009.5761},
}
Figure