隐马尔可夫模型

Posted on

隐马尔可夫模型

概率图模型大致分为两类：

  • 第一类使用有向无环图表示变量之间的关系，称为有向图模型或贝叶斯网；
  • 第二类使用无向图表示变量间的相关关系，称为无向图模型或马尔可夫网。

隐马尔可夫模型（Hidden Markov Model，HMM）是结构最简单的d动态贝叶斯网，可用于标注问题的统计学习模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于生成模型。

1. 基本概念

1.1. 定义

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

隐马尔可夫模型的确定：

  1. 初始概率分布；
  2. 状态转移概率分布；
  3. 观测概率分布。

设\(Q\)是所有可能的状态的集合，\(V\)是所有可能的观测的集合： \[Q = \{q_1, q_2, \cdots, q_N\}, \quad V = \{v_1, v_2, \cdots, v_M\}\] 其中\(N\)是可能的状态数，\(M\)是可能的观测数。

\(I\)是长度为\(T\)的状态序列，\(O\)是对应的观测序列： \[I = \{i_1, i_2, \cdots, i_T\}, \quad O=\{o_1, o_2, \cdots, o_T\}\]

\(A\)是状态转移概率矩阵： \[A = [a_{ij}]_{N \times N}\] 其中 \[a_{ij} = P(i_{t+1} = q_j | i_t = q_i), \quad i=1,2,\cdots, N; \quad j=1,2,\cdots, N\] 是在时刻\(t\)处于状态\(q_i\)的条件下在时刻\(t+1\)转移到状态\(q_j\)的概率。

\(B\)是观测概率矩阵： \[B = [b_j(k)]_{N \times M}\] 其中 \[b_j(k) = P(o_t = v_k| i_t = q_j), \quad k = 1,2,\cdots, M; \quad j = 1,2,\cdots, N\] 是在时刻\(t\)处于状态\(q_j\)的条件下生成观测\(v_k\)的概率。

\(\pi\)是初始状态概率向量： \[\pi = (\pi_i)\] 其中 \[\pi_i = P(i_1 = q_i), \quad i=1,2,\cdots, N\] 是时刻\(t=1\)处于状态\(q_i\)的概率。

隐马尔可夫模型由初始状态概率向量\(\pi\)、状态转移概率矩阵\(A\)和观测概率矩阵\(B\)决定。\(\pi\)和\(A\)决定状态序列，\(B\)决定观测序列。
隐马尔可夫模型\(\lambda\)的三元符号表示： \[\lambda = (A,B,\pmb{\pi})\] 这也成为隐马尔可夫模型的三要素。

隐马尔可夫模型做出了两个基本假设：

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

1.2. 观测序列的生成过程

1.3. 3个基本问题

隐马尔可夫模型有3个基本问题：

  1. 概率计算问题：给定模型\(\lambda = (A,B,\pi)\)和观测序列\(O=\{o_1,o_2,\cdots,o_T\}\)，计算在模型\(\lambda\)下观测序列\(O\)出现的概率\(P(O|\lambda)\)；
  2. 学习问题：已知观测序列\(O=\{o_1,o_2,\cdots,o_T\}\)，估计模型\(\lambda = (A,B,\pi)\)参数，使得在该模型下观测序列概率\(P(O|\lambda)\)最大，即用极大似然估计的方法估计参数；
  3. 预测问题：也称“解码问题”，已知模型\(\lambda = (A,B,\pi)\)和观测序列\(O=\{o_1,o_2,\cdots,o_T\}\)，求给定观测序列条件概率\(P(I|O)\)最大的状态序列\(I=\{i_1, i_2, \cdots, i_T\}\)。即给定观测序列，求最有可能的对应的状态序列。

2. 概率计算算法

计算\(P(O|\lambda)\)最直接的方法就是对所有可能的状态序列求和，但时间开销太大，所以需要设计更为有效的算法。

2.1. 前向算法

前向概率：给定马尔可夫模型\(\lambda\)，定义到时刻\(t\)部分观测序列为\(o_1,o_2,\cdots,o_t\)且状态为\(q_i\)的概率为前向概率，记作 \[\alpha_t (i) = P(o_1, o_2, \cdots, o_t, i_t = q_i | \lambda)\] 可以递推地求得前向概率\(\alpha_t(i)\)即观察序列概率\(P(O|\lambda)\)。

如下图所示，前向算法实际上是基于状态序列的路径结构递推计算\(P(O|\lambda)\)的算法。前向算法高效的关键是其局部计算前向概率，然后利用路径结构将前向概率“递推”到全局，得到\(P(O|\lambda)\)。减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果，避免重复计算。

2.2. 后向算法

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

利用前向概率和后向概率的定义可以将观测序列概率\(P(O| \lambda)\)统一写成 \[P(O | \lambda) = \sum_{i=1}^N \sum_{i=1}^N \alpha_t(i) a_{ij} b_j (o_{t+1}) \beta_{t+1} (j) , \quad t = 1,2,\cdots, T-1\] 当\(t=1\)和\(t=T-1\)时分别为式（10.21）和式（10.17）。

2.3. 一些概率与期望值的计算

利用前向概率和后向概率，可以得到关于单个状态和两个状态概率的计算公式。

  1. 给定模型\(\lambda\)和观测\(O\)，在时刻\(t\)处于状态\(q_i\)的概率，记 \[\gamma_t(i) = P(i_t = q_i | O, \lambda)\] 可以通过前向后向概率计算。事实上， \[\gamma_t(i) = P(i_t = q_i | O, \lambda) = \frac{P(i_t = q_i, O | \lambda)}{P(O | \lambda)}\] 由前向概率\(\alpha_t(i)\)和后向概率\(\beta_t(i)\)定义可知： \[\alpha_t(i) \beta_t(i) = P(i_t = q_i, O | \lambda)\] 于是得到： \[\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)} \tag{10.24}\]

  2. 给定模型\(\lambda\)和观测\(O\)，在时刻\(t\)处于状态\(q_i\)且在时刻\(t+1\)处于状态\(q_j\)的概率，记 \[\xi_t(i,j) = P(i_t = q_i, i_{t+1} = q_j | O, \lambda)\] 可以通过前向后向概率计算： \[\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_{i=1}^N \sum_{j=1}^N P(i_t = q_i, i_{t+1} = q_j, O | \lambda)}\] 而 \[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)\] 所以 \[\xi_t(i,j) = \frac{\alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{i=1}^N \sum_{j=1}^N \alpha_t(i) a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)} \tag{10.26}\]

  3. 将\(\gamma_t(i)\)和\(\xi_t(i,j)\)对各个时刻\(t\)求和，可得到如下期望值：

  • 在观测\(O\)下状态\(i\)出现的期望值：\(\sum_{t=1}^T \gamma_t(i)\)；
  • 在观测\(O\)下由状态\(i\)转移的期望值：\(\sum_{t=1}^{T-1} \gamma_t(i)\)；
  • 在观测\(O\)下由状态\(i\)转移到状态\(j\)的期望值：\(\sum_{t=1}^{T-1} \xi_t(i,j)\)

3. 学习算法

隐马尔可夫模型的学习，根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可分别由监督学习与非监督学习实现。

3.1. 监督学习方法

假设已给训练数据包含\(S\)个长度相同的观测序列和对应的状态序列\(\{(O_1, I_1), (O_2, I_2), \cdots, (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}}, \quad i=1,2,\cdots, N; \quad j = 1,2,\cdots,N\]
  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}}, \quad j=1,2,\cdots,N; \quad k=1,2,\cdots,N\]
  3. 初始状态概率\(\pi_i\)的估计\(\hat{\pi}_i\)为\(S\)个样本中初始状态为\(q_i\)的频率。

由于监督学习需要使用标注数据，人工代价很高，所以有时会利用非监督学习方法。

3.2. Baum-Welch算法

假设给定训练数据只包含\(S\)个长度为\(T\)的观测序列\(\{O_1,O_2,\cdots,O_S\}\)而没有对应的状态序列，目标是学习隐马尔可夫模型\(\lambda = (A,B,\pmb{\pi})\)的参数。这里将观测序列数据看作观测数据\(O\)，状态序列数据看做不可观测的隐数据\(I\)，那么隐马尔可夫模型事实上是一个含有隐变量的概率模型 \[P(O|\lambda) = \sum_I P(O|I, \lambda) P(I|\lambda)\] 其参数的学习可以由EM算法实现：

  1. 确定完全数据的对数似然函数：
    所有观测数据写成\(O=(o_1, o_2, \cdots, o_T)\)，所有隐数据写成\(I=(i_1, i_2, \cdots, i_T)\)，完全数据是\((O,I) = (o_1, o_2, \cdots, o_T, i_1, i_2, \cdots, i_T)\)，完全数据的对数似然函数是\(\log P(O,I | \lambda)\)。
  2. EM算法的E步：求\(Q\)函数\(Q(\lambda, \bar{\lambda})\) \[Q (\lambda, \bar{\lambda}) = \sum_I \log P(O,I | \lambda) P(O,I | \lambda)\] 其中，\(\bar{\lambda}\)是隐马尔可夫模型参数的当前估计值，\(\lambda\)是要极大化的隐马尔可夫模型参数，式中省略了对\(\lambda\)而言的常数因子\(1 / P(O | \bar{\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})\)可以写成： \[\begin{align} Q(\lambda, \bar{\lambda}) = & \sum_I \log \pi_{i_1} P(O,I|\bar{\lambda}) \nonumber \\ & + \sum_I \left( \sum_{t=1}^{T-1} \log a_{i_t,i_{t+1}} \right) P(O,I | \bar{\lambda})+ \sum_I \left( \sum_{t=1}^T \log b_{i_t} (o_t) \right) P(O,I | \bar{\lambda}) \tag{10.34} \end{align}\]
  3. EM算法的M步：极大化\(Q\)函数\(Q(\lambda, \bar{\lambda})\)求模型参数\(A,B,\pmb{\pi}\) 由于要极大化的参数在式（10.34）中单独地出现在3个项中，所以只需对各项分别极大化。
    1. 第一项可以写成： \[\sum_I \log \pi_{i_0} P(O,I | \bar{\lambda}) = \sum_{i=1}^N \log \pi_i P(O, i_1 = i | \bar{\lambda})\] 由于有约束条件\(\sum_{i=1}^N \pi_i = 1\)，利用拉格朗日乘子法，写出拉格朗日函数： \[\sum_{i=1}^N \log \pi_i P(O,i_1 = i| \bar{\lambda}) + \gamma \left(\sum_{i=1}^N \pi_i - 1 \right)\] 对其求偏导数并令结果为0： \[\frac{\partial}{\partial \pi_i} \left[ \sum_{i=1}^N \log \pi_i P(O,i_1 = i | \bar{\lambda}) + \gamma \left(\sum_{i=1}^N \pi_i - 1 \right) \right] = 0\] 得 \[P(O, i_1 = i | \bar{\lambda}) + \gamma \pi_i = 0\] 对\(i\)求和得到\(\gamma\) \[\gamma = - P(O|\bar{\lambda})\] 带入式中得到 \[\pi_i = \frac{P(O, i_1 = i | \bar{\lambda})}{P(O | \bar{\lambda})} \tag{10.36}\]
    2. 第二项可以写成： \[\sum_I \left( \sum_{t=1}^{T-1} \log a_{i_t,i_{t+1}} \right) 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})} \tag{10.37}\]
    3. 第三项： \[\sum_I \left( \sum_{t=1}^T \log b_{i_t} (o_t) \right) 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})} \tag{10.38}\]

3.3. Baum-Welch模型参数估计公式

将式（10.36）~式（10.38）中的各概率分别用\(\gamma_t(i)\)，\(\xi_t(i,j)\)表示，则可将相应的公式写成： \[\begin{align} a_{ij} &= \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t (i)} \nonumber \\ b_j(k) &= \frac{\sum_{t=1, o_t = v_k}^T \gamma_t(j)}{\sum_{t=1}^T \gamma_t(j)} \nonumber \\ \pi_i &= \gamma_1 (i) \nonumber \end{align}\] 其中，\(\gamma_t(i)\)和\(\xi_t (i,j)\)分别由式（10.24）和式（10.26）给出。

算法如下：

4. 预测算法

隐马尔可夫模型预测的两种算法：近似算法与维特比算法（viterbi algorithm）。

4.1. 近似算法

近似算法的思想：在每个时刻\(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^* = \mathop{\arg \max}_{1 \leqslant i \leqslant N} [\gamma_t(i)] , \quad i=1,2,\cdots,T\] 从而得到状态序列\(I^*= (i_1^*, i_2^*, \cdots, i_T^*)\)。
近似算法的优点是计算简单，其缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。

4.2. 维特比算法

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

根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻\(t\)通过节点\(i_t^*\)，那么这一路径从节点\(i_t^*\)到终点\(i_T^*\)的部分路径，对于从\(i_t^*\)到\(i_T^*\)的所有可能的部分路径来说，必须是最优的。
算法流程：从时刻\(t=1\)开始，递推地计算在时刻\(t\)状态为\(i\)的各条部分路径的最大概率，直至得到时刻\(t=T\)状态为\(i\)的各条路径的最大概率，时刻\(t=T\)的最大概率即为最优路径的概率\(P^*\)，最优路径的终结点\(i_T^*\)也同时得到。之后，为了找出最优路径的各个节点，从终结点\(i_T^*\)开始，由后向前逐步求得节点\(i_{T-1}^*, \cdots, i_1^*\)，得到最优路径\(I^* = (i_1^*, i_2^*, \cdots, i_T^*)\)。

导入两个变量\(\delta\)和\(\psi\)，定义在时刻\(t\)状态为\(i\)的所有单个路径\((i_1,i_2, \cdots, i_t)\)中概率最大值为 \[\delta_t(i) = \max_{i_1,i_2,\cdots,i_{t-1}} P(i_t = i,i_{t-1}j,\cdots,i_1,o_t, \cdots, o_1 | \lambda), \quad i=1,2,\cdots,N\] 由定义可得变量\(\delta\)的递推公式： \[\begin{align} \delta_{t+1}(i) &= \max_{i_1,i_2,\cdots,i_t} P(i_{t+1} = i,i_t,\cdots,i_1, o_{t+1},\cdots, o_1 | \lambda) \nonumber \\ &= \max_{1 \leqslant j \leqslant N} [\delta_t(j) a_{ji}] b_i(o_{t+1}) \quad i=1,2,\cdots,N; \quad t=1,2,\cdots,T-1 \nonumber \\ \end{align}\]

定义在时刻\(t\)状态为\(i\)的所有单个路径\((i_1,i_2,\cdots,i_{t-1},i)\)中概率最大的路径的第\(t-1\)个节点为 \[\psi_t(i) = \mathop{\arg \max}_{1 \leqslant j \leqslant N} [\delta_{t-1} (j) a_{ji}], \quad i=1,2,\cdots,N\]

算法如下：