Shadow Dirichlet for Restricted Probability Modeling

Bela A. Frigyik, Maya R. Gupta, Yihua ChenNeurIPS 2010

This paper introduces a clever way to model random probability distributions when we already know they must satisfy certain constraints—such as being monotonic or staying within a specific range.

The authors propose the Shadow Dirichlet distribution, which transforms a standard Dirichlet distribution through a linear map to restrict its support to a specific subset of the probability simplex. This approach allows for efficient Bayesian modeling of constrained probabilities (like regularized or monotonic functions) while avoiding the computational headaches of renormalizing distributions over restricted domains.

What Problem Does This Paper Address?

In machine learning, we often model probability mass functions (pmfs) as random variables using the Dirichlet distribution. While the Dirichlet is mathematically convenient (it is conjugate to the multinomial distribution), it assumes the entire "probability simplex"—the space where all components sum to one—is valid.

However, real-world data often comes with strings attached. For example:

  • Regularization: We might know a pmf should be "close" to a generic background model.
  • Bounded Variation: We might know that the probability of "espresso" should be similar to the probability of "latte."
  • Monotonicity: In some classification tasks, we expect probabilities to increase or decrease steadily across an ordered space.

The standard way to handle this is to "clip" the Dirichlet distribution to these restricted areas and renormalize it. Unfortunately, this makes the math messy: you lose closed-form solutions for the mean and covariance, and generating samples becomes incredibly slow because you have to "reject" any sample that falls outside the allowed zone.

Methods: The Shadow Dirichlet

To solve this, the authors introduce the Shadow Dirichlet. Instead of truncating the distribution, they transform it.

Comparison of Standard, Shadow, and Renormalized Dirichlet distributions
  1. The Transformation: Let $\tilde{\Theta}$ be a random pmf from a standard Dirichlet. They define a new random pmf $\Theta = M\tilde{\Theta}$, where $M$ is a fixed, full-rank, left-stochastic matrix (meaning its columns sum to 1).
  2. The "Shadow": The matrix $M$ acts as a linear map that "pushes" the standard Dirichlet into a specific convex subset of the simplex. The original Dirichlet is called the "shadow" of the resulting distribution.
  3. Construction: The paper provides specific ways to build the matrix $M$ for different needs:
  4. Regularized PMFs: Mapping the simplex to a smaller area centered around a "prior" distribution.
  5. Monotonic PMFs: A specific matrix structure that ensures every generated pmf is monotonically increasing.
  6. Estimation: To learn the parameters from data (especially when the data consists of counts or histograms), the authors derive an Expectation-Maximization (EM) algorithm. This allows researchers to estimate the underlying Dirichlet parameters even when they only observe noisy samples from the "shadowed" space.

Key Insights and Ideas

  • Geometry over Truncation: By using a linear transformation ($M$) rather than truncation, the authors preserve the tractability of the Dirichlet. You can still calculate means and covariances easily by simply multiplying the standard Dirichlet properties by $M$.
  • Maximum Entropy: The authors prove that their specific constructions for $M$ (for regularization and monotonicity) are "optimal" in an information-theoretic sense. They provide the maximum entropy (the least biased distribution) that still satisfies the required constraints.
  • Encoding Side-Information: The $M$ matrix serves as a powerful "design parameter." It allows a practitioner to bake expert knowledge—like product similarities or physical constraints—directly into the geometry of the statistical model.

Key Results

The paper evaluates the model using both synthetic simulations and real-world datasets, including retail sales data for 20 different puzzles over 10 months. The authors used a "similarity matrix" (how often puzzles were bought together) to construct the $M$ matrix, testing if the Shadow Dirichlet could better predict future sales proportions than standard models.

True vs. Estimated Distributions
  • Computational Efficiency: Unlike renormalized Dirichlets, the Shadow Dirichlet allows for "trivial" sampling (just draw from a standard Dirichlet and multiply by $M$) and has an efficient EM algorithm for parameter estimation.
  • Improved Prediction: In the puzzle sales experiment, the Shadow Dirichlet consistently outperformed the standard Dirichlet, the simple Multinomial, and the empirical mean. For example, for the month of March, the Shadow Dirichlet achieved a squared error of 0.0197, compared to 0.0227 for the standard Dirichlet and 0.0231 for the Multinomial.
  • Robustness: The model proved effective at "smoothing" predictions by forcing related items to have similar probability estimates, which is particularly useful when data is sparse.

Limitations and Future Work

While powerful, the Shadow Dirichlet does have some limitations:

  • Matrix Inversion: The basic density formula requires $M$ to be invertible (full-rank). While the authors discuss "fat" matrices (where the support has more vertices than dimensions), the math becomes more complex, requiring integration over fibers.
  • Learning M: In many cases, $M$ is designed by an expert. While the authors suggest some heuristics for learning $M$ directly from data, they acknowledge that this is a non-convex and difficult optimization problem.
  • Mixtures: A single Shadow Dirichlet can only model a single convex subset. To model more complex, non-convex constraints (like "either increasing or decreasing"), one would need to use a mixture of Shadow Dirichlets.

Summary updated

BibTeX
@inproceedings{frigyik2010shadow,
  author = {Bela A. Frigyik and Maya R. Gupta and Yihua Chen},
  title = {{Shadow Dirichlet for Restricted Probability Modeling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
}
Figure