Sungjoo Ha

Belief Propagation

Counting

Think of counting people in a tree by message passing.

Factor graphs and the sum-product algorithm

Appendix A of "Factor graphs and the sum-product algorithm"

From Factor Trees to Expression Trees Let $g(x, x_1, \ldots, x_{N - 1})$ be a function that can be represented by a cycle-free connected factor graph. i.e., a factor tree $T$. We are interested in developing an expression for

$$\sum_{\sim x} g(x, x_1, \ldots, x_{N - 1})$$

i.e., the summary for $x$ of $g$. We consider $x$ to be the root of $T$, so that all other vertices of $T$ are descendents of $x$.

Assuming that $x$ has $K$ neighbors in $T$, then without loss of generality $g$ may be written in the form

$$g(x, x_1, \ldots, x_{N - 1}) = \prod_{i = 1}^K F_i (x, X_i)$$

where $F_i(x, X_i)$ is the product of all local functions in the subtree of $T$ that have the $i$-th neighbor of $x$ as root, and $X_i$ is the set of variables in that subtree. Since $T$ is a tree, for $i \neq j$, $X_i \bigcap X_j = \emptyset$ and $X_1 \bigcup \cdots \bigcup X_K = \{x_1,, \ldots, x_{N - 1} \}$, i.e., $X_1, \ldots, X_K$ is a partition of $\{x_1, \ldots, x_{N-1}\}$. This decomposition is represented by the generic factor tree of Fig. 23, in which $F_1(x, X_1)$ is shown in expanded form.

Consider the case $i=1$. To compute the summary for $x$ of $F_1$, observe that, without loss of generality, $F_1(x, X_1)$ can be written as

$$F_1(x, X_1) = f_1(x, x_1, \ldots, x_L) \cdot G_1(x_1, X_{11}) \cdot G_2(x_2, X_{12}) \cdots G_L(x_L, X_{1L})$

where, for convenience, we have numbered the arguments of $g$ so that $f_1(x, x_1, \ldots, x_L)$ is the first neighbor of $x$. This decomposition is illustrated in Fig 23. We note that $\{x_1, \ldots, x_L \}, X_{11}, \ldots, X_{1L}$ is a partition of $X_1$. Again, using the fact that these sets are pair-wise-disjoint and applying the distributive law, we obtain

\begin{align} \sum_{\sim \{x\}} F_1(x, X_1) &= \sum_{\sim \{x\}} f_1(x, x_1, \ldots, x_L) \cdot G_1(x_1, X_{11}) \cdots G_L(x_L, X_{1L}) \\ &= \sum_{x_1, \ldots, x_L} f_1(x, x_1, \ldots, x_L) (\sum_{X_{11}} G_1 (x_1, X_{11})) \cdots (\sum_{X_{1L}} G_L(x_L, X_{1L})) \\ &= \sum_{\sim \{x\}} (f_1(x, x_1, \ldots, x_L) \prod_{i=1}^L \sum_{\sim \{x_i\}}G(x_i, X_{1i})) \end{align}

In words, we see that if $f_1(x, x_1, \ldots, x_L)$ is a neighbor of $x$, to compute the summary for $x$ of the product of the local functions in the subtree of $T$ descending from $f_1$, we should do the following:

  1. for each neighbor $x_i$ of $f_1$ (other than $x$), compute the summary for $x_i$ of the product of the functions in the subtree descending from $x_i$;

  2. form the product of these summaries with $f_1$, summarizing the result for $x$.

The problem of computing the summary for $x_i$ of the product of the local subtree descending from $x_i$ is a problem of the same general form with which we began, and so the same general approach can be applied recursively. The result of this recusion justifies the transformation of the factor tree for $g$ with root vertex $x$ into an expression tree for $\sum_{\sim \{x\}} g(x, x_1, \ldots, x_{N - 1})$, as illustrated in Fig 5.