Chapter 5 General Algorithms for Exact Inference

“Graphical Models” is the name of a branch of Statistics and Artificial Intelligence that deals with probabilistic models whose parameters typically have a local structure that can be depicted by using a graph that is not fully connected. Missing interactions are depicted by missing edges in the graph which is a very efficient representation when nearly all of the possible interactions are missing.

Hinton [24]

[[A quick tour through the three major inference algorithms discussed in class…. The main idea is to represent statistical structure—independence—with graphs (missing edges), and then translate the task of statistical inference into operations on those graphs. ]]

Fundamentally, inference involves two operations, multiplying and summing (or integrating). (Normalization of the result is also generally required, but this only needs to happen once, so we ignore it for now.) The data structures to which these operations are applied are probability distributions in the case of directed graphs, and potential functions in the case of undirected graphs—but the operations are the same. The multiplication operation can be described more precisely as merging conditional and marginal distributions via the chain rule of probability. (This is less obvious, but still true, for undirected graphs.) Subsequent renormalization yields the posterior distribution, so we might call this posteriorization^†^†margin: posteriorization . Summation (or integration for continuous random variables) can be described more precisely as adding up copies of a function for all possible configurations of one or more of the input arguments—marginalization.

Why inference is hard.

This sounds elegant and straightforward, but unfortunately it also is attended by two major and ineluctable difficulties. The first is that very few probability distributions are closed under both of these operations. For example, an exponential-family (prior) distribution, ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}}}\right)}$ , when used with the (exponential-family) likelihood to which it is conjugate, ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{y}}{}\middle|{\color[rgb]{.75,0,.25}% \definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}}}\right)}$ , is closed under multiplication, or more precisely under posteriorization: ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}}}\right)}$ and ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}}\middle|{\color[rgb]{.75,0,.25}% \definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{y}}{}}\right)}$ are members of the same exponential family. But this pair of distributions is only in special cases closed under marginalization; that is, ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{y}}{}}\right)}$ is not typically in the same family as ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}}}\right)}$ . Similarly….^†^†margin: elliptic/stable distributions

Two well known exceptions are (1) linear-Gaussian models and (2) categorical distributions (including, of course, special cases like the Bernoulli distribution), which is why we have focused on models composed of these in Chapter 3. This is certainly a very restrictive set of distributions. On the other hand, we do not always need every random variable in the graph to be closed under the inference operations. For example, a model that pairs a Poisson emission ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}y}\middle|{\color[rgb]{.75,0,.25}% \definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\lambda}}\right)}$ with a categorical prior distribution ${\hat{p}\mathopen{}\mathclose{{}\left({\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}\lambda}}\right)}$ of rate parameters can easily be inverted with Bayes rule; as long as we don’t need to do much with the marginal distribution over observations ${\hat{Y}}$ , no problems will arise. Furthermore, we can always discretize the domain of a random variable, resulting in a categorical distribution, which is closed under posteriorization and marginalization.

Still, we should not consider discretization to be a panacea. It is in some sense the worst possible distribution, since marginalization over categorical random variables is exponential in the number of variables, with base equal to the number of categories. This is the second major obstacle to inference. As Hinton reminds us, inference in graphs is efficient “when nearly all of the possible interactions are missing.” More structured distributions are not quite as expensive as the categorical, but the fundamental problem remains that the time complexity of marginalization scales at least polynomially, and in the worst case exponentially, in (roughly speaking) the number of variables with direct dependencies on each other.

The inference algorithms discussed in this chapter address this second difficulty. Their aim is to try to reach at least this lower bound; that is, to minimize the number of variables whose joint interactions we need to keep track of.

A simple example of inference with discrete random variables.

We focus in this chapter on categorical random variables, for which the multiplication and summing operations are simple. Indeed, the data structures—distributions or potentials—are just multiway tables. For example, the directed graph in Fig. 5.1a could correspond to Bernoulli random variables and be parameterized by:

\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}x_{i}})=\begin{pmatrix}0.3\\ 0.7\end{pmatrix}

for the parentless nodes;

\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}x_{i}}|{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{% rgb}{.75,0,.25}x_{j}})=\begin{pmatrix}0.6&0.2\\ 0.4&0.8\\ \end{pmatrix}

for the single-parent nodes; and

\displaystyle\hat{p}({\hat{X}}_{i}=0|{\color[rgb]{.75,0,.25}\definecolor[named% ]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}},{\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{k}})=\begin{pmatrix}0.1&0.3\\ 0.2&0.4\\ \end{pmatrix},

\displaystyle\hat{p}({\hat{X}}_{i}=1|{\color[rgb]{.75,0,.25}\definecolor[named% ]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}},{\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{k}})=\begin{pmatrix}0.9&0.7\\ 0.8&0.6\\ \end{pmatrix}

for the two-parent nodes. In any case, the entire graph is parameterized by one-, two-, or three-way tables.

The corresponding operations are broadcast multiplication and (sum) reduction. For example, turning again to the graph in Fig. 5.1a, we could represent all the conditional and marginal probabilities given above using tensors with the following shapes:

1 # a convenient bookkeeping strategy

2 assert p_X1.shape == (2, 1, 1, 1, 1, 1, 1, 1)

3 assert p_X2.shape == (1, 2, 1, 1, 1, 1, 1, 1)

4 assert p_X3givenX1X2.shape == (2, 2, 2, 1, 1, 1, 1, 1)

5 assert p_X4givenX3.shape == (1, 1, 2, 2, 1, 1, 1, 1)

6 assert p_X5givenX3.shape == (1, 1, 2, 1, 2, 1, 1, 1)

7 assert p_X6givenX4.shape == (1, 1, 1, 2, 1, 2, 1, 1)

8 assert p_X7givenX5.shape == (1, 1, 1, 1, 2, 1, 2, 1)

9 assert p_X8givenX6X7.shape == (1, 1, 1, 1, 1, 2, 2, 2)

Then the “joint” distribution $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}x_{1}},{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{% rgb}{.75,0,.25}x_{2}},{\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}x_{3}})$ , for example, could be computed with broadcast multiplication as

1 # chain rule of probability with broadcast multiplication

2 p_X1X2X3 = p_X3givenX1X2*p_X1*p_X2

3 assert p_X1X2X3.shape == (2, 2, 2, 1, 1, 1, 1, 1)

Marginalization is then carried out by reducing (summing) the multiway tensor along some of its dimensions. For example, $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}x_{3}})$ could be computed by collapsing the three-way tensor representing $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}x_{1}},{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{% rgb}{.75,0,.25}x_{2}},{\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}x_{3}})$ over its first and second dimensions:

1 # marginalize by collapsing over ways of the tensor

2 p_X3 = p_X1X2X3.sum(axis=(0, 1), keepdims=True)

3 assert p_X3.shape == (1, 1, 2, 1, 1, 1, 1, 1)

yielding a single row (or column).