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)$mi→j​(xj​)=xi​∑​ϕi​(xi​)ψij​(xi​,xj​)k∈N(i)\{j}∏​mk→i​(xi​)

  • 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)$p×i​(xi​)∝ϕi​(xi​)j∈N(i)∏​mj→i​(xi​)

• Remarks

  • 什么是 message？

  • tree 的一枝表示什么？实际上就是一个条件分布，如下图中实际上就是 $m_2(x_1)=\sum_{x_2,x_4,x_5}p(x_2,x_4,x_5|x_1)$m2​(x1​)=∑x2​,x4​,x5​​p(x2​,x4​,x5​∣x1​)

    

2. Sum-product algorithm on factor trees

• 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)$mi→a​(xi​)=b∈N(i)\{a}∏​mb→i​(xi​)

  • 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)$ma→i​(xi​)=xN(a)\{i}​∑​fa​(xi​,xN(a)\{i}​)j∈N(a)\{i}∏​mj→a​(xj​)

3. Max-Product for undirected tree/factor tree

4. Parallel Max-Product

• 所有节点同时运算，至多需要 d(最长path的length) 次迭代即可
• trick: 整体的减少乘法次数

• 点赞
• 收藏
• 分享
• • 文章举报

Bonennult 发布了37 篇原创文章 · 获赞 27 · 访问量 2万+ 私信 关注