概率推理（AIMA Part IV）

本笔记对应 AIMA（Artificial Intelligence: A Modern Approach）第12–14章的内容，涵盖不确定性的量化、概率推理以及时序概率推理。

---

1. 不确定性推理概述

1.1 为什么逻辑不够用？

在前面的笔记中，我们学习了命题逻辑和一阶逻辑。逻辑推理是确定性的：一个命题要么为真，要么为假。然而，现实世界中的智能体往往面临以下挑战：

• 信息不完整：智能体无法观察到世界的全部状态。例如医生无法直接看到患者体内的病变。
• 传感器噪声：观测本身存在误差。
• 非确定性效果：同一动作在不同条件下可能产生不同结果。
• 模型简化：即使是最精细的模型也无法完全刻画真实世界。

在逻辑框架下，处理这些不确定性需要列举所有可能的异常情况（qualification problem），这在实际中是不可行的。因此，我们转向概率论作为信念度（degree of belief）的形式化工具。

1.2 概率作为信念度

概率公理要求任何理性智能体的信念都满足 Kolmogorov 公理：

1. \(0 \le P(A) \le 1\)
2. \(P(\text{True}) = 1,\ P(\text{False}) = 0\)
3. \(P(A \lor B) = P(A) + P(B) - P(A \land B)\)

AIMA 指出，如果一个智能体的信念违反这些公理，就可以构造一组赌局使其必然亏损（Dutch Book 定理）。这为使用概率来量化不确定性提供了规范性论证。

---

2. 贝叶斯规则与推理

2.1 条件概率与贝叶斯规则

条件概率定义为：

\[ P(A \mid B) = \frac{P(A \land B)}{P(B)}, \quad P(B) > 0 \]

由此直接推导出贝叶斯规则（Bayes' Rule）：

\[ P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)} \]

术语	含义	说明
\(P(A)\)	先验概率（Prior）	在观察到证据 \(B\) 之前对 \(A\) 的信念
\(P(B \mid A)\)	似然（Likelihood）	假设 \(A\) 为真时观察到 \(B\) 的概率
\(P(A \mid B)\)	后验概率（Posterior）	观察到证据 \(B\) 之后对 \(A\) 的更新信念
\(P(B)\)	边际似然（Evidence）	归一化常数，\(P(B) = \sum_a P(B \mid A=a) P(A=a)\)

2.2 朴素贝叶斯

当多个证据 \(E_1, E_2, \dots, E_n\) 在给定假设 \(H\) 的条件下条件独立时：

\[ P(H \mid E_1, \dots, E_n) \propto P(H) \prod_{i=1}^{n} P(E_i \mid H) \]

这就是朴素贝叶斯（Naive Bayes）模型，在垃圾邮件过滤、文本分类等任务中有广泛应用。

---

3. 贝叶斯网络

3.1 定义

贝叶斯网络（Bayesian Network）是一个有向无环图（DAG），其中：

• 每个节点代表一个随机变量
• 每条有向边表示直接的概率依赖关系
• 每个节点附带一个条件概率表（CPT, Conditional Probability Table）

联合概率分布可以分解为：

\[ P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i)) \]

经典示例：报警网络

考虑以下场景：地震或入室盗窃都可能触发警报，警报响了邻居 John 和 Mary 可能会打电话给你。

[Burglary]  [Earthquake]
     \         /
      v       v
      [Alarm]
     /       \
    v         v
[JohnCalls] [MaryCalls]

这个网络只需要 10 个独立参数（而完整联合概率表需要 \(2^5 - 1 = 31\) 个参数）。

3.2 条件独立性

贝叶斯网络编码了丰富的条件独立关系。核心性质是马尔可夫条件：

给定其父节点，每个节点与其所有非后代节点条件独立。

记为 \(X \perp\!\!\!\perp Y \mid Z\)，即 \(P(X \mid Y, Z) = P(X \mid Z)\)。

3.3 d-分离

d-分离（d-separation）是判断贝叶斯网络中条件独立性的图论准则。三种基本连接结构：

结构	形式	中间节点未观测	中间节点已观测
链（Chain）	\(X \to Z \to Y\)	\(X, Y\) 相关	\(X \perp\!\!\!\perp Y \mid Z\)
分叉（Fork）	\(X \leftarrow Z \to Y\)	\(X, Y\) 相关	\(X \perp\!\!\!\perp Y \mid Z\)
对撞（Collider）	\(X \to Z \leftarrow Y\)	\(X \perp\!\!\!\perp Y\)	\(X, Y\) 变得相关

对撞节点的反直觉性

在对撞结构中，观测中间节点反而会引入依赖关系。这被称为"解释消除效应"（explaining away）。例如：才华和外貌独立，但如果我们只观察成功人士（才华 → 成功 ← 外貌），在成功人群中才华和外貌呈现负相关。

---

4. 贝叶斯网络推理

4.1 精确推断

变量消元（Variable Elimination） 是最基本的精确推断算法：

\[ P(Q \mid E = e) \propto \sum_{H} \prod_{i} P(X_i \mid \text{Parents}(X_i)) \bigg|_{E=e} \]

步骤	操作
1	确定查询变量 \(Q\) 和证据变量 \(E\)
2	选择消元顺序（影响效率，最优顺序的寻找是 NP-hard）
3	对每个待消元的隐变量，合并相关因子并求和消除
4	归一化得到后验概率

团树算法（Junction Tree / Clique Tree）：将贝叶斯网络转化为团树结构，通过消息传递实现精确推断。对于树形结构的网络，信念传播（Belief Propagation）可以在线性时间内完成推断。

4.2 近似推断

当网络规模较大、精确推断不可行时，使用近似方法：

直接采样（Direct Sampling）：按拓扑顺序逐节点采样，生成联合分布的样本。

似然加权（Likelihood Weighting）：

• 固定证据变量的值，只对非证据变量采样
• 每个样本赋予权重 \(w = \prod_{i \in E} P(e_i \mid \text{Parents}(E_i))\)
• 相比拒绝采样（Rejection Sampling）更高效

MCMC（马尔可夫链蒙特卡洛）：

• Gibbs 采样：逐变量从条件分布中采样
  • \(X_i^{(t+1)} \sim P(X_i \mid X_1^{(t+1)}, \dots, X_{i-1}^{(t+1)}, X_{i+1}^{(t)}, \dots, X_n^{(t)})\)
  • 在贝叶斯网络中，每个变量的条件分布只依赖于其马尔可夫毯（Markov Blanket）：父节点、子节点、以及子节点的其他父节点

方法	优势	劣势
变量消元	精确	最坏指数复杂度
似然加权	实现简单，有偏但一致	证据概率极低时方差大
Gibbs 采样	渐近精确	收敛速度不确定

---

5. 时序概率模型

5.1 马尔可夫链

马尔可夫链满足一阶马尔可夫性质：

\[ P(X_{t+1} \mid X_0, X_1, \dots, X_t) = P(X_{t+1} \mid X_t) \]

即未来状态只依赖于当前状态，与历史无关。状态转移由转移矩阵 \(T\) 描述，其中 \(T_{ij} = P(X_{t+1} = j \mid X_t = i)\)。

5.2 隐马尔可夫模型（HMM）

隐马尔可夫模型在马尔可夫链的基础上引入了不可直接观测的隐状态：

• 隐状态序列 \(Z_1, Z_2, \dots, Z_T\)：满足一阶马尔可夫性
• 观测序列 \(X_1, X_2, \dots, X_T\)：每个观测只依赖当前隐状态

参数 \(\lambda = (\pi, A, B)\)：

参数	含义
\(\pi_i = P(Z_1 = i)\)	初始状态分布
\(A_{ij} = P(Z_{t+1} = j \mid Z_t = i)\)	状态转移概率
\(B_{ik} = P(X_t = k \mid Z_t = i)\)	发射概率（观测概率）

5.3 HMM 三大核心问题

问题	描述	算法	复杂度
评估（Evaluation）	给定模型和观测序列，计算 \(P(X \mid \lambda)\)	前向算法（Forward）	\(O(N^2 T)\)
解码（Decoding）	给定模型和观测序列，找最可能的隐状态序列	Viterbi 算法	\(O(N^2 T)\)
学习（Learning）	给定观测序列，估计模型参数	Baum-Welch（EM）	迭代收敛

前向算法：定义前向变量 \(\alpha_t(i) = P(X_1, \dots, X_t, Z_t = i \mid \lambda)\)

\[ \begin{aligned} \alpha_1(i) &= \pi_i \cdot B_{i, X_1} \\ \alpha_{t+1}(j) &= \left[\sum_{i=1}^{N} \alpha_t(i) \cdot A_{ij}\right] \cdot B_{j, X_{t+1}} \end{aligned} \]

Viterbi 算法：使用动态规划，定义 \(\delta_t(j) = \max_{z_1, \dots, z_{t-1}} P(z_1, \dots, z_{t-1}, Z_t = j, X_1, \dots, X_t)\)

\[ \delta_t(j) = \max_{i} \left[\delta_{t-1}(i) \cdot A_{ij}\right] \cdot B_{j, X_t} \]

通过回溯指针（backpointer）恢复最优路径。

Baum-Welch 算法：EM 算法在 HMM 上的特化。E 步计算前向-后向变量得到隐状态后验分布，M 步更新参数 \(\pi, A, B\)。迭代保证似然单调递增。

---

6. 卡尔曼滤波

卡尔曼滤波（Kalman Filter）是连续状态空间上的时序推理方法，假设线性高斯模型：

状态转移模型（线性 + 高斯噪声）：

\[ \mathbf{x}_{t+1} = F \mathbf{x}_t + B \mathbf{u}_t + \mathbf{w}_t, \quad \mathbf{w}_t \sim \mathcal{N}(\mathbf{0}, Q) \]

观测模型（线性 + 高斯噪声）：

\[ \mathbf{z}_t = H \mathbf{x}_t + \mathbf{v}_t, \quad \mathbf{v}_t \sim \mathcal{N}(\mathbf{0}, R) \]

卡尔曼滤波包含两个交替进行的步骤：

步骤	操作	说明
预测（Predict）	\(\hat{\mathbf{x}}_{t\mid t-1} = F\hat{\mathbf{x}}_{t-1\mid t-1} + B\mathbf{u}_t\)	根据状态转移模型预测下一时刻状态
	\(P_{t\mid t-1} = FP_{t-1\mid t-1}F^T + Q\)	预测协方差
更新（Update）	\(K_t = P_{t\mid t-1}H^T(HP_{t\mid t-1}H^T + R)^{-1}\)	计算卡尔曼增益
	\(\hat{\mathbf{x}}_{t\mid t} = \hat{\mathbf{x}}_{t\mid t-1} + K_t(\mathbf{z}_t - H\hat{\mathbf{x}}_{t\mid t-1})\)	融合观测信息更新状态

卡尔曼滤波在目标跟踪、导航（GPS/INS融合）、机器人定位等领域有广泛应用。当系统非线性时，可使用扩展卡尔曼滤波（EKF）或无迹卡尔曼滤波（UKF）。

---

7. 动态贝叶斯网络（DBN）

动态贝叶斯网络（Dynamic Bayesian Network, DBN）是贝叶斯网络在时序上的推广。HMM 和卡尔曼滤波都可以视为 DBN 的特殊情况：

模型	隐状态	观测	转移/观测模型
HMM	单个离散变量	单个离散/连续变量	表格（CPT）
卡尔曼滤波	连续向量	连续向量	线性高斯
通用 DBN	任意结构的变量集合	任意结构的变量集合	任意 CPT/函数

DBN 的推断方法包括：

• 精确推断：展开为静态贝叶斯网络后使用变量消元（仅适用于小规模问题）
• 近似推断：粒子滤波（Particle Filtering），即序贯蒙特卡洛方法，通过一组加权粒子表示后验分布

---

交叉引用

与本站其他笔记的关联

• 本站的 概率推理 笔记包含更深入的概率图模型内容，包括马尔可夫随机场（MRF）、条件随机场（CRF）、变分推断、概率编程以及因果推断。
• 深度学习中的变分自编码器（VAE） 和扩散模型是概率推理与神经网络结合的前沿方向。
• 强化学习笔记中讨论的POMDP（部分可观测马尔可夫决策过程）直接建立在 HMM 的基础之上。

---

参考资料

• Russell & Norvig, Artificial Intelligence: A Modern Approach, Chapters 12–14
• Koller & Friedman, Probabilistic Graphical Models: Principles and Techniques
• Bishop, Pattern Recognition and Machine Learning, Chapters 8, 13

---

评论