第五讲 · 隐马尔可夫模型

有些问题天然带着一条时间轴：天气每天变化、语音由一串音素组成、手写字符可以按竖直切片依次扫描。我们能看到的是天气描述、声音波形或图像特征，却真正关心它们背后的状态。

隐马尔可夫模型（Hidden Markov Model，HMM）就是为这种问题准备的：系统内部有一条看不见的状态序列，每个状态一边决定下一时刻的状态，一边随机地产生当前能看到的观测。

一、先从马尔可夫链开始

设第 $t$ 时刻的状态为 $S_t$。一阶马尔可夫性假设为

$$P(S_t\mid S_1,\ldots,S_{t-1})=P(S_t\mid S_{t-1}).$$

它并不是说“过去完全没用”，而是说：当前状态已经浓缩了预测未来所需的历史信息。知道今天的天气后，预测明天时不再额外查看前天的天气。

若转移规律不随时间改变，还可以写成齐次转移概率

$$a_{ij}=P(S_t=j\mid S_{t-1}=i),\qquad \sum_j a_{ij}=1.$$

把所有 $a_{ij}$ 排成矩阵就得到状态转移矩阵 $A$。另用

$$\pi_i=P(S_1=i),\qquad \sum_i\pi_i=1$$

表示初始状态分布。于是，一条具体状态路径 $Q=(q_1,\ldots,q_T)$ 的概率为

$$P(Q)=\pi_{q_1}\prod_{t=2}^{T}a_{q_{t-1}q_t}.$$

这就是普通马尔可夫链：状态本身可以直接看到。HMM 再加上一层“遮挡”。

二、HMM 多出的观测层

设隐藏状态共有 $N$ 种，观测符号共有 $M$ 种。状态 $i$ 生成观测 $v_k$ 的概率为

$$b_i(k)=P(O_t=v_k\mid S_t=i),\qquad \sum_{k=1}^{M}b_i(k)=1.$$

所有发射概率组成矩阵 $B$。一个 HMM 通常记为

$$\lambda=(A,B,\boldsymbol{\pi}).$$

给定状态序列 $Q=(q_1,\ldots,q_T)$ 与观测序列 $O=(o_1,\ldots,o_T)$，二者的联合概率是

$$P(O,Q\mid\lambda) =\pi_{q_1}b_{q_1}(o_1) \prod_{t=2}^{T}a_{q_{t-1}q_t}b_{q_t}(o_t).$$

这个式子很重要：初始时“选状态再发射”，以后每一步都是“转移到新状态，再由新状态发射观测”。

课件用“从若干只缸里摸彩球”解释这件事：缸是隐藏状态，球的颜色是观测；我们看得到摸出的颜色，却看不到每次用了哪只缸。语音识别中，隐藏状态可以对应音素的内部阶段，观测则来自连续语音切片提取出的特征。

HMM 还包含一个条件独立假设：给定当前状态 $S_t$ 后，当前观测 $O_t$ 不再依赖其他时刻的状态和观测。正是这两个局部假设，让原本指数级的序列计算可以用动态规划完成。

三、HMM 的三个基本问题

已知	想求	典型算法
模型 $\lambda$、观测 $O$	$P(O\mid\lambda)$，模型与观测有多匹配	前向算法
模型 $\lambda$、观测 $O$	最可能的隐藏状态序列 $Q^*$	Viterbi 算法
观测序列 $O$	让 $P(O\mid\lambda)$ 尽量大的参数	Baum-Welch 算法

“观测序列最可能由哪个模型产生”和“在一个模型内最可能走过哪条路径”是两个不同问题。前者要把所有可能路径的概率相加，后者只取其中概率最大的一条。

四、前向算法：把所有路径汇总起来

如果直接枚举状态路径，共有 $N^T$ 种可能。前向算法把到达同一时刻、同一状态的所有路径先合并。

定义前向量

$$\alpha_t(i)=P(o_1,\ldots,o_t,S_t=i\mid\lambda).$$

递推分三步：

1. 初始化

   $$\alpha_1(i)=\pi_i b_i(o_1).$$

2. 从 $t=2$ 递推到 $T$

   $$\alpha_t(j) =b_j(o_t)\sum_{i=1}^{N}\alpha_{t-1}(i)a_{ij}.$$

3. 汇总最后时刻

   $$P(O\mid\lambda)=\sum_{i=1}^{N}\alpha_T(i).$$

复杂度从枚举的指数级降为 $O(TN^2)$。实践中序列很长时，连续相乘会造成浮点下溢，通常对每一步做缩放或转入对数域。

与它方向相反的后向量

$$\beta_t(i)=P(o_{t+1},\ldots,o_T\mid S_t=i,\lambda)$$

从末尾向前递推。前向量与后向量合起来，可以计算“在看到整段观测后，第 $t$ 时刻处于状态 $i$ 的后验概率”，这既能用于逐位置解码，也是 Baum-Welch 学习的基础。

五、Viterbi：只保留最佳路径

Viterbi 与前向算法的框架几乎相同，只是把“求和”换成“取最大值”，并额外记住最大值从哪里来。

定义

$$\delta_t(j)= \max_{q_1,\ldots,q_{t-1}} P(q_1,\ldots,q_{t-1},S_t=j,o_1,\ldots,o_t\mid\lambda).$$

初始化为

$$\delta_1(j)=\pi_jb_j(o_1).$$

递推为

$$\delta_t(j) =b_j(o_t)\max_i\left[\delta_{t-1}(i)a_{ij}\right],$$

同时记录回溯指针

$$\psi_t(j)=\arg\max_i\left[\delta_{t-1}(i)a_{ij}\right].$$

最后从 $\arg\max_j\delta_T(j)$ 出发，沿 $\psi$ 逆序回溯，就得到整条最佳路径。复杂度同样是 $O(TN^2)$。

完整算例：从朋友圈猜同行朋友

课件给出三个隐藏状态：这一周陪朋友 A、B 或 C。初始分布为

$$\boldsymbol{\pi}=(0.2,0.4,0.4).$$

转移矩阵与发射概率分别为

$$A= \begin{bmatrix} 0.5&0.2&0.3\\ 0.3&0.5&0.2\\ 0.2&0.3&0.5 \end{bmatrix},\qquad B= \begin{array}{c|cc} &\text{吃饭}&\text{看电影}\\\hline A&0.5&0.5\\ B&0.4&0.6\\ C&0.7&0.3 \end{array}.$$

现在观测到连续三周为“吃饭、看电影、吃饭”。第一周

$$\boldsymbol{\delta}_1 =(0.2\times0.5,\ 0.4\times0.4,\ 0.4\times0.7) =(0.10,0.16,0.28).$$

第二周分别计算到 A、B、C 的最佳概率：

$$\begin{aligned} \delta_2(A)&=0.5\max(0.10\times0.5,0.16\times0.3,0.28\times0.2)=0.028,\\ \delta_2(B)&=0.6\max(0.10\times0.2,0.16\times0.5,0.28\times0.3)=0.0504,\\ \delta_2(C)&=0.3\max(0.10\times0.3,0.16\times0.2,0.28\times0.5)=0.042. \end{aligned}$$

第三周得到

$$\boldsymbol{\delta}_3=(0.00756,0.01008,0.0147).$$

末尾最大值落在 C，沿指针回溯仍是 C、C，所以最佳隐藏路径为

$$C\rightarrow C\rightarrow C,\qquad P(O,Q^*\mid\lambda)=0.0147.$$

若用前向算法把所有路径相加，则

$$P(O\mid\lambda)=0.130218.$$

这也给出一个很实用的自检：最佳单条路径的概率一定不大于全部路径概率之和，这里 $0.0147<0.130218$。

六、参数怎样学出来

隐藏状态已标注

若训练数据同时给出状态序列与观测序列，就直接用频数做最大似然估计：

$$a_{ij} =\frac{\text{从状态 }i\text{ 转移到 }j\text{ 的次数}} {\text{从状态 }i\text{ 出发的总次数}},$$ $$b_i(k) =\frac{\text{状态 }i\text{ 发射观测 }v_k\text{ 的次数}} {\text{处于状态 }i\text{ 的总次数}}.$$

初始概率 $\pi_i$ 则由各序列第一时刻处于状态 $i$ 的频率估计。

只有观测，没有状态标注

此时无法直接计数。Baum-Welch 算法把隐藏路径当作缺失变量，反复执行：

1. 用当前参数运行前向-后向算法，计算每个时刻处于各状态、发生各转移的后验期望次数；
2. 用“期望转移次数 / 期望出发次数”更新 $A$，用“期望发射次数 / 期望占用次数”更新 $B$；
3. 重复直到观测似然不再明显增加。

这就是 EM 思想在 HMM 上的具体实现。它会让训练数据的似然单调不减，但一般只能保证到达局部最优，因此初始化可能影响结果。

七、序列识别如何落地

课件给出一个字符识别练习：把字符从左到右切成若干竖条，每条的“岛屿数量”作为观测。字符 A 与 B 各自拥有一个左到右 HMM。观测序列为

$$O=(1,3,2,1).$$

把模型允许的三条状态路径概率相加，课件算得

$$P(O\mid\lambda_A)=0.0023976,\qquad P(O\mid\lambda_B)=0.0096768.$$

因为后者更大，这段观测更可能由字符 B 的模型生成。这个例子展示了两层动态规划的分工：在每个候选字符模型内部汇总路径得到似然，再在多个模型之间比较似然完成分类。

课件给出的实际建模流程可以归纳为：

1. 根据问题确定隐藏状态、观测及拓扑结构；
2. 用已知序列估计 $A$、$B$、$\boldsymbol{\pi}$；
3. 对新序列计算似然，或用 Viterbi / 后验概率解码；
4. 用独立数据检查识别效果，而不是只看训练似然。

本讲速记

• 马尔可夫链描述“状态怎样转移”，HMM 还描述“状态怎样产生观测”。
• HMM 三组参数是初始分布 $\boldsymbol{\pi}$、转移矩阵 $A$、发射矩阵 $B$。
• 前向算法对所有路径求和，回答观测有多可能；Viterbi 对路径取最大值并回溯，回答最可能经历了哪些状态。
• 状态已知时用频数估计；状态未知时用前向-后向计算期望，再由 Baum-Welch 迭代更新。
• 所有概率分布的元素都应非负且归一化；最佳路径概率不应超过观测总似然。