Exercises

$\partial A = \{1\}, \partial B = \{1,2\}, \partial C = \{2,3\}, \partial D = \{3,4\}$.

4 variable nodes + 4 factor nodes = 8 nodes. Edges: $1 + 2 + 2 + 2 = 7$. $E = V + F - 1 = 8 - 1 = 7$. ✓ This is a tree (in fact a chain with a leaf factor at node 1).

A single factor node $f$ connected to all three variable nodes. This is a star with the factor at the center. It is a tree (no cycles).

Inference cost is $|\mathcal{X}|^3$ — the factor's own size. Factor graphs do not make dense factors cheap; they just make the structure explicit.

$\mathbf{T} = \begin{pmatrix} 0.9 & 0.1 \\ 0.1 & 0.9 \end{pmatrix}$ for states $\{0,1\}$.

Starting from $x_1 = 0$: $\mu_{\text{fwd}}(x_2) = T[0, x_2] = (0.9, 0.1)$.

Backward from $x_4 = 1$: compute $\mu_{\text{bwd}}(x_3) = T[x_3, 1] = (0.1, 0.9)$. Then $\mu_{\text{bwd}}(x_2) = \sum_{x_3} T[x_2, x_3] \cdot \mu_{\text{bwd}}(x_3)$ $= (0.9 \cdot 0.1 + 0.1 \cdot 0.9, 0.1 \cdot 0.1 + 0.9 \cdot 0.9) = (0.18, 0.82)$.

$b(x_2) \propto (0.9, 0.1) \cdot (0.18, 0.82) = (0.162, 0.082)$, so $p(x_2 = 0 | x_1 = 0, x_4 = 1) = 0.162/0.244 \approx 0.664$. $p(x_2 = 1 | \ldots) \approx 0.336$.

Regardless of elimination order, at some point a horizontal or vertical line of $k$ variables must be active (connects upper and lower halves). Eliminating any variable on that line creates a clique among the others.

Exact inference cost is $|\mathcal{X}|^{\text{tree-width} + 1} \geq |\mathcal{X}|^{k+1}$. For $k = 10, |\mathcal{X}| = 2$: $2^{11} = 2048$. For $k = 20$: $2^{21} \approx 2\times 10^6$. For $k = 30$: $2^{31} \approx 2\times 10^9$. Exact inference on a $30\times30$ Ising grid is already at the edge of feasibility.

Row 1: columns $\{1,2,3\}$. Row 2: $\{3,4,5\}$. Row 3: $\{1,5,6\}$.

Rows 1&2: share column 3 only. Rows 1&3: share column 1 only. Rows 2&3: share column 5 only. No two rows share 2 or more columns.

No 4-cycles. Girth $\geq 6$. This matrix would be considered acceptable for loopy BP decoding (absent longer cycles that degrade performance).

Variable nodes $x_0, x_1, x_2, x_3, x_4$ (treating $x_0$ as a boundary). Factors: $f_1(x_0, x_1), f_2(x_1, x_2), f_3(x_2, x_3), f_4(x_3, x_4)$. Prior factors $g_t(x_t)$ on each variable.

Chain structure, tree-width 1 (pairwise factors on a chain). BCJR runs in $O(n|\mathcal{X}|^2)$.

For a tree with $n$ nodes, sum-product computes exact marginals. Base case: $n = 1$ (single node) is trivial.

Rooting at variable node $i$, each neighbor factor $a \in \partial i$ is the root of a subtree $\mathcal{T}_a$ containing variables $\mathbf{x}_{\mathcal{T}_a}$.

$p(x_i) = \sum_{\mathbf{x}_{-i}} \prod_a \left[\prod_{b \in \mathcal{T}_a} f_b\right]$. Since the subtrees share only $x_i$, the sum factorizes: $p(x_i) \propto \prod_a \sum_{\mathbf{x}_{\mathcal{T}_a \setminus i}} \prod_{b \in \mathcal{T}_a} f_b = \prod_a \mu_{a \to i}(x_i)$, by definition of the message.

$V + F - 1 = 12 + 8 - 1 = 19$. $E = 24 > 19$. Not a tree.

$E - V - F + 1 = 24 - 12 - 8 + 1 = 5$. The graph has 5 independent cycles (in the cycle space).

$f_A = p(a), f_B = p(b|a), f_C = p(c|a), f_D = p(d|b,c)$.

$\partial A = \{a\}, \partial B = \{a, b\}, \partial C = \{a, c\}, \partial D = \{b, c, d\}$.

The path $a - f_B - b - f_D - c - f_C - a$ closes a cycle. Not a tree. This is the classical "V-structure" (common child) causing a loop in the factor graph.

Leaves have trivial incoming messages; their outgoing messages depend only on themselves. After the first pass (outward from leaves to root), all messages from leaves toward root are set.

After root-to-leaves pass, all messages from root toward leaves are set. Now every directed edge has a message value.

The next iteration recomputes each message using its inputs — which are unchanged. So iterate once more and nothing changes. A fixed point is reached in two passes.

After $t$ iterations, message $\mu_{a \to i}$ depends on observations within a $t$-hop neighborhood of $i$. If $t < g/2$, this neighborhood is a tree (no cycle fits).

The computation is identical to sum-product on the $t$-hop unrolled tree around $i$. For $t < g/2$ iterations, loopy BP = exact BP on a finite tree.

Loopy BP makes its first mistake only after $\lceil g/2 \rceil$ iterations. Large girth delays the onset of approximation errors.

1 variable node at depth 0.

$d_v$ check nodes adjacent to the origin. Each check has $d_c - 1$ other variable neighbors: $d_v (d_c - 1)$ variables at depth 2.

Each variable at depth $2k$ has $d_v - 1$ new check neighbors (one check is the parent), each leading to $d_c - 1$ new variable nodes. At depth $2t$: $d_v (d_c - 1)^{t} (d_v - 1)^{t-1}$... actually let me redo. Number of variables at depth $2k$ is $d_v (d_c - 1) \prod_{j=1}^{k-1}(d_v - 1)(d_c - 1) = d_v (d_c - 1)^k (d_v - 1)^{k-1}$.

Girth $\geq 2t$ ensures no two paths of length $< t$ from origin meet, so the enumeration is exact (no double-counting).

A ring of $n$ binary variables with pairwise factor $f(x_i, x_{i+1}) = \exp(-\theta x_i x_{i+1})$ (antiferromagnetic, $\theta > 0$). For $n$ odd, BP has multiple fixed points by frustration.

With multiple fixed points, different initializations lead to different outputs. Convergence is not guaranteed to the "best" fixed point; damping and random restarts may be needed.

In practice, check BP by running from multiple initializations and comparing outputs. Divergence between runs is a red flag.

On trees. The Bethe approximation treats factor marginals as if they were independent except for the consistency constraints. On a tree, the global distribution literally factorizes pairwise in this way. On loops, there is residual dependence not captured.

Two rows sharing $\geq 2$ column indices. Since each row has 3 ones out of 4 columns, and $\binom{4}{3} = 4$, two rows differ in exactly one position. Hence they share 2 columns — always. So girth is exactly 4 for any such code.

Maximum girth is 4 for this size. To avoid 4-cycles we would need either more variable nodes ($n \geq 6$) or smaller check degree.

Variable nodes: $x_1, x_2, \ldots, x_T$ (continuous). Factors:

• $f_t(x_t, x_{t+1}) = \mathcal{N}(x_{t+1}; Ax_t, Q)$ — transitions.
• $g_t(x_t) = \mathcal{N}(y_t; Cx_t, R)$ — observations (clamped).

Chain of state variables with transition factors and unary observation factors. Tree-width 1.

Each message is a Gaussian (mean + covariance of dimension $d$). Message update involves matrix multiplies and inversions: $O(d^3)$ per step. Total $O(Td^3)$ — the Kalman filter complexity.

A pairwise factor graph converts to a Markov random field with one edge per pairwise factor. Conversely, every pairwise MRF has a unique factor graph (one factor per edge). The graphs are isomorphic after collapsing factor nodes.

Pairwise MRFs are a restricted family. Real-world models with ternary or higher-arity factors (e.g., parity checks) are more naturally expressed as factor graphs.

A fixed point satisfies $\mu = T(\mu)$ for the message update operator $T$. This condition is independent of update order.

Flooding: all messages update simultaneously, $\mu^{(t+1)} = T(\mu^{(t)})$. Serial: messages update one at a time in some order. Jacobian of the update differs: serial can converge when flooding oscillates, because it uses freshly updated messages.

Serial scheduling typically converges faster and more reliably. The standard LDPC decoder uses a layered (block serial) schedule.

(1) Channel decoding (LDPC, turbo): Tanner graph + loopy BP. (2) Signal processing (Kalman filter, HMM): chain graphs + forward-backward. (3) Machine learning (Bayesian networks, MRFs): message passing, variational inference, sampling. Also: robotics (SLAM), statistical physics (Ising models), compressed sensing.

Choose overlapping regions (clusters) that cover each factor. Form a region graph: larger regions at top, smaller (intersections) below.

Pass messages between regions. The resulting fixed points minimize a Kikuchi free energy, a generalization of Bethe that accounts for multi-node correlations.

Larger regions → better approximation, but exponential cost in region size. Generalized BP bridges loopy BP (regions = factors) and exact inference (regions = whole graph).