(9.1)

Once the model parameters have been estimated, the mean of the posterior for a new example can be calculated, which can then serve as a reduced dimensional representation for it. The mathematics (though still perhaps daunting) is greatly simplified by the fact that marginalizing, multiplying and dividing Gaussians distributions produces other Gaussian distributions that are functions of observed values, mean vectors, and covariance matrices. In fact, many more sophisticated methods and models for data analysis rely on the ease with which key quantities can be computed when the underlying model is based on linear Gaussian forms.

Marginal log-likelihood for PPCA

Given a probabilistic model with hidden variables, the Bayesian philosophy is to integrate out the uncertainly associated with them. As we have just seen, linear Gaussian models make it possible to obtain the marginal probability of the data, p(x), which takes the form of a Gaussian distribution. Then, the learning problem is tantamount to maximizing the probability of the given data under the model. The probability that variable x is observed to be $\tilde{\mathbf{x}}$ is indicated by $p(\tilde{\mathbf{x}})=p(\mathbf{x}=\tilde{\mathbf{x}})$. The log (marginal) likelihood of the parameters given all the observed data $\tilde{\mathbf{X}}$ can be maximized using this objective function:

$L(\tilde{\mathbf{X}};\theta )=\log \left[\prod _{i=1}^{N}P({\tilde{\mathbf{x}}}_i;\theta )\right]=\sum _{i=1}^N\log [N({\tilde{\mathbf{x}}}_i;\mathbf{\mu },\mathbf{W}{\mathbf{W}}^{\mathbf{T}}+{\sigma }^2\mathbf{I})],$

where the parameters $\theta =\{\mathbf{W},\mathbf{\mu },{\sigma }^2\}$, consist of a matrix, a vector, and a scalar. We will assume henceforth that the data has been mean-centered: $\mathbf{\mu }\mathbf{=}\mathbf{0}$. (However, when creating generalizations of this approach there can be advantages to retaining the mean as an explicit parameter of the model.)

Expected log-likelihood for PPCA

Section 9.4 showed that the derivative of the log marginal likelihood of a hidden variable model with respect to its parameters equals the derivative of the expected log joint likelihood, where the expectation is taken with respect to the exact posterior distribution over the model’s hidden variables. The underlying Gaussian formulation of PPCA means that an exact posterior can be computed, which provides an alternative way to optimize the model based on the expected log-likelihood. The log joint probability of all data and all hidden variables H under the model is

$L(\tilde{\mathbf{X}},\mathbf{H};\theta )=\log \left[\prod _{i=1}^{N}p({\tilde{\mathbf{x}}}_i,{\mathbf{h}}_i;\theta )\right]=\sum _{i=1}^N\log [p({\tilde{\mathbf{x}}}_i|{\mathbf{h}}_i;\mathbf{W})p({\mathbf{h}}_i;{\sigma }^2)].$

Notice that while the data $\tilde{\mathbf{X}}$ is observed, the hidden variables h_i are unknown, so for a given parameter value $\theta =\tilde{\theta }$ this expression does not evaluate to a scalar quantity. It can be converted into a scalar-valued function using the expected log-likelihood, which can then be optimized. As we saw in Section 9.4, the expected log-likelihood of the data using the posterior distribution of each example for the expectations is given by

$E{[L(\tilde{\mathbf{X}},\mathbf{H};\theta )]}_{p(\mathbf{H}|\tilde{\mathbf{X}})}=\sum _{i=1}^{N}E{\left[\log \right[p({\tilde{\mathbf{x}}}_i,{\mathbf{h}}_i;\theta )\left]\right]}_{p({\mathbf{h}}_i|{\tilde{\mathbf{x}}}_i)}.$

Expected gradient for PPCA

Gradient descent can be used to learn the parameter matrix W using the expected log-likelihood as the objective, an example of the expected gradient approach discussed in Section 9.4. The gradient is a sum over examples, and a fairly lengthy derivation shows that each example contributes the following term to this sum:

$\begin{array}{ll}\frac{\partial }{\partial \mathbf{W}}E[L(\tilde{\mathbf{x}},\mathbf{h})]\hfill & =E\left[\mathbf{W}\mathbf{h}{\mathbf{h}}^{\mathrm{T}}\right]-E\left[\tilde{\mathbf{x}}{\mathbf{h}}^T\right]\hfill \\ \hfill & =\mathbf{W}E\left[\mathbf{h}{\mathbf{h}}^{\mathrm{T}}\right]-\tilde{\mathbf{x}}E{\left[\mathbf{h}\right]}^T,\hfill \end{array}$ (9.2)

(9.2)

where in all cases the expectations are taken with respect to the posterior, $p(\mathbf{h}|\tilde{\mathbf{x}})$, using the current settings of the model parameters. This partial derivative has a natural interpretation as a difference between two expectations. The second term creates a matrix the same size as W, consisting of an observation and the hidden variable representation. The first term simply replaces the observation with a similar Wh factor, which could be thought of as the model’s prediction of the input. (We will revisit this interpretation when we examine conditional probability models in Section 9.7 and restricted Boltzmann machines in Section 10.5.)

This shows that the model reconstructs the data as it ascends the gradient. If the optimization converges to a model that perfectly reconstructs the data, the derivative in (9.2) will be zero. Other probabilistic models examined show similar forms for the gradients for key parameters, consisting of differences of expectations—but different types of expectation are involved.

To compute these quantities, note that the expected value $E\left[\mathbf{h}\right]={\mathbf{M}}^{-1}{\mathbf{W}}^{\mathrm{T}}(\mathbf{x}-\mathbf{\mu })$ can be obtained from the mean of the posterior distribution for each example given by (9.1). The E[hh^T] term can be found using the fact that E[hh^T]=cov[h]+E[h]E[h]^T, where cov[h] is the posterior covariance matrix, which we also know from (9.1) is ${\sigma }^2{\mathbf{M}}^{-1}$.

EM for PPCA

An alternative to gradient ascent using the expected log-likelihood is to formulate the model as an expected gradient-based learning procedure using the classical EM algorithm. The M-step update can be obtained by setting the derivative in (9.2) to zero and solving for W. This can be expressed in closed form: W in the first term is independent of the expectation and can therefore be moved out of the expectation and terms re-arranged into a closed-form M-step. In a zero mean model with $\mathbf{D}={\sigma }^2\mathbf{I}$ and some small value for ${\sigma }^2$, the E and M steps of the PPCA EM algorithm can be rewritten

where all expectations are taken with respect to each example’s posterior distribution, $p({\mathbf{h}}_i|{\tilde{\mathbf{x}}}_i)$, and, as above, $\mathbf{M}=(\mathbf{W}{\mathbf{W}}^T+{\sigma }^2\mathbf{I})$.

The EM algorithm can be further simplified by taking the limit as ${\sigma }^2$ approaches zero. This is the zero input noise case, and it implies M=WW^T. Define the matrix Z=E[H], each column of which contains the expected vector from $P({\mathbf{h}}_i|{\tilde{\mathbf{x}}}_i)$ for one of the hidden variables h_i, so that $E\left[\mathbf{H}{\mathbf{H}}^T\right]=E\left[\mathbf{H}\right]E\left[{\mathbf{H}}^T\right]=\mathbf{Z}{\mathbf{Z}}^T$. This yields simple and elegant equations for the E and M steps:

where both equations operate on the entire data matrix $\tilde{\mathbf{X}}$.

The probabilistic formulation of principal component analysis permits traditional likelihoods to be defined, which supports maximum likelihood based learning and probabilistic inference. This in turn leads to natural methods for dealing with missing data. It also leads on to the other models discussed below.

Factor graphs, Bayesian networks, and the logistic regression model

It is instructive to compare the factor graph for a naïvely constructed Bayesian model with the factor graph for a Naïve Bayes model of the same set of variables (and, later, with the factor graph for a logistic regression formulation of the same problem). Fig. 9.14A and B shows the Bayesian network and its factor graph for a network with a child node y that has several parents x_i, i=1,…,n. Fig. 9.14B involves a large conditional probability table for $P(y|x_1,\dots ,x_n)$, with many parameters that must be estimated or specified, because in

$P(y,x_1,\dots ,x_n)=P(y|x_1,\dots ,x_n)\prod _{i-1}^{n}P(x_i)$

the number of parameters increases exponentially with the number of parent variables. In contrast, Fig. 9.14C and D shows the Bayesian network and its factor graph for the Naïve Bayes model. Here the number of parameters is linear in the number of children because the model breaks down into the product of functions involving y and just one x_i, because the underlying factorization is

$P(y,x_1,\dots ,x_n)=P(y)\prod _{i-1}^{n}P(x_i|y).$

The factor graphs show the different complexities very clearly. The graph in Fig. 9.14B has a factor involving n+1 variables, while the factors in Fig. 9.14D involve no more than two variables.

Factor graphs can be extended to clarify an important distinction for conditional models. The Bayesian network of Fig. 9.15A involves a large table for the conditional distribution of y given many x_i’s, but a logistic regression model could be used to reduce the number of parameters for $P(y|x_1,\dots ,x_n)$ from exponential to linear, depicted in Fig. 9.15B.

Let us assume that all variables are binary. Given a separate function f_i(y,x_i) for each binary variable x_i, the conditional distribution defined by a logistic regression model has the form

$\begin{array}{ll}P(y|x_1,\dots ,x_n)\hfill & =\frac{1}{Z(x_1,\dots ,x_n)}\mathrm{e}\mathrm{x}\mathrm{p}\left(\sum _{i=1}^n{w}_i{f}_i(y,x_i)\right)\hfill \\ \hfill & =\frac{1}{Z(x_1,\dots ,x_n)}\prod _{i=1}^n{\varphi }_i(x_i,y).\hfill \end{array}$

where the denominator Z is a data-dependent normalization term that makes the conditional distribution sum to 1, and ${\varphi }_i(x_i,y)=\mathrm{e}\mathrm{x}\mathrm{p}(w_i{f}_i(y,x_i))$. This corresponds to a factor graph that resembles the Naïve Bayes model, but with the factorized conditional distribution shown in Fig. 9.15B. Here, curved rectangles represent variables that are not explicitly defined as random variables. This graph represents the conditional probability function $P(y|x_1,\dots ,x_n)$, and the number of parameters scales linearly because each function is connected to just a pair of variables.

Marginal probabilities

Given a Bayesian network, an initial step is to determine the marginal probability of each node given no observations whatsoever. These single node marginals differ from the conditional and unconditional probabilities that were used to specify the network. Indeed, software packages for manipulating Bayesian networks often take the definition of a network in terms of the underlying conditional and unconditional probabilities and show the user the single node marginals for each node in a visual interface. The marginal for variable x_i is

$P(x_i)=\sum _{x_{j\ne i}}P(x_1,\dots ,x_n),$

where the sum is over the states of all variables x_j ≠x_i, and can be computed by the sum-product algorithm. In fact, the same algorithm serves in many other situations, such as when some variables are observed and we wish to compute the belief of others, and also for finding the posterior distributions needed for learning—e.g., using the EM algorithm.

Consider the task of computing the marginal probability of variable x₃ given the observation $x_4={\tilde{x}}_4$ from the Bayesian network in Fig. 9.12A. Since we are conditioning on a variable, we need to compute a marginal conditional probability. This corresponds to the practical notion of posing a query, where the model is used to infer an updated belief about x₃ given the state of variable x₄.

Since other variables in the graph have not been observed, they should be integrated out of the graphical model to obtain the desired result:

$P(x_3|{\tilde{x}}_4)=\frac{P(x_3,{\tilde{x}}_4)}{P({\tilde{x}}_4)}=\frac{P(x_3,{\tilde{x}}_4)}{\sum _{x_3}(x_3,{\tilde{x}}_4)},$

Here the key probability of interest is

$\begin{array}{ll}P(x_3,{\tilde{x}}_4)\hfill & =\sum _{x_1}\sum _{x_2}\sum _{x_5}P(x_1,x_2,x_3,{\tilde{x}}_4,x_5)\hfill \\ \hfill & =\sum _{x_1}\sum _{x_2}\sum _{x_5}P(x_1)P(x_2)P(x_3|x_1)P({\tilde{x}}_4|x_1,x_2)P(x_5|x_2).\hfill \end{array}$

However, this sum involves a large data structure containing the joint probability, composed of the products over the individual probabilities. The sum-product algorithm refers to a much better solution: simply push the sums as far as possible to the right before computing products of probabilities. Here, the required marginalization can be computed by

$\begin{array}{ll}P(x_3,{\tilde{x}}_4)\hfill & =\sum _{x_1}P(x_3|x_1)P(x_1)\sum _{x_2}P({\tilde{x}}_4|x_1,x_2)P(x_2)\sum _{x_5}P(x_5|x_2)\hfill \\ \hfill & =\sum _{x_1}P(x_3|x_1)P(x_1)P({\tilde{x}}_4|x_1)\hfill \\ \hfill & =\sum _{x_1}P(x_1,x_3,{\tilde{x}}_4).\hfill \end{array}$

The sum-product algorithm

The approach illustrated by this simple example can be generalized into an algorithm for computing marginals that can be transformed into conditional marginals if desired. Conceptually, it is based on sending messages between the variables and functions defined by a factor graph.

Begin with variable or function nodes that have only one connection. Function nodes send the message ${\mu }_{f\to x}(x)=f(x)$ to the variable connected to them, while variable nodes send ${\mu }_{x\to f}(x)=1$. Each node waits until it has received a message from all neighbors except the one it sent its message to. Then function nodes send messages of the following form to variable x:

${\mu }_{f\to x}(x)=\sum _{x_1,\dots ,x_K}f(x,x_1,\dots ,x_K)\prod _{k\in N(f)x}{\mu }_{x_k\to f}(x_k),$

where N(f)x represents the set of the function node f’s neighbors, excluding the recipient variable x; we write these variables of the K other neighboring nodes as x₁,…,x_K. If a variable is observed, messages for functions involving it no longer need a sum over the states of the variable, the function is evaluated with the observed state. One could think of the associated variable node as being transformed into the new modified function. There is then no variable to function message for the observed variable.

Variable nodes send messages of this form to functions:

${\mu }_{x\to f}(x)={\mu }_{f_1\to x}(x)\dots {\mu }_{f_K\to x}(x)=\prod _{k\in N(x)f}{\mu }_{f_k\to x}(x),$

where the product is over the messages from all neighboring functions N(x) other than the recipient function f; i.e., $fk\in N(x)f$. When the algorithm terminates, the marginal probability of each node is the product over all incoming messages from all functions connected to the variable:

$P(x_i)={\mu }_{f_1\to x}(x)\dots {\mu }_{f_K\to x}(x){\mu }_{f_{K+1}\to x}(x)=\prod _{k=1}^{K+1}{\mu }_{f_k\to x}(x),$

This is written as a product over K+1 function messages to emphasize its similarity to the variable-to-function-node messages. After sending a message to any given function f consisting of the product of K messages, the variable simply needs to receive one more incoming message back from f to compute its marginal.

If some of the variables in the graph are observed, the algorithm yields the marginal probability of each variable and the observations. The marginal conditional distribution for each variable can be obtained by normalizing the result by the probability of the observation, obtainable from any node by summing over x_i in the resulting distributions, which have the form $P(x_i,\{{\tilde{x}}_{j\in O}\})$ where O is the set of indices of the observed variables.

As is often the case with probability models, multiplying many probabilities quickly leads to very small numbers. The sum-product algorithm is often implemented with rescaling. Alternatively, the computations can be performed in log space (as they are in the max-product algorithm; see below), leading to computations of the form $c=\log (\exp (a)+\exp (b))$. To help prevent loss of precision when computing the exponents, note that

$c=\log (e^a+e^b)=a+\log (1+e^{b-a})=b+\log (1+e^{a-b}),$

and pick the expression with the smaller exponent.

Sum-product algorithm example

The idea behind the sum-product algorithm is to push sums as far to the right as possible, and this is done efficiently for all variables simultaneously. When the algorithm is used to compute $P(x_3,{\tilde{x}}_4)$ from the Bayesian network in Fig. 9.12A and the corresponding factor graph in Fig. 9.17, the key messages involved are:

$P(x_3,{\tilde{x}}_4)=\underset{6a}{\underbrace{\sum _{x_1}P(x_3|x_1)\underset{5a}{\underbrace{\underset{1d}{\underbrace{P(x_1)}}\underset{4a}{\underbrace{\sum _{x_2}P({\tilde{x}}_4|x_1,x_2)\underset{3a}{\underbrace{\underset{1c}{\underbrace{P(x_2)}}\underset{2a}{\underbrace{\sum _{x_5}P(x_5|x_2)}}}}}}}}}}·\underset{1a}{\underbrace{1}}$

These numbered messages can be written

$\begin{array}{l}\mathrm{1a}:{\mu }_{x_5\to f_E}(x_5)=1,\text{1c}:{\mu }_{f_B\to x_2}(x_2)=f_B(x_2),\text{1d}:{\mu }_{f_A\to x_1}(x_1)=f_A(x_1)\hfill \\ 2\mathrm{a}:{\mu }_{f_E\to x_2}(x_2)=\sum _{x_5}{f}_E(x_5,x_2)\hfill \\ 3\mathrm{a}:{\mu }_{x_2\to f_D}(x_5)={\mu }_{f_B\to x_2}(x_2){\mu }_{f_E\to x_2}(x_2)\hfill \\ 4\mathrm{a}:{\mu }_{f_D\to x_1}(x_1)=\sum _{x_2}{f}_D({\tilde{x}}_4|x_1,x_2){\mu }_{x_2\to f_D}(x_5)\hfill \\ 5\mathrm{a}:{\mu }_{x_1\to f_C}(x_1)={\mu }_{f_A\to x_1}(x_1){\mu }_{f_D\to x_1}(x_1)\hfill \\ 6\mathrm{a}:{\mu }_{f_C\to x_3}(x_3)=\sum _{x_1}{f}_C(x_3,x_1){\mu }_{x_1\to f_C}(x_1)\hfill \end{array}$

Keep in mind that the complete algorithm will yield all single-variable marginals in the graph using the other messages shown in Fig. 9.17, but not enumerated above. This simple example is based on a Bayesian network, which transforms into a chain-structured factor graph when ${\tilde{x}}_4$ is observed, and the message passing structure resembles the computations used for the hidden Markov models and conditional random fields discussed below. For long chains or large tree-structured networks, such computations are essential for computing the necessary quantities efficiently, without recourse to approximate methods.

Most probable explanation example

Finding the most probable configuration of all other variables in our example given $x_4={\tilde{x}}_4$ involves searching for

$\left\{x_1^{*},x_2^{*},x_3^{*},x_5^{*}\right\}=\underset{x_1,x_2,x_3,x_5}{\arg \max }P(x_1,x_2,x_3,x_5|{\tilde{x}}_4),$

for which

$P(x_1^{*},x_2^{*},x_3^{*},x_5^{*}|{\tilde{x}}_4)=\underset{x_1,x_2,x_3,x_5}{\max }P(x_1,x_2,x_3,x_5|{\tilde{x}}_4).$

The joint probability is related to the conditional by a constant, so one could equally well find the maximum of $P(x_1,x_2,x_3,{\tilde{x}}_4,x_5)$. Because max behaves in a similar way to sum, we can take a tip from the sum-product and push the max operations as far to the right as possible, noting that $\max (ab,ac)=a\max (b,c)$. Here,

$\begin{array}{l}{\displaystyle \underset{x_1}{\max }}{\displaystyle \underset{x_2}{\max }}{\displaystyle \underset{x_3}{\max }}{\displaystyle \underset{x_5}{\max }}P(x_1,x_2,x_3,{\tilde{x}}_4,x_5)\hfill \\ ={\displaystyle \underset{x_3}{\max }}{\displaystyle \underset{x_1}{\max }}P(x_1)P(x_3|x_1){\displaystyle \underset{x_2}{\max }}P(x_2)P({\tilde{x}}_4|x_1,x_2){\displaystyle \underset{x_5}{\max }}P(x_5|x_2).\hfill \end{array}$

Consider the max over x₅ at the far right, which seeks the greatest probability among the possible states of x₅ for each of the possible states of x₂. This involves creating a table giving the maximum values of x₅ for each configuration of x₂. The next operation to the left, the max over x₂, involves multiplying the current maximum values in the table for x₂ by the corresponding probabilities for $P(x_2)P({\tilde{x}}_4|x_1,x_2)$. We thus need to find the maximum for each state of x₂ for each state of x₁, which can be modeled by producing a message over the states of x₁ with the greatest values obtained for each possible state based on all information propagated so far from the right.

This process continues until eventually we have a final max over x₃. This gives a single value, the probability of the most probable explanation, which corresponds to the entry in the data structure with scores for each state of x₃. By changing which variable is used to compute the final max, we can extract it from any variable, because this will lead to the same maximum value. However, taking the arg max for each variable will yield the desired most probable explanation $x_1^{*},x_2^{*},x_3^{*},x_5^{*}$—the configuration of all variables which has the greatest probability. Generalizing these ideas and performing them efficiently leads to the max-product algorithm, a general template for performing such computations exactly in arbitrary tree-structured graphs.

The max-product or max-sum algorithm

The max-product algorithm can be used to find the most probable explanation in a tree-structured probability model. It is generally implemented in logarithmic space to alleviate problems with numerical stability, where it is better characterized as the max-sum algorithm. Since the log function increases monotonically, $\log (\underset{x}{\max }p(x))=\underset{x}{\max }\log p(x)$, and, as mentioned above, $\max (c+a,c+b)=c+\max (a,b)$. These properties allow the maximum probability configuration in a tree-structured probability model to be computed as follows.

As in the sum-product algorithm, variables or factors that have only one connection in the graph begin by sending either a function-to-variable message consisting of ${\mu }_{x\to f}(x)=0$, or a variable-to-function message consisting of ${\mu }_{f\to x}(x)=\log f(x)$. Each function and variable node in the graph waits until it has received a message from all neighbors other than the node that will receive its message. Then function nodes send messages of the following form to variable x

${\mu }_{f\to x}(x)=\underset{x_1,\dots ,x_K}{\max }\left[\log f(x,x_1,\dots ,x_K)+\sum _{k\in N(f)x}{\mu }_{x_k\to f}(x_k)\right],$

where the notation N(f)x is the same as for the sum-product algorithm above. Likewise, variables send messages of this form to functions:

${\mu }_{x\to f}(x)=\sum _{k\in N(x)f}{\mu }_{f_k\to x}(x),$

where the sum is over the messages from all functions other than the recipient function. When the algorithm terminates, the probability of the most probable configuration can be extracted from any node using

$p*=\underset{x}{\max }\left[\sum _{k\in N(x)}{\mu }_{f_k\to x}(x)\right].$

The most probable configuration itself can be obtained by applying this computation to each variable:

$x*=\underset{x}{\text{arg}\max }\left[\sum _{k\in N(x)}{\mu }_{f_k\to x}(x)\right].$

To understand how this works for a concrete example, follow the sequence of messages illustrated in Fig. 9.17, but use the max-product messages defined above and the final computations for the max and arg max in place of the sum-product messages we examined earlier.

The max-product algorithm is widely used to make final predictions for tree-structured Bayesian networks, as well as for sequences of labels in conditional random fields and hidden Markov models, discussed in Sections 9.7 and 9.8, respectively.