通过枚举进行推理

14.4.1 通过枚举进行推理

第十三章解释了任何条件概率都可以通过将全联合概率分布表中的某些项相加而计算得到。更明确地说，查询P(X|e)可以通过公式（13.6）来回答，为了方便，这里我们重复一下这个公式：

现在，贝叶斯网络给出了全联合概率分布的完备表示。更明确地说，公式（14.1）表明联合概率分布中的项P(x, e, y)可以根据网络写成条件概率乘积的形式。因此，在贝叶斯网络中可以通过计算条件概率的乘积并求和来回答查询。

在图13.4中，给出了一个算法ENUMERATE-JOINT-ASK，通过根据全联合概率分布进行枚举来实现推理。算法将全联合概率分布 P 作为输入，不断在其中查找数据。将该算法更改成以贝叶斯网络 bn为输入是一件非常容易的事情，然后可以通过计算来自bn的条件概率表中相应条目的乘积以“查找”联合概率分布的条目。

考虑查询P(Burglary|JohnCalls = true, MaryCalls = true)。该查询的隐变量是Earthquake和Alarm。根据公式（13.6），使用变量的首字母以便简化表达式，我们有：[15]

于是贝叶斯网络的语义（公式（14.1））给了我们一个根据条件概率表描述的表达式。为了简化，我们仅给出Burglary = true的计算过程：

为了计算这个表达式，我们需要对4个项进行加法运算，而每一项都是通过5个数相乘计算得到。在最糟糕的情况下我们需要对所有的变量进行求和，因此对于有n个布尔变量的网络而言，算法的复杂度将是O(n 2n)。

不过根据下面这个简单的观察事实可以得到对算法的改进：P(b)项是常数，因此可以从对 a 和 e的求和符号中挪出去，而P(e)项也可以从对a的求和符号中挪出去。因此我们得到：

这个表达式可以通过按顺序循环遍历所有变量并把条件概率表中的对应条目乘起来进行求值计算。对于每次求和运算，我们还需要对变量的可能取值进行循环。计算过程的结构如图 14.8 所示。利用图 14.2中的数据，我们得到P(b|j, m) = α × 0.00059224，¬b的相应计算结果为α × 0.0014919。因此有

P(B|j, m) = α 0.00059224, 0.0014919 ≈ 0.284, 0.716

也就是说，在两个邻居都给你打电话的条件下出现盗贼的概率大约是28％。

公式（14.3）中表达式的计算过程在图14.8中显示为一棵表达树。图14.9中的ENUMERATION-ASK算法通过深度优先递归对这棵树进行求值。因此，算法ENUMERATION-ASK的空间复杂度对于变量个数是线性的——这非常高效，算法对全联合分布求和而不用显式地构造它。不幸的是，对于一个有n个布尔变量的网络，该算法的时间复杂度始终都是O(2n) ——比前面描述的那种简单算法的O(n2n)复杂度要低，但仍然非常可怕。关于图14.8中的树，有一件值得注意的事情，即它明确给出了算法所需计算的重复子表达式。对于e的每个不同取值，乘积P(j|a)P(m|a)和P(j|¬a)P(m|¬a)都分别计算了两次。下一节描述能够避免这种计算浪费的方法。

图14.8 公式（14.3）所示表达式的结构。求值运算过程自顶向下进行，将每条路径上的值相乘，并在“+”节点求和。注意从节点j到m的重复路径

图14.9 在贝叶斯网络上回答查询的枚举算法