Posterior distributions are computable from predictive distributions

Cameron E. Freer, Daniel M. RoyAISTATS 2010 · OpenReview

Abstract

As we devise more complicated prior distributions, will inference algorithms keep up? We highlight a negative result in computable probability theory by Ackerman, Freer, and Roy (2010) that shows that there exist computable priors with noncomputable posteriors. In addition to providing a brief survey of computable probability theory geared towards the A.I. and statistics community, we give a new result characterizing when conditioning is computable in the setting of exchangeable sequences, and provide a computational perspective on work by Orbanz (2010) on conjugate nonparametric models. In particular, using a computable extension of de Finetti’s theorem (Freer and Roy 2009), we describe how to transform a posterior predictive rule for generating an exchangeable sequence into an algorithm for computing the posterior distribution of the directing random measure.

Introduction

In the realm of Bayesian statistics, the transition from a prior belief to a posterior distribution via observed data is the cornerstone of inference. As machine learning models grow in complexity—moving from simple parametric models to infinite-dimensional nonparametrics—the community often assumes that if a model is well-defined, its posterior is inherently calculable. However, work in Computable Probability Theory (CPT) has revealed a fundamental challenge: Bayesian conditioning is not always a computable operation.

This paper explores the boundary between what we can define and what we can compute. While the general case for Bayesian inference is fraught with noncomputability, the authors identify a critical "silver lining" for exchangeable sequences. They demonstrate that for this broad class of models, the ability to predict future observations is computationally equivalent to the ability to perform full posterior inference.

The Problem: The Noncomputability of Bayes

The central tension arises from the fact that a "computable" prior does not necessarily yield a "computable" posterior. In CPT, a probability measure is considered computable if there exists an algorithm that can provide increasingly accurate approximations of the measure of any given set.

Ackerman, Freer, and Roy (2010) previously established a negative result: there exist scenarios where the prior and the likelihood are computable, yet the resulting posterior is noncomputable. This means that no matter how much computational power is applied, no algorithm can determine the posterior to arbitrary precision. This gap is particularly problematic in nonparametric Bayesian models where the standard Bayes' Rule (Likelihood $\times$ Prior) often fails due to the lack of a dominating measure or the presence of infinite-dimensional spaces.

Methods: Bridging Prediction and Inference

To find a path forward, the authors focus on exchangeable sequences. A sequence of random variables is exchangeable if its joint distribution is invariant under permutations of the indices. According to de Finetti’s Theorem, such sequences can be viewed as being independent and identically distributed (i.i.d.) conditioned on some underlying "directing random measure."

The authors leverage a "computable version" of de Finetti’s theorem to establish their results. Their methodology involves three primary steps:

  1. Computable Representation: Probability distributions are treated as points within a computable topological space, allowing them to be manipulated by algorithms.
  2. Sequence Hallucination: They demonstrate that if one possesses a computable posterior predictive rule—an algorithm to compute $P[X_{k+1} | X_{1:k}]$—one can "hallucinate" or simulate an infinite sequence of future observations.
  3. Algorithmic Transformation: They prove the existence of a program that can transform this infinite simulated sequence back into a representation of the posterior distribution of the directing measure.

Key Insights: The Prediction-Inference Equivalence

The most significant contribution of the paper is the characterization of the relationship between prediction and inference. The authors prove that for an exchangeable sequence, the sequence of posterior distributions is computable if and only if the sequence of posterior predictive rules is computable.

This equivalence suggests that prediction and inference are two sides of the same computational coin. If an agent can accurately simulate the next data point based on previous observations, that agent implicitly possesses all the information required to compute the posterior of the model itself. This provides a rigorous foundation for why predictive methods (like the Blackwell-MacQueen urn scheme for Dirichlet Processes) are so effective: they are computationally sufficient for full Bayesian inference.

Results and Implications

The paper provides several key theoretical results:

  • Theorem 4 (The Core Result): This formalizes the equivalence between the computability of the posterior and the posterior predictive rule.
  • Nonparametric Applications: The authors show that complex objects like the Dirichlet Process can be handled through this framework. Even though the Dirichlet Process is infinite-dimensional, its predictive rule (the Chinese Restaurant Process) is computable, which in turn guarantees the computability of its posterior.
  • Sufficient Statistics: A corollary states that if a model possesses computable sufficient statistics and a computable predictive rule based on those statistics, the posterior is guaranteed to be computable.

Limitations and Future Directions

While the paper provides a powerful existence proof, it also highlights significant practical hurdles. The algorithm derived from the proof is "rather inefficient," serving more as a theoretical guarantee of computability than a practical tool for real-time inference. The transformation from a predictive rule to a posterior involves simulating infinite sequences, which is not directly applicable to finite-time computation.

Furthermore, the results are strictly tied to the assumption of exchangeability. Many modern data structures, such as time-series with temporal dependencies or graphs with complex relational structures, violate exchangeability. Extending these computability results to non-exchangeable settings remains an open and vital area of research.

Conclusion

By framing Bayesian inference through the lens of Computable Probability Theory, Ackerman, Freer, and Roy provide a clear boundary for what is possible in automated reasoning. Their work confirms that while the general Bayesian update is not universally computable, the structural regularity provided by exchangeability ensures that if we can predict the future, we can understand the model that generated it.

Summary updated

Abstract

As we devise more complicated prior distributions, will inference algorithms keep up? We highlight a negative result in computable probability theory by Ackerman, Freer, and Roy (2010) that shows that there exist computable priors with noncomputable posteriors. In addition to providing a brief survey of computable probability theory geared towards the A.I. and statistics community, we give a new result characterizing when conditioning is computable in the setting of exchangeable sequences, and provide a computational perspective on work by Orbanz (2010) on conjugate nonparametric models. In particular, using a computable extension of de Finetti’s theorem (Freer and Roy 2009), we describe how to transform a posterior predictive rule for generating an exchangeable sequence into an algorithm for computing the posterior distribution of the directing random measure.
BibTeX
@inproceedings{freer2010posterior,
  author = {Cameron E. Freer and Daniel M. Roy},
  title = {{Posterior distributions are computable from predictive distributions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=BKZ-kv3v1z5},
}
Figure