Suppose we have an agent that makes an observation about the world \(y\in\mathcal{Y}\) and has some internal model that describes the likelihood of that observation \(y\) conditioned on some hidden state of the world \(x\in\mathcal{X}\), which we denote by \(p(y | x)\), and a prior distribution on the hidden states of the world \(p(x)\). Bayes’ rule states that \[p(x | y) = \frac{p(y | x)p(x)}{p(y)} = \frac{p(y | x)p(x)}{\int {p(y | x)p(x)}dx},\]
so in principle the agent can calculate the posterior density over hidden states of the world under its internal model by multiplying the likelihood \(p(y | x)\) by the prior \(p(x)\) and normalising by the marginal \(p(y)\). The challenge is that computing the marginal term requires integrating over all of the possible hidden states. For \(x \in \mathbb{R}^d\), a grid with \(k\) points per dimension costs \(O(k^d)\); discrete with \(K\) values per site costs \(K^d\), and so in general exact inference quickly grows to be intractable.
The consequence is that if an agent wants to do Bayesian inference they face a choice:
- restrict the internal model to conjugate exponential families or low tree-width discrete structure e.g., belief propagation on trees to do exact inference in polynomial time.
- asymptotically exact but expensive methods on arbitrary internal models e.g., MCMC, particle filters.
- do some form of approximate inference that is biased but relatively cheap e.g., variational inference.
Category 1) includes some of the most important algorithms that we depend on in our daily life. For example, linear-Gaussian case is the Kalman filter, which runs on essentially every vehicle with a GPS. The Kalman filter relies on two properties to make the computation tractable: a state space model is a chain, so the marginalisation decomposes into a recursion over time (small tree width), and the prior and likelihood are conjugate, so every step of that recursion stays Gaussian and can be done analytically.
Category 2) trades analysis for compute: rather than solving for the posterior in closed form, we draw random samples from it, and the more samples we are willing to pay for, the closer we get to the exact answer. But how can we sample from a distribution whose density we cannot even normalise? The key observation is that most sampling schemes never need \(p(y)\) at all: in the Metropolis–Hastings acceptance ratio the normaliser appears in both numerator and denominator and cancels, so an unnormalised density \(p(y|x)p(x)\) — which we can always evaluate — is enough to build a chain whose stationary distribution is the posterior we wanted and if we have enough samples we asymptotically converge to the correct posterior. The limitaion is that multimodal posteriors can trap a chain for exponentially long stretches, and even with gradient information every step costs a likelihood evaluation that may touch the entire dataset.
For many models of interest today e.g., neural nets, the techniques in categories 1 and 2 are not sufficient because we do not have a conjugate likelihood and prior, and these models are typically have high dimensional state spaces, making MCMC and numerical quadrature too computational costly to be feasible. This motivates the study of algorithms in category 3): approximate inference approaches such as variational inference, which convert the intractable integration problem into a more tractable optimisation problem. These will be the subject of the next post.