What are the factors that cause the posterior distributions to be intractable?

Question

In Bayesian statistics, it is often mentioned that the posterior distribution is intractable and thus approximate inference must be applied. What are the factors that cause this intractability?

Answer 1

I had the opportunity to ask David Blei this question in person, and he told me that intractability in this context means one of two things:

1. The integral has no closed-form solution. This might be when we're modeling some complex, real-world data and we simply cannot write the distribution down on paper.

2. The integral is computationally intractable. He recommended that I sit down with a pen and paper and actually work out the marginal evidence for the Bayesian mixture of Gaussians. You'll see that it is computationally intractable, i.e. exponential. He gives a nice example of this in a recent paper (See 2.1 The problem of approximate inference).

FWIW, I find this word choice confusing, since (1) it is overloaded in meaning and (2) it is already used widely in CS to refer only to computational intractability.

Answer 2

The issue is mainly that Bayesian analysis involves integrals, often multidimensional ones in realistic problems, and it's these integrals that are typically intractable analytically (except in a few special cases requiring the use of conjugate priors).

By contrast, much of non-Bayesian statistics is based on maximum likelihood -- finding the maximum of a (usually multidimensional) function, which involves knowledge of its derivatives, i.e. differentiation. Even so numerical methods are used in many more complex problems, but it's possible to get further more often without them, and the numerical methods can be simpler (even if less simple ones may perform better in practice).

So I'd say it comes down to the fact that differentiation is more tractable than integration.

Answer 3

Tractability is related to closed-formness of an expression.

Problems are said to be tractable if they can be solved in terms of a closed-form expression.

In mathematics, a closed-form expression is a mathematical expression that can be evaluated in a finite number of operations. It may contain constants, variables, certain "well-known" operations (e.g., + − × ÷), and functions (e.g., nth root, exponent, logarithm, trigonometric functions, and inverse hyperbolic functions), but usually no limit. The set of operations and functions admitted in a closed-form expression may vary with author and context.

So intractability means that there is some kind of limit/infinity involved (like infinite summation in integrals) which can not be evaluated in a finite number of operations and thus approximation techniques (like MCMC) must be used.

The Wikipedia article points to Cobham's thesis which tries to formalize this "amount of operations", and thus tractability.

Answer 4

Actually, there are a range of possibilities:

1. a closed form expression is available for the posterior (example: $Y\sim \text{Bin}(n,\pi)$, prior for $\pi$: $\text{Beta}(a,b)$ and the posterior $p(\pi|Y=y)$ is a $\text{Beta}(a+y,b+n-y)$ distribution),
2. the posterior is tractable up to the normalizing constant (example: $Y\sim \text{Bin}(n,\pi)$, prior for $\log \pi$ is $N(\mu, \sigma^2)$ and $p(\pi|Y=y) \propto p(y|\pi) p(\pi)$)
3. the data generating process is some complicated mechanism that is so complex that we cannot write down a likelihod (or if we can it takes forever to evaluate), but we can simulate from the data generating process (e.g. some kind of process for how certain properties develop over many generations in a population). To continue the example from above, in this case we would have no closed form expression for $p(y|\pi)$, but could simulate realizations of $Y$ given a specific value of $\pi$ (let's not even talk about the case where we have no idea how the data arises...).

People usually mean something like (2) when they talk about an (analytically) non-tractable posterior and something like (3) when they talk about a non-tractable likelihood. It is the third case when approximate Bayesian computation is one of the options, while in the second case MCMC methods are usually feasible (which you may argue are in some sense approximate). I am not entirely sure, which of these two the quote your provided refers to.