Variable Elimination Complexity

消元Z主要有两步，一步是因子求积，第二步是边缘化，即对所有含有Z的因子进行一个求和，得到一个新的因子，并将变量Z边缘化掉。因此，每一个因子乘积最多被加一次（消元变量和他无关的时候就不用加这个因子了）。
想要消元B，做因子乘积的时候，把和b有关的因子乘积乘起来，为了求右边那个大表格的每一行，我们需要乘以的二元因子数量是$m_{k}-1$mk​−1，如为了求取3个变量的联合分布需要把两个因子相乘。$N_{k}$Nk​就是你这scope的排列组合数量，$2^{3}=8$23=8。因此整体的计算负担为$N_{k}*(m_{k}-1)$Nk​∗(mk​−1)。

而在消元过程中，我们实际上需要累加所有的情况，因此，$N_{k}$Nk​就是计算量，需要被累加元素的个数。

Elimination on Graph

在消元的时候，我们涉及的变量越多，消元复杂度就越高。所以我们尽量应该选择孤独的变量来进行消元。首先我们需要把贝叶斯网络中的V-structure添加边变成马尔可夫网络。因为，V-Structure中的三个变量是通过条件概率对应的三元因子联系在一起的。
由于对I的消元，我们生成了一个fill-edge，因为和I有关的因子被求和成了一个$\tau$τ，这个新因子包含的元素被联系在了一起。

Finding Elimination Order

很遗憾又是NP-HARD。只能用一些贪婪搜索算法之类的。只能搞一些启发式算法，这些算法都不能保证找到最好的顺序。
这些方法不保证好使。。。
但是在某些情况下，如机器人SLAM中，用MIN-FILL就可以实现BA图模型的稀疏性，毕竟别人发了IJRR