Some Properties of joint Probability Distributions

Marek J. DruzdzelUAI 1994

TL;DR

This paper argues that in most uncertain AI models, a small fraction of possible states will account for the vast majority of the total probability. This is because the joint probability distribution over model variables tends to follow a lognormal distribution, a consequence of applying the Central Limit Theorem to the multiplicative nature of probability calculations. This finding is crucial for developing efficient approximate reasoning algorithms in AI.

What Problem Does This Paper Address?

Many Artificial Intelligence (AI) systems designed to reason under uncertainty rely on probabilistic models. These models represent a domain as a set of possible "states of the world," where only one state is true at any given time. For complex domains, the number of possible states can be astronomically large (exponential in the number of variables). This poses a significant computational challenge for AI systems. Intuitively, it seems that for these systems to work effectively, they must be focusing on a small subset of these states. However, there's been a lack of formal justification for why this should be the case. This paper aims to provide that justification by analyzing the properties of joint probability distributions in uncertain models.

Methods

The core of the paper's argument lies in applying the Central Limit Theorem (CLT). The authors rewrite the joint probability distribution of a model's variables as a product of individual prior and conditional probability distributions. By taking the logarithm of this product, it transforms into a sum of random variables. The CLT states that the sum of a large number of independent random variables, regardless of their individual distributions, tends towards a normal distribution.

The paper then shows that if the logarithm of the probability of a state is normally distributed, then the probability of the state itself follows a lognormal distribution. Lognormal distributions are characterized by being highly skewed, meaning that a small number of values can have very high probabilities, while the vast majority have very low probabilities. The authors explore this under different assumptions about the individual conditional probability distributions:

  • Arbitrary Conditional Probability Distributions: Even when individual conditional probabilities are diverse, the CLT still suggests a lognormal distribution for state probabilities. The paper demonstrates that if individual conditional probabilities are "extreme" (i.e., highly skewed), a small fraction of states will dominate the probability space.
  • Identical Conditional Probability Distributions: In a simpler case where all variables' conditional distributions are identical (or permutations of each other), the CLT still leads to a lognormal distribution for state probabilities.
  • Identically Distributed Conditional Probability Distributions: This section relaxes the assumption to where conditional distributions are not necessarily identical but come from the same underlying distribution.

Datasets

The paper uses a subset of the ALARM (A Logical Reasoning Model) medical diagnostic model for evaluation. ALARM is a well-known probabilistic model for monitoring anesthesia patients. The authors selected subsets of ALARM with 7 to 13 variables due to the computational intractability of analyzing the full model. They also performed simulations to empirically support their theoretical derivations.

Key Insights and Ideas

  • Lognormal Distribution is the Norm: The paper provides a strong theoretical basis for why joint probability distributions in uncertain AI models tend to be lognormal. This is a direct consequence of the multiplicative nature of probability calculations and the CLT.
  • "A Few States Dominate": The skewed nature of the lognormal distribution means that a tiny fraction of possible states will account for a disproportionately large share of the total probability mass. This is the formal justification for why AI systems can often focus on a small subset of states.
  • Asymmetry is Key: The asymmetry in individual conditional probability distributions is the driving force behind the extreme skewness of the joint probability distribution. The more "extreme" or skewed the individual probabilities, the more pronounced this effect.
  • Practical Implications for Reasoning: This finding has direct implications for developing efficient approximate reasoning algorithms. If we know that a few states are overwhelmingly probable, we can focus computational effort on those states, leading to faster and more tractable solutions.

Key Results

  • The paper theoretically demonstrates that the probabilities of individual states in uncertain models are expected to be drawn from lognormal distributions.
  • This lognormal distribution implies that a small fraction of states can account for a large portion of the total probability space, while the remaining states have negligible probability.
  • Empirical results from analyzing subsets of the ALARM model and simulations confirm these theoretical predictions, showing a strong skewness in the distribution of state probabilities. For example, in a subset of 13 variables, the most likely state covered 0.52 of the probability space, and the top 49 states (out of over 500,000) covered 0.91 of the space.

Limitations and Future Work

  • Assumptions for CLT: The paper acknowledges that the application of the CLT relies on certain assumptions, particularly regarding the independence of variables and the divergence of variances. While the authors argue these assumptions are "sufficiently weak" for practical models, they are still assumptions.
  • Static Systems: The analysis primarily focuses on static systems. The authors suggest that the argument can be extended to dynamic systems by replacing variables with time-indexed variables, but this is a direction for future work.
  • Computational Tractability: While the findings suggest approximate reasoning is feasible, the paper notes that controlling for precision in atypical symmetric models is crucial to avoid incorrect posterior beliefs or decisions.
  • Future Work: The paper suggests that this analysis provides a foundation for developing approximate reasoning schemes that are both correct and computationally tractable. Future work could involve designing specific algorithms that leverage this property, such as considering only the most probable states until a certain error threshold is met.

Summary updated

BibTeX
@inproceedings{druzdzel1994some,
  author = {Marek J. Druzdzel},
  title = {{Some Properties of joint Probability Distributions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure