贝叶斯网络中的变量消除

Question

我们最近研究了变量消除，老师强调它是贝叶斯网络使得消除变差效率更高。 我对此有点困惑，为什么会出现这种情况？ 希望你们能给我一些想法，非常感谢。

罗伯特

Answer 1

我想这是因为它可以消除一个变量是其有且只有一个变量，它是依赖于它。在贝叶斯网络中，这些将很容易找到，因为它们是单个孩子的节点。

Answer 2

贝叶斯网络可以利用变量消除的顺序的，因为内置于条件独立性假设。

具体地，想象具有联合分布P（A，B，C，d）和想知道的边际P（a）。如果你对条件独立性一无所知，你可以通过对b，c和d进行求和来计算。如果这些具有k-ary域，则需要执行O（k^3）操作。

另一方面，假设你有一个贝氏网，其中A是根，B是A的孩子，C是B的孩子，D是C的孩子。然后，你可以重写关节作为P（a | b）P（b | c）P（c | d）P（d）并且尽可能地将你的三个总和分配到等式的右边。当你真的想计算P（a）时，你可以预先计算sum_d P（d）的值并存储这个函数。同样，您可以预先计算P（c | d）* sum_d P（d）的值并存储它。

通过这种方式，您最终可以完成O（k^w * + 1）的工作，其中W *是贝叶斯网络中任何节点的最大子数。在这种情况下，我们做O（k^2）的工作，这也是我们必须保留在内存中的最大条件概率表的大小。请注意，这比我们原来的O（k^3）结果要好，如果我们有更多的变量，情况会更好。

简而言之，BN的条件独立性允许您更有效地排除变量。对此的另一个解释可以在http://www.cs.uiuc.edu/class/sp08/cs440/notes/varElimLec.pdf找到。