Bayes Nets -- Inference(12)

ZaynPei Lv6
  2025-08-23 22:00 2025-08-23 22:00 Created   2025-08-27 14:57:08 2025-08-27 14:57:08 Updated      3.4k Words  12 Mins

上一讲我们学会了如何用贝叶斯网络来紧凑地表示一个复杂的联合概率分布。这一讲的核心问题是：有了这个紧凑的表示，我们如何高效地进行计算，从而回答概率查询(也就是推理问题)？

推理问题可以分为精确推理和近似推理, 这一节我们考虑精确推理

首先, 假如我们有一个完整的联合概率分布表, 只需要查表就可以得到所要的结果, 但是在贝叶斯网络的基础上, 我们有一种更智能的算法，能够在不生成完整联合分布的情况下完成推理。这个算法就是变量消除 (Variable Elimination)。

变量消除 (Variable Elimination)

变量消除是一种高效的精确推理算法，其核心思想是通过重新排列计算顺序来避免重复计算。

当我们想计算某个变量的边缘概率或条件概率时，不需要先计算出整个联合概率分布，而是通过将求和操作推入乘积内部，逐一消去无关的变量，从而大大降低计算复杂度。这个过程被称为“求和-乘积”算法（Sum-Product Algorithm）。

整个过程可以概括为以下四个主要步骤：

  1. 初始化: 将贝叶斯网络中的每一个条件概率表（CPT）视为一个独立的因子（Factor）。这些因子是关于其所依赖变量的函数。

  2. 迭代消除变量: 根据预定的消除顺序，逐一处理每个需要被消除的变量。对于每个待消除的变量，执行以下操作：

  • 找出相关因子：找到所有包含该变量的因子。

  • 因子相乘：将这些相关因子全部相乘，生成一个新的、更大的临时因子。

  • 求和消除：对这个新的临时因子，关于待消除的变量进行求和（或积分）。这个操作的结果是一个不包含该变量的新因子。

  • 更新因子集：将原始的相关因子从集合中移除，并将新生成的因子加入到集合中。

  1. 重复直至求出目标: 重复第二步，直到所有需要被消除的变量都被处理完毕。此时，剩下的因子只包含我们所查询的目标变量（以及任何给定的证据变量）。

  2. 最终计算与归一化: 将所有剩余的因子相乘，得到一个包含目标变量边缘概率的最终因子。如果需要计算条件概率，最后一步还要进行归一化处理，使所有可能结果的概率之和为1。

示例分析

让我们通过一个简单的”草地湿润”例子来展示变量消除的过程。

假设我们有一个包含四个二元变量（真/假）的贝叶斯网络： - C：多云（Cloudy） - S：洒水器打开（Sprinkler On） - R：下雨（Rain） - W：草地湿润（Grass is Wet）

这个网络的依赖关系如下图所示： - C→S - C→R
- S→W - R→W

对应的条件概率表（CPT）如下（为了便于计算，我们使用简单的数值）：

P(C): - P(C = T) = 0.5 - P(C = F) = 0.5

P(S|C): | C | S=T | S=F | |:–|:—–|:—–| | T | 0.1 | 0.9 | | F | 0.5 | 0.5 |

P(R|C): | C | R=T | R=F | |:–|:—–|:—–| | T | 0.8 | 0.2 | | F | 0.1 | 0.9 |

P(W|S, R): | S | R | W=T | W=F | |:–|:–|:—–|:—–| | T | T | 0.99 | 0.01 | | T | F | 0.9 | 0.1 | | F | T | 0.9 | 0.1 | | F | F | 0.0 | 1.0 |

我们的目标是：计算草地湿润的边缘概率 P(W = T)。

变量消除法的具体过程：

步骤 1: 建立联合概率分布表达式

首先，根据贝叶斯网络的结构，我们可以使用链式法则将整个网络的联合概率分布表示为所有节点的条件概率的乘积：

P(C, S, R, W) = P(C) ⋅ P(S|C) ⋅ P(R|C) ⋅ P(W|S, R)

步骤 2: 设定求和表达式

为了得到 P(W = T)，我们需要对除了 W 以外的所有变量进行求和（即积分），并将 W 的状态设定为 T：

P(W = T) = ∑C∑S∑RP(C, S, R, W = T)

如果直接进行计算，我们需要构建一个包含 24 = 16 种组合的巨大表格，然后逐行求和。变量消除法通过改变求和顺序来优化这个过程。

步骤 3: 确定消除顺序和重写表达式

变量消除法的关键是将求和操作推入乘积内部。我们可以选择一个合适的消除顺序（例如，在本例中我们按 C→R→S 的顺序进行消除），将上一步的表达式改写为：

P(W = T) = ∑S∑R[∑CP(C) ⋅ P(S|C) ⋅ P(R|C)] ⋅ P(W = T|S, R)

为什么要这样做？这样改写后，我们每次只对表达式中的一小部分进行求和，而不是对整个联合概率分布求和。每次求和的结果是一个新的”因子”或”表格”，这个新表格的维度比原始联合分布小得多。

步骤 4: 逐个消除变量

  1. 消除变量 C

我们首先计算表达式中与 C 相关的那一部分：

f1(S, R) = ∑CP(C) ⋅ P(S|C) ⋅ P(R|C)

这个新的因子 f1(S, R) 是一个关于 S 和 R 的表格。它代表了 P(S, R) 的联合概率分布。

我们来计算 f1(S, R) 表格中的每一项：

f1(S = T, R = T)：

f1(S = T, R = F)：

f1(S = F, R = T)：

f1(S = F, R = F)：

  1. 消除变量 R

将上一步得到的 f1(S, R) 因子与 P(W = T|S, R) 相乘，并对 R 求和。我们得到一个新的因子 f2(S, W = T)：

f2(S, W = T) = ∑Rf1(S, R) ⋅ P(W = T|S, R)

f2(S = T, W = T)：

f2(S = F, W = T)：

  1. 消除变量 S

最后，我们对剩下的因子 f2(S, W = T) 进行求和，得到最终结果 P(W = T)：

结论和总结： 通过变量消除法，我们成功计算出了 P(W = T) 的精确值，为 0.62235。

计算代价对比

1. 暴力计算法的计算量

目标：计算 P(W = T) = ∑C∑S∑RP(C, S, R, W = T)

步骤 1: 构建完整的联合概率分布表

为了计算联合概率分布 P(C, S, R, W)，我们需要为每个可能的变量组合（2 × 2 × 2 × 2 = 16 种组合）计算其概率值。

每一行的计算都需要将四个概率相乘：P(C) ⋅ P(S|C) ⋅ P(R|C) ⋅ P(W|S, R)。这涉及到 3 次乘法。

例如，计算第一行 P(C = T, S = T, R = T, W = T)： 0.5 × 0.1 × 0.8 × 0.99 （3次乘法）

总乘法次数：16 行 × 3 次乘法/行 = 48 次乘法。

步骤 2: 对变量 C, S, R 求和

在得到完整的16行联合概率表之后，我们需要找出所有 W=T 的行（共有 23 = 8 行），然后将它们的概率值相加。

总加法次数：将 8 个数字相加需要 7 次加法。

暴力计算法总结
  • 总计算量：48 次乘法 + 7 次加法 = 55 次运算
  • 内存需求：需要存储一个包含 16 行的完整联合概率表

2. 变量消除法的计算量

现在我们回顾一下变量消除法的每一步，并统计运算次数。

步骤 1: 消除变量 C，生成因子 f1(S, R)

这个因子 f1(S, R) 是一个 2 × 2 的表格，有 4 个条目。计算每个条目都需要一次求和，求和的每一项都是三个概率的乘积。

例如： f1(S = T, R = T) = [P(C = T)P(S = T|C = T)P(R = T|C = T)] + [P(C = F)P(S = T|C = F)P(R = T|C = F)]

计算一个条目所需的运算： - 方括号内各有 2 次乘法，共 2 × 2 = 4 次乘法 - 两个方括号相加，需要 1 次加法

总运算量：4 个条目 × (4 次乘法 + 1 次加法) = 16 次乘法 + 4 次加法

内存需求：生成一个包含 4 行的新表 f1(S, R)

步骤 2: 消除变量 R，生成因子 f2(S, W = T)

这个因子 f2(S, W = T) 是一个 2 × 1 的表格，有 2 个条目。

例如： f2(S = T, W = T) = [f1(S = T, R = T) ⋅ P(W = T|S = T, R = T)] + [f1(S = T, R = F) ⋅ P(W = T|S = T, R = F)]

计算一个条目所需的运算： - 方括号内各有 1 次乘法，共 1 × 2 = 2 次乘法 - 两个方括号相加，需要 1 次加法

总运算量：2 个条目 × (2 次乘法 + 1 次加法) = 4 次乘法 + 2 次加法

内存需求：生成一个包含 2 行的新表 f2(S, W = T)

步骤 3: 消除变量 S，得到最终结果 P(W = T)

P(W = T) = f2(S = T, W = T) + f2(S = F, W = T)

总运算量：1 次加法

变量消除法总结
  • 总乘法次数：16 + 4 = 20 次乘法
  • 总加法次数：4 + 2 + 1 = 7 次加法
  • 总计算量：20 次乘法 + 7 次加法 = 27 次运算
  • 内存需求：在整个计算过程中，我们创建的最大的中间表是 f1(S, R)，它只有 4 行

信念传播（Belief Propagation, BP）

信念传播 (Belief Propagation, BP) 是一种在概率图模型（如贝叶斯网络或马尔可夫随机场）上进行推断的算法。它的核心思想可以被形象地描述为：图中的每个节点都是一个独立的计算单元，它们通过相互之间“传递消息” (passing messages) 来不断更新自己对某个变量状态的“信念” (belief)。

  • 信念 (Belief)：指的是一个节点（变量）的边际概率分布 (Marginal Probability Distribution)。简单来说，就是综合了图中所有可用信息后，我们对这个变量取不同值的可能性有多大的判断。

  • 消息 (Message)：一个节点传递给其邻居节点的信息。这个消息总结了除了从那个邻居接收到的信息之外，它所知道的所有其他信息。这就像是在说：“嘿，这是我从其他所有人那里听到的所有消息汇总，现在我告诉你，但不包括你告诉我的那部分。”

信念传播算法通过一个迭代的消息传递过程来计算每个节点的信念。我们可以把它分为两种主要情况：

在树状结构图上：精确推断

当概率图的结构是一个树 (Tree) 或者 多义树 (Polytree)（即图中没有任何无向环路）时，信念传播是一种精确推断算法。它能准确地计算出每个变量的边际概率。

步骤说明：

初始化: 随机选择一个根节点。

消息收集 (从叶到根): 从图的叶子节点开始，每个节点收集来自其子节点的所有消息，然后计算并向其父节点发送一条新的消息。这个过程一直持续到根节点收到了来自其所有子节点的消息。

消息分发 (从根到叶): 根节点收到所有消息后，开始向其子节点分发消息。然后，每个节点再根据从父节点收到的消息，计算并向它的子节点继续分发消息，直到消息传递到所有的叶子节点。

计算信念: 当每个节点都收到了来自其所有邻居的消息后，它就可以利用这些消息来计算自己的最终信念（即边际概率）。

为什么是精确的？ 因为在树状结构中，从任何一个邻居传来的信息路径都是唯一的，信息不会“绕一圈”回来，所以消息的传递不会产生冗余或循环依赖，保证了计算的准确性。

在带环路的图上：环路信念传播 (Loopy Belief Propagation)

当图中存在环路 (Cycles) 时，情况就变得复杂了。一个节点发出的消息可能会沿着环路绕一圈后，又以某种形式传回给自己。这违反了标准信念传播算法的基本假设。

在这种情况下，我们使用的算法被称为 环路信念传播 (Loopy Belief Propagation, LBP)。

核心思想: 尽管理论上不再保证准确性，但我们可以假装图没有环路，然后像在树上一样，让所有节点并行地、迭代地向邻居发送消息。

步骤说明:

初始化: 用随机值或均匀分布初始化所有消息。

迭代更新: 在每一步迭代中，每个节点都根据它上一轮从邻居那里收到的消息，计算并更新它将要发送给邻居的新消息。

重复: 重复这个过程，直到消息收敛（即消息值不再有明显变化）或者达到预设的最大迭代次数。

计算信念: 算法停止后，用最后一次迭代的消息来估算每个节点的信念。

结果: LBP 是一种近似推断算法。它不保证能收敛，即使收敛了，其计算出的信念也只是真实边际概率的一个近似值。然而，在实践中，LBP 在许多应用（如计算机视觉、纠错码领域）中都表现得非常出色，常常能给出很好的近似结果。

On this page
Bayes Nets -- Inference(12)
  1. 变量消除 (Variable Elimination)
    1. 示例分析
      1. 计算代价对比
      2. 1. 暴力计算法的计算量
        1. 步骤 1: 构建完整的联合概率分布表
        2. 步骤 2: 对变量 C, S, R 求和
        3. 暴力计算法总结
      3. 2. 变量消除法的计算量
        1. 步骤 1: 消除变量 C，生成因子 f1(S, R)
        2. 步骤 2: 消除变量 R，生成因子 f2(S, W = T)
        3. 步骤 3: 消除变量 S，得到最终结果 P(W = T)
        4. 变量消除法总结
  2. 信念传播（Belief Propagation, BP）
    1. 在树状结构图上：精确推断
    2. 在带环路的图上：环路信念传播 (Loopy Belief Propagation)