PAPER NOTES · 2001
Factor 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.
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
01
The factorization
02
The five-step example
03
Inside one message
Arrow keys advance · Page Up / Page Down navigate from a demo · Escape returns focus to the slides
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 498–503
1 / 14
01 · THE COMPUTATIONAL PROBLEM
A 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)\]
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 499
2 / 14
01 · EXAMPLE 1, EQUATION (2)
The 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)\]
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
Five variables · Five factors · Nine edges · A connected tree, redrawn in the orientation of Figure 7
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 499–500, 503
3 / 14
01 · WHY THE GRAPH SAVES WORK
The 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}\]
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 500
4 / 14
01 · EQUATIONS (5) AND (6)
Two 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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 502–503
5 / 14
02 · A NUMERICAL VERSION OF EXAMPLE 1
Concrete 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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 499–503
6 / 14
02 · FIGURE 7 AND SECTION II-D
The five-step message schedule
Messages move inward, meet across the central edge, then move outward.
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 503
7 / 14
02 · INTERACTIVE EXAMPLE
How 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
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
\[\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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 503
8 / 14
03 · ANATOMY OF A MESSAGE
Inside 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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 503
9 / 14
03 · INTERACTIVE CALCULATION
Each 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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 502–503
10 / 14
04 · TERMINATION AND NORMALIZATION
Messages combine into exact marginals
A marginal uses every incoming factor message; an outgoing message excludes one.
\[g_i(x_i)=\prod_{f\in N(x_i)}\mu_{f\to x_i}(x_i),\qquad p_i(x_i)=\frac{g_i(x_i)}{\sum_{a\in\{0,1\}}g_i(a)}\]
\[\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.
\(p(x_1=1)\)
0.2935
\(p(x_2=1)\)
0.6148
\(p(x_3=1)\)
0.5830
\(p(x_4=1)\)
0.4929
\(p(x_5=1)\)
0.6054
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 503
11 / 14
04 · WHY A TREE IS SPECIAL
One cut separates the information
Every message summarizes the factors on its sender’s side of an edge.
\(f_A\)
\(x_1\)
\(f_B\)
\(x_2\)
\(f_C\)
\(x_3\)
\(f_D\)
\(x_4\)
\(f_E\)
\(x_5\)
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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 501–503, 516–517
12 / 14
05 · THE WIDER PAPER
The 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.
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 506–514
13 / 14
SOURCES & READING
The paper and the worked example
The source supplies the symbolic example; this lesson supplies its numerical instantiation.
Factor Graphs and the Sum-Product Algorithm
Frank R. Kschischang, Brendan J. Frey and Hans-Andrea Loeliger.
IEEE Transactions on Information Theory, 47(2), 498–519, February 2001.
DOI: 10.1109/18.910572 ↗
Author-hosted paper at ETH Zürich ↗
Example 1 & Figure 1: pp. 499–500 · Update rules: p. 502
Five-step example & Figure 7: p. 503 · Cyclic graphs: Section V
Static reading / print view ↗
BAI LIPING · RANDOM THOUGHTS
Kschischang, Frey & Loeliger (2001) · p. 498–519
14 / 14