Abstract: We compute the expected value of the Kullback-Leibler divergence to various fundamental statistical models with respect to canonical priors on the probability simplex. We obtain closed formulas for the expected model approximation errors, depending on the dimension of the models and the cardinalities of their sample spaces. For the uniform prior, the expected divergence from any model containing the uniform distribution is bounded by a constant $1-\gamma$, and for the models that we consider, this bound is approached if the state space is very large and the models' dimension does not grow too fast. For Dirichlet priors the expected divergence is bounded in a similar way, if the concentration parameters take reasonable values. These results serve as reference values for more complicated statistical models.
Introduction: Beyond Worst-Case Analysis
In statistical modeling, we often use structures like neural networks or graphical models to approximate complex probability distributions. A central question is how "wrong" these models are. Traditionally, this is measured via the Kullback-Leibler (KL) divergence. Most theoretical work focuses on worst-case analysis, which often suggests that error grows indefinitely as the number of possible outcomes ($N$) increases.
However, this paper demonstrates that worst-case scenarios are often unrepresentative. By calculating the expected error—the average divergence when the "true" distribution is chosen randomly—the authors find that for many fundamental models, the error remains remarkably small and stable, even as the state space scales to infinity.
Methods and Model Classes
The researchers derived closed-form expressions for expected distances using Dirichlet priors to define the distribution of "true" models on the probability simplex. They analyzed several key model classes:
- Independence Models: Variables are assumed to be independent.
- Partition Models: Outcomes are grouped into discrete blocks.
- Decomposable Hierarchical Models: These models can be represented as a "junction tree" of smaller, overlapping components.
By leveraging the aggregation properties of Dirichlet distributions, the authors were able to solve complex integrals to find exact formulas for the expected KL divergence from these models to the true distribution.
Key Insights: The Stability of Error
The most significant finding is the existence of a "magic constant." For a uniform prior, the expected divergence from any model containing the uniform distribution is bounded by $1 - \gamma \approx 0.4228$, where $\gamma$ is the Euler-Mascheroni constant.
This result implies scale invariance: as long as a model's dimension remains relatively small, its average approximation error does not explode as the state space grows. While the worst-case error might grow logarithmically ($\log N$), the average case stays flat. This suggests that the "bad" distributions that are difficult for these models to approximate are statistically rare.
Results and Numerical Verification
The paper provides exact theorems for expected entropy and divergence. For symmetric Dirichlet priors with parameter $a$, the error is approximately $h(a) - \log(a) - \gamma$. For independence and decomposable models, the paper proves that as the number of elementary events $N \to \infty$, the expected divergence converges exactly to $1 - \gamma$.
Numerical simulations involving tens of thousands of sampled distributions confirmed these theoretical limits, showing that different model architectures and prior parameters converge to predictable horizontal asymptotes as system size increases.
Limitations and Future Directions
While these results offer a more optimistic view of model performance, they rely on the choice of a Dirichlet prior. Real-world data often possesses more complex structures—such as sparsity or clustering—that a uniform or symmetric Dirichlet prior may not fully capture. Furthermore, while the authors conjecture these bounds apply to more complex architectures like Restricted Boltzmann Machines (RBMs), formal proofs for deep, non-linear models remain a subject for future research.
Summary updated