第14章概率图模型

🎯 学习目标

理解概率图模型的基本概念和表示
掌握隐马尔可夫模型的三个基本问题
理解贝叶斯网络的结构和推断
了解马尔可夫随机场和条件随机场

14.1 隐马尔可夫模型

HMM基本概念

隐马尔可夫模型（Hidden Markov Model, HMM） 是一种用于建模序列数据的概率图模型，包含隐藏状态序列和观测序列。

HMM的组成

状态集合 $S = {s_{1}, s_{2}, \dots, s_{N}}$ ：隐藏状态空间
观测集合 $O = {o_{1}, o_{2}, \dots, o_{M}}$ ：可观测输出空间
状态转移概率 $A = [a_{i j}]$ ： $a_{i j} = P (s_{j} | s_{i})$ ，从状态i转移到状态j的概率
观测概率 $B = [b_{j} (k)]$ ： $b_{j} (k) = P (o_{k} | s_{j})$ ，在状态j下观测到 $o_{k}$ 的概率
初始状态概率 $π = [π_{i}]$ ： $π_{i} = P (s_{1} = s_{i})$ ，初始状态为 $s_{i}$ 的概率

马尔可夫假设

一阶马尔可夫性：当前状态只依赖于前一时刻的状态，与更早的历史无关。

P (q_{t} | q_{t - 1}, q_{t - 2}, \dots, q_{1}) = P (q_{t} | q_{t - 1})

💡 典型应用

语音识别：观测是声学信号，隐藏状态是音素或词
词性标注：观测是单词，隐藏状态是词性（名词、动词等）
生物序列分析：基因序列分析、蛋白质结构预测

HMM的三个基本问题

1. 概率计算问题（Evaluation）

给定模型 $λ = (A, B, π)$ 和观测序列 O，计算 $P (O | λ)$ 。算法：前向算法（Forward Algorithm）或后向算法（Backward Algorithm）。

2. 学习问题（Learning）

给定观测序列 O，学习模型参数 $λ = (A, B, π)$ 使得 $P (O | λ)$ 最大。算法：Baum-Welch算法（EM算法的特例）。

3. 解码问题（Decoding）

给定模型 $λ$ 和观测序列 O，找到最可能的隐藏状态序列 Q。算法：Viterbi算法（动态规划）。

Viterbi算法

Viterbi算法 用动态规划找到最可能的状态序列，是HMM解码的核心算法。

算法步骤

初始化： $δ_{1} (i) = π_{i} \cdot b_{i} (o_{1})$ ， $ψ_{1} (i) = 0$
递推：对 t = 2, 3, ..., T：
- $δ_{t} (j) = max_{i} [δ_{t - 1} (i) \cdot a_{i j}] \cdot b_{j} (o_{t})$
- $ψ_{t} (j) = \arg max_{i} [δ_{t - 1} (i) \cdot a_{i j}]$
终止： $P^{*} = max_{i} δ_{T} (i)$ ， $q_{T}^{*} = \arg max_{i} δ_{T} (i)$
回溯： $q_{t - 1}^{*} = ψ_{t} (q_{t}^{*})$ ，得到最优路径

时间复杂度： $O (T N^{2})$ ，其中T是序列长度，N是状态数量。

14.2 马尔可夫随机场

概率图模型概述

概率图模型（Probabilistic Graphical Model, PGM） 用图结构表示变量间的概率依赖关系，节点表示随机变量，边表示依赖关系。

有向图模型（贝叶斯网络）：用有向无环图（DAG）表示因果关系，边表示条件概率。联合概率分解为条件概率的乘积。
无向图模型（马尔可夫随机场）：用无向图表示变量间的对称依赖关系，基于团（clique）定义联合概率。

马尔可夫随机场（MRF）

马尔可夫随机场（Markov Random Field, MRF） 是一种无向概率图模型，满足局部马尔可夫性质。

成对马尔可夫性：给定其他所有变量，两个不相邻的变量条件独立：

u ⊥ v ∣ X ∖ {u, v} （如果u和v不相邻）

局部马尔可夫性：给定邻居变量，一个变量与其他变量条件独立：

v ⊥ X ∖ ({v} \cup N (v)) ∣ N (v)

其中 N(v) 是v的邻居集合。

基于势函数的联合概率

联合概率由各个团（clique）上的势函数（potential function）定义：

P (X) = \frac{1}{Z} \prod_{C \in C} ψ_{C} (X_{C})

Z是归一化因子（配分函数）， $ψ_{C}$ 是团C上的势函数。

条件随机场（CRF）

条件随机场（Conditional Random Field, CRF） 是给定观测序列条件下的马尔可夫随机场，常用于序列标注任务。

线性链CRF

对于序列标注，条件概率定义为：

P (y | x) = \frac{1}{Z (x)} \exp (\sum_{t} \sum_{k} λ_{k} f_{k} (y_{t - 1}, y_{t}, x, t))

$f_{k}$ 是特征函数， $λ_{k}$ 是对应权重， $Z (x)$ 是归一化因子。

CRF vs HMM

HMM：生成式模型，建模 $P (x, y) = P (y) P (x | y)$ ，有严格的独立性假设
CRF：判别式模型，直接建模 $P (y | x)$ ，可以使用任意特征，无需独立性假设

CRF通常比HMM在序列标注任务上表现更好，但训练更复杂。

应用：词性标注、命名实体识别、中文分词、信息抽取等序列标注任务。

14.3 学习与推断

概率图模型的推断

推断（Inference） 是概率图模型的核心任务，包括边际概率计算、最大后验估计（MAP）等。

精确推断

变量消除（Variable Elimination）：利用分配律，通过消除变量逐步计算边际概率
信念传播（Belief Propagation）：在树结构图上通过消息传递进行推断
团树算法（Junction Tree）：将图转换为树结构后进行精确推断

近似推断

当精确推断计算复杂度过高时（NP难），使用近似方法：

采样方法：MCMC（马尔可夫链蒙特卡洛）、吉布斯采样
变分推断：用简单分布近似复杂分布，转化为优化问题
循环信念传播：在有环图上迭代运行信念传播直到收敛

参数学习

完全数据的参数学习

当所有变量都可观测时，可以直接用最大似然估计：有向图估计每个条件概率表（CPT），无向图估计各团的势函数参数。

隐变量的参数学习

当存在隐变量时，使用EM算法：

E步：根据当前参数计算隐变量的后验分布
M步：最大化期望对数似然，更新参数
重复直到收敛

HMM的Baum-Welch算法和GMM的EM算法都是这一框架的实例。

结构学习

结构学习 是从数据中学习图的结构（变量间的依赖关系），比参数学习更具挑战性。

基于评分的方法

定义评分函数（如BIC、AIC），搜索使得评分最高的图结构：

score (G) = \log P (D | G) - \frac{d}{2} \log m

第一项：数据拟合度，第二项：模型复杂度惩罚。

基于约束的方法

通过统计独立性测试发现变量间的条件独立关系，据此构建图结构。例如PC算法、IC算法等。

挑战

结构学习的搜索空间巨大（超指数级），且很多问题是NP难的。实际中常结合领域知识或使用启发式搜索。

14.4 近似推断

MCMC采样

马尔可夫链蒙特卡洛（MCMC） 通过构造马尔可夫链来对目标分布进行采样，从而近似计算期望和边际概率。

Metropolis-Hastings算法

初始化状态 $x^{(0)}$
对 t = 1, 2, ..., T：
- 从提议分布 $q (x^{'} | x^{(t - 1)})$ 采样候选状态 x'
- 计算接受率： $α = min (1, \frac{P (x^{'}) q (x^{(t - 1)} | x^{'})}{P (x^{(t - 1)}) q (x^{'} | x^{(t - 1)})})$
- 以概率 α 接受 x'，否则保持 $x^{(t - 1)}$

经过足够多步骤后，样本的分布收敛到目标分布 P(x)。

吉布斯采样（Gibbs Sampling）

MH算法的特例，每次只更新一个变量，条件概率作为提议分布：

随机初始化所有变量
循环：对每个变量 $x_{i}$ ，从条件分布 $P (x_{i} | x_{- i})$ 中采样更新
重复直到收敛

吉布斯采样简单易实现，在高维问题中广泛应用。

变分推断

变分推断（Variational Inference） 将推断问题转化为优化问题，用简单分布 q(x) 近似复杂的后验分布 p(x|D)。

KL散度最小化

目标是最小化 q(x) 和 p(x|D) 之间的KL散度：

min KL (q ∥ p) = min E_{q} [\log q (x)] - E_{q} [\log p (x, D)]

平均场近似

假设 q(x) 可以分解为独立分布的乘积：

q (x) = \prod_{i} q_{i} (x_{i})

通过坐标上升法迭代优化每个 $q_{i}$ ，直到收敛。

变分推断优点：确定性算法、可重复；收敛速度通常比MCMC快；易于分布式计算。缺点：只能得到近似解；可能陷入局部最优；需要选择近似分布族。

14.5 话题模型

隐狄利克雷分配（LDA）

LDA（Latent Dirichlet Allocation） 是一种话题模型，用于发现文档集合中的潜在主题。

生成过程

LDA假设每篇文档由多个话题混合而成，每个话题由词的分布定义：

对每个话题k，从Dirichlet分布生成词分布 $ϕ_{k} \sim Dir (β)$
对每篇文档d：
- 从Dirichlet分布生成话题分布 $θ_{d} \sim Dir (α)$
- 对文档中的每个词位置n：选择话题 $z_{d n} \sim Mult (θ_{d})$ ，然后从该话题的词分布选择词 $w_{d n} \sim Mult (ϕ_{z_{d n}})$

超参数

α：文档-话题分布的Dirichlet先验，控制话题稀疏性
β：话题-词分布的Dirichlet先验，控制词稀疏性
K：话题数量（需要预先指定）

LDA推断

吉布斯采样：迭代采样每个词的话题分配，基于其他词的话题
变分EM：用变分推断近似后验分布，交替优化参数

💡 应用

文档分类：基于话题分布对文档分类
信息检索：基于话题相似度检索相关文档
推荐系统：基于用户的话题偏好推荐
文本摘要：提取代表性话题和词汇

第14章 概率图模型 ​

🎯 学习目标 ​

14.1 隐马尔可夫模型 ​

14.2 马尔可夫随机场 ​

14.3 学习与推断 ​

14.4 近似推断 ​

14.5 话题模型 ​