01 / 14Factor graphs & the sum-product algorithm
Frank R. Kschischang · Brendan J. Frey · Hans-Andrea Loeliger
Belief propagation,
one message at a time
A reading of the paper’s opening example: how local sums and products recover global marginals.
Kschischang, Frey & Loeliger (2001) · p. 498–503
02 / 14A marginal sums over everything else
The global function is a product; the question concerns just one of its variables.
\[g(x_1,\ldots,x_n)=\prod_{a\in F} f_a(\mathbf x_a)\]
\[g_i(x_i)=\sum_{\mathbf x\setminus x_i}\prod_{a\in F}f_a(\mathbf x_a)\]
For nonnegative factors with finite, positive total mass, normalize the marginal to obtain a probability.
\[p_i(x_i)=\frac{g_i(x_i)}{Z},\quad Z=\sum_{x_i}g_i(x_i)\]
Kschischang, Frey & Loeliger (2001) · p. 499
03 / 14The paper’s five-variable factor graph
A circle represents a variable; a square represents one local function.
\[g(\mathbf x)=f_A(x_1)f_B(x_2)f_C(x_1,x_2,x_3)f_D(x_3,x_4)f_E(x_3,x_5)\]
Five variables · Five factors · Nine edges · A connected tree, redrawn in the orientation of Figure 7
Kschischang, Frey & Loeliger (2001) · p. 499–500, 503
04 / 14The distributive law exposes reusable sums
For the central variable, the three branches can be summarized independently.
\[\begin{aligned}g_3(x_3)=&\underbrace{\sum_{x_1,x_2}f_A(x_1)f_B(x_2)f_C(x_1,x_2,x_3)}_{\text{left branch}}\\[-2pt]&\times\underbrace{\sum_{x_4}f_D(x_3,x_4)}_{\text{upper branch}}\times\underbrace{\sum_{x_5}f_E(x_3,x_5)}_{\text{lower branch}}\end{aligned}\]
Each bracket is a function of only the variable at the branch boundary.
Store that function as a message. Reuse it when computing other marginals.
Kschischang, Frey & Loeliger (2001) · p. 500
05 / 14Two local message rules
Every outgoing message excludes the message arriving from its recipient.
Variable → factor
Multiply the other incoming messages, point by point.
\[\mu_{x\to f}(x)=\prod_{h\in N(x)\setminus\{f\}}\mu_{h\to x}(x)\]
Factor → variable
Multiply by the local factor, then sum out every variable except the recipient.
\[\mu_{f\to x}(x)=\sum_{\mathbf x_f\setminus x} f(\mathbf x_f)\!\prod_{y\in N(f)\setminus\{x\}}\mu_{y\to f}(y)\]
Leaf variable: \(\mu=1\). Leaf factor: send the factor itself. A message is a function, not a single belief.
Kschischang, Frey & Loeliger (2001) · p. 502–503
06 / 14Concrete factor values for the demo
The paper leaves these functions symbolic. The following binary model is a teaching choice.
\(x_i\in\{0,1\}\) for every variable. Factor arguments and graph topology remain exactly those of Example 1.
\[f_A=[0.7,\;0.3],\quad f_B=[0.4,\;0.6]\]
\[f_C=\begin{cases}q&x_3=x_1\oplus x_2\\1-q&\text{otherwise}\end{cases}\quad q=0.85\]
The XOR of two bits is 1 when they differ. The central factor favors that relation.
\[f_D=\begin{pmatrix}3&1\\1&2\end{pmatrix}\]
\[f_E=\begin{pmatrix}2&1\\1&4\end{pmatrix}\]
Rows index \(x_3\); columns index \(x_4\) or \(x_5\). These are nonnegative weights.
Kschischang, Frey & Loeliger (2001) · p. 499–503
07 / 14The five-step message schedule
Messages move inward, meet across the central edge, then move outward.
1
Leaves send their initial messages
2
The outer branches summarize
3
The central edge carries both directions
4
The centre sends outward
5
The leaf marginals are available
Next: compare the two central messages at step 3. Select step 1 to replay the full schedule.
Kschischang, Frey & Loeliger (2001) · p. 503
08 / 14How each message is computed
Click an arrow for its arithmetic, or a variable for the messages that form its belief.
STEP 3 / 5 · The two halves exchange summaries
\[\begin{aligned}\mu_{f_C\to x_3}(1)&=0.15(0.7)(0.4)\\&\quad+0.85(0.7)(0.6)\\&\quad+0.85(0.3)(0.4)\\&\quad+0.15(0.3)(0.6)\\&=0.528\end{aligned}\]
\[\mu_{f_C\to x_3}=[0.472,\;0.528]\]
The left message summarizes \(f_A,f_B,f_C\). It excludes the return message from \(x_3\).
Combining all three inputs at \(x_3\) gives \(p(x_3=1)=0.5830\) after normalization.
Kschischang, Frey & Loeliger (2001) · p. 503
09 / 14Inside the central factor’s sum
Hold the destination variable fixed. Enumerate only the other factor arguments.
\[\mu_{f_C\to x_3}(x_3)=\sum_{x_1,x_2}f_A(x_1)f_B(x_2)f_C(x_1,x_2,x_3)\]
For \(x_3=1\), the four contributions are
\[\begin{aligned}0.7\cdot0.4\cdot0.15&=0.042\\0.7\cdot0.6\cdot0.85&=0.357\\0.3\cdot0.4\cdot0.85&=0.102\\0.3\cdot0.6\cdot0.15&=0.027\end{aligned}\]
\[\mu_{f_C\to x_3}(1)=0.528\]
The recipient’s message \(\mu_{x_3\to f_C}\) does not appear in this sum.
Next: change the factor inputs. At \(q=0.5\), the outgoing message is uniform.
Kschischang, Frey & Loeliger (2001) · p. 503
10 / 14Each output value gets its own sum
Choose the retained value, then vary the two unary weights and the XOR agreement.
Retained value: \(x_3=1\)
\[\begin{array}{cc|ccc|c}x_1&x_2&f_A&f_B&f_C&\text{product}\\\hline0&0&0.7&0.4&0.15&0.042\\0&1&0.7&0.6&0.85&0.357\\1&0&0.3&0.4&0.85&0.102\\1&1&0.3&0.6&0.15&0.027\end{array}\]
\[\mu_{f_C\to x_3}=[0.472,\;0.528]\]
Every row multiplies local evidence. The final addition eliminates the two input variables.
The numerical values are illustrative; the update is the paper’s exact sum-product rule.
Kschischang, Frey & Loeliger (2001) · p. 502–503
11 / 14Messages combine into exact marginals
A marginal uses every incoming factor message; an outgoing message excludes one.
\[\begin{aligned}g_3&=[0.472,\;0.528]\odot[4,\;3]\odot[3,\;5]\\&=[5.664,\;7.920]\\Z&=13.584\end{aligned}\]
Normalize once to obtain \(p_3(1)\approx0.583039\). The central message alone would give 0.528.
| Variable | Probability of 1 |
|---|
| \(x_1\) | 0.293507 |
| \(x_2\) | 0.614841 |
| \(x_3\) | 0.583039 |
| \(x_4\) | 0.492933 |
| \(x_5\) | 0.605418 |
Kschischang, Frey & Loeliger (2001) · p. 503
12 / 14One cut separates the information
Every message summarizes the factors on its sender’s side of an edge.
CUT ONE EDGE
On a tree, the two sides share only the boundary variable. Their factors are disjoint.
Sum each side separately, then multiply the two messages to recover the exact marginal. Two messages per edge suffice.
Local cost still grows with the number of states in a factor’s arguments.
Kschischang, Frey & Loeliger (2001) · p. 501–503, 516–517
13 / 14The same rule appears in many algorithms
Graph structure and message representation determine the familiar special case.
Chain / hidden Markov model
Forward–backward uses finite state message vectors.
Linear Gaussian state model
Gaussian messages give Kalman filtering and smoothing.
Alternative sum/product operations
The semiring view connects related dynamic programs.
What changes with cycles?
Messages are reused iteratively, and the separated-subtree argument no longer applies.
Convergence and exact marginals are not guaranteed in general.
The five-step exact result belongs to this tree.
Kschischang, Frey & Loeliger (2001) · p. 506–514
14 / 14The paper and the worked example
The source supplies the symbolic example; this lesson supplies its numerical instantiation.
Frank R. Kschischang, Brendan J. Frey and Hans-Andrea Loeliger.
IEEE Transactions on Information Theory, 47(2), 498–519, February 2001.
Example 1 & Figure 1: pp. 499–500 · Update rules: p. 502
Five-step example & Figure 7: p. 503 · Cyclic graphs: Section V
Kschischang, Frey & Loeliger (2001) · p. 498–519