基础
什么样的问题可以用HMM模型
- 可以用HMM的问题具备两个特征
- 问题是基于序列的，例如：时间序列、状态序列等
- 问题中有两类数据，可以观测的观测序列和无法观测的隐藏序列
- 举个栗子
- 打字的时候，键盘打出来的一系列字符是可以观测的观测序列，而我脑子里想通过这些字符写的一段话是没法观测的隐藏序列
- 说话的时候，声音是观测序列，而实际想表达的是隐藏序列，得通过声音来判断出想表达的隐藏序列
HMM模型定义
举个栗子说明
- 栗子来源于《统计学习方法=李航》
- 栗子如下：
假设有3个盒子，每个盒子有多个红白两种球，数量如下表：
| 盒子 | 1 | 2 | 3 |
|---|---|---|---|
| 红 | 5 | 4 | 7 |
| 白 | 5 | 6 | 3 |
有放回抽球3次，规则如下：
- 第一次从盒1抽的概率0.2，盒2、盒3均是0.4
- 接下来每一次的抽取规则：
- 如果当前抽的盒1，则按0.5、0.2、0.3进行盒1、2、3抽取
- 如果当前抽的盒2，则按0.3、0.5、0.2进行盒1、2、3抽取
- 如果当前抽的盒3，则按0.2、0.3、0.5进行盒1、2、3抽取
- 抽3次，得到观测序列：$O=\{\text{红、白、红}\}$，而隐藏序列是$Q=\{\text{盒子1、2、3}\}$，因为不知道每个球是从哪个盒子抽出的
从上述规则可以提取出：
- 观测序列集合$V=\{\text{红、白}\},M=2$
- 隐藏序列集合$Q=\{\text{盒子1、2、3}\},N=3$
- 隐藏序列初始状态分布$\Pi =(0.2,0.4,0.4)^T$
- 隐藏序列转移分布矩阵$A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 &0.5 \end{array} \right)$
- 观测序列概率矩阵$B = \left( \begin{array} {ccc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right)$，行是盒1、2、3，列是红、白
通俗定义
- 设$Q = \{q_1,q_2,…,q_N\}, \; V =\{v_1,v_2,…v_M\}$分别为隐藏序列集合、可观测序列集合
- 设$I = \{i_1,i_2,…,i_T\}, \; O =\{o_1,o_2,…o_T\}$分别为隐藏序列列表、可观测序列列表
- 其中任意一个$i_t \in Q$，任意一个$o_t \in V$
两个重要假设+一个隐藏序列集合初始分布
- 齐次马尔科夫链假设，即$i_t$只依赖于$i_{t-1}$，
- 这样转移概率矩阵表示成$A=\Big [a_{ij}\Big ]_{N \times N}$，其中$a_{ij} = P(i_{t+1} = q_j | i_t= q_i)$
- 观测独立性假设，即任意时刻的观测序列值仅依赖当前时刻的隐藏序列值
- 这样观测序列概率矩阵表示成$B = \Big [b_j(k) \Big ]_{N \times M}$，其中$b_j(k) = P(o_t = v_k | i_t= q_j)$
- 除此之外需要一组在时刻$t=1$的隐藏序列集合的概率分布$\Pi = \Big [ \pi(i)\Big ]_N \; 其中 \;\pi(i) = P(i_1 = q_i)$
HMM定义
- 则HMM表示为$\lambda = (A, B, \Pi)$
HMM观测序列的生成
- 输入：$\lambda = (A, B, \Pi)$
- 输出：$O =\{o_1,o_2,…o_T\}$，长度为$T$
- 生成步骤：
- 根据初始状态概率分布$\Pi$生成隐藏状态$i_1$
- for t in range(1, T+1)
- 按照隐藏状态$i_t$的观测状态分布$b_{i_t}(k)$生成观测状态$o_t$
- 按照隐藏状态$i_t$的转移概率分布$a_{i_t,i_{t+1}}$生成隐藏状态$i_{t+1}$
HMM模型需要解决的三个问题
- 评估观测序列概率，给定模型和观测序列，计算观测序列出现的概率，前向后向算法
- 模型参数学习，给定观测序列，估计模型的参数使观测序列出现的概率最大，基于EM算法的鲍姆-韦尔奇算法
- 预测，给定模型和观测序列，求给定观测序列后，最可能出现的隐藏序列，基于动态规划的维特比算法
解决办法
问题一：评估观测序列概率
暴力求解
步骤
- 我们可以列举出所有可能出现的长度为$T$的隐藏序列$I = \{i_1,i_2,…,i_T\}$，任意一个隐藏序列$I = \{i_1,i_2,…,i_T\}$出现的概率为：$P(I|\lambda) = \pi_{i_1} a_{i_1i_2} a_{i_2i_3}… a_{i_{T-1}\;\;i_T}$
- 对于固定的隐藏序列$I = \{i_1,i_2,…,i_T\}$，我们要求的观测序列$O =\{o_1,o_2,…o_T\}$出现的概率为：$P(O|I, \lambda) = b_{i_1}(o_1)b_{i_2}(o_2)…b_{i_T}(o_T)$
- 则$O,T$的联合概率为：$P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)…a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)$
- 最后求观测序列$O$在模型$\lambda$下出现的条件概率$P(O|\lambda)$为：$P(O|\lambda) = \sum\limits_{I}P(O,I|\lambda) = \sum\limits_{i_1,i_2,…i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)…a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)$
问题：
- 暴力求解太耗时，当隐藏状态数$N$太大时
- 时间复杂度：$O(TN^T)$
前向算法
- 前向概率定义：$\alpha_t(i) = P(o_1,o_2,…o_t, i_t =q_i | \lambda)$
步骤
- 计算时刻1的各个隐藏状态前向概率：$\alpha_1(i) = \pi_ib_i(o_1),\; i=1,2,…N$
- from t=2 to T：
- 计算时刻$t$的各个隐藏状态前行概率：$\alpha_{t+1}(i) = \Big[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\Big]b_i(o_{t+1}),\; i=1,2,…N$
- 计算最终结果：$P(O|\lambda) = \sum\limits_{i=1}^N\alpha_T(i)$
问题
- 时间复杂度：$O(TN^2)$
后向算法
- 后向概率定义：$\beta_t(i) = P(o_{t+1},o_{t+2},…o_T| i_t =q_i , \lambda)$
步骤
- 初始化时刻$T$各个隐藏状态后向概率：$\beta_T(i) = 1,\; i=1,2,…N$
- from t=T-1 to 1：
- 计算时刻$t$的后向概率：$\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\; i=1,2,…N$
- 计算最终结果：$P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$
问题
- 时间复杂度：$O(TN^2)$
问题二：模型参数学习：学习$A,B,\lambda$
根据前向后向算法计算常用概率
- 给定模型$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$的概率为：$\gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)}= \frac{ \alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)}$
- 给定模型$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$，且时刻$t+1$处于状态$q_j$的概率为：$\xi_t(i,j) = P(i_t = q_i, i_{t+1}=q_j | O,\lambda) = \frac{ P(i_t = q_i, i_{t+1}=q_j , O|\lambda)}{P(O|\lambda)}=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s)}$
- 由1、2可得：
- 在观测序列$O$下状态$i$出现的期望值为：$\sum\limits_{t=1}^T\gamma_t(i)$
- 在观测序列$O$下状态$i$转移的期望值为：$\sum\limits_{t=1}^{T-1}\gamma_t(i)$
- 在观测序列$O$下状态$i$转移到状态$j$的期望值为：$\sum\limits_{t=1}^{T-1}\xi_t(i,j)$
求解模型参数：简单情况-隐藏序列已知
已知$D$个长度为$T$的观测序列和对应的隐藏序列，即$\{(O_1, I_1), (O_2, I_2), …(O_D, I_D)\}$，求解如下：
- 统计从隐藏状态$q_i$到$q_j$的频率计数为$A_{ij}$，那么可得隐藏状态转移矩阵$A$
- 统计样本隐藏状态为$q_j$且观测状态为$v_k$的频率计数为$B_{jk}$，则观测状态矩阵为$B$
- 统计样本初始隐藏状态为$q_i$的频率计数为$C(i)$，则初始概率分布为$\Pi$
求解模型参数：复杂情况-隐藏序列未知
已知$D$个长度为$T$的观测序列，即$\{(O_1), (O_2), …(O_D)\}$，
鲍姆-韦尔奇算法
- E步：求出联合分布$P(O,I|\lambda)$基于条件概率$P(I|O,\overline{\lambda})$的期望表达式：$L(\lambda, \overline{\lambda}) = \sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)$
- M步：极大化上式，更新参数：$\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)$
- 不断迭代EM步，直到收敛
具体步骤
输入：$\{(O_1), (O_2), …(O_D)\}$
输出：HMM模型参数
步骤：
随机初始化所有的$\Pi,A,B$
对于每个样本，用前向后向算法计算$\gamma_t^{(d)}(i)，\xi_t^{(d)}(i,j), t =1,2…T$
更新模型参数：
如果$\Pi,A,B$已经收敛，则算法结束，否则从第二步开始继续迭代
问题三：预测-维特比算法
两个局部状态
在时刻$t$隐藏状态为$i$所有可能的状态转移路径$i_1,i_2,…i_t$中的概率最大值，记为$\delta_t(i) = \max_{i_1,i_2,…i_{t-1}}\;P(i_t=i, i_1,i_2,…i_{t-1},o_t,o_{t-1},…o_1|\lambda),\; i =1,2,…N$，且递推表达式为：
在时刻$t$隐藏状态为$i$所有单个状态转移路径$(i_1,i_2,…,i_{t-1},i)$中概率最大的转移路径中第$t-1$个节点的隐藏状态为$\Psi_t(i)$，其递推表达式为：
算法流程
输入：HMM模型$\lambda = (A,B,\Pi)$，观测序列$O=(o_1,o_2,…o_T)$
输出：最有可能的隐藏状态序列$I^= \{i_1^,i_2^,…i_T^\}$
步骤：
初始化局部状态：
from t=2 to T：
计算时刻$T$最大的$\delta_T(i)$以及对应的$\Psi_T(i)$，开始回溯得到最可能的隐藏状态序列$I^= \{i_1^,i_2^,…i_T^\}$
举个栗子
输入：
计算：
观测状态为
红：然后观测状态为
白：然后观测状态为
红：现在开始回溯，此时最大概率为$\delta_3(3)$，从而得到$i_3^* =3$
由于$\Psi_3(3)=3,\Psi_2(3)=3$，所以最终最可能的隐藏状态序列为$(3,3,3)$
进阶
为什么这里的维特比和中文分词那里不太相同？
- 中文分词时，我们没有观测序列和隐藏序列的区别，只有一种状态
维特比算法与dijkstra算法区别？
- 维特比算法使用动态规划，而dijkstra是贪心算法
- 维特比算法仅仅局限于求序列最短路径，而dijkstra是通用的求最短路径方法
