HMM模型

HMM模型基础

隐马尔科夫模型（Hidden Markov Model，以下简称HMM）是比较经典的机器学习模型了，它在语言识别，自然语言处理，模式识别等领域得到广泛的应用。当然，随着目前深度学习的崛起，尤其是RNN，LSTM等神经网络序列模型的火热，HMM的地位有所下降。但是作为一个经典的模型，学习HMM的模型和对应算法，对我们解决问题建模的能力提高以及算法思路的拓展还是很好的。

什么样的问题需要HMM模型

首先我们来看看什么样的问题解决可以用HMM模型。使用HMM模型时我们的问题一般有这两个特征：１）我们的问题是基于序列的，比如时间序列，或者状态序列。２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了。再举一个，我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。

从这些例子中，我们可以发现，HMM模型可以无处不在。但是上面的描述还不精确，下面我们用精确的数学符号来表述我们的HMM模型。

HMM模型的定义

对于HMM模型，首先我们假设\(Q\)是所有可能的隐藏状态的集合，\(V\)是所有可能的观测状态的集合，即： \[ Q=\left \{ q_1,q_2,...,q_N \right \},V=\left \{ v_1,v_2,...,v_M \right \} \] 其中，\(N\)是可能的隐藏状态数，\(M\)是所有可能的观察状态数。

对于一个长度为\(T\)的序列，\(I\)对应的状态序列, \(O\)是对应的观察序列，即： \[ I=\left \{ i_1,i_2,...,i_T \right \},O=\left \{ o_1,o_2,...,o_T \right \} \] 其中，任意一个隐藏状态\(i_t\in Q\),任意一个观察状态\(o_t\in V\)

HMM模型做了两个很重要的假设如下：

1）齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态，这个我们在MCMC(二)马尔科夫链中有详细讲述。当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个。但是这样假设的好处就是模型简单，便于求解。如果在时刻𝑡的隐藏状态是\(i_t=q_i\),在时刻𝑡+1的隐藏状态是\(i_t+1=q_j\), 则从时刻𝑡到时刻\(t+1\)的HMM状态转移概率\(a_{ij}\)可以表示为： \[ a_{ij}=P(i_{t+1}=q_j|i_t=q_i) \] 这样\(a_{ij}\)可以组成马尔科夫链的状态转移矩阵\(A\): \[ A=\left [ a_{ij} \right ]_{N\times N} \]

2） 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。如果在时刻𝑡的隐藏状态是\(i_t=q_i\), 而对应的观察状态为\(o_t=v_k\), 则该时刻观察状态𝑣𝑘在隐藏状态\(qj\)下生成的概率为\(b_j(k)\),满足： \[ b_j(k)=P(o_t=v_k|i_t=q_j) \] 这样\(b_j(k)\)可以组成观测状态生成的概率矩阵\(B\): \[ B=\left [ b_j(k) \right ]_{N\times M} \] 除此之外，我们需要一组在时刻\(t=1\)的隐藏状态概率分布$$: \[ \prod =\left [ \pi (i) \right ]_N,其中\pi (i)=P(i_1=q_i) \] 一个HMM模型，可以由隐藏状态初始概率分布$\(, 状态转移概率矩阵\)A\(和观测状态概率矩阵\)B\(决定。\)\(,\)A\(决定状态序列，\)B\(决定观测序列。因此，HMM模型可以由一个三元组\)$表示如下： \[\lambda = (A, B, \Pi)\]

一个HMM模型实例

下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型，例子来源于李航的《统计学习方法》。 假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里

盒子	1	2	3
红球数	5	4	7
白球数	5	6	3

按照下面的方法从盒子里抽球，开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列: \[ O=\left \{红,白,红 \right \} \] 注意在这个过程中，观察者只能看到球的颜色序列，却不能看到球是从哪个盒子里取出的。

那么按照我们上一节HMM模型的定义，我们的观察集合是: \[ V=\left \{红,白 \right \}, M=2 \] 我们的集合状态是： \[ Q=\left \{盒子1,盒子2,盒子3 \right \}, N=3 \] 而观察序列和状态序列的长度为3.

初始状态分布为： \[ \prod =\left ( 0.2,0.4,0.4 \right )^T \] 状态转移分布矩阵为： \[ A=\begin{pmatrix} 0.5 & 0.2 &0.3 \\ 0.3&0.5 &0.2 \\ 0.2 &0.3 &0.5 \end{pmatrix} \] 观测状态概率矩阵为 \[ B=\begin{pmatrix} 0.5 &0.5 \\ 0.4&0.6 \\ 0.7&0.3 \end{pmatrix} \]

HMM观测序列的生成

从上一节的例子，我们也可以抽象出HMM观测序列生成的过程。 输入的是HMM的模型\(\lambda = (A, B, \Pi)\),观测序列的长度\(T\) 输出是观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\) 生成的过程如下：

1）根据初始状态概率分布\(\prod\)生成隐藏状态\(i_i\)

2. for t from 1 to T

1. 按照隐藏状态\(i_t\)的观测状态分布\(b_{i_t}\)生成观察状态\(o_t\)
2. 按照隐藏状态𝑖𝑡的状态转移概率分布\(a_{i_t} i_{t+1}\)产生隐藏状态\(i_t+1\) 所有的\(o_t\)一起形成观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\)

HMM模型的三个基本问题

HMM模型一共有三个经典的问题需要解决：

1） 评估观察序列概率。即给定模型\(\lambda = (A, B, \Pi)\)和观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\)，计算在模型𝜆下观测序列𝑂出现的概率\(P(O|\lambda)\)。这个问题的求解需要用到前向后向算法，我们在这个系列的第二篇会详细讲解。这个问题是HMM模型三个问题中最简单的。

2）模型参数学习问题。即给定观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\)，估计模型\(\lambda = (A, B, \Pi)\)的参数，使该模型下观测序列的条件概率𝑃(𝑂|𝜆)最大。这个问题的求解需要用到基于EM算法的鲍姆-韦尔奇算法， 我们在这个系列的第三篇会详细讲解。这个问题是HMM模型三个问题中最复杂的。

3）预测问题，也称为解码问题。即给定模型\(\lambda =(A,B,\Pi)\)和观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\)，求给定观测序列条件下，最可能出现的对应的状态序列，这个问题的求解需要用到基于动态规划的维特比算法，我们在这个系列的第四篇会详细讲解。这个问题是HMM模型三个问题中复杂度居中的算法。

维特比算法解码隐藏状态序列

HMM模型的解码问题最常用的算法是维特比算法，当然也有其他的算法可以求解这个问题。同时维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题，比如之前讲到的文本挖掘的分词原理中我们讲到了单独用维特比算法来做分词。

HMM最可能隐藏状态序列求解概述

在HMM模型的解码问题中，给定模型\(\lambda = (A, B, \Pi)\)和观测序列\(O=\left \{ o_1,o_2,...,o_T \right \}\)，求给定观测序列O条件下，最可能出现的对应的状态序列\(T^*=\left \{i_1^*,i_2^*,...,i_T^* \right \}\),即\(P(I^*|O)\)要最大化。

一个可能的近似解法是求出观测序列𝑂在每个时刻𝑡最可能的隐藏状态\(i_t^*\)然后得到一个近似的隐藏状态序列\(T^*=\left \{i_1^*,i_2^*,...,i_T^* \right \}\)。要这样近似求解不难，利用隐马尔科夫模型HMM前向后向算法评估观察序列概率中的定义：在给定模型\(\lambda\)和观测序列\(O\)时，在时刻𝑡处于状态\(q_i\)的概率是\(\gamma_t(i)\)，这个概率可以通过HMM的前向算法与后向算法计算。这样我们有： \[ i_t^* = arg \max_{1 \leq i \leq N}[\gamma_t(i)], \; t =1,2,...T \] 近似算法很简单，但是却不能保证预测的状态序列是整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。

而维特比算法可以将HMM的状态序列作为一个整体来考虑，避免近似算法的问题，下面我们来看看维特比算法进行HMM解码的方法。

维特比算法概述

维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。在文本挖掘的分词原理中我们已经讲到了维特比算法的一些细节。

既然是动态规划算法，那么就需要找到合适的局部状态，以及局部状态的递推公式。在HMM中，维特比算法定义了两个局部状态用于递推。

第一个局部状态是在时刻𝑡隐藏状态为\(i\)所有可能的状态转移路径\(i_1,i_2,...i_t\)中的概率最大值。记为\(\delta_t(i)\): \[ \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 \] 由\(\delta_t(i)\)的定义可以得到\(\delta\)的递推表达式： \[ \begin{align} \delta_{t+1}(i) & = \max_{i_1,i_2,...i_{t}}\;P(i_{t+1}=i, i_1,i_2,...i_{t},o_{t+1},o_{t},...o_1|\lambda) \\ & = \max_{1 \leq j \leq N}\;[\delta_t(j)a_{ji}]b_i(o_{t+1})\end{align} \] 第二个局部状态由第一个局部状态递推得到。我们定义在时刻𝑡隐藏状态为𝑖的所有单个状态转移路径\((i_1,i_2,...,i_{t-1},i)\)中概率最大的转移路径中第\(t−1\)个节点的隐藏状态为\(\Psi_t(i)\),其递推表达式可以表示为： \[ \Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}] \]

有了这两个局部状态，我们就可以从时刻0一直递推到时刻\(T\)，然后利用\(\Psi_t(i)\)记录的前一个最可能的状态节点回溯，直到找到最优的隐藏状态序列。

维特比算法流程总结

现在我们来总结下维特比算法的流程：

输入：HMM模型\(\lambda = (A, B, \Pi)\)，观测序列\(O=(o_1,o_2,...o_T)\)

输出：最有可能的隐藏状态序列\(I^*= \{i_1^*,i_2^*,...i_T^*\}\)

1）初始化局部状态： \[ \delta_1(i) = \pi_ib_i(o_1),\;i=1,2...N \\ \Psi_1(i)=0,\;i=1,2...N \] 2) 进行动态规划递推时刻\(t=2,3,...T\)时刻的局部状态： \[ \delta_{t}(i) = \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]b_i(0_{t}),\;i=1,2...N \\ \Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}],\;i=1,2...N \] 3) 计算时刻\(T\)最大的\(\delta_t(i)\)，即为最可能隐藏状态序列出现的概率。计算时刻\(T\)最大的\(\Psi_t(i)\)，即为时刻\(T\)最可能的隐藏状态。 \[ P* = \max_{1 \leq j \leq N}\delta_{T}(i) \\ i_T^* = arg \; \max_{1 \leq j \leq N}\;[\delta_{T}(i)] \] 4) 利用局部状态\(\Psi_t(i)\)开始回溯。对于\(t=T-1,T-2,...,1\): \[ i_t^* = \Psi_{t+1}(i_{t+1}^*) \] 最终得到最有可能的隐藏状态序列\(I^*= \{i_1^*,i_2^*,...i_T^*\}\)

HMM维特比算法求解实例

下面我们仍然用HMM模型中盒子与球的例子来看看HMM维特比算法求解。

我们的观察集合是: \[ V=\{红，白\}，M=2 \] 我们的状态集合是: \[ Q =\{盒子1，盒子2，盒子3\}， N=3 \]

而观察序列和状态序列的长度为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) \] 球的颜色的观测序列: \[ O=\{红，白，红\} \] 按照我们上一节的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测状态为1： \[ \delta_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1 \\ \delta_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16 \\ \delta_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28 \\ \Psi_1(1)=\Psi_1(2) =\Psi_1(3) =0 \] 现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2： \[ \delta_2(1) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j1}]b_1(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.5, 0.16 \times 0.3, 0.28\times 0.2] \times 0.5 = 0.028 \\ \Psi_2(1)=3 \\ \delta_2(2) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j2}]b_2(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.2, 0.16 \times 0.5, 0.28\times 0.3] \times 0.6 = 0.0504 \\ \Psi_2(2)=3 \\ \delta_2(3) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j3}]b_3(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.3, 0.16 \times 0.2, 0.28\times 0.5] \times 0.3 = 0.042 \\ \Psi_2(3)=3 \] 继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1： \[ \delta_3(1) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j1}]b_1(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.5, 0.0504 \times 0.3, 0.042\times 0.2] \times 0.5 = 0.00756 \\ \Psi_3(1)=2 \\ \delta_3(2) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j2}]b_2(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.2, 0.0504\times 0.5, 0.042\times 0.3] \times 0.4 = 0.01008 \\ \Psi_3(2)=2 \\ \delta_3(3) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j3}]b_3(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.3, 0.0504 \times 0.2, 0.042\times 0.5] \times 0.7 = 0.0147 \\ \Psi_3(3)=3 \] 此时已经到最后的时刻，我们开始准备回溯。此时最大概率为\(\delta_3(3)\),从而得到\(i_3^* =3\)

由于\(\Psi_3(3)=3\),所以\(i_2^* =3\), 而又由于\(\Psi_2(3)=3\),所以𝑖∗1=3。从而得到最终的最可能的隐藏状态序列为：\((3,3,3)\)

HMM模型维特比算法总结

如果大家看过之前写的文本挖掘的分词原理中的维特比算法，就会发现这两篇之中的维特比算法稍有不同。主要原因是在中文分词时，我们没有观察状态和隐藏状态的区别，只有一种状态。但是维特比算法的核心是定义动态规划的局部状态与局部递推公式，这一点在中文分词维特比算法和HMM的维特比算法是相同的，也是维特比算法的精华所在。

维特比算法也是寻找序列最短路径的一个通用方法，和dijkstra算法有些类似，但是dijkstra算法并没有使用动态规划，而是贪心算法。同时维特比算法仅仅局限于求序列最短路径，而dijkstra算法是通用的求最短路径的方法。