"> "> 机器学习-隐马尔科夫模型 | Yufei Luo's Blog

Yufei Luo's Blog

But I was so much older then, I am younger than that now.

Yufei Luo's Blog

机器学习-隐马尔科夫模型

发表于 更新于 分类于 ， 阅读次数：
本文字数： 9k 阅读时长 ≈ 8 分钟

基本概念

隐马尔科夫模型（Hidden Markov Model，HMM）是可以用于标注问题的统计学习模型，描述由隐藏的马尔科夫随机链随机生成观测序列的过程。HMM属于生成模型，在语音识别、自然语言处理、生物信息等领域有着广泛的应用。

定义

隐马尔科夫模型是关于时序的概率模型，它描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐马尔科夫链随机生成的状态的序列被称为状态序列；每个状态生成一个观测，由此产生的观测的随机序列被称为观测序列。序列中的每一个位置又可以看作一个时刻。

隐马尔科夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。用数学语言可以描述如下：

设\(Q=\{q_1,q_2,\dots,q_N\}\)是所有可能的状态的集合，\(V=\{v_1,v_2,\dots,v_M\}\)是所有可能的观测的集合。\(I=\{i_1,i_2,\dots,i_T\}\)是长度为\(T\)的状态序列，\(O=\{o_1,o_2,\dots,o_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\)的概率。

隐马尔科夫模型由初始状态概率向量\(\pi\)、状态转移概率矩阵\(A\)和观测概率矩阵\(B\)决定。\(\pi\)和\(A\)决定状态序列，\(B\)决定观测序列。因此一个隐马尔科夫模型\(\lambda\)可以用三元符号表示： \[ \lambda=(A,B,\pi) \] 状态转移矩阵\(A\)和初始状态概率向量\(\pi\)确定了隐藏的马尔科夫链，生成不可观测的状态序列；观测概率矩阵\(B\)确定了如何从状态生成序列，与状态序列总和确定了如何产生观测序列。

从定义可知，隐马尔科夫模型做了两个基本假设：

  1. 齐次马尔科夫性假设：假设隐藏的马尔科夫链在任意时刻\(t\)的状态只依赖于前一时刻的状态，与其他时刻的状态和观测无关，也与时刻\(t\)无关
  2. 观测独立性假设：即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。

隐马尔科夫模型可以用于标注，标注问题指的是给定观测的序列预测其预测的标记序列，此时状态就对应于标记。可以假设标注问题的数据是由隐马尔科夫模型生成的，这样就可以用隐马尔科夫模型的学习与预测算法进行标注。

示例

下面是一个简单的隐马尔科夫模型的例子。我们假设有4个盒子，每个盒子里都装有红白两种颜色的球，盒子里的红白球数量如下表：

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

按照如下办法抽球，从而产生一个球的颜色观测序列：开始时，从4个盒子里面等概率地随机选取一个盒子，从中随机抽取一个球，记录颜色之后放回；然后从当前盒子转移到下一个盒子，如果当前盒子为1，那么下个盒子一定是2，如果当前是盒子2或3，那么分别以概率0.4和0.6转移到左边或者右边的盒子，如果当前为盒子4，那么以各0.5的概率停留在盒子4或者转移到盒子3；确定转移的盒子之后，再从中随机抽取一个球，记录其颜色并放回。如此重复5次，得到一个球的颜色观测序列\(O=\{o_1,o_2,\dots,o_5\}\)。在这一过程中，观察者只能观察到球的颜色序列，观测不到球是从哪个盒子取出的。

在这个例子中有两个随机序列：一个是盒子的序列，即状态序列；另一个是球颜色的序列，即观测序列。前者是隐藏的，只有后者是可观测到的。这个例子便为一个隐马尔科夫模型的例子。根据所给条件，我们可以确定如下的模型三要素：

  • 初始概率分布为\(\pi=(0.25,0.25,0.25,0.25)\)
  • 状态转移概率分布为\(A=\begin{bmatrix}0 & 1 & 0 & 0 \\ 0.4 & 0 & 0.6 & 0 \\0 & 0.4 & 0 & 0.6 \\0 & 0 & 0.5 & 0.5 \end{bmatrix}\)
  • 观测概率分布为\(B=\begin{bmatrix} 0.5 & 0.5 \\ 0.3 & 0.7 \\0.6 & 0.4 \\0.8 & 0.2 \end{bmatrix}\)

观测序列的生成

根据隐马尔科夫模型的定义，一个长度为\(T\)的观测序列\(O=\{o_1,o_2,\dots,o_T\}\)的生成过程如下：

  1. 按照初始状态分布\(\pi\)产生状态\(i_1\)
  2. \(t=1\sim T\)，做如下操作：
    1. 按照状态\(i_t\)的观测概率分布\(b_{i_t}(k)\)生成\(o_t\)
    2. 按照状态\(i_t\)的状态转移概率分布\(\{a_{i_t i_{t+1}}\}\)产生状态\(i_{t+1}\)

基本问题

对于隐马尔科夫模型有3个基本问题：

  1. 概率计算问题：给定模型\(\lambda\)和观测序列\(O\)，计算在模型\(\lambda\)下观测序列\(O\)出现的概率\(P(O|\lambda)\)
  2. 学习问题：已知观测序列\(O\)，估计模型\(\lambda\)的参数，使得在该模型下观测序列概率\(P(O|\lambda)\)最大
  3. 预测问题：也称为解码问题，已知模型\(\lambda\)和观测序列\(O\)，求观测序列\(O\)最有可能对应的状态序列\(I\)

概率计算算法

直接计算法

给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=(o_1,o_2,\dots,o_T)\)，要计算观测序列\(O\)出现的概率\(P(O|\lambda)\)，最直接的办法是按照概率公式直接计算。通过列举所有可能的长度为\(T\)的状态序列\(I\)，求各个状态序列与观测序列\(O\)的联合概率\(P(O,I|\lambda)\)，然后对所有可能的状态序列求和得到\(P(O|\lambda)\)。

状态序列\(I=(i_1,i_2,\dots,i_T)\)的概率是： \[ P(I|\lambda)=\pi_{i_1}a_{i_1 i_2}a_{i_2 i_3}\cdots a_{i_{T-1} i_T} \] 对于固定的状态序列\(I=(i_1,i_2,\dots,i_T)\)，观测序列\(O=(o_1,o_2,\dots,o_T)\)出现的概率为： \[ P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\cdots b_{i_T}(o_T) \] \(O\)和\(I\)同时出现的联合概率为： \[ \begin{aligned} P(O,I|\lambda)=& P(O|I,\lambda)P(I|\lambda) \\ =& \pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2}b_{i_2}(o_2)\cdots a_{i_{T-1} i_T}b_{i_T}(o_T) \end{aligned} \] 但是上述公式的计算量很大，因此不可行。一种有效计算观测序列概率\(P(O|\lambda)\)的算法为前向-后向算法。

前向算法

首先给出前向概率的定义。给定隐马尔科夫模型\(\lambda\)，定义到时刻\(t\)部分观测序列为\(o_1,o_2,\dots,o_t\)且状态为\(q_i\)的概率为前向概率，记为： \[ \alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda) \] 前向概率以及观测序列概率可以通过递推的方式求得：

  1. 计算初值：\(\alpha_1(i)=\pi_i b_i(o_1)\)，\(i=1,2,\dots,N\)。这一步是初始化前向概率，相当于计算初始时刻状态\(i_1=q_i\)和观测\(o_1\)的联合概率
  2. 递推：对于\(t=1,2,\dots,T-1\)，计算\(\alpha_{t+1}(i)=[\sum_{j=1}^{N}\alpha_t(j)a_{ji}]b_i(o_{t+1})\)，\(i=1,2,\dots,N\)。这一步计算时刻\(1\sim t+1\)部分观测序列为\(o_1,o_2,\dots,o_t,o_{t+1}\)且在时刻\(t+1\)处于状态\(q_i\)的前向概率。这一公式代表同时考虑\(t\)时刻所有可能的\(N\)个状态，并对其求和。
  3. 终止：\(P(O|\lambda)=\sum_{i=1}^{N} \alpha_T(i)\)

前向算法实际是基于状态序列的路径结构递推计算\(P(O|\lambda)\)的算法，它高效的关键是局部计算前向概率，然后利用路径结构将前向概率“递推”到全局。这样，每一次计算直接引用前一个时刻的计算结果，从而避免了重复计算。递推的计算流程可以表示为下图：

image-20210914234546383

后向算法

首先给出后向概率的定义。给定隐马尔科夫模型\(\lambda\)，定义在时刻\(t\)状态为\(q_i\)的条件下，从\(t+1\)到\(T\)的部分观测序列为\(o_{t+1},o_{t+2},\dots,o_{T}\)的概率为后向概率，记为 \[ \beta_t(i)=P(o_{t+1},o_{t+2},\dots,o_{T}|i_t=q_i,\lambda) \] 可以用递推的办法求得后向概率\(\beta_t(i)\)以及观测序列概率\(P(O|\lambda)\)。

观测序列概率的后向算法步骤如下：

  1. 初始化：\(\beta_T(i)=1\)，\(i=1,2,\dots,N\)
  2. 对于\(t=T-1,T-2,\dots,1\)，计算\(\beta_t(i)=\sum_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\)，\(i=1,2,\dots,N\)
  3. \(P(O|\lambda)=\sum_{i=1}^{N}\pi_i b_i(o_1)\beta_1(i)\)

后向算法与前向算法的思路基本类似，相当于是前向算法的“镜像”版本。后向概率的递推计算流程如下图：

image-20210914235830617

学习算法

监督学习

假设已给的训练数据包含\(S\)个长度相同的观测序列和对应的状态序列\(\{(O_1,I_1),(O_2,I_2),\dots,(O_S,I_S)\}\)，那么可以用极大似然估计法来估计隐马尔科夫模型的参数。

具体方法为：

  1. 估计转移概率\(a_{ij}\)

    设样本中时刻\(t\)处于状态\(i\)，时刻\(t+1\)处于状态\(j\)的频数为\(A_{ij}\)，那么状态转移概率\(a_{ij}\)的估计值为： \[ \hat{a_{ij}}=\frac{A_{ij}}{\sum_{j=1}^{N}A_{ij}} \]

  2. 观测概率\(b_j(k)\)的估计

    设样本中状态为\(j\)并观测为\(k\)的频数为\(B_{jk}\)，那么状态为\(j\)观测为\(k\)的概率\(b_j(k)\)的估计为： \[ \hat{b}_j(k)=\frac{B_{jk}}{\sum_{k=1}^{M}B_{jk}} \]

  3. 初始状态概率\(\pi_i\)的估计

    \(\hat{\pi}\)为\(S\)个样本中初始状态为\(q_i\)的概率。

Baum-Welch算法

由于监督学习需要使用标注数据，而人工标注训练数据往往代价很高，因此有时候会利用非监督学习的办法。我们假定给定训练数据只包含了\(S\)个长度为\(T\)的观测序列\(\{O_1,O_2,\dots,O_S\}\)，而没有对应的状态序列，目标是学习隐马尔科夫模型\(\lambda=(A,B,\pi)\)的参数。我们将观测序列数据看作是观测数据\(O\)，状态序列数据看作不可观测的隐数据\(I\)，那么隐马尔科夫模型事实上是一个含有隐变量的概率模型 \[ P(O|\lambda)=\sum_{I}P(O|I,\lambda)P(I|\lambda) \] 它的参数学习可以通过EM算法来实现，步骤如下：

  1. 确定完全数据的对数似然函数

    所有观测数据可以写为\(O=\{o_1,o_2,\dots,o_T\}\)，所有隐数据写为\(I=\{i_1,i_2,\dots,i_T\}\)，完全数据为\((O,I)=\{o_1,o_2,\dots,o_T,i_1,i_2,\dots,i_T\}\)，完全数据的对数似然函数为\(\log P(O,I|\lambda)\)

  2. EM算法的E步：求\(Q\)函数\(Q(\lambda,\bar{\lambda})\)（公式中略去了对于\(\lambda\)而言的常数因子\(1/P(O|\bar{\lambda})\)） \[ Q(\lambda,\bar{\lambda})=\sum_{I}P(O,I|\bar{\lambda})\log P(O,I|\lambda) \] 其中\(\bar{\lambda}\)为隐马尔科夫模型参数的当前估计值，\(\lambda\)是要极大化的隐马尔科夫模型参数。

    由于 \[ P(O,I|\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2}b_{i_2}(o_2)\cdots a_{i_{T-1} i_T}b_{i_T}(o_T) \] 因此函数\(Q(\lambda,\bar{\lambda})\)可以写成： \[ Q(\lambda,\bar{\lambda})=\sum_{I}\log \pi_{i_1}P(O,I|\bar{\lambda})+\sum_{I}(\sum_{t=1}^{T-1}\log a_{i_t i_{t+1}})P(O,I|\bar{\lambda})+\sum_{I}(\sum_{t=1}^{T}\log b_{i_t}(o_t))P(O,I|\bar{\lambda}) \]

  3. EM算法的M步：极大化\(Q\)函数，求模型参数\(A\)，\(B\)和\(\pi\)

    由于要极大化的参数在上式中单独出现在3个项中，所以只需要对各项分别做极大化：

    1. 第1项可以写为： \[ \sum_{I}\log \pi_{i_1}P(O,I|\bar{\lambda})=\sum_{i=1}^{N}\log \pi_i P(O,i_1=i|\bar{\lambda}) \] 其中\(\pi_i\)满足约束条件\(\sum_{i=1}^{N}\pi_i=1\)，可以利用拉格朗日乘子法解得： \[ \pi_i=\frac{P(O,i_1=i|\bar{\lambda})}{P(O|\bar{\lambda})} \]

    2. 第2项可以写为： \[ \sum_{I}(\sum_{t=1}^{T-1}\log a_{i_t i_{t+1}})P(O,I|\bar{\lambda})=\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{t=1}^{T-1}\log a_{ij}P(O,i_t=i,i_{t+1}=j|\bar{\lambda}) \] 类似地，使用具有约束条件\(\sum_{j=1}^N a_{ij}=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})} \]

    3. 第3项可以写为： \[ \sum_{I}(\sum_{t=1}^{T}\log b_{i_t}(o_t))P(O,I|\bar{\lambda})=\sum_{j=1}^{N}\sum_{t=1}^{T}\log b_j(o_t)P(O,i_t=j|\bar{\lambda}) \] 同样使用拉格朗日乘子法，约束条件为\(\sum_{k=1}^{M}b_j(k)=1\)。需要注意的是，此时只有在\(o_t=v_k\)时，\(b_j(o_t)\)对\(b_j(k)\)的偏导数才不为0。以\(I(o_t=v_k)\)表示，可得： \[ b_j(k)=\frac{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda})I(o_t=v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda})} \]

    上述公式里面的概率值需要通过前向或者后向公式进行计算。

预测算法

近似算法

近似算法的思想是，在每个时刻\(t\)选择在该时刻最有可能出现的状态\(i_t^*\)，从而得到一个状态序列\(I^*=(i_1^*,i_2^*,\cdots,i_T^*)\)，将它作为预测的结果。

给定隐马尔科夫模型\(\lambda\)和观测序列\(O\)，在时刻\(t\)处于状态\(q_i\)的概率\(\gamma_t(i)\)是： \[ \gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{N}\alpha_t(j)\beta_t(j)} \] 在每一个时刻\(t\)最有可能的状态\(i_t^*\)是： \[ i_t^*=\arg \max_{i\le i\le N}[\gamma_t(i)], t=1,2,\dots,T \] 从而得到状态序列\(I^*=(i_1^*,i_2^*,\cdots,i_T^*)\)。

近似算法的优点是计算简单，其缺点是无法保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。事实上，上述方法得到的状态序列有可能存在转移状态为0的相邻状态。尽管如此，这一算法仍然是有用的。

维特比算法

维特比算法实际是用动态规划算法求解隐马尔科夫预测问题，即使用动态规划求概率最大路径（最优路径）。此时一条路径对应于一个状态序列。

根据动态规划原理，最优路径具有如下特性：如果最优路径为时刻\(t\)通过结点\(i_t^*\)，那么这一路径从结点\(i_t^*\)到终点\(i^*_T\)的部分路径，对于从\(i_t^*\)到\(i^*_T\)的所有可能的部分路径来说，必须是最优的。假如不是这样，那么从\(i_t^*\)到\(i^*_T\)就会有另一条更好的部分路径存在，如果把它和从\(i_1^*\)到\(i^*_t\)的部分路径连接起来，就可以得到一条比原路径更优的路径。

依据这一原理，我们只需要从时刻\(t=1\)开始，递推地计算在时刻\(t\)状态为\(i\)的各条部分路径的最大概率，直至得到时刻\(t=T\)状态为\(i\)的各条路径的最大概率。时刻\(t=T\)的最大概率即为最优路径的概率\(P^*\)，也同时得到了最优路径的终点\(i_T^*\)。之后，为了找出最优路径的各个节点，从终点\(i_T^*\)开始，由后向前逐步求得结点\(i_{T-1}^*,\dots,i_1^*\)，从而得到最优路径\(I^*=(i_1^*,i_2^*,\cdots,i_T^*)\)。

定义\(\delta_t(i)\)为时刻\(t\)状态为\(i\)的所有单个路径\((i_1.i_2,\dots,i_t)\)中概率的最大值，即 \[ \delta_t(i)=\max_{i_1,i_2,\dots,i_{t-1}} P(i_t=i,i_{t-1},\dots,i_1,o_t,\dots,o_1|\lambda),~i=1,2,\dots,N \] 由定义可知\(\delta\)的递推公式： \[ \begin{aligned} \delta_{t+1}(i)=&\max_{i_1,i_2,\dots,i_t} P(i_{t+1}=i,i_t,\dots,i_1,o_{t+1},\dots,o_1|\lambda) \\ =& \max_{1\le j \le N} [\delta_t(j)a_{ji}]b_i(o_{t+1}) ,i=1,2,\dots,N;t=1,2,\dots,T-1 \end{aligned} \] 定义\(\psi_t(i)\)为在时刻\(t\)状态为\(i\)的所有单个路径\((i_1.i_2,\dots,i_t)\)中，概率最大路径的第\(t-1\)个结点： \[ \psi_t(i)=\arg\max_{1\le j \le N} [\delta_{t-1}(j)a_{ji}], i=1,2,\dots,N \] 维特比算法的步骤如下：

  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)=\max_{1\le j \le N} [\delta_{t-1}(j)a_{ji}]b_i(o_t), i=1,2,\dots,N\\ \psi_t(i)=\arg\max_{i\le j\le N}[\delta_{t-1}(j)a_{ji}], i=1,2,\dots,N \]

  3. 终止： \[ P^*=\max_{1\le i \le N}\delta_T(i) \\ i_T^*=\arg \max_{1\le i \le N}[\delta_T(i)] \]

  4. 最优路径回溯：对\(t=T-1,T-2,\dots,1\)， \[ i^*_t=\psi_{t+1}(i^*_{t+1}) \] 从而求得最优路径\(I^*=(i_1^*,i_2^*,\cdots,i_T^*)\)

参考

  1. 统计学习方法，李航
  2. 如何用简单易懂的例子解释隐马尔可夫模型？ - 知乎 (zhihu.com)
  3. 如何通俗地讲解 viterbi 算法？ - 知乎 (zhihu.com)