隐马尔科夫模型（Hidden Markov Model，HHM）是一种有向图模型，属于生成式模型，考虑联合概率分布。

HHM有两组变量，第一组是状态变量$I = \{i_1, i_2,....., i_T\}$I={i1​,i2​,.....,iT​}，$i_t$it​表示第t时刻的状态，通常假定状态变量是不可被观测的、隐藏的，这应该也是名字的由来吧；

第二组变量是观测变量，$O = \{o_1, o_2,....,o_T\}$O={o1​,o2​,....,oT​}，$o_t$ot​表示第t时刻的观测值。

为了更好地理解，我们这是假设O是离散变量，并且假定O的取值范围为$V={v_1, v_2,...,v_M}$V=v1​,v2​,...,vM​

还有一个状态I的枚举值，即不同时刻的状态是在$Q=\{q_1, q_2,.....,q_N\}$Q={q1​,q2​,.....,qN​}之间转换的。

一、马尔科夫链

首先，在了解HHM之前，我们需要知道**马尔科夫链：**在任一时刻t，观测变量的取值$o_t$ot​仅依赖于当前的状态变量$i_t$it​，与其他时刻的状态变量及观测变量无关；同时，当前的状态值$i_t$it​仅依赖于前一个时刻的状态$i_{t-1}$it−1​，与状态无关。

如下图：

二、隐马尔科夫模型原理

HHM就是基于这种马尔科夫链的，即基于以上的假设，所以它的联合概率分布为：

$P(o_1,i_1,...,o_T,i_T) = P(i_1)P(o_1|i_1)\prod_{i=2}^T P(i_i|i_{i-1})P(o_i|i_i)$P(o1​,i1​,...,oT​,iT​)=P(i1​)P(o1​∣i1​)i=2∏T​P(ii​∣ii−1​)P(oi​∣ii​)

这就是HHM的模型结构了。一个模型肯定还包含参数，机器学习的本质就是找到一组最优的参数，使得模型的拟合效果最好，HHM也不例外。

那么，HHM的参数包括以下3组：

1. 状态转移概率A：$a_{ij} = P(i_{t+1}=q_j|i_t=q_i), 1<=i,j<=N$aij​=P(it+1​=qj​∣it​=qi​),1<=i,j<=N，即t时刻状态为$q_i$qi​时，t+1时刻状态为$q_j$qj​的概率
2. 输出观测概率B：$b_j(k) = P(o_t=q_k|i_t=q_j), 1<=j<=N,1<=k<=M$bj​(k)=P(ot​=qk​∣it​=qj​),1<=j<=N,1<=k<=M，即t时刻的状态为$q_i$qi​时，观测值为$o_j$oj​的概率
3. 初设状态概率$\pi_i$πi​：$\pi = (\pi_1, \pi_2,...,\pi_N), 1<=i<=N$π=(π1​,π2​,...,πN​),1<=i<=N，即初设时刻各状态出现的概率。

那么，给定一个隐马尔科夫模型，它产生观测序列的步骤如下$\{o_1, o_2,....,o_T\}${o1​,o2​,....,oT​}：

(1) 当t = 1时，根据初设状态概率$\pi$π选择初设状态$i_1$i1​；

(2) 根据状态$i_t$it​和输出观测概率B选择观测值$o_t$ot​；

(3) 根据状态$i_t$it​和状态转移概率A确定$i_{t+1}$it+1​；

(4) 当t < T，令t = t + 1，并跳转至第2步，否则终止，观测序列已全部生产完毕。

三个基本问题

1. 概率计算问题。给定模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O = \{o_1, o_2,....,o_T\}$O={o1​,o2​,....,oT​}，计算观测序列O出现的概率$P(O|\lambda)$P(O∣λ)
2. 学习问题。已知观测序列$O = \{o_1, o_2,....,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,....,o_T\}$O={o1​,o2​,....,oT​}，求对给定观测序列条件概率P(I|O)最大的隐藏状态$I = \{i_1, i_2,....., i_T\}$I={i1​,i2​,.....,iT​}

三、概率计算

1. 前向算法

给定隐马尔科夫模型$\lambda$λ，至时刻t的观测序列为$\{o_1, o_2,....,o_t\}${o1​,o2​,....,ot​}，且状态为$q_i$qi​的概率为前向概率：

$\alpha_t(i)=P(o_1, o_2,....,o_t,i_t=q_i|\lambda)$αt​(i)=P(o1​,o2​,....,ot​,it​=qi​∣λ)

我们可以通过递推的方式求得前向概率$\alpha_t(i)$αt​(i)及观测序列概率$P(O|\lambda)$P(O∣λ)，具体的算法步骤如下：

(1) 时刻t=1，$\alpha_1(i)=\pi_ib_i(o_1),i=1,2,...,N$α1​(i)=πi​bi​(o1​),i=1,2,...,N

(2) 对于时刻$t=1,2,...,T-1$t=1,2,...,T−1：

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

(3) $P(O|\lambda)=\sum^N_{i=1}\alpha_T(i)$P(O∣λ)=∑i=1N​αT​(i)

2. 后向算法

给定隐马尔科夫模型$\lambda$λ，满足时刻t的状态为$q_i$qi​的条件下，从时刻t+1到T的观测序列为$\{o_{t+1}, o_{t+2},....,o_T\}${ot+1​,ot+2​,....,oT​}的概率为后向概率：

$\beta_t(i)=P(o_{t+1}, o_{t+2},....,o_T|i_t=q_i,\lambda)$βt​(i)=P(ot+1​,ot+2​,....,oT​∣it​=qi​,λ)

我们同样可以通过递推的方式求得前向概率$\beta_t(i)$βt​(i)及观测序列概率$P(O|\lambda)$P(O∣λ)，具体的算法步骤如下：

(1) 对于最后时刻T，规定$\beta_T(i)=1$βT​(i)=1

(2) 对于时刻t=T-1, T-2, … , 1：

$\beta_t(i)=\sum^N_{j=1}a_{ij}b_j(o_{t+1})\beta_{t+1}(j), i=1,2,...,N$βt​(i)=∑j=1N​aij​bj​(ot+1​)βt+1​(j),i=1,2,...,N

(3) $P(O|\lambda)=\sum^N_{i=1}\pi_ib_i(o_1)\beta_1(i)$P(O∣λ)=∑i=1N​πi​bi​(o1​)β1​(i)

这里我们可以这里理解 ：$\beta_1(i)$β1​(i)表示时刻t=1的状态为$q_1$q1​时，从时刻t=2到T的观测序列为$\{o_{2}, o_{3},....,o_T\}${o2​,o3​,....,oT​}的概率，$\pi_ib_i(o_1)$πi​bi​(o1​)当然就是时刻t=1的状态为$q_1$q1​的概率了，那么$\pi_ib_i(o_1)\beta_1(i)$πi​bi​(o1​)β1​(i)也就是时刻t=1的状态为$q_1$q1​的条件下的条件概率了。

但是观测序列概率是没有限定观测序列的状态取值的，所以，要把所有状态下的观测序列概率累加起来才是最后的观测序列概率，即上式。

这里跟上面的前向算法求得的观测序列概率的思想是类似的。

3. 常用的概率计算

1. 根据已知的隐马尔科夫模型$\lambda$λ和观测序列O，在时刻 t 处于状态$q_i$qi​的概率：

   $\gamma_t(i)=P(i_t=q_i|O,\lambda)$γt​(i)=P(it​=qi​∣O,λ)

   并且，根据条件概率的公式进行推导可知：

   $\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}$γt​(i)=P(it​=qi​∣O,λ)=P(O∣λ)P(it​=qi​,O∣λ)​

   再结合前向和后向概率，可得到：

   $P(i_t=q_i,O|\lambda)=\alpha_t(i)\beta_t(i)$P(it​=qi​,O∣λ)=αt​(i)βt​(i)

   （这里多琢磨几遍前向概率和后向概率的定义，就可以理解为什么了）

   则：

   $\gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum^N_{j=1}\alpha_t(j)\beta_t(j)}$γt​(i)=P(O∣λ)αt​(i)βt​(i)​=∑j=1N​αt​(j)βt​(j)αt​(i)βt​(i)​

   （分母的转换是这么理解：在已知$\lambda$λ的情况下，观测序列为O时，状态可以为任何一种状态，那么每一种状态下观测序列为O的概率累加，就是观测序列的概率了）

2. 根据已知的隐马尔科夫模型$\lambda$λ和观测序列O，在时刻 t 处于状态$q_i$qi​，并且在时刻t+1处于状态$q_j$qj​的概率：

   $\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)$ξt​(i,j)=P(it​=qi​,it+1​=qj​∣O,λ)

   跟上面的思路一致：

   $\xi_t(i,j)=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{P(O|\lambda)}=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{\sum^N_{i=1}\sum^N_{j=1}P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}$ξt​(i,j)=P(O∣λ)P(it​=qi​,it+1​=qj​,O∣λ)​=∑i=1N​∑j=1N​P(it​=qi​,it+1​=qj​,O∣λ)P(it​=qi​,it+1​=qj​,O∣λ)​

   $P(i_t=q_i,i_{t+1}=q_j,O|\lambda)=\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$P(it​=qi​,it+1​=qj​,O∣λ)=αt​(i)aij​bj​(ot+1​)βt+1​(j)

三、实际应用

可能看了上面隐马尔科夫模型的原理之后，很多人都有点懵，不知道能用来做什么？

我们举个例子：中文分词。

“我们是中国人”，这一句话分词之后应该是这样的：我(B)们(E)|是(O)|中(B)国(M)人(E)。

各个标签的含义——B：单词的第一个字，M：单词的中间字，E：单词的最后一个字，O：仅有一个字组成的词。

将隐马尔科夫模型应用到分词中，那么观测序列对应的是文本句子，隐藏状态对应则的是句子中每个字的标签。

四、模型训练(学习)

上面我们提到了，HHM的参数有三组${A,B,\pi}$A,B,π，那么如何确定最优的参数呢？

1. 监督学习

当我们的样本数据是带有标签时，即训练数据包含观测序列以及对应的状态，我们就可以通过极大似然法来估计HHM的参数，计算方法如下：

(1) 状态转移概率A: $\hat{a}_{ij} = \frac{A_{ij}}{\sum_{k=1}^NA_{ik}},1<=i,j<=N$a^ij​=∑k=1N​Aik​Aij​​,1<=i,j<=N

$A_{ij}$Aij​表示样本中时刻t处于状态$q_i$qi​转移到时刻t+1处于状态$q_j$qj​的频次。

如上面分词的例子，$A_{ij}$Aij​可以理解为当前这个字的标签为$q_i$qi​(假如为B)，下一个词的标签为$q_j$qj​（假如为E）的频次。

(2) 输出观测概率B：$\hat{b}_{ij} = \frac{B_{ij}}{\sum_{k=1}^NB_{ik}},1<=i<=N,1<=j<=M$b^ij​=∑k=1N​Bik​Bij​​,1<=i<=N,1<=j<=M

$B_{ij}$Bij​表示样本中t时刻的状态为$q_i$qi​时，观测值为$o_j$oj​的频次。

如当前的字为$o_j$oj​（假如为"我"），标签为$q_i$qi​（假如为B）的频次。

(3) 初设状态概率$\pi$π：$\hat{\pi}_i$π^i​为初设状态为$q_i$qi​的频率。

2. Baum-Welch算法

如果样本数据时没有带标签的，即训练数据只包含观测序列O，但对应的状态$I$I未知。

那此时的隐马尔科夫模型是一个含有隐变量的概率模型：

$P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)$P(O∣λ)=∑I​P(O∣I,λ)P(I∣λ)

它的参数学习可以由Baum-Welch算法实现，本质还是EM。EM的基本思想是先将参数的初设估计值加入到似然函数Q中，然后对Q进行极大化（一般就是求导，令其等于0），得到新的参数估计值，一直重复，直到收敛。

此时，对数似然函数是$logP(O,I|\lambda)$logP(O,I∣λ)

(1) EM算法的E步：求Q函数：

$Q(\lambda,\bar{\lambda})=\sum_IlogP(O,I|\lambda)P(O,I|\bar{\lambda})$Q(λ,λˉ)=∑I​logP(O,I∣λ)P(O,I∣λˉ)

$\lambda$λ是要极大化的隐马尔科夫模型的参数，$\bar{\lambda}$λˉ是参数的当前估计值。

因为$P(O,I|\lambda)=\pi_{i1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}...a_{i_{T-1}i_T}b_{i_T}(o_T)$P(O,I∣λ)=πi1​bi1​​(o1​)ai1​i2​​bi2​​...aiT−1​iT​​biT​​(oT​)

因此$Q(\lambda,\bar{\lambda})=\sum_Ilog\pi_{i_1}P(O,I|\bar{\lambda})+\sum_I\left(\sum^{T-1}_{t=1}log\alpha_{i_ti_{t+1}}\right)P(O,I|\bar{\lambda})+\sum_I\left(\sum^T_{t=1}logb_{i_t}(o_t)\right)P(O,I|\bar{\lambda})$Q(λ,λˉ)=∑I​logπi1​​P(O,I∣λˉ)+∑I​(∑t=1T−1​logαit​it+1​​)P(O,I∣λˉ)+∑I​(∑t=1T​logbit​​(ot​))P(O,I∣λˉ)

(2) EM算法的M步：极大化Q函数，得到新的参数估计值$A,B,\lambda$A,B,λ

由于三个参数单独出现在Q函数的3个项中，那么我们可以对各项分别极大化。

a. 首先是第1项求$\lambda$λ：

$\sum_Ilog\pi_{i_1}P(O,I|\bar{\lambda})=\sum^N_{i=1}log\pi_iP(O,i_1=i|\bar{\lambda})$∑I​logπi1​​P(O,I∣λˉ)=∑i=1N​logπi​P(O,i1​=i∣λˉ)

为什么这个等式成立呢？因为当隐马尔科夫模型的参数确定后，时刻t=1的状态$i_1$i1​确定了，那么O和$I$I都能确定，这里是把$i_1$i1​的所有独立事件概率加起来

$\pi_i$πi​满足约束条件$\sum^N_{i=1}\pi=1$∑i=1N​π=1，可以利用拉格朗日乘子法，拉格朗日函数为：

$\sum^N_{i=1}log\pi_iP(O,i_1=i|\bar{\lambda})+\gamma\left(\sum^N_{i=1}\pi_i-1\right)$∑i=1N​logπi​P(O,i1​=i∣λˉ)+γ(∑i=1N​πi​−1)

求偏导并令其等于0：

$\frac{\partial}{\partial \pi_i}\left[\sum^N_{i=1}log\pi_iP(O,i_1=i|\bar{\lambda})+\gamma\left(\sum^N_{i=1}\pi_i-1\right)\right]=0$∂πi​∂​[∑i=1N​logπi​P(O,i1​=i∣λˉ)+γ(∑i=1N​πi​−1)]=0

得到：$P(O,i_1=i|\bar{\lambda})+\gamma\pi_i=0$P(O,i1​=i∣λˉ)+γπi​=0

对所有i求和，得到：$\gamma=-P(O|\bar{\lambda})$γ=−P(O∣λˉ)

因为$i_1\in(1,2,...,N)$i1​∈(1,2,...,N)，所以$P(O,i_1=i|\bar{\lambda})$P(O,i1​=i∣λˉ)中按$i$i从1到N累计起来其实就等于$P(O|\bar{\lambda})$P(O∣λˉ)

最终，$\pi_i=\frac{P(O,i_1=i|\bar{\lambda})}{P(O|\bar{\lambda})}$πi​=P(O∣λˉ)P(O,i1​=i∣λˉ)​

b. Q函数的第2项求a：

$\sum_I\left(\sum^{T-1}_{t=1}log\alpha_{i_ti_{t+1}}\right)P(O,I|\bar{\lambda})=\sum^N_{i=1}\sum^N_{j=1}\sum^{T-1}_{t=1}a_{ij}P(O,i_t=i,i_{t+1}=j|\bar{\lambda})$∑I​(∑t=1T−1​logαit​it+1​​)P(O,I∣λˉ)=∑i=1N​∑j=1N​∑t=1T−1​aij​P(O,it​=i,it+1​=j∣λˉ)

同样存在约束条件：$\sum^N_{j=1}a_{ij}=1$∑j=1N​aij​=1，类似上面的做法，可以求得：

$a_{ij}=\frac{\sum^{T-1}_{t=1}P(O,i_t=i,i_{t+1}=j|\bar{\lambda})}{\sum^{T-1}_{t=1}P(O,i_t=i)|\bar{\lambda}}$aij​=∑t=1T−1​P(O,it​=i)∣λˉ∑t=1T−1​P(O,it​=i,it+1​=j∣λˉ)​

c. Q函数的第3项求b：

$\sum_I\left(\sum^T_{t=1}logb_{i_t}(o_t)\right)P(O,I|\bar{\lambda})=\sum^N_{j=1}\sum^T_{t=1}logb_j(o_t)_iP(O,i_t=j|\bar{\lambda})$∑I​(∑t=1T​logbit​​(ot​))P(O,I∣λˉ)=∑j=1N​∑t=1T​logbj​(ot​)i​P(O,it​=j∣λˉ)

约束条件：$\sum^M_{k=1}b_j(k)=1$∑k=1M​bj​(k)=1，这里需要注意只有当$o_t=v_k$ot​=vk​时$b_j(o_t)$bj​(ot​)对$b_j(k)$bj​(k)的偏导数才不等于0，用$I(o_t=v_k)$I(ot​=vk​)表示，求得：

$b_j(k)=\frac{\sum^T_{t=1}P(O,i_t=j|\bar{\lambda})I(o_t=v_k)}{\sum^T_{t=1}P(O,i_t=j|\bar{\lambda})}$bj​(k)=∑t=1T​P(O,it​=j∣λˉ)∑t=1T​P(O,it​=j∣λˉ)I(ot​=vk​)​

(3) 最后，用上面的概率表示：

$a_{ij}=\frac{\sum^{T-1}_{t=1}\xi_t(i,j)}{\sum^{T-1}_{t=1}\gamma_t(i)}$aij​=∑t=1T−1​γt​(i)∑t=1T−1​ξt​(i,j)​

$b_j(k)=\frac{\sum^T_{t=1,o_t=v_k}\gamma_t(j)}{\sum^T_{t=1}\gamma_t(j)}$bj​(k)=∑t=1T​γt​(j)∑t=1,ot​=vk​T​γt​(j)​

$\pi_i=\gamma_1(i)$πi​=γ1​(i)

五、模型预测

那么，通过训练，我们得到了最优的参数，也相当于我们得到了一个拟合效果最好的隐马尔科夫模型，此时我们如何预测观测序列的状态呢？即给定隐马尔科夫模型$\lambda=[A,B,\pi]$λ=[A,B,π]，如何通过观测序列来推断对应的隐藏状态。

举个例子：例如我们这个模型用于语音识别中，那么观测序列就是语音了，隐藏状态即为文字。语音识别的作用就是将语音转化为对应的文字，那如果隐马尔科夫模型通过观测序列得到隐藏状态，不就是将语音转化为文字了。

这个时候就需要使用到维特比(Viterbi)算法，在这篇博客中有详细介绍。但在隐马尔科夫模型中需要稍作调整，下面我给出书上的一个例子。

维特比(Viterbi)算法