统计推断(十一) Sum-product algorithm

1. Sum-product(Message passing) on trees

目的是为了计算边缘分布，相比于 elimination 的优势在于可以用较少的计算次数计算所有随机变量的边缘分布，关键在于复用 message
algorithm
- Step 1: Compute messages
  $m_{i \rightarrow j}\left(x_{j}\right)=\sum_{x_{i}} \phi_{i}\left(x_{i}\right) \psi_{i j}\left(x_{i}, x_{j}\right) \prod_{k \in N(i) \backslash\{j\}} m_{k \rightarrow i}\left(x_{i}\right)$
- Step 2: Compute marginals
  $p_{\times i}\left(x_{i}\right) \propto \phi_{i}\left(x_{i}\right) \prod_{j \in N(i)} m_{j \rightarrow i}\left(x_{i}\right)$
Remarks
- 什么是 message？
- tree 的一枝表示什么？实际上就是一个条件分布，如下图中实际上就是 $m_2(x_1)=\sum_{x_2,x_4,x_5}p(x_2,x_4,x_5|x_1)$

algorithm
- Message from variable to factor
  $m_{i \rightarrow a}\left(x_{i}\right)=\prod_{b \in N(i) \backslash\{a\}} m_{b \rightarrow i}\left(x_{i}\right)$
- Message from factor to variable
  $m_{a \rightarrow i}\left(x_{i}\right)=\sum_{\mathbf{x}_{N(a) \backslash\{i\}}} f_{a}\left(x_{i}, \mathbf{x}_{N(a) \backslash\{i\}}\right) \prod_{j \in N(a) \backslash\{i\}} m_{j \rightarrow a}\left(x_{j}\right)$