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

和积算法/信念传播算法

1. Sum-product(Message passing) on trees

• 目的是为了计算边缘分布，相比于 elimination 的优势在于可以用较少的计算次数计算所有随机变量的边缘分布，关键在于复用 message

• algorithm

  • Step 1: Compute messages $$m_{i\to j}\left(x_j\right)=\sum _{x_i}{\varphi }_i\left(x_i\right){\psi }_{ij}(x_i,x_j)\prod _{k\in N(i)\mathrm{\setminus }\{j\}}{m}_{k\to i}\left(x_i\right)$$

  • Step 2: Compute marginals $$p_{\times i}\left(x_i\right)\propto {\varphi }_i\left(x_i\right)\prod _{j\in N(i)}{m}_{j\to i}\left(x_i\right)$$

• Remarks

  • 什么是 message？

  • tree 的一枝表示什么？实际上就是一个条件分布，如下图中实际上就是 $$

    

    message

2. Sum-product algorithm on factor trees

• algorithm

  • Message from variable to factor $$

  • Message from factor to variable $$

3. Max-Product for undirected tree/factor tree

4. Parallel Max-Product

• 所有节点同时运算，至多需要 d(最长path的length) 次迭代即可

• trick: 整体的减少乘法次数 $$