Conditional Probability Queries

NP-Hard Problem

在一个概率图模型里，查询一组变量为给定值时的概率是一个NP-HARD问题，不仅如此，降低问题所需答案的精度，仍然是一个NP-Hard问题。因为求解概率分母Z的时候，涉及到众多变量的众多组合情况，需要求的因子太多了。

Sum-Product

条件概率的计算上，虽然分子只是连乘了几个不同的因子，变量后我们可以把与这个变量取值矛盾的部分给删除掉，计算量有所缩减。除此之外，求解条件概率的时候，分子采用联合概率$P(Y, E = e)$P(Y,E=e)，分母采用边缘概率$P(E = e)$P(E=e)，这样这俩概率，在计算时无需求解归一化分母Z，因为Z将会消除。

MAP Inference

实际上MAP就是在求，已经知道$E=e$E=e的情况下，除了$E$E以外的其他变量$Y$Y最有可能是多少，这里对$Y$Y的理解应该是，不能等于E，但也不是任取，总之得有关联。$Y$Y的最大后验并非其边缘概率的最大值，而是在已经知道$E$E的情况下，$Y$Y最大的概率值。

NP-Hard Problem

很遗憾，在给定概率图模型上寻找给定Evidence的最大后验，这又是一个NP-Hard问题降低精度后还是一样Hard。

Max-Product

这个后验概率的分母是一个常值，和条件概率不同，由于我们需要最大化它，而不是求它，可以忽略分母，只看分子。而分子我们可以看一下，是一系列reduced factor的乘积，我们需要再这些乘积之间横向比较，选出一个最大值，这才是我们要求解的最大后验对应的$Y$Y。

Variable Elimination Algorithm

从这个图例我们可以看出来，我们把某个与求和有关的因子$(\phi_{1}(A,B))$(ϕ1​(A,B))留在求和号$\Sigma$Σ右边，把其他因子提到前面，最后这个求和就可以把A给消元了，留下一个先验$\tau_{1}(B)$τ1​(B)，至此，A就没了，B成了马尔科夫链的末端。
同样的，我们可以把B也给消元了。

更复杂的情况下，可以看到，我们再边缘化D的时候，遇到了两项，我们对这两项求和，得到了一个有两个scope元素的因子$\tau_{2}(G,I)$τ2​(G,I)。这个生成的$\tau$τ以后再遇到需要消元的时候可以变成一个新的$\tau$τ。

Variable Elimination with evidence

当有Evidence时，我们消元的时候就不对那些已经有Evidence的变量进行求和。因为他们就只有一个取值。除此之外，还需要将包含Evidence变量的因子替换成reduced factor。

Variable Elimination in Marcov Networks

马尔可夫网络的消元和前面一模一样。最后求出来的那个$\tau_{3} = \tilde{P}(D) \propto P(D)$τ3​=P~(D)∝P(D)。
实际上消元就是对包含待消元元素的因子进行求和的过程。消元之后，因子图中会减少一个被消元变量$Z$Z和一到多个被求和因子$\phi$ϕ，增加一个因子$\tau$τ，而这个$\tau$τ就是那些被求和因子的和，被作为新的因子添加到因子图。但是若最后想得到一个分布，需要对最终求得的$\tau$τ进行一波归一化操作。

Updated