1. Elimination algorithm

• 主要目的是为了计算边缘分布

• Reconstituted graph: 若消去的随机变量为 $x_k$xk​，则所有与 $x_k$xk​ 连接的随机变量会形成一个新的 clique

  

• 复杂度

  • Brute-force marginalization：$O\left(|\mathcal{X}|^N\right)$O(∣X∣N)
  • Zig-zag elimination：$O\left(|\mathcal{X}|^{\sqrt{N}}\right)$O(∣X∣N​)

2. MAP elimination algorithm

• 计算 MAP $\boldsymbol{x}^{*} \in \arg \max _{\boldsymbol{x} \in \mathcal{X}^{N}} p_{\mathbf{x}}(\boldsymbol{x})$x∗∈argmaxx∈XN​px​(x)
  $\begin{array}{l}{\max _{x, y} f(x) g(x, y)=\max _{x}\left(f(x) \max _{y} g(x, y)\right)} \\ {\sum_{x, y} f(x) g(x, y)=\sum_{x}\left(f(x) \sum_{y} g(x, y)\right)}\end{array}$maxx,y​f(x)g(x,y)=maxx​(f(x)maxy​g(x,y))∑x,y​f(x)g(x,y)=∑x​(f(x)∑y​g(x,y))​

• example
  $p_{\mathbf{x}}(\boldsymbol{x}) \propto \exp \left(x_{1} x_{2}-x_{1} x_{3}-x_{2} x_{4}+x_{3} x_{4}+x_{3} x_{5}\right)$px​(x)∝exp(x1​x2​−x1​x3​−x2​x4​+x3​x4​+x3​x5​)
  

• algorithm

  

• complexicity

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

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