下载掌阅APP，畅读海量书库
立即打开
在更复杂的贝叶斯网络中，可以使用不同的方法执行有效的推理。其中一种方法被称为“ 和-积”变量消除 （sum-product variable elimination），该方法将消除隐藏变量（求和）与链式规则（乘积）的应用交织在一起的行为。这里建议尽早将变量边缘化，以避免产生大的因子，从而获得更好的效率。
我们将通过计算图3-1中贝叶斯网络的分布 P （ B | d 1 ， c 1 ）来演示说明变量消除的算法实现。与网络中的节点相关联的条件概率分布可以采用以下因子来表示：
由于 D 和 C 是观测变量，通过设置证据 D =1和 C =1，最后两个因子可以使用 ϕ 6 （ E ）和 ϕ 7 （ E ）来替代。
然后，我们依次消除所隐藏的各个变量。可以使用不同的策略来选择消除顺序，但在本例中，我们先任意选择 E ，然后选择 S 。为了消除 E ，我们取涉及 E 的所有因子的乘积，然后将 E 边缘化，从而得到一个新的因子：
现在可以丢弃 ϕ 3 、 ϕ 6 和 ϕ 7 ，因为我们需要的所有信息都包含在 ϕ 8 中。
接下来，我们消除 S 。同样，我们收集涉及 S 的所有剩余因子并从这些因子的乘积中排除 S ：
我们丢弃 ϕ 2 和 ϕ 8 ，剩下 ϕ 1 （ B ）和 ϕ 9 （ B ）。最后，我们对这两个因子的乘积进行归一化，得到表示 P （ B | d 1 ， c 1 ）的因子。
这个过程相当于计算以下内容：
其结果与采取朴素过程的结果相同，但这个过程的效率更高。朴素过程先计算所有因子的乘积，然后边缘化：
在算法3-5中，对“和-积”变量消除算法进行实现。该算法将贝叶斯网络、一组查询变量、观察值列表以及变量消除的顺序作为输入。首先设置所有观察值。然后，对于每个变量，将包含该变量的所有因子相乘，接下来将该变量边缘化。这个新的因子取代了处理之前的因子，然后对下一个变量重复这个过程。
算法3-5 “和-积”变量消除算法的一种实现。该算法采用贝叶斯网络bn、查询变量列表query和证据evidence作为参数，各个变量按照ordering给出的消除顺序依次进行处理
对于许多网络，变量消除允许在一段时间内完成推理，该时间与网络的大小规模成线性缩放，但在最坏的情况下，变量消除算法具有指数级的时间复杂度。变量的消除顺序将会影响算法的计算量。选择变量消除的最佳顺序是NP -困难 （NP-hard）问题 [1] ，这意味着在最坏的情况下，变量消除算法不能在多项式时间内完成（参见3.5节）。即使我们找到了变量消除的最佳顺序，变量消除仍然需要指数级的计算量。变量消除启发式方法通常试图最小化算法生成的中间因子中所涉及的变量数量。