最近看论文又看到了隐马尔可夫模型（Hiden Markov Model, HMM），几个月前曾经了解了一些HMM的基本原理，但是现在又有些模糊了。好记性不如烂笔头啊，还是系统梳理一下HMM的知识，毕竟是个挺常用的模型。
基本概念
”隐马尔可夫模型“是一个关于时序的概率模型， 简单来说，就是一个隐藏的马尔可夫链，由初始状态开始，随机生成不可观测的状态序列，而每个状态又会随机产生一个观测值，形成一个可观测的观测序列。其中，初始状态由初始概率分布确定，状态序列根据状态转移概率分布产生，而观测序列根据观测概率分布产生。所以，隐马尔可夫模型由这三个概率分布决定，它们是马尔可夫模型的三要素。
隐马尔可夫模型有两个重要的假设：一是每一个时刻的状态至于前一个时刻的状态有关，二是观测值只与当前状态有关，与其他状态与观测值无关。
数学描述
为了后文方便，这里统一对HMM进行一个数学描述，定义一些数学符号。
设\(Q\)是所有可能的状态集合，\(V\)是所有可能的观测的集合
\(Q=\{q_1,q_2,...,q_N\}\), \(V=\{v_1,v_2,...v_M\}\)
其中，\(N\)是可能的状态数，\(M\)是可能的观测数。
设\(I\)是长度为\(T\)的状态序列，\(O\)是对应的观测序列
\(I=\{i_1,i_2,...i_T\}\), \(O=\{o_1,o_2,...o_T\}\)
其中，\(i_t\in Q\), \(o_t\in V\)
设\(A\)是状态转移概率矩阵：
\[A=[a_{ij}]_{N\times N}\]其中，\(a_{ij}\)表示由状态\(q_i\)转移到状态\(q_j\)的概率。
设\(B\)是观测概率矩阵：
\[B=[b_j(k)]_{N\times M}\]其中\(b_j(k)\)表示处于状态\(q_j\)的条件下生成观测\(v_k\)的概率。
设\(\pi\)是初始状态概率向量:
\[\pi=\{\pi_i\}\]其中，\(\pi_i\)表示在t=1时模型处于状态\(q_i\)的概率。
根据前文所述，一个隐马尔可夫模型\(\lambda\)可由\(A、B、\pi\)确定，其中，\(\pi\)和\(A\)决定状态序列，\(B\)决定观测序列，所以，\(\lambda\)可以表示为\(\lambda=(A,B,\pi)\)。
三个基本问题
HMM有三个基本问题：
- 概率计算问题。给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=\{o_1,o_2,...,o_T\}\),计算在模型\(\lambda\)下，观测序列\(O\)出现的概率\(P(O\mid\lambda)\)。
- 学习问题。已知观测序列\(O=\{o_1,o_2,...,o_T\}\),估计模型参数\(\lambda=(A,B,\pi)\),使得在该模型下观测序列的概率\(P(O\mid \lambda)\)最大。
- 预测问题，也叫解码问题。已知模型\(\lambda=(A,B,\pi)\)和观测序列\(O=\{o_1,o_2,...,o_T\}\)，求对给定观测序列条件概率\(P(I\mid O)\)最大的状态序列\(I\)。 即根据给定的观测序列，求最有可能的状态序列。
概率计算问题
给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=(o_1,o_2,...,o_T)\)，计算观测序列O出现的概率\(P(O\mid \lambda)\).
直接计算法
概率计算问题最直接的想法就是穷举所有可能的长度为T的状态序列，然后求各个状态序列出现给定观测序列的概率，最后累加求和，就是所得。
状态序列\(I=\{i_1,i_2,...i_T\}\)出现的概率为
\[P(I\mid \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\mid I,\lambda)\),
\[P(O\mid I,\lambda) = b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)\]\(O\)和\(I\)同时出现的联合概率为
\[P(O,I\mid \lambda)=P(I\mid \lambda)P(O\mid I,\lambda)\]然后，对所有可能的状态序列求和，得到观测序列的概率,即
\[P(O\mid \lambda)=\sum_IP(I\mid \lambda)P(O\mid I,\lambda)\]这种直接算法的复杂度达到了\(O(TN^T)\)（长度为T的观测序列，每个可能的状态数有N个，一共可能的状态序列有\(N^T\)个，每个状态序列还要计算一次观测序列出现的概率），所以在计算上一般不采用。
前向算法
定义前向概率
\[a_t(i) = P(o_1,o_2,...,o_t,i_t = q_i\mid \lambda)\]表示在时刻t，观测序列为\(o_1,o_2,...o_t\)且状态为\(q_i\)的概率。
则可以从\(t = 1\)开始递推计算前向概率，直到时刻\(T\)， 然后将时刻\(T\)的各前向概率相加即可得到\(P(O\mid \lambda)\)
算法流程如下：
整个计算过程的路径结构如下：
从图中可以看到，前向计算的复杂度是\(O(TN^2)\)的。
后向算法
定义后向概率
\[\beta(i) = P(o_{t+1},o_{t+2},...,o_T\mid i_t=q_i,\lambda)\]表示在时刻\(t\)，状态为\(q_i\)的条件下，从\(t+1\)到\(T\)的部分观测序列为\(o_{t+1},o_{t+2},...,o_T\)的概率。
则可以从\(t=T\)开始递推向前计算后向概率，直到\(t=1\).
算法流程如下：
递推的路径如下：
同样后向算法的复杂度也是\(O(TN^2)\)。
学习问题
在给定观测序列和状态序列的条件下，学习问题比较简单，只需要统计各个状态转换出现的频数，然后除以总数即可，这是有监督的学习问题。比较复杂的问题是只知道观测序列，如何学习出模型参数，这也叫做非监督的学习问题。
非监督的学习问题其实完全可以用EM算法来解决，而HMM中的Baum-Welch算法本质上也就是EM算法的一个实现，用来解决非监督的学习问题。
算法的具体流程这里就不详细说明了，可以参考《统计学习方法》里关于这一章的讨论。
预测算法
近似算法
近似算法的思想就是，对于每个时刻，计算最有可能出现的状态，以此来得到状态序列的预测。
给定隐马尔可夫模型\(\lambda\)和观测序列\(O\)，在时刻t处于状态\(q_i\)的概率\(\gamma(i)\)为：
\[\gamma(i)= \frac{\alpha_t(i)\beta_t(i)}{\sum^N_{j=1}\alpha_t(j)\beta_t(j)}\]其中\(\alpha\)和\(\beta\)分别代表前向概率和后向概率。
由此得到每个时刻使得\(\gamma\)值最大的状态，从而得到状态序列的估计。
近似算法的优点在于计算简单，但是不能保证序列整体的可能性最大，因为有可能出现相邻两个状态之间的概率实际是0的情况。
维特比算法
维特比算法实际是应用动态规划的方法来计算最有可能的状态序列。
算法的主要思路是从\(t=1\)开始，递推地计算在时刻\(t\)处于状态\(i\)的各个可能路径中概率最大的一条，直到\(t=T\)的时候，然后回溯得到经过的各个状态节点。
其中\(\delta_t(i)\)是t时刻处于状态i的各个路径中概率最大的值，\(\mathit\Psi\)表示概率最大的路径上的第\(t-1\)个节点（也就是上一个节点，用来回溯路径）。
