隐马尔科夫模型(HMM)

模型定义

隐马尔科夫模型是关于时序的模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态序列，再由各个状态随机生成一个观测从而产生观测序列的过程。其中涉及的关键概念包括以下两个：

• 状态序列：由隐藏的马尔科夫链随机生成的不可见的状态的序列

• 观测序列：状态序列中的每个不可见的状态都会生成一个可见的观测，而由此产生的观测的随机序列，就叫做观测序列。

而一个隐马尔科夫模型实际是由__初始概率分布、状态转移概率分布和观测概率分布__确定的。

设$Q=\{q_{1},q_{2},\dots,q_{N}\}$Q={q1​,q2​,…,qN​}是所有可能的隐藏状态的集合，$V=\{v_{1},v_{2}.\dots,v_{M} \}$V={v1​,v2​.…,vM​}是所有可能的观测的集合。$I=(i_{1},i_{2},\dots,i_{T})$I=(i1​,i2​,…,iT​)是长度为$T$T的状态序列，$O=(o_{1},o_{2},\dotso_{T})$O=(o1​,o2​,…T​)为对应的观测序列：

• 初始概率分布向量$\pi=(\pi_{j})$π=(πj​)：$\pi_{j}$πj​表示状态序列中$t=1$t=1时刻取值为$q_{j}$qj​的概率，初始概率分布向量中的每个元素表示的是时刻$t=1$t=1时一种取值的出现概率。

  $\pi_{j}=P(i_{1}=q_{j})$πj​=P(i1​=qj​)

• 状态转移概率矩阵$A=[a_{ij}]_{N\times N}$A=[aij​]N×N​：$N$N为隐藏状态数，其中的每个元素$a_{ij}$aij​表示的是每个时刻的状态$q_{i}$qi​转移到下一时刻的状态$q_{j}$qj​的概率

  $a_{ij}=P(i_{t+1}=q_{j} | i_{t}=q_{i}), \quad i = 1,2,\dots,N; \quad j=1,2,\dots,N$aij​=P(it+1​=qj​∣it​=qi​),i=1,2,…,N;j=1,2,…,N

• 观测概率矩阵$B=[b_{j}(k)]_{N\times M}$B=[bj​(k)]N×M​：$N$N为隐藏状态数，$M$M为观测状态数。其中的每个元素$b_{j}(k)$bj​(k)表示的是每个时刻处于状态$q_{j}$qj​时，生成观测$v_{k}$vk​的概率

  $b_{j}(k)=P(o_{t}=v_{k}|i_{t}=q_{j}), \quad k=1,2,\dots,M; \quad j=1,2,\dots,N$bj​(k)=P(ot​=vk​∣it​=qj​),k=1,2,…,M;j=1,2,…,N

由以上定义可知吗，其实马尔科夫模型是基于两个基本假设的：

• 齐次马尔科夫假设：假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态和观测序列无关，也与时刻$t$t无关。

  $P(i_{t}|i_{t-1},o_{t-1},\dots,i_{1},o_{1})=P(i_{t}|i_{t-1}), \quad t=1,2,\dots,T$P(it​∣it−1​,ot−1​,…,i1​,o1​)=P(it​∣it−1​),t=1,2,…,T

• 观测独立性假设：假设任意时刻的观测值依赖于该时刻的马尔科夫链的隐藏状态，与其他观测和状态无关。

  $P(o_{t}|i_{T},o_{T},i_{T-1},o_{T-1},\dots,i_{t+1},o_{t+1},i_{t-1},o_{t-1},\dots,i_{1},o_{1})=P(o_{t}|i_{t})$P(ot​∣iT​,oT​,iT−1​,oT−1​,…,it+1​,ot+1​,it−1​,ot−1​,…,i1​,o1​)=P(ot​∣it​)

以上讲了一堆概念和假设，我相信第一次接触隐马模型的同学应该不太能完全理解(反正我当时就是云里雾里的……)。那么如何更直观的将这些概念和假设串联在一起来理解隐马模型呢，其实看下面这个图就够了

​ 由这个图中可知，观测序列的元素之间是互不影响的，它们只受对应时刻的状态序列中的元素影响，每个状态序列中的状态值对应每个观测序列中的观测值都有一个转移概率$P(o_{t}|i_{t})$P(ot​∣it​)。而状态序列中的每个元素都只受其前一时刻元素的影响，状态序列中的每个元素对应其他元素都有一个转移概率$P(i_{t} |i_{t-1})$P(it​∣it−1​)。

​ 以基于字标注法的中文分词问题为例，其中的标注集为$\{S,B,M,E\}${S,B,M,E}，当观测序列为句子今天你学习了吗，对应的状态序列为BESBESS，对于分词问题，观测序列显然是可见的，而状态序列是需要预测当前不可见的。这个例子中，初始概率值为$P(i_{i}='B')$P(ii​=′B′)，今和天对应的状态转移概率值为$P(i_{2}='天'|i_{1}='今')$P(i2​=′天′∣i1​=′今′)，今和对应的状态B之间的观测概率为$P(o_{1}='今'|i_{1}='B')$P(o1​=′今′∣i1​=′B′)。其他时刻的状态转移概率值和观测概率值都类似，不再赘述。最后要求的就是对应观测序列概率最大的状态序列，即是我们要求的分词标注序列。这也是隐马模型中的三大基本问题之一的预测问题。

隐马尔科夫模型的三个基本问题

1. 概率计算问题：给定模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_{1},o_{2},\cdots,o_{T})$O=(o1​,o2​,⋯,oT​)，计算在模型$\lambda$λ下观测序列$O$O出现的概率$P(O|\lambda)$P(O∣λ)
2. 学习问题：已知观测序列$O=(o_{1},o_{2},\cdots,o_{T})$O=(o1​,o2​,⋯,oT​)，估计模型$\lambda=(A,B,\pi)$λ=(A,B,π)的参数，使得在该模型下观测序列概率$P(O|\lambda)$P(O∣λ)最大。即用极大似然估计的方法来估计参数。
3. 预测问题：也成为解码问题。已知模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_{1},o_{2},\cdots,o_{T})$O=(o1​,o2​,⋯,oT​)，求对给定观测序列条件概率$P(I|O)$P(I∣O)最大的状态序列$I=(i_{1},i_{2},\cdots,i_{T})$I=(i1​,i2​,⋯,iT​)。即给定观测序列，求最有可能的对应的状态序列。上一节举的词性标注的例子，就是一种很典型的预测问题。

接下来就分别总结一下这三种问题的解决算法。

概率计算算法

​ 概率计算算法要解决的问题是当给定模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_{1},o_{2},\cdots,o_{T})$O=(o1​,o2​,⋯,oT​)，计算在模型$\lambda$λ下观测序列$O$O出现的概率$P(O|\lambda)$P(O∣λ)。一般可行的计算算法包括前向和后向算法两种。前向算法是从初始位置开始计算概率，而后向概率是从序列末尾开始计算概率的。

前向概率

​ 首先给出前向概率的定义，在给定隐马尔可夫模型$\lambda$λ的前提下，定义到时刻$t$t部分观测序列为$o_{1},o_{2},\cdots,o_{t}$o1​,o2​,⋯,ot​且状态为$q_{i}$qi​的概率为前向概率，记作：

$\alpha_{t}(i)=P(o_{1},o_{2},\cdots,o_{t},i_{t}=q_{i}|\lambda)$αt​(i)=P(o1​,o2​,⋯,ot​,it​=qi​∣λ)

​

​ 前向算法计算$P(O|\lambda)$P(O∣λ)的流程：

1. 初始化：$t=1$t=1时刻各种可能状态得到观测值$o_{1}$o1​的概率

   ​ $\alpha_{1}(i)=\pi_{i}b_{i}(o_{1}), \quad i=1,2,\cdots,N$α1​(i)=πi​bi​(o1​),i=1,2,⋯,N

2. 递推：

   $\alpha_{t+1}(i)=\left [ \sum_{j=1}^{N}\alpha_{t}(j)a_{ji} \right ] b_{i}(o_{t+1}), \quad i=1,2,\cdots,N$αt+1​(i)=[j=1∑N​αt​(j)aji​]bi​(ot+1​),i=1,2,⋯,N

   前面已经提到过齐次马尔科夫假设，要计算$t+1$t+1时刻的概率，只需要考虑$t$t时刻的状态，而$t$t时刻的状态有$N$N种取值，每种状态取值对应到$t+1$t+1时刻的状态都有一个转移概率。由概率论的知识可知，要计算$t+1$t+1时刻状态取值为$q_{i}$qi​的概率需要将这$N$N种情况对应的概率相加，图示如下图：

   

   另外好需要注意的是每个$\alpha_{t}(i)$αt​(i)对应计算的都是当前观测序列出现的概率，所以最后一定要乘以$b_{i}(o_{t})$bi​(ot​)

3. 终止：终止时，将序列末尾的各种状态取值情况下得到最终观测的概率相加，即可得观测序列出现的概率。

   ​ $P(O|\lambda)= \sum_{i=1}^{N}\alpha_{T}(i)$P(O∣λ)=i=1∑N​αT​(i)

后向概率

​ 后向概率是从观测序列的末尾开始计算的，初始状态假设末尾的概率为1，再从后往前计算，其实思想与前向算法是一致的，不再赘述，有兴趣的去翻李航老师的书吧。

学习算法

​ 学习算法要考虑的问题是如何在给定了训练数据的情况下，得到隐马尔可夫模型中的初始概率分布向量$\pi$π、状态转移概率矩阵$A$A和观测概率矩阵$B$B的值。根据训练数据是否包括状态序列，学习算法又可以分为以下两种：

• 监督学习：训练数据包含了观测序列和其对应的状态序列
• 无监督学习：训练数据只包含了观测数据，而不包括对应的状态序列

监督学习

​ 监督学习的方法其实就是基于大数定理，用频度来近似估计概率值。假设给定训练数据集包含了$S$S个长度相同的观测序列和对应的状态序列$\{(O_{1},I_{1}),(O_{2},I_{2}),\cdots,(O_{S},I_{S}) \}${(O1​,I1​),(O2​,I2​),⋯,(OS​,IS​)}，那么利用极大似然估计法来估计隐马尔可夫模型中的参数的方法如下：

1. 首先根据训练数据集，得到初始状态频数向量$\widehat{\pi}$π、状态转移频数矩阵和$\widehat{A}$A和观测频数矩阵$\widehat{B}$B：

   • 初始状态频数向量中每个元素表示的是某个状态作为状态序列的起始的次数。以上述的中文分词的例子来说，就是训练集中每一句话的开头状态分别是$S,B,M,E$S,B,M,E的次数，这里会得到一个四维的初始状态频数向量。
   • 状态转移频数矩阵中的每个元素$a_{ij}$aij​表示的是训练集中从$t-1$t−1时刻的状态$q_{i}$qi​转移到$t$t时刻的状态$q_{j}$qj​的次数，$t$t可以为任意值。同样以上述中文分词的例子来说，如果给定的状态集合是$\{ S,B,M,E\}${S,B,M,E}，则由观测序列今天你学习了吗和对应的状态序列BESBESS，我们可以得到的如$B$B到$E$E的频数为$a_{1,3}=2$a1,3​=2。
   • 观测频数矩阵中的每个元素$b_{j}(k)$bj​(k)表示的是$t$t时刻由状态$q_{j}$qj​生成其对应观测$v_{k}$vk​的频数。同样以上个例子来说，我们可以得到状态B到对应观测今的频数为1

2. 然后根据得到的频数矩阵或向量，得到对应的概率分布：每次都是先算每一行的总数，然后用每种情况对应的频数和总数相除得到对应的概率分布

   • 初始状态概率分布向量的估计：

     ​ $\pi_{i}=\frac{\widehat{\pi}_{i}}{\sum_{k=1}^{N}\widehat{\pi}_{i}}$πi​=∑k=1N​πi​πi​​

   • 状态转移概率分布矩阵的估计：

     $a_{ij}=\frac{\widehat{a}_{ij}}{\sum_{k=1}^{N}\widehat{a}_{ik}}$aij​=∑k=1N​aik​aij​​

   • 观测概率矩阵的估计：

     $b_{j}(k)=\frac{\widehat{b}_{jk}}{\sum_{s=1}^{M}\widehat{b}_{js}}$bj​(k)=∑s=1M​bjs​bjk​​

无监督学习——Baum-Welch算法

​ 这一部分还没看，等看完了EM算法再来补充吧(学习路漫漫啊)

预测算法

​ 预测算法主要解决在已知模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_{1},o_{2},\cdots,o_{T})$O=(o1​,o2​,⋯,oT​)的情况下，求对给定观测序列条件概率$P(I|O)$P(I∣O)最大的状态序列$I=(i_{1},i_{2},\cdots,i_{T})$I=(i1​,i2​,⋯,iT​)。即给定观测序列，求最有可能的对应的状态序列。近似算法和维特比算法都可以用来解决这个问题。

近似算法

​ 近似算法实际算是一种贪心算法，每次都是取当前最优即可。近似算法的基本思想是，在每个时刻$t$t选择当前时刻最有可能出现的状态$i_{t}^{*}$it∗​，从而得到一个状态序列$I^{*}=(i^{*}_{1},i^{*}_{2},\cdots,i^{*}_{T})$I∗=(i1∗​,i2∗​,⋯,iT∗​)，这种算法很明显只考虑了当前的局部最优，最终得到的状态序列并不一定是全局最优的，但它的优点是计算足够简单。

维特比算法

​ 维特比算法实际用的是动态规划的思想来解决隐马模型中的预测问题，即用动态规划求概率最大路径，这时一条路径对应一个状态序列。

​ 根据动态规划原理，最优路径应该具有这样的特性：如果最优路径在时刻$t$t经过节点$i^{*}_{t}$it∗​，那么从节点$i^{*}_{1}$i1∗​到节点$i^{*}_{t}$it∗​的部分路径，对于所有可能的路径必须是最优的。因为如果不是局部最优的，那么在$i^{*}_{1}$i1∗​和$i^{*}_{t}$it∗​之间必然存在至少一条更优的路径，如果把这部分路径和从$i^{*}_{t}$it∗​到$i^{*}_{T}$iT∗​的路径连接起来，会得到一条比当前路径更好的路径。

​ 依据以上的原理，我们只需要从时刻$t=1$t=1开始，递推的计算在时刻$t$t状态为$i$i的各部分路径的最大概率，直至得到时刻$t=T$t=T状态为$i$i的各条路径的最大概率，即可得所求的最大概率的状态序列。在$t$t时刻，我们需要记录下能使当前概率最大的$t-1$t−1时刻的状态，依次递推，在$t=T$t=T时刻进行回溯，即可得到最大概率对应的最优路径，路径上的每个节点表示当前时刻的状态取值。

​ 在具体实现上，维特比算法需要维护两个矩阵：

• 一个是__概率矩阵$A=[a_{ij}]_{N\times T}$A=[aij​]N×T​：__其中的每个元素$a_{ij}$aij​表示$t=j$t=j时刻状态为$q_{i}$qi​的最优路径对应的概率
• 一个是__路径矩阵$B=[b_{ij}]_{N\times T}$B=[bij​]N×T​：__其中的每个元素$b_{ij}$bij​表示$t=j$t=j时刻状态为$q_{i}$qi​对应的最大路径中$t-1$t−1时刻的状态取值

​ 更多的信息可以参考大佬的博客数学之美：维特比和维特比算法，我觉得写得比较好。