隐马尔可夫模型笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  最近看了李航老师的《统计学习方法》,本文主要记录一些关于隐马尔可夫模型的笔记,包括了概率计算问题,学习问题和预测问题。

隐马尔可夫模型(hidden Markov model, HMM)

  有关马尔可夫链的内容在这篇文章中有记录,这里就不多说了。
  我们简单的定义一下隐马尔可夫模型,隐马尔可夫模型通常可以由初始状态概率分布,状态转移概率分布和观测概率分布,我们定义以下符号。

  • \(Q\)是所有可能的状态集合,\(N\)是可能的状态数,\(Q=\left\{q_{1}, q_{2}, \cdots, q_{N}\right\}\)
  • \(V\)是所有可能的观测的集合,\(M\)是可能的观测数,\(V=\left\{v_{1}, v_{2}, \cdots, v_{M}\right\}\)
  • \(I\)是长度为\(T\)的状态序列,\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\)
  • \(O\)是对应的观测序列,\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\)
  • \(A\)是状态转移概率矩阵,\(A=\left[a_{i j}\right]_{N \times N}\),其中\(a_{i j}=P\left(i_{i+1}=q_{j} | i_{t}=q_{i}\right), \quad i=1,2, \cdots, N ; j=1,2, \cdots, N\)
  • \(B\)是观测概率矩阵,\(B=\left[b_{j}(k)\right]_{N \times M}\),其中\(b_{j}(k)=P\left(o_{t}=v_{k} | i_{t}=q_{j}\right), \quad k=1,2, \cdots, M ; j=1,2, \cdots, N\)
  • \(\pi\)是初始状态概率向量,\(\pi = (\pi_i)\),其中\(\pi_{i}=P\left(i_{1}=q_{i}\right), \quad i=1,2, \cdots, N\)

  隐马尔可夫模型\(\lambda\)可以由三元符号表示,即\(\lambda=(A,B,\pi)\)\(A,B,\pi\)也称为隐马尔可夫模型的三要素。状态转移概率矩阵\(A\)与初始状态概率向量\(\pi\)确定了隐藏的马尔可夫链,生成不可观测的状态序列。观测概率矩阵\(B\)确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列。
  从定义可知,隐马尔可夫模型作了两个基本假设:

  • 齐次马尔可夫性假设,即假设隐藏的马尔可夫链在任意时刻\(t\)的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关,也与时刻\(t\)无关: \[ P\left(i_{t} | i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(i_{t} | i_{t-1}\right), \quad t=1,2, \cdots, T \]
  • 观测独立性假设,即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关: \[ P\left(o_{t} | i_{T}, o_{T}, i_{T-1}, o_{T-1}, \cdots, i_{t+1}, o_{t+1}, i_{t-1}, i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(o_{t} | i_{t}\right) \]

  隐马尔可夫模型可以用于标注,这时状态对应着标记。标注问题是给定观测的序列预测其对应的标记序列。可以假设标注问题的数据是由隐马尔可夫模型生成的。这样我们可以利用隐马尔可夫模型的学习与预测算法进行标注。
  隐马尔可夫模型还有3个基本问题:

  1. 概率计算问题。给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\),计算在模型\(\lambda\)下观测序列\(O\)出现的概率\(P(O|\))$。

  2. 学习问题。己知观测序列\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\),估计模型\(\lambda=(A,B,\pi)\)参数,使得在该模型下观测序列概率\(P(O|\lambda)\)最大,即用极大似然估计的方法估计参数。

  3. 预测问题,也称为解码问题。已知模型\(\lambda=(A,B,\pi)\)和观测序列\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\),求对给定观测序列条件概率\(P(O|\lambda)\)最大的状态序列\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\),即给定观测序列,求最有可能的对应的状态序列。

概率计算法方法

  计算观测序列概率\(P(O|\lambda)\),有前向(forward)和后向(backward)两种算法。

直接计算法

  在介绍前向和后向算法之前,先介绍概念上可行但计算上不可行的直接计算法。直接计算法给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\),计算观测序列\(O\)出现的概率\(P(O|\lambda)\),按概率公式直接计算,通过列举所有可能的长度为T的状态序列\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\),求各个状态序列\(I\)与观测序\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\)的联合概率\(P(O,I|\lambda)\),然后对所有可能的状态序列求和,得到\(P(O|\lambda)\)
  状态序列\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\)的概率是: \[ P(I | \lambda)=\pi_{i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \cdots a_{i_{r-1} i_{T}} \]   对固定的状态序列\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\),观测序列\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\)的概率是\(P(O|I, \lambda)\)\[ P(O | I, \lambda)=b_{i_{1}}\left(o_{1}\right) b_{i_{2}}\left(o_{2}\right) \cdots b_{i_{T}}\left(o_{\mathrm{T}}\right) \]   \(O\)\(I\)同时出现的联合概率为: \[ \begin{aligned} P(O, I | \lambda)&=P(O | I, \lambda) P(I | \lambda) \\ &=\pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots a_{i_{i_{-1} i_{T}}} b_{i_{T}}\left(o_{T}\right) \end{aligned} \]   然后,对所有可能的状态序列\(I\)求和,得到: \[ \begin{aligned} P(O | \lambda)&=\sum_{I} P(O | I, \lambda) P(I | \lambda) \\ &=\sum_{i_{1}, i_{2}, \cdots, i_{T}} \pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots a_{i_{i_{-1} i_{T}}} b_{i_{T}}\left(o_{T}\right) \end{aligned} \]   上式的计算量很大,是\(O(TN^T)\)阶的,所以这种算法不可行。

前向算法

  前向概率指的是\(\alpha_{t}(i)=P\left(o_{1}, o_{2}, \cdots, o_{t}, i_{t}=q_{i} | \lambda\right)\),我们可以通过下面的方法递推地求得前向概率\(\alpha_t(i)\)及观测序列概率\(P(O|\lambda)\)

  1. 初值 \[ \alpha_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), \quad i=1,2, \cdots, N \]
  2. 递推,对\(t=1,2, \cdots, T-1\) \[ \alpha_{t+1}(i)=\left[\sum_{j=1}^{N} \alpha_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), \quad i=1,2, \cdots, N \]
  3. 终止 \[ P(O | \lambda)=\sum_{i=1}^{N} \alpha_{T}(i) \]

  如上图所示,前向算法实际是基于“状态序列的路径结构”来进行递推计算。前向算法高效的关键是其局部计算前向概率,然后利用路径结构将前向概率“递推”到全局,得到\(P(O | \lambda)\)。每个\(\alpha_{t+1}(i)\)的计算利用前一时刻\(N\)\(\alpha_{t}(j)\)。减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果,避免重复计算。这样,利用前向概率计算\(P(O | \lambda)\)的计算量是\(O(N^2T)\)阶的,而不是直接计算的\(O(TN^T)\)阶。

后向算法

  后向概率指的是\(\beta_{t}(i)=P\left(o_{t+1}, o_{t+2}, \cdots, o_{T} | i_{t}=q_{i}, \lambda\right)\),同样可以用递推的方法求得后向概率\(\beta_{t}(i)\)及观测序列概率\(P(O | \lambda)\)

  1. \[ \beta_{T}(i)=1, \quad i=1,2, \cdots, N \]
  2. \(t=T-1, T-2, \cdots, 1\)
    \[ \beta_{t}(i)=\sum_{j=1}^{N} a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad i=1,2, \cdots, N \]
  3. \[ P(O | \lambda)=\sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}(i) \]

  利用前向概率和后向概率的定义可以将观测序列概率\(P(O | \lambda)\)统一写成: \[ P(O | \lambda)=\sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{t}(i) a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad t=1,2, \cdots, T-1 \]   此式当\(t=1\)时即为\(P(O | \lambda)=\sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}(i)\)\(t=T-1\)时即为\(P(O | \lambda)=\sum_{i=1}^{N} \alpha_{T}(i)\)

一些概率与期望值的计算

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

  • 给定模型\(\lambda\)和观测\(O\),在时刻\(t\)处于状态\(q_i\)的概率,记\(\gamma_{t}(i)=P\left(i_{t}=q_{i} | O, \lambda\right)\)
      通过前向后向概率计算,得: \[ \gamma_{t}(i)=P\left(i_{t}=q_{i} | O, \lambda\right)=\frac{P\left(i_{t}=q_{i}, O | \lambda\right)}{P(O | \lambda)} \]   由前向概率和后向概率定义可知: \[ \alpha_{t}(i) \beta_{t}(i)=P\left(i_{t}=q_{i}, O | \lambda\right) \]   即: \[ \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)} \]

  • 给定模型\(\lambda\)和观测\(O\),在时刻\(t\)处于状态\(q_i\)且在时刻\(t+1\)处于状态\(q_j\)的概率,记\(\xi_{t}(i, j)=P\left(i_{t}=q_{i}, i_{t+1}=q_{j} | O, \lambda\right)\)
      可以通过前向后向概率计算: \[ \xi_{i}(i, j)=\frac{P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)}{P(O | \lambda)}=\frac{P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)}{\sum_{i=1}^{N} \sum_{j=1}^{N} P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)} \]   而: \[ P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)=\alpha_{t}(i) a_{j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j) \]   所以: \[ P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O | \lambda\right)=\alpha_{t}(i) a_{j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j) \]

  将\(\gamma_{t}(i)\)\(\xi_{t}(i, j)\)对各个时刻\(t\)求和,可以得到一些有用的期望值:

  1. 在观测\(O\)状态\(i\)出现的期望值:
    \[ \sum_{i=1}^{T} \gamma_{i}(i) \]
  2. 在观测\(O\)下由状态\(i\)转移的期望值:
    \[ \sum_{i=1}^{T-1} \gamma_{t}(i) \]
  3. 在观测\(O\)下由状态\(i\)转移到状态\(j\)的期望值:
    \[ \sum_{t=1}^{T-1} \xi_{t}(i, j) \]

学习算法

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

监督学习方法

  假设已给训练数据包含\(S\)个长度相同的观测序列和对应的状态序列\(\left\{\left(O_{1}, I_{1}\right),\left(O_{2}, I_{2}\right), \cdots,\left(O_{s}, I_{S}\right)\right\}\),那么可以利用极大似然估计法来估计隐马尔可夫模型的参数,步骤如下:

  1. 转移概率\(a_{ij}\)的估计
      设样本中时刻\(t\)处于状态\(i\)时刻\(t+1\)转移到状态\(j\)的频数为\(A_{ij}\),那么状态转移概率\(a_{ij}\)的估计是: \[ \hat{a}_{i j}=\frac{A_{ij}}{\sum_{j=1}^{N} A_{i j}}, \quad i=1,2, \cdots, N ; j=1,2, \cdots, N \]
  2. 观测概率\(b_j(k)\)的估计
      设样本中状态为\(j\)并观测为\(k\)的频数是\(B_{jk}\),那么状态为\(j\)观测为\(k\)的概率\(b_j(k)\)的估计是: \[ \hat{b}_{j}(k)=\frac{B_{j k}}{\sum_{k=1}^{M} B_{j k}}, \quad j=1,2, \cdots, N_{i} \quad k=1,2, \cdots, M \] 3.初始状态概率\(\pi_i\)的估计\(\hat{\pi}_i\)\(S\)个样本中初始状态为\(q_i\)的频率。

非监督学习方法

  由于监督学习需要使用训练数据,而人工标注训练数据往往代价很高,有时就会利用非监督学习的方法。Baum-Welch算法就是一种非监督学习的算法。

Baum-Welch算法

  假设给定训练数据只包含\(S\)个长度为\(T\)的观测序列\(\left\{O_{1}, O_{2}, \cdots, O_{s}\right\}\)而没有对应的状态序列,目标是学习隐马尔可夫模型\(\lambda=(A,B,\pi)\)的参数。我们将观测序列数据看作观测数据\(O\),状态序列数据看作不可观测的隐数据\(I\),那么隐马尔可夫模型事实上是一个含有隐变量的概率模型: \[ P(O | \lambda)=\sum_{I} P(O | I, \lambda) P(I | \lambda) \]   它的参数学习可以由EM算法实现:

  1. 确定完全数据的对数似然函数
      所有观测数据写成\(O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)\),所有隐数据写成\(I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)\),完全数据是\((O, I)=\left(o_{1}, o_{2}, \cdots, o_{T}, i_{1}, i_{2}, \cdots, i_{T}\right)\),完全数据的对数似然函数是\(\log P(O, I | \lambda)\)
  2. EM算法的E步:求\(Q\)函数\(Q(\lambda, \overline{\lambda})=\sum_{I} \log P(O, I | \lambda) P(O, I | \overline{\lambda})\)
      \(\overline{\lambda}\)是隐马尔可夫模型参数的当前估计值,\(\overline{\lambda}\)是要极大化的隐马尔可夫模型参数: \[ P(O, I | \lambda)=\pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \cdots a_{i_{T-1} i_{T}} b_{i_{T}}\left(o_{T}\right) \]   于是函数\(Q(\lambda, \overline{\lambda})\)可以写成: \[ Q(\lambda, \overline{\lambda})=\sum_{I} \log \pi_{i_1} P(O, I | \overline{\lambda}) + \sum_{I}\left(\sum_{t=1}^{T-1} \log a_{i_ti_{t+1}}\right) P(O, I | \overline{\lambda})+\sum_{I}\left(\sum_{t=1}^{T} \log b_{i_{t}}\left(o_{t}\right)\right) P(O, I | \overline{\lambda}) \]   式中求和都是对所有训练数据的序列总长度\(T\)进行的。
  3. EM算法的M步:极大化\(Q\)函数\(Q(\lambda, \overline{\lambda})\)求模型参数\(A,B,\pi\)
      由于要极大化的参数在\(Q(\lambda, \overline{\lambda})\)中单独地出现在3个项中,所以只需对各项分别极大化。
    1. 第1项可以写成: \[ \sum_{I} \log \pi_{i_{0}} P(O, I | \overline{\lambda})=\sum_{i=1}^{N} \log \pi_{i} P\left(O, i_{1}=i | \overline{\lambda}\right) \]   注意到\(\pi_i\)满足约束条件\(\sum_{i=1}^{N} \pi_{i}=1\),利用拉格朗日乘子法,写出拉格朗日函数: \[ \sum_{i=1}^{N} \log \pi_{i} P\left(O, i_{1}=i | \overline{\lambda}\right)+\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\left(O, i_{1}=i | \overline{\lambda}\right)+\gamma\left(\sum_{i=1}^{N} \pi_{i}-1\right)\right]=0 \]   得: \[ P\left(O, i_{1}=i | \overline{\lambda}\right)+\gamma \pi_{i}=0 \]   对\(i\)求和得到\(\gamma\)\[ \gamma=-P(O | \overline{\lambda}) \]   代入偏导数即得: \[ \pi_{i}=\frac{P\left(O, i_{1}=i | \overline{\lambda}\right)}{P(O | \overline{\lambda})} \]
    2. 第2项可以写成:
      \[ \sum_{I}\left(\sum_{t=1}^{T-1} \log a_{i_{t}, i_{t+1}}\right) P(O, I | \overline{\lambda})=\sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{t=1}^{T-1} \log a_{i j} P\left(O, i_{t}=i, i_{t+1}=j | \overline{\lambda}\right) \]   类似第1项,应用具有约束条件\(\sum_{j=1}^{N} a_{i j}=1\)的拉格朗日乘子法可以求出: \[ a_{i j}=\frac{\sum_{i=1}^{T-1} P\left(O, i_{t}=i, i_{t+1}=j | \overline{\lambda}\right)}{\sum_{t=1}^{T-1} P\left(O, i_{t}=i | \overline{\lambda}\right)} \]
    3. 第3项为: \[ \sum_{I}\left(\sum_{t=1}^{T} \log b_{i_{t}}\left(o_{t}\right)\right) P(O, I | \overline{\lambda})=\sum_{j=1}^{N} \sum_{t=1}^{T} \log b_{j}\left(o_{t}\right) P\left(O, i_{t}=j | \overline{\lambda}\right) \]   同样用拉格朗日乘子法,约束条件是\(E \sum_{k=1}^{M} b_{j}(k)=1\)。注意,只有在\(o_t=v_k\)\(b_{j}\left(o_{t}\right)\)\(b_{j}(k)=1\)的偏导数才不为0,以\(I\left(o_{t}=v_{k}\right)\)表示,求得: \[ b_{j}(k)=\frac{\sum_{i=1}^{T} P\left(O, i_{t}=j | \overline{\lambda}\right) I\left(o_{t}=v_{k}\right)}{\sum_{i=1}^{T} P\left(O, i_{t}=j | \overline{\lambda}\right)} \]

  将上面三项中的各概率分别用\(\gamma_{t}(i), \quad \xi_{t}(i, j)\)表示,则可将相应的公式写成: \[ a_{i j}=\frac{\sum_{t=1}^{T-1} \xi_{t}(i, j)}{\sum_{t=1}^{T-1} \gamma_{t}(i)} \\ b_{j}(k)=\frac{\sum_{t=1,o_t=v_{k}}^{T} \gamma_{t}(j)}{\sum_{t=1}^{T} \gamma_{t}(j)} \\ \pi_{i}=\gamma_{1}(i) \]   上面三式便是Baum-Welch算法,它是EM算法在隐马尔可夫模型学习中的具体实现。它实际上也是一个递推的过程,对\(n=0\),选取\(a_{i j}^{(0)},b_{j}(k)^{(0)},\pi_{i}^{(0)}\),得到模型\(\lambda^{(0)}=\left(A^{(0)}, B^{(0)}, \pi^{(0)}\right)\)。然后对于\(n=1,2,\cdots\)递推: \[ a_{i j}^{(n+1)}=\frac{\sum_{t=1}^{T-1} \xi_{i}(i, j)}{\sum_{t=1}^{T-1} \gamma_{t}(i)}\\ b_{j}(k)^{(n+1)}=\frac{\sum_{t=1, o_t=v_{k}}^{T} \gamma_{t}(j)}{\sum_{t=1}^{T} \gamma_{t}(j)} \]   最后终止得到模型参数\(\lambda^{(n+1)}=\left(A^{(n+1)}, B^{(n+1)}, \pi^{(n+1)}\right)\)

预测算法

  隐马尔可夫模型预测有两种算法:近似算法与维特比算法

近似算法

  近似算法的想法是在每个时刻,选择在该时刻最有可能出现的状态\(i_t^*\),从而得到一个状态序列\(I^{*}=\left(i_{1}^{*}, i_{2}^{*}, \cdots, i_{T}^{*}\right)\),将它作为预测的结果。
  给定隐马尔可夫模型\(\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_{i}(i)}{\sum_{j=1}^{N} \alpha_{t}(j) \beta_{t}(j)} \]   在每一时刻\(t\)最有可能的状态\(i_t^*\)是: \[ i_{t}^{*}=\arg \max _{1 \leqslant i \leqslant N}\left[\gamma_{t}(i)\right], \quad t=1,2, \cdots, T \]   近似算法的优点是计算简单,其缺点是不能保证预测的状态序列整体是最有可能的状态序列,因为预测的状态序列可能有实际不发生的部分。事实上,上述方法得到的状态序列中有可能存在转移概率为0的相邻状态,即对某些\(a_{ij}=0\)时,但是近似算法仍然是有用的。

维特比算法(Viterbi algorithm)

  维特比算法实际是用动态规划解隐马尔可夫模型预测问题,用动态规划求概率最大路径(最优路径)。这时一条路径对应着一个状态序列。
  根据动态规划原理,最优路径具有这样的特性:如果最优路径在时刻\(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}^{*}, \cdots, i_{1}^{*}\),得到最优路径\(I^{*}=\left(i_{1}^{*}, i_{2}^{*}, \cdots, i_{T}^{*}\right)\)
  首先导入两个变量\(\delta\)\(\psi\),定义在时刻\(t\)状态为\(i\)的所有单个路径\(\left(i_{1}, i_{2}, \cdots, i_{t}\right)\)中概率最大值为: \[ \delta_{t}(i)=\max _{i, i_{2}, \cdots, i_{t-1}} P\left(i_{t}=i, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1} | \lambda\right), \quad i=1,2, \cdots, N \]   由定义可得变量\(\delta\)的递推公式: \[ \begin{aligned} \delta_{t+1}(i) &=\max _{i_{1}, i_{2}, \cdots, i_t} P\left(i_{t+1}=i, i_{t}, \cdots, i_{1}, o_{t+1}, \cdots, o_{1} | \lambda\right) \\ &=\max _{1 \leq j \leq N}\left[\delta_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), \quad i=1,2, \cdots, N ; t=1,2, \cdots, T-1 \end{aligned} \]   定义在时刻\(t\)状态为\(i\)的所有单个路径\(\left(i_{1}, i_{2}, \cdots, i_{t-1}, i\right)\)中概率最大的路径的第\(t-1\)个结点为: \[ \psi_{t}(i)=\arg \max _{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j) a_{j i}\right], \qquad i=1,2, \cdots, N \]   简单来说,维特比算法就是分为四个步骤:

  1. 初始化 \[ \begin{array}{cc}{\delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right),} & {i=1,2, \cdots, N} \\ {\psi_{1}(i)=0,} & {i=1,2, \cdots, N}\end{array} \]
  2. 递推,对\(t=2,3, \cdots, T\) \[ \begin{array}{ll}{\delta_{t}(i)=\max _{1 \leqslant j \leq N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i}\left(o_{t}\right),} & {i=1,2, \cdots, N} \\ {\psi_{t}(i)=\arg \max _{1 \leqslant j \leq N}\left[\delta_{t-1}(j) a_{j i}\right],} & {i=1,2, \cdots, N}\end{array} \]
  3. 终止 \[ \begin{array}{c}{P^{*}=\max _{1 \leqslant i \leqslant N} \delta_{T}(i)} \\ {i_{T}^{*}=\arg \max _{1 \leqslant i \leqslant N}\left[\delta_{T}(i)\right]}\end{array} \]
  4. 最优路径回溯,对\(t=T-1, T-2, \cdots, 1\),求得最优路径\(I^{*}=\left(i_{1}^{*}, i_{2}^{*}, \cdots, i_{T}^{*}\right)\) \[ i_{t}^{*}=\psi_{t+1}\left(i_{t+1}^{*}\right) \]

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 隐马尔可夫模型(hidden Markov model, HMM)
  3. 3. 概率计算法方法
    1. 3.1. 直接计算法
    2. 3.2. 前向算法
    3. 3.3. 后向算法
    4. 3.4. 一些概率与期望值的计算
  4. 4. 学习算法
    1. 4.1. 监督学习方法
    2. 4.2. 非监督学习方法
    3. 4.3. Baum-Welch算法
  5. 5. 预测算法
    1. 5.1. 近似算法
    2. 5.2. 维特比算法(Viterbi algorithm)
  6. 6. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...