6.6 贝叶斯网络中的精确推理 (Exact Inference in Bayes Nets)
推理是寻找某个概率分布 \(P(Q_1 \dots Q_k | e_1 \dots e_k)\) 的值的问题，如本笔记开头的概率推理部分所述。给定一个贝叶斯网络，我们可以通过形成联合 PDF 并使用枚举推理来简单地解决这个问题。这需要创建和迭代一个指数级大的表。
6.6.1 变量消元 (Variable Elimination)
另一种方法是逐个消去隐藏变量。要消去 (eliminate) 变量 \(X\)，我们：
- 连接（相乘）所有涉及 \(X\) 的因子。
- 对 \(X\) 求和消元。
因子 (factor) 简单地定义为_未归一化的概率_。在变量消元的所有时刻，每个因子都将与其对应的概率成正比，但每个因子的潜在分布不一定像概率分布那样总和为 1。变量消元的伪代码如下：
让我们用一个例子让这些想法更具体。假设我们有一个如下所示的模型，其中 \(T\)、\(C\)、\(S\) 和 \(E\) 可以取二进制值。这里，\(T\) 代表冒险者拿走宝藏的机会，\(C\) 代表如果冒险者拿走宝藏，笼子落在冒险者身上的机会，\(S\) 代表如果冒险者拿走宝藏，蛇被释放的机会，\(E\) 代表给定关于笼子和蛇的状态信息，冒险者逃脱的机会。
在这种情况下，我们有因子 \(P(T)\)、\(P(C|T)\)、\(P(S|T)\) 和 \(P(E|C,S)\)。假设我们想计算 \(P(T | +e)\)。枚举推理方法是形成 16 行联合 PDF \(P(T, C, S, E)\)，只选择对应于 +e 的行，然后对 \(C\) 和 \(S\) 求和消元，最后归一化。
另一种方法是一次消去一个变量，先消去 \(C\)，然后消去 \(S\)。我们将按如下方式进行：
连接（相乘）所有涉及 \(C\) 的因子，形成 \(f_1(C, +e, T, S) = P(C|T) \cdot P(+e|C, S)\)。有时这写成 \(P(C, +e | T, S)\)。
从这个新因子中对 \(C\) 求和消元，给我们留下一个新因子 \(f_2(+e, T, S)\)，有时写成 \(P(+e | T, S)\)。
连接所有涉及 \(S\) 的因子，形成 \(F_3(+e, S, T)=P(S|T) \cdot f_2(+e, T, S)\)，有时写成 \(P(+e, S | T)\)。
对 \(S\) 求和消元，产生 \(f_4(+e, T)\)，有时写成 \(P(+e | T)\)。
连接剩余的因子，得到 \(f_5(+e, T) = f_4(+e, T) \cdot P(T)\)。
一旦我们有了 \(f_5(+e, T)\)，我们可以通过归一化轻松计算 \(P(T|+e)\)。
当编写由连接产生的因子时，我们可以使用像 \(f_1(C, +e, T, S)\) 这样的因子符号，它忽略条件符号并简单地提供包含在此因子中的变量列表。
或者，我们可以写 \(P(C, +e | T, S)\)，即使这不保证是一个有效的概率分布（例如，行总和可能不为 1）。为了机械地推导这个表达式，请注意原始因子中条件符号左侧的所有变量（这里是 \(P(C|T)\) 中的 \(C\) 和 \(P(E|C,S)\) 中的 \(E\)）都停留在符号的左侧。然后，所有剩余的变量（这里是 \(T\) 和 \(S\)）都在符号的右侧。
这种编写因子的方法基于链式法则的重复应用。在上面的例子中，我们知道我们不能在条件符号的两侧都有变量。此外，我们知道：
\[P(T, C, S, +e) = P(T) P(S | T) P(C | T) P(+e | C, S) = P(S, T) P(C | T) P(+e | C, S)\]所以：
\[P(C | T) P(+e | C, S) = \frac{P(T, C, S, +e)}{P(S, T)} = P(C, +e | T, S)\]虽然变量消元过程在概念上更复杂，但生成的任何因子的最大大小只有 8 行，而不是像我们形成整个联合 PDF 那样是 16 行。
看待这个问题的另一种方式是观察 \(P(T|+e)\) 的计算可以通过枚举推理如下完成：
\[\alpha \sum_s{\sum_c{P(T)P(s|T)P(c|T)P(+e|c,s)}}\]或者通过变量消元如下完成：
\[\alpha P(T)\sum_s{P(s|T)\sum_c{P(c|T)P(+e|c,s)}}\]我们可以看到这两个方程是等价的，除了在变量消元中，我们将与求和无关的项移到了每个求和之外！
作为关于变量消元的最后一点说明，重要的是要观察到，只有当我们能够将最大因子的大小限制在一个合理的值时，它才比枚举推理有所改进。