In this lecture, we will wrap up our discussion on message passing.
For our discussion, we started with a pairwise MRF
$$ \begin{aligned}
p(x) &= \frac{1}{Z} \prod_i \phi_i(x_i) \prod_{(i, j) \in \mathrm{pairs}} \phi_{i, j} (x_i, x_j). \\ \end{aligned} $$
Then, the message from $i$ to $j$ is given by
$$ \begin{aligned} m_{i \rightarrow j}(x_j) = \sum_{x_i} \phi_i(x_i)\phi_{i,j}(x_i, x_j) \prod_{l \in \mathrm{nb}(i) \backslash j} m_{l \rightarrow i} (x_i). \end{aligned} $$
Remember:
Whenever we do message passing, we need to do this in the correct order, that is, when you compute $m_{i \rightarrow j}, m_{l \rightarrow i}$ must already exist (messages from all other neighbors of $j$ apart from $i$.)
This also hints at the class of graphs for which message passing works: If there is a loop (cycle) in the graph, then there is no good way to order the nodes in the loop (try it—you will soon realize that this is a chicken and an egg problem.)
However, If your graphs are tree-like (or a collection of tree-like sub-graphs: a forest), the message passing algorithms are a great alternative!
Normalization Constant
The normalization constant for the MRF is given by
$$
Z = \sum_{x_i} \phi_i (x_i)\prod_{j \in \mathrm{nb}(i)} m_{j \rightarrow i} (x_i).
$$
Notice, we can calculate the normalization constant using any node $i$ (of course, we require all the messages to this node.)
Singleton Marginals
The singleton marginal is given by
$$ p(x_i) = \frac{1}{Z} \phi_i(x_i) \prod_{j \in \mathrm{nb}(i)} m_{j \rightarrow i} (x_i).
$$
The above equation is eerily similar to the equation for the normalization constant. If you stare at this long enough, the difference will become apparent. The normalization constant sums over the different numerators of singleton marginal terms to—unsurprisingly—normalize the distribution.