3.5 General inference algorithms

[[So far, inference has looked like a (possibly iterative) application of Bayes’s theorem. The most complicated structure we’ve considered is the binary tree underlying the HMM and the state-space models. Now we’d like to generalize to more complicated directed and undirected graphs.

The basic intuition is that we can construct efficient algorithms for trees and tree-like graphs. Therefore, the basis of our derivation of the very general junction-tree algorithm will be to convert non-tree graphs into something tree-like. We may have to bite the bullet and accept large cliques, which are bad from a computation perspective…. The alternatives are approximate inference (loopy BP, variational inference, sampling methods).

At the heart of inference is normalization. This is the “hard” part of Bayes’s rule, because it may involve an intractable integral; or it may involve summing over all the configurations of the random variables, the number of the former being exponential in the number of the latter.

The other setting in which we had to compute normalizers was undirected graphical models, since the product of the potential functions on an undirected graph is an unnormalized distribution. But this too can be assimilated to inference with Bayes’s theorem. To see this, consider the undirected graphical model in Fig. 3.1A, for which the joint distribution is

for some normalizer $Z$. The independence statements asserted by this graph—e.g., ${\bm{\hat{X}}}_{1}\mathchoice{\mathrel{\hbox to 0.0pt{$\displaystyle\perp$}$—follow from the usual graph-separation criterion.

Now consider the graphical model in Fig. 3.1B, which we assert to be normalized. Thus

In this graph, ${\bm{\hat{X}}}_{1}$ and ${\bm{\hat{X}}}_{4}$ are no longer independent conditioned on ${\bm{\hat{X}}}_{2},{\bm{\hat{X}}}_{3}$, since there is a connecting path through ${\bm{\hat{Y}}}$. But conditioning on ${\bm{\hat{Y}}}$ clearly restores all of the independence statements of Fig. 3.1A. Therefore if, for a particular value $\bm{\hat{y}}$ of ${\bm{\hat{Y}}}$, we define

then

The last line follows from summing both sides over all configurations of ${\bm{\hat{X}}}$. In fine, the missing normalizer is $\check{p}(\bm{\hat{y}})$.

More generally, the product of potentials for any undirected graphical model with nodes ${\bm{\hat{X}}}_{1},\ldots,{\bm{\hat{X}}}_{N}$ can be interpreted as a slice through some normalized distribution, $\check{p}(\leavevmode\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{$, where the auxiliary random variable ${\bm{\hat{Y}}}$ did not occur in the original graph. Under this interpretation, computing the partition function is equivalent to computing the marginal probability of $\bm{\hat{y}}{}$—another instance of inference with Bayes’s theorem.