第二章：概率模型（Probabilistic Models）

笔记与详细解释

2.1 表示（Representation）

2.1.1 信念度与概率（Degrees of Belief and Probability）

不确定性（Uncertainty） 在现实世界中普遍存在，主要来源于两个方面：

信息不完整：例如，我们监测数千公里外的卫星时，突然失去通信信号。此时我们无法确定是卫星上的电力系统故障、通信系统故障，还是地面监控系统的问题。
预测的局限性：无论是人类行为（如操作员对决策支持系统的响应）还是物理系统（如卫星轨道），都存在难以精确预测的因素。

【注】 为了在不确定条件下进行理性决策，我们需要一种形式化的表示方法来量化不确定性。概率论正是这样一种强有力的工具。

信念比较关系

设 $E$ 表示"卫星存在电力异常"，$T$ 表示"卫星存在推进器异常"： - 如果我们认为 $E$ 比 $T$ 更可能，则记为 $E \succ T$ - 如果两者同等可能，则记为 $E \sim T$

类似地，在给定条件 $C$（通信中断）下： - $(E|C) \succ (T|C)$ 表示"给定通信中断，电力异常的可能性大于推进器异常"

概率公理化

在全域可比性（Universal Comparability） 和传递性（Transitivity） 的假设下，我们可以将信念度映射到一个实值函数 $P$：

\[ P(A|C) > P(B|C) \iff (A|C) \succ (B|C) \]

\[ P(A|C) = P(B|C) \iff (A|C) \sim (B|C) \]

在这些假设下，$P$ 满足基本概率公理： - $0 \leq P(A|B) \leq 1$ - $P(A|B) = 1$ 表示在条件 $B$ 下 $A$ 必然为真 - $P(A|B) = 0$ 表示在条件 $B$ 下 $A$ 不可能为真

条件概率定义

【定义】条件概率（Conditional Probability）：

\[ P(A|B) = \frac{P(A, B)}{P(B)} \tag{2.1} \]

其中 $P(A, B)$ 表示 $A$ 和 $B$ 同时为真的概率。

【注】 条件概率公式（2.1）也可以写为 $P(A, B) = P(A|B)P(B)$。

全概率定律（Law of Total Probability）

设 $B$ 是一组互斥且完备的命题集合，则：

\[ P(A|C) = \sum_{B \in \mathcal{B}} P(A|B, C)P(B|C) \tag{2.2} \]

【注】 全概率定律是计算复杂事件概率的基本工具，特别是在分解问题时会经常用到。

贝叶斯规则（Bayes' Rule）

由条件概率定义可以直接推导：

\[ P(A|B) = \frac{P(B|A)P(A)}{P(B)} \tag{2.3} \]

【注】 贝叶斯规则是本书的核心公式，在推理和学习中都有广泛应用。它允许我们根据已知结果反推未知原因的概率（似然与先验的转换）。

2.1.2 概率分布（Probability Distributions）

离散分布

设 $A$ 为二元随机变量，取值 $\{0, 1\}$。概率分布 $P(A)$ 由 $P(a^0)$ 和 $P(a^1)$ 决定，其中 $P(a^1) = 1 - P(a^0)$。

【注】 一般地，如果离散变量有 $n$ 个取值，则需要 $n-1$ 个独立参数。

连续分布

对于连续随机变量，单点概率为无穷小。考虑均匀分布 $U(0, 10)$，取值为特定常数 $\pi$ 的概率为零，但取值为区间 $(3, 4)$ 内的概率为 $1/10$。

累积分布函数与概率密度函数

累积分布函数（CDF）：$P(a) = \int_{-\infty}^{a} p(x) dx$
概率密度函数（PDF）：$p(a)da$ 表示落在区间 $(a, a+da)$ 的概率

\[ P(a) = \int_{-\infty}^{a} p(x) dx \tag{2.4} \]

高斯分布（Gaussian Distribution）

【重要】 高斯分布（正态分布）是最常用的连续分布之一，仅需两个参数：均值 $\mu$ 和方差 $\sigma^2$。

\[ p(w) = \mathcal{N}(w | \mu, \sigma^2) \tag{2.5} \]

其中密度函数为：

\[ \mathcal{N}(w | \mu, \sigma^2) = \frac{1}{\sigma} \phi\left(\frac{w - \mu}{\sigma}\right) \tag{2.6} \]

标准正态密度函数为：

\[ \phi(x) = \frac{1}{\sqrt{2\pi}} \exp(-x^2/2) \tag{2.7} \]

【注】 高斯分布的优点是计算方便，但有两个主要局限： 1. 赋予负值非零概率（有时不合理） 2. 单峰（Unimodal）——无法表示多峰分布

截断高斯分布（Truncated Gaussian）

为解决上述问题，可以使用截断高斯分布，限制取值范围 $[a, b]$：

\[ \mathcal{N}(w | \mu, \sigma^2, a, b) = \frac{1}{\Phi\left(\frac{b-\mu}{\sigma}\right) - \Phi\left(\frac{a-\mu}{\sigma}\right)} \cdot \frac{1}{\sigma} \phi\left(\frac{w-\mu}{\sigma}\right) \tag{2.8} \]

其中 $\Phi$ 是标准正态累积分布函数：

\[ \Phi(x) = \int_{-\infty}^{x} \phi(t) dt \tag{2.9} \]

【实例】 飞机高度建模：截断范围设为 $0$ ft 到 $65,000$ ft。

多峰分布的表示

高度分布在 JFK 机场终端区域是多峰的（每 1000 ft 有一个峰值），普通高斯分布不合适。解决方案包括：

高斯混合模型（GMM）：多个高斯分布的加权平均

\[ p(x | \mu_1, \sigma_1^2, \ldots, \mu_n, \sigma_n^2, \rho_1, \ldots, \rho_n) = \sum_{i=1}^{n} \rho_i \mathcal{N}(x | \mu_i, \sigma_i^2) \tag{2.10} \]

其中 $\sum \rho_i = 1$。

离散化（Discretization）：将取值范围划分为区间（bin），用分段均匀分布近似。

【注】 图 2.1 展示了不同离散粒度（100 ft、200 ft、1000 ft bins）对高度分布表示的影响。1000 ft 的粗粒度会丢失重要特征。

2.1.3 联合分布（Joint Distributions）

【问题】 联合分布的参数数量随变量数指数增长。

对于 $n$ 个二元变量，需要 $2^n - 1$ 个独立参数。当 $n=3$ 时，$2^3 = 8$ 种组合，但只需 $7$ 个独立参数（因为概率和为 1）。

【注】 这就是所谓的维度灾难（Curse of Dimensionality），直接表示联合分布在实际应用中几乎不可行。

2.1.4 贝叶斯网络表示（Bayesian Network Representation）

基本定义

贝叶斯网络是一种紧凑的联合分布表示方法，由图结构（节点和有向边）组成： - 每个节点对应一个随机变量 - 有向边表示直接的概率关系 - 图中不允许有环（是有向无环图，即 DAG）

节点 $X_i$ 的条件分布为 $P(X_i | \text{Pa}_{X_i})$，其中 $\text{Pa}_{X_i}$ 是 $X_i$ 的父节点集合。

卫星监控示例

图 2.2 和 2.3 展示了一个包含 5 个二元变量的贝叶斯网络：

变量	含义	父节点
B	电池故障	无
S	太阳能板故障	无
E	电气系统故障	B, S
D	轨迹偏移	E
C	通信中断	E

链式规则（Chain Rule for Bayesian Networks）

\[ P(x_1, \ldots, x_n) = \prod_{i=1}^{n} P(x_i | \text{pa}_{x_i}) \tag{2.11} \]

【实例】 计算"一切正常"的概率：

\[ P(b^0, s^0, e^0, d^0, c^0) = P(b^0) P(s^0) P(e^0 | b^0, s^0) P(d^0 | e^0) P(c^0 | e^0) \tag{2.12} \]

参数节省

完全指定 5 个二元变量的联合分布需要 $2^5 - 1 = 31$ 个独立参数。

使用贝叶斯网络结构，只需 $1 + 1 + 4 + 2 + 2 = 10$ 个独立参数： - $P(B)$：1 参数 - $P(S)$：1 参数 - $P(E|B,S)$：$2^2 = 4$ 参数 - $P(D|E)$：2 参数 - $P(C|E)$：2 参数

【注】 在大型网络中，参数节省效果更加显著。这正是贝叶斯网络的核心优势。

2.1.5 条件独立（Conditional Independence）

边缘独立

变量 $A$ 和 $B$ 独立，当且仅当：

\[ A \perp B \iff P(A, B) = P(A)P(B) \iff P(A) = P(A|B) \]

【实例】 卫星电池故障 $B$ 与太阳能板故障 $S$ 假设为独立——知道其中一个发生不影响对另一个发生的信念。

条件独立

给定 $C$，$A$ 和 $B$ 条件独立，当且仅当：

\[ (A \perp B | C) \iff P(A, B | C) = P(A|C) P(B|C) \iff P(A|C) = P(A|B,C) \]

【实例】 给定电气系统故障 $E$，轨迹偏移 $D$ 与通信中断 $C$ 条件独立： $(D \perp C | E)$

即：如果已知电气系统故障，那么观察到通信中断不会改变对轨迹偏移的信念。

d-分离（D-Separation）

d-分离 用于判断图中节点间的条件独立关系。路径被节点集 $C$ d-分离的条件：

链（Chain）：$X \rightarrow Y \rightarrow Z$，若 $Y \in C$，则路径被阻断
分叉（Fork）：$X \leftarrow Y \rightarrow Z$，若 $Y \in C$，则路径被阻断
倒叉（V-Structure/Inverted Fork）：$X \rightarrow Y \leftarrow Z$，若 $Y \notin C$ 且 $Y$ 的后代都不在 $C$ 中，则路径被阻断

【注】 "解释效应（Explaining Away）"：在倒叉结构 $B \rightarrow E \leftarrow S$ 中，给定 $E$ 后，$B$ 和 $S$ 不再独立。例如，知道电气系统故障后，观察到电池故障会降低对太阳能板故障的信念。

马尔可夫毯（Markov Blanket）：最小节点集，使给定该毯后节点与所有其他节点条件独立。

2.1.6 混合贝叶斯网络（Hybrid Bayesian Networks）

实际应用中常需要同时包含离散和连续变量。

示例：飞机识别

翼展 $W$（连续）
军事机？$M$（二元离散）
雷达横截面 $C$（连续）
检测到？$D$（二元离散）

条件线性高斯（Conditional Linear Gaussian）

当连续变量 $C$ 依赖连续变量 $W$ 和离散变量 $M$ 时：

\[ p(c|w) = \mathcal{N}(c | \theta_1 w + \theta_2, \theta_3) \tag{2.13} \]

考虑 $M$ 的影响，使用条件线性高斯：

\[ p(c|w, m) = \begin{cases} \mathcal{N}(c | \theta_1 w + \theta_2, \theta_3) & \text{if } m^0 \\ \mathcal{N}(c | \theta_4 w + \theta_5, \theta_6) & \text{if } m^1 \end{cases} \tag{2.14} \]

软阈值（Soft Threshold）

对于 $P(D|C)$，可以用 logit 模型（S 型曲线）代替硬阈值：

\[ P(d^1 | c) = \frac{1}{1 + \exp\left(-\frac{2(c - \theta_1)}{\theta_2}\right)} \tag{2.15} \]

或 probit 模型：

\[ P(d^1 | c) = \Phi\left(\frac{c - \theta_1}{\theta_2}\right) \tag{2.16} \]

【注】 软阈值避免了硬阈值导致的零概率问题，使模型更鲁棒。

2.1.7 时序模型（Temporal Models）

马尔可夫链（Markov Chain）

时序模型描述变量随时间的演化。马尔可夫链假设当前状态 $S_t$ 只依赖于前一时刻 $S_{t-1}$：

\[ P(S_t | S_{t-1}) \quad \text{（状态转移模型）} \]

如果转移分布不随时间变化，则为平稳（Stationary） 模型。

【实例】 飞机状态：$s = (h, \dot{h})$，其中 $h$ 是高度，$\dot{h}$ 是垂直速率。

多元高斯分布

\[ p(s) = \mathcal{N}(s | \mu, \Sigma) \tag{2.17} \]

其中 $\Sigma$ 是协方差矩阵，密度函数为：

\[ \mathcal{N}(s | \mu, \Sigma) = \frac{1}{(2\pi)^{k/2} |\Sigma|^{1/2}} \exp\left(-\frac{1}{2}(s-\mu)^\top \Sigma^{-1}(s-\mu)\right) \tag{2.18} \]

线性高斯状态转移

\[ p(s_t | s_{t-1}) = \mathcal{N}(s_t | M s_{t-1} + b, \Sigma) \tag{2.19} \]

例如： $$ M s_{t-1} + b = \begin{bmatrix} 1 & 1 \ 0 & 1 \end{bmatrix} s_{t-1} $$ 表示飞机平均保持当前高度但有恒定的垂直速率变化。

隐马尔可夫模型（HMM）与线性动态系统

HMM：离散状态 + 观测
线性动态系统（Linear Dynamical System）：连续状态 + 线性高斯条件分布

动态贝叶斯网络（Dynamic Bayesian Network）

用两个贝叶斯网络表示：初始分布网络和转移分布网络（双切片结构）。

2.2 推理（Inference）

推理（Inference）：给定观测变量值，确定一个或多个未观测变量的分布。

【术语】 - 查询变量（Query Variable）：待推断的变量 - 证据变量（Evidence Variable）：已观测到值的变量 - 隐变量（Hidden Variable）：既非查询也非证据的变量

【实例】 在卫星网络中，计算 $P(B | d^1, c^1)$： - 查询：$B$（电池故障） - 证据：$D=1$（轨迹偏移），$C=1$（通信中断） - 隐变量：$S$（太阳能板故障），$E$（电气系统故障）

2.2.1 分类推理（Inference for Classification）

朴素贝叶斯模型（Naive Bayes Model）：给定类 $C$，特征 $O_1, \ldots, O_n$ 条件独立：

\[ (O_i \perp O_j | C) \quad \forall i \neq j \]

链式规则应用

\[ P(c, o_{1:n}) = P(c) \prod_{i=1}^{n} P(o_i | c) \tag{2.22} \]

后验概率计算

\[ P(c | o_{1:n}) = \frac{P(c, o_{1:n})}{P(o_{1:n})} \tag{2.23} \]

利用全概率定律：

\[ P(o_{1:n}) = \sum_c P(c, o_{1:n}) \tag{2.24} \]

归一化技巧

由于分母不含 $c$，可以先计算未归一化概率，再统一归一化：

\[ P(c | o_{1:n}) \propto P(c, o_{1:n}) \tag{2.26} \]

【实例】 - $P(\text{bird}, \text{slow}, \text{little fluctuation}) = 0.03$ - $P(\text{aircraft}, \text{slow}, \text{little fluctuation}) = 0.01$

归一化后： $$ P(\text{bird} | \text{slow}, \text{little fluctuation}) = \frac{0.03}{0.03 + 0.01} = 0.75 $$

【注】 朴素贝叶斯虽"朴素"（条件独立假设），但在实践中往往效果很好，是常用的分类方法。

2.2.2 时序模型推理（Inference in Temporal Models）

四种常见推理任务

滤波（Filtering）：$P(S_t | O_{0:t})$
预测（Prediction）：$P(S_{t'} | O_{0:t})$，其中 $t' > t$
平滑（Smoothing）：$P(S_{t'} | O_{0:t})$，其中 $t' < t$
最可能解释（Most Likely Explanation）：$\arg\max_S P(S_{0:t} | O_{0:t})$

递归贝叶斯估计（Recursive Bayesian Estimation）

以 HMM 为例，说明滤波的递归更新：

由贝叶斯规则和条件独立性：

\[ P(s_t | o_{0:t}) \propto P(o_t | s_t) \sum_{s_{t-1}} P(s_t | s_{t-1}) P(s_{t-1} | o_{0:t-1}) \tag{2.33} \]

算法 2.1 展示了完整的递归贝叶斯估计算法。

【注】 对于线性动态系统，卡尔曼滤波（Kalman Filter） 可以高效计算——只需更新均值和协方差。

2.2.3 精确推理（Exact Inference）

边缘化（Marginalization）

通过求和消除隐变量：

\[ P(b^1, d^1, c^1) = \sum_s \sum_e P(b^1, s, e, d^1, c^1) \tag{2.35} \]

应用链式规则：

\[ P(b^1, d^1, c^1) = \sum_s \sum_e P(b^1) P(s) P(e | b^1, s) P(d^1 | e) P(c^1 | e) \tag{2.36} \]

变量消除法（Variable Elimination）

核心思想：按顺序消除隐变量，每次只处理涉及该变量的因子表。

示例计算 $P(B | d^1, c^1)$：

定义因子：$T_1(B), T_2(S), T_3(E, B, S), T_4(D, E), T_5(C, E)$
证据 $D=1, C=1$ 时，替换为 $T_6(E), T_7(E)$
消除 $E$：$T_8(B, S) = \sum_e T_3(e, B, S) T_6(e) T_7(e)$
消除 $S$：$T_9(B) = \sum_s T_2(s) T_8(B, s)$
归一化 $T_1(B) \cdot T_9(B)$

算法 2.2 给出了变量消除的完整伪代码。

【注】 变量消除的时间复杂度在一般情况下是线性的，但最坏情况是指数级的，取决于变量消除顺序。

信念传播（Belief Propagation）

在树状结构（无无向环）的网络中，信念传播可线性时间精确推理。

对于有环网络，需要使用 连接树算法（Junction Tree Algorithm） 转化为树结构。

2.2.4 精确推理的复杂性（Complexity of Exact Inference）

计算复杂性类

P：多项式时间可解
NP：解可在多项式时间验证
NP-hard：至少与 NP 中最难问题一样难
NP-complete：既是 NP-hard 又在 NP 中

【注】 普遍认为 $P \neq NP$，这正是现代密码学的基础。

贝叶斯网络推理的 NP-硬度

可以证明精确推理是 NP-hard 的，通过从 3SAT（首个已知 NP 完全问题）规约：

3SAT：判断布尔公式是否可满足
给定 3SAT 实例，可以构造等价的贝叶斯网络
公式可满足 $\iff$ $P(y^1) > 0$

【注】 这意味着不存在对所有贝叶斯网络都高效（多项式时间）的精确推理算法，研究近似推理方法是必要的。

2.2.5 近似推理（Approximate Inference）

直接采样（Direct Sampling）

对节点进行拓扑排序
按顺序从条件分布采样

算法 2.3 拓扑排序，算法 2.4 直接采样。

问题：当观测概率很低时，大量样本与观测不一致被丢弃。

似然加权采样（Likelihood Weighted Sampling）

改进：观测变量直接赋值为观测值，样本权重为条件概率的乘积。

算法 2.5 似然加权采样。

【注】 所有样本都与观测一致，但$E=0$ 的样本权重远小于 $E=1$ 的（如公式 2.44-2.45：0.95 vs 0.01）。

吉布斯采样（Gibbs Sampling）

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

样本不独立，下一个样本依赖当前样本
渐近地，从目标分布采样

算法 2.6 吉布斯采样，算法 2.7 计算单点条件分布（利用马尔可夫毯）。

【注】 需要burn-in 期让链收敛到稳态分布，且常需要 thinning（每 k 个样本取 1 个）减少自相关性。

图 2.16 比较

三种方法在化学检测网络上的收敛速度： - 直接采样最慢 - 似然加权较快 - 吉布斯采样最快（此例中）

其他方法

环信念传播（Loopy Belief Propagation）：可用于有环网络，虽不保证精确但实际效果往往不错。

2.3 参数学习（Parameter Learning）

2.3.1 最大似然参数学习（Maximum Likelihood Parameter Learning）

二项分布示例

设 $n$ 次飞行中 $m$ 次碰撞，参数 $\theta = P(c^1)$。

似然函数：

\[ P(D | \theta) \propto \theta^m (1-\theta)^{n-m} \tag{2.53} \]

对数似然：

\[ \ell(\theta) = m \ln \theta + (n-m) \ln(1-\theta) \tag{2.55} \]

求导并设为零：

\[ \frac{\partial \ell}{\partial \theta} = \frac{m}{\theta} - \frac{n-m}{1-\theta} = 0 \]

解得：

\[ \hat{\theta} = \frac{m}{n} \tag{2.57} \]

【注】 这就是我们直觉上的"频率"估计——$m/n$。

K 值离散分布

若变量有 $k$ 个取值，最大似然估计：

\[ \hat{\theta}_i = \frac{m_i}{\sum_{j=1}^{k} m_j} \tag{2.58} \]

高斯参数估计

对连续分布同样适用：

\[ \hat{\mu} = \frac{1}{n} \sum_{i=1}^{n} v_i \tag{2.62} \]

\[ \hat{\sigma}^2 = \frac{1}{n} \sum_{i=1}^{n} (v_i - \hat{\mu})^2 \tag{2.63} \]

【注】 图 2.17 展示了用高斯近似飞机速度分布，$\hat{\mu} = 100.2$ kt，$\hat{\sigma} = 31$ kt。

2.3.2 贝叶斯参数学习（Bayesian Parameter Learning）

最大似然的问题

若数据很少（甚至无观测），最大似然可能给出不合理的估计。例如，一周内无碰撞记录则 $\hat{\theta} = 0$——这显然不对。

贝叶斯方法

将参数也视为随机变量，学习其后验分布 $p(\theta | D)$。

先验：均匀先验 $p(\theta) = 1$（对应 Beta(1,1)）

后验推导：

\[ p(\theta | o_{1:n}) \propto p(\theta) \prod_{i=1}^{n} P(o_i | \theta) = \theta^m (1-\theta)^{n-m} \tag{2.68} \]

归一化后：

\[ p(\theta | o_{1:n}) = \text{Beta}(\theta | m+1, n-m+1) \tag{2.71} \]

Beta 分布

Beta 分布的参数化形式：

\[ \text{Beta}(\theta | \alpha, \beta) = \frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)} \theta^{\alpha-1} (1-\theta)^{\beta-1} \]

其中 $\alpha, \beta$ 是伪计数（Pseudocounts）。

共轭性质：Beta 先验 + 二项似然 → Beta 后验

观测到 $o_i = 1$：后验 $\text{Beta}(\alpha+1, \beta)$
观测到 $o_i = 0$：后验 $\text{Beta}(\alpha, \beta+1)$

先验选择

均匀先验 Beta(1,1)：无信息先验
Beta(2,2)：稍微中心化于 0.5
Beta(10,10)：更强烈地中心化

【注】 先验的重要性随数据量增加而减小——这是贝叶斯方法相对于频率派方法的重要优势之一。

Dirichlet 分布

Dirichlet 分布是 Beta 分布在多值情形下的推广，用于离散分布的参数学习：

\[ \text{Dir}(\theta_{1:n} | \alpha_{1:n}) = \frac{\Gamma(\alpha_0)}{\prod_{i=1}^{n} \Gamma(\alpha_i)} \prod_{i=1}^{n} \theta_i^{\alpha_i - 1} \tag{2.72} \]

其中 $\alpha_0 = \sum_{i=1}^{n} \alpha_i$。

同样具有共轭性质： $$ p(\theta_{1:n} | \alpha_{1:n}, m_{1:n}) = \text{Dir}(\theta_{1:n} | \alpha_1+m_1, \ldots, \alpha_n+m_n) \tag{2.73} $$

2.3.3 非参数学习（Nonparametric Learning）

非参数方法：参数数量随数据量增长。

核密度估计（Kernel Density Estimation）

\[ p(x) = \frac{1}{n} \sum_{i=1}^{n} K(x - o_i) \tag{2.74} \]

其中 $K$ 是核函数，满足 $\int K = 1$，通常取零均值高斯分布。

带宽（Bandwidth）：核函数的标准差，控制光滑程度。 - 带宽过大：过度光滑 - 带宽过小：噪声过大

【注】 贝叶斯方法可用于带宽选择，这里不再展开。

2.4 结构学习（Structure Learning）

2.4.1 贝叶斯结构评分（Bayesian Structure Scoring）

目标：找到使 $P(G | D)$ 最大的图结构 $G$。

记号

$r_i$：变量 $X_i$ 的取值数
$q_i$：父节点 $\text{Pa}_{X_i}$ 的取值数
$m_{ijk}$：数据集中 $X_i = k$ 且 $\text{Pa}_{X_i} = \pi_{ij}$ 的次数
$\theta_{ijk} = P(X_i = k | \text{Pa}_{X_i} = \pi_{ij})$

贝叶斯得分

由贝叶斯规则和全概率定律：

\[ P(G | D) \propto P(G) \int P(D | \theta, G) p(\theta | G) d\theta \tag{2.79} \]

使用 Dirichlet 先验，解析积分后得到：

\[ \ln P(G | D) = \ln P(G) + \sum_{i=1}^{n} \sum_{j=1}^{q_i} \left[ \ln \frac{\Gamma(\alpha_{ij0})}{\Gamma(\alpha_{ij0} + m_{ij0})} + \sum_{k=1}^{r_i} \ln \frac{\Gamma(\alpha_{ijk} + m_{ijk})}{\Gamma(\alpha_{ijk})} \right] \tag{2.83} \]

【注】 对数形式更便于数值计算，避免小概率相乘的下溢问题。

模型复杂度平衡

贝叶斯得分的一个关键优点：自动平衡模型复杂度与数据拟合优度。

【实例】 图 2.21 比较了： - 完全独立模型：参数最少（3 个），数据少时得分最高 - 完全连接模型：参数最多（7 个），数据足够多时能更好拟合 - 真实模型：4 参数，介于两者之间

在约 5000 样本以内，完全独立模型优于真实模型；超过 10000 样本后，完全连接模型开始超过完全独立模型。

2.4.2 有向图搜索（Directed Graph Search）

搜索空间

贝叶斯网络结构数量超指数增长： - 10 个节点：$4.2 \times 10^{18}$ 种结构 - 20 个节点：$2.4 \times 10^{72}$ 种结构

无法穷举，需要启发式搜索。

K2 算法

算法 2.8： 1. 从无边的图开始 2. 给定变量顺序，贪心地添加能最大提升得分的父节点 3. 直到添加任何父节点都不能提升得分

局限：依赖给定变量顺序，不保证全局最优。

局部搜索（Local Search / Hill Climbing）

算法 2.9： 1. 从初始图 $G_0$ 开始 2. 移动到得分最高的邻居 3. 直到没有邻居能提升得分

基本图操作： - 添加有向边 $A \rightarrow B$ - 删除边 $A \rightarrow B$ - 反转边 $A \rightarrow B$ 为 $A \leftarrow B$

局部最优的应对策略

策略	说明
随机重启	局部最优后随机重新开始
模拟退火	按概率接受更差解，随时间减少随机性
禁忌搜索	维护禁忌表，避免重复访问
遗传算法	种群进化、交叉、变异
Memetic 算法	遗传算法 + 局部搜索

【注】 全局最优仍然是 NP-hard 的，但局部最优在很多应用中已足够好。

2.4.3 马尔可夫等价类（Markov Equivalence Classes）

等价类定义

不同有向无环图可能编码相同的条件独立关系，称这些图为马尔可夫等价。

判断准则：两个图马尔可夫等价 $\iff$ 它们有相同的边（不考虑方向）和相同的不道德 v-结构（Immoral V-Structure）。

不道德 v-结构：$X \rightarrow Y \leftarrow Z$，其中 $X$ 和 $Z$ 不直接相连。

计分等价性

使用 BDe 先验（特别是 BDeu）时，马尔可夫等价的图得相同分数——这就是得分等价（Score Equivalent） 性质。

均匀先验 $\alpha_{ijk} = 1$ 不严格满足得分等价，但通常差异很小。

2.4.4 部分有向图搜索（Partially Directed Graph Search）

基本图（Essential Graph）

马尔可夫等价类可以用部分有向图（Essential Graph） 表示： - 必有向边：在所有等价成员中方向一致 - 无向边：方向在成员间可不同

搜索空间优化

搜索部分有向图的空间比搜索完全有向图小得多，效率更高。

基本操作： - 添加边 $A - B$ 或 $A \rightarrow B$ - 删除边 $A - B$ - 反转 $A \rightarrow B$ - 形成 v-结构 $A \rightarrow B \leftarrow C$

【注】 这种方法在大型网络学习中更实用。

2.5 本章小结

不确定性来源：信息不完整、预测局限性
概率论是量化不确定性的形式化框架
贝叶斯网络紧凑表示联合分布，利用条件独立减少参数
推理：精确推理在一般情况是 NP-hard 的；近似推理方法（采样、信念传播等）在实际中更常用
参数学习：最大似然估计简单但对稀疏数据敏感；贝叶斯方法通过先验引入归纳偏置，具有更好的概率解释
结构学习：NP-hard，但启发式搜索（K2、局部搜索等）可在实际中找到良好结构
马尔可夫等价类帮助减少搜索空间

2.6 延伸阅读

主题	参考文献
概率图模型（全面）	Koller & Friedman, Probabilistic Graphical Models
贝叶斯推理与机器学习	Barber, Bayesian Reasoning and Machine Learning
人工智能	Russell & Norvig, Artificial Intelligence: A Modern Approach
概率论基础	Jaynes, Probability Theory: The Logic of Science
贝叶斯网络推理	Cooper, NP-hard 证明 (1990)
K2 算法	Cooper & Herskovits (1992)
BDe 先验	Heckerman, Geiger & Chickering (1995)

本笔记基于《Decision Making Under Uncertainty: Theory and Application》第二章编写，Kochenderfer, MIT Press, 2015