HMM 隐马尔可夫模型 (Hidden Markov Model)

核心思想

HMM 是一种描述由隐状态序列生成观测序列的概率图模型。隐状态之间通过马尔可夫链连接，观测值由当前隐状态生成。

模型定义

HMM 由五元组 $\lambda =(\mathcal{S},\mathcal{O},\mathbf{A},\mathbf{B},\mathit{\pi })$ 定义：

符号	含义
$\mathcal{S}=\{s_1,\dots ,s_N\}$	$N$ 个隐状态集合
$\mathcal{O}=\{o_1,\dots ,o_M\}$	$M$ 个观测符号集合
$\mathbf{A}=[a_{ij}{]}_{N\times N}$	状态转移概率矩阵
$\mathbf{B}=[b_j(k){]}_{N\times M}$	发射概率矩阵
$\mathit{\pi }=[{\pi }_i{]}_N$	初始状态概率

两个基本假设

1. 一阶马尔可夫假设：$P(q_t\mid q_{t-1},q_{t-2},\dots )=P(q_t\mid q_{t-1})$
2. 观测独立假设：$P(o_t\mid q_1,\dots ,q_T,o_1,\dots ,o_T)=P(o_t\mid q_t)$

三大基本问题

问题一：评估 (Evaluation)

给定模型 $\lambda$ 和观测序列 $\mathbf{O}=(o_1,\dots ,o_T)$，计算 $P(\mathbf{O}\mid \lambda )$。

前向算法

定义前向变量：

$${\alpha }_t(i)=P(o_1,o_2,\dots ,o_t,q_t=s_i\mid \lambda )$$

初始化：

$${\alpha }_1(i)={\pi }_i\cdot b_i(o_1),i=1,\dots ,N$$

递推：

$${\alpha }_{t+1}(j)=[\sum _{i=1}^N{\alpha }_t(i)\cdot a_{ij}]\cdot b_j(o_{t+1})$$

终止：

$$P(\mathbf{O}\mid \lambda )=\sum _{i=1}^N{\alpha }_T(i)$$

时间复杂度从暴力的 $O(N^T)$ 降至 $O(N^{2}T)$。

问题二：解码 (Decoding)

给定模型和观测，找最可能的隐状态序列 ${\mathbf{Q}}^{\ast }=\arg \underset{\mathbf{Q}}{max}P(\mathbf{Q}\mid \mathbf{O},\lambda )$。

Viterbi 算法

定义：

$${\delta }_t(i)=\underset{q_1,\dots ,q_{t-1}}{max}P(q_1,\dots ,q_t=s_i,o_1,\dots ,o_t\mid \lambda )$$

初始化：

$${\delta }_1(i)={\pi }_i\cdot b_i(o_1),{\psi }_1(i)=0$$

递推：

$${\delta }_t(j)=\underset{1\le i\le N}{max}[{\delta }_{t-1}(i)\cdot a_{ij}]\cdot b_j(o_t)$$$${\psi }_t(j)=\arg \underset{1\le i\le N}{max}[{\delta }_{t-1}(i)\cdot a_{ij}]$$

终止：

$$P^{\ast }=\underset{1\le i\le N}{max}{\delta }_T(i),q_T^{\ast }=\arg \underset{i}{max}{\delta }_T(i)$$

回溯：

$$q_t^{\ast }={\psi }_{t+1}(q_{t+1}^{\ast }),t=T-1,\dots ,1$$

问题三：学习 (Learning)

给定观测序列，估计模型参数 $\lambda$。使用 Baum-Welch 算法（EM 算法的特殊形式）。

后向变量

$${\beta }_t(i)=P(o_{t+1},\dots ,o_T\mid q_t=s_i,\lambda )$$

E 步

$${\xi }_t(i,j)=\frac{{\alpha }_t(i)\cdot a_{ij}\cdot b_j(o_{t+1})\cdot {\beta }_{t+1}(j)}{P(\mathbf{O}\mid \lambda )}$$$${\gamma }_t(i)=\sum _{j=1}^N{\xi }_t(i,j)$$

M 步

$${\hat{\pi }}_i={\gamma }_1(i)$$$${\hat{a}}_{ij}=\frac{\sum _{t=1}^{T-1}{\xi }_t(i,j)}{\sum _{t=1}^{T-1}{\gamma }_t(i)}$$$${\hat{b}}_j(k)=\frac{\sum _{t=1}^T{\gamma }_t(j)\cdot \mathbb{1}(o_t=k)}{\sum _{t=1}^T{\gamma }_t(j)}$$

代码对应

python -m pipelines.probabilistic.hmm