一个图模型包含 $N$ 个随机变量 $\underline{x}=(x_1,\dots,x_N)$，从有限字母表 $\mathcal{X}$ 中取值. 需要解决一些问题，例如：

• 给定一些条件，求另一些变量的边缘分布；
• 一些后验估计相关

但是我们不会去直接计算联合分布 $p(\underline{x})$，因为它的状态空间是指数级别 $|\mathcal{X}|^N$ 个取值. BP 将这个问题转化为局部计算，利用图的稀疏性/特殊结构来避免指数级别的计算.

Example 1: Ising chain

Ferromagnetic Ising model has $\underline{\sigma}=(\sigma_1,\dots, \sigma_N), \sigma_i\in\{1,-1\}$ with joint distribution

$$ \mu_\beta(\underline{\sigma}) = \frac{1}{Z} \exp\left(\beta \sum_{i=1}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^N\sigma_i\right) $$

where $Z$ is the partition function.

我们计算 $\sigma_j$ 的 marginal distribution, 这里用 $\propto$ 来省略归一化因子:

$$\mu(\sigma_j)\propto\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^N\sigma_i\right) \\=\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{j-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^{j-1}\sigma_i\right)\exp\left(\beta\sum_{i=j}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=j+1}^{N}\sigma_i\right)\exp\left(\beta B\sigma_{j}\right)$$

分配拆开即可，是两个和的乘积. 定义 “message”:

This decomposition is interesting because the various messages can be computed iteratively.