后续会回来补充代码

1 隐马尔可夫模型

  隐马尔可夫模型(Hidden Markov Model,HMM)是可用于标注问题的统计学模型，描述由隐藏的马尔可夫链随机生成观测序列的过程。

1.1 数学定义

  隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成同一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成状态序列，而每一个状态又生成一个观测。序列的每一个位置称作一个时刻。
  隐马尔可夫模型可以由初始状态概率向量$\pi$，状态转移矩阵$A$和观测矩阵$B$决定。$\pi$和$A$决定状态序列，$B$决定观测序列。隐马尔可夫模型可以记作：$\lambda =(\pi ,A,B)$。其各个部分的介绍如下：
  记 Q = { q 1 , q 2 , … , q N } Q=\{q_{1},q_{2},\dots,q_{N}\} Q={q1​,q2​,…,qN​}为所有可能的状态集合， V = { v 1 , v 2 , … , v M } V=\{v_{1}, v_{2},\dots,v_{M}\} V={v1​,v2​,…,vM​}为所有可能的观测集合。假设目前得到的$T$个时刻观测序列$O=(o_1,o_2，\dots ,o_T)$，其对应的状态序列记为$I=(i_1,i_2,\dots ,i_T)$。状态序列是不可知的
  状态转移矩阵$A=[a_{ij}{]}_{N\times N}$, 其中$a_{ij}=P(i_{t+1}=q_j|i_t=q_i),i,j=1,2,\dots ,N$，即为在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。观测矩阵$B=[b_j(k){]}_{N\times M}$，其中$b_j(k)=P(o_t=v_k|i_t=q_j),k=1,2,\dots ,M,j=1,2,\dots ,N$为时刻$t$处于状态$q_j$的条件下生成观测$v_k$的概率。
  初始状态变量$\pi =({\pi }_i)$，其中${\pi }_i=P(i_1=q_i),i=1,2,\dots ,N$为初始时刻$t=1$处于状态$q_i$的概率。

1.2 基本假设

• 齐次马尔可夫假设：隐藏的马尔科夫链在任意时刻$t$的状态只依赖于其前一个时刻状态，与其他时刻的状态和观测无关，也与时刻$t$无关：$$P(i_t|i_{t-1},o_{t-1},\dots ,i_1,o_1)=P(i_t|i_{t-1}),t=1,2,\dots ,T$$
• 观测独立性假设：任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

1.3 基本问题

• 概率计算问题：给定模型$\lambda =(\pi ,A,B)$和观测序列$O$，计算该观测序列出现的概率$P(O|\lambda )$。求解该问题可以使用前向算法和后向算法，这里不详细介绍。
• 学习问题：已知观测序列$O$，估计模型$\lambda =(\pi ,A,B)$参数，使得在该模型下观测序列概率$P(O|\lambda )$最大。求解该问题主要使用Baum-Welch算法(这个算法是EM算法的一种特例，EM算法在三硬币模型上的推导过程参考：https://blog.csdn.net/yeshang_lady/article/details/132151771)。这里不再赘述。
• 预测问题：又被称为解码问题。已知模型$\lambda =(\pi ,A,B)$和观测序列$O$，求对给定观测序列条件概率$P(I|O)$最大的状态序列。这里主要介绍维特比算法。

2 预测问题

2.1 维特比算法

  维特比算法是一个动态规划算法，其规划过程与前向算法类似。两个算法的区别在于：评估问题的前向算法会保留每一条路径的概率，最终结果是各概率之和；维特比算法是计算给定观测序列下最可能的隐藏状态序列，因此每一步都只保留概率最大的路径，最终结果是一条概率最大的路径。其算法流程如下：

输入: 模型$\lambda =(A,B,\pi )$和观测序列$O=(o_1,o_2,\dots ,o_T)$；
输出：最优路径$I^{\ast }=(i_1^{\ast },i_2^{\ast },\dots ,i_T^{\ast })$。
步骤: (1)初始化$${\delta }_1(i)={\pi }_i{b}_i(o_1),i=1,2,\dots ,N$$$${\Psi }_1(i)=0,i=1,2,\dots ,N$$(2)递推。对$t=2,3,\dots ,T$ $${\delta }_t(i)=\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\dots ,N$$$${\Psi }_t(i)=arg\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\dots ,N$$(3)终止$$P^{\ast }=\underset{1\le j\le N}{\max }{\delta }_T(i)$$$$i_T^{\ast }=arg\underset{1\le j\le N}{\max }[{\delta }_T(i)]$$(4)最优路径回溯。对$t=T-1,T-2,\dots ,1$$$i_t^{\ast }={\Psi }_{t+1}(i_{t+1}^{\ast })$$求得最优路径$I^{\ast }=(i_1^{\ast },i_2^{\ast },\dots ,i_T^{\ast })$

参考资料

1. 《统计学习方法》