11°

统计学习方法10—隐马尔可夫模型推导

  隐马尔可夫模型(HMM)是一种标注模型,描述由隐藏的马尔可夫链随机生成观测序列的过程,属于生成模型。其在语音识别,自然语言处理,模式识别等领域有着广泛的应用。
#### 1.基本概念
  友好起见,我们以例子来导出马尔可夫的定义

  • 盒子与球模型
      设有4个盒子,每个盒子里装有红白两种颜色的球。该模型抽取过程定义如下:先等概率选择一个盒子,从中抽取一次得到一个观测结果,然后换盒子,并且换盒子的过程中服从一些概率,比如1号盒子到2、3、4号的概率分别为0.1、0.4、0.5。2号盒子到1、2、3、4号的概率分别为0.3、0.2、0.1、0.4。假设抽取了5次,结果为“红,白,白,红,红”。
      总共抽取了5次,那么得到一个时间长度为5的观测序列,这里”红,白,白,红,红“便是最终的观测序列,其中每次抽取是在不同的盒子中进行的,这5次选择的盒子构成了一个状态随机序列,表示是在什么状态下抽取的。注意模型开始假设是等概率选择一个盒子,这个概率叫初始状态概率\(\pi\)
      设所有可能的状态Q有N种,可能的V观测有M种,为了公式表达方便, 用 \(q=i\) 表示状态为第\(i\) 个状态, \(q_t=i\)表示在 \(t\) 时刻的状态是第 \(i\) 个状态,\(y_t\) 表示第 \(t\)个时刻的观测。
      其中每个状态(当前盒子)都有转移到另一个状态的概率,这些概率可以方便的用矩阵表示,并且这个矩阵一定是方阵,
    \[ A=[a_{ij} ] _ {N*N} \]其中,\[a_{ij} = P(q_{(t+1)} =j|q_t = i), i=1,2,...,N;j=1,2,...,N\]表示在时刻 t 处于状态 i 的条件下在下一时刻 t+1 转移到状态 j 的概率。
      除了状态转移矩阵,要知道还有每个状态下各个观测事件发生的概率,因此也用矩阵B将其表示
    \[B = [b_j(k)]_{N*M}\]其中,\[ b_j(k) = P(y_t = v_k|q_t = j) \]表示在状态 \(j\) 下生成观测\(v_k\)的概率。
      \(\pi\)表示初始状态概率向量
    \[\pi = (\pi_i) , \]其中,\(\pi = P(q_1 =i)\),表示\(t = 1\)时刻处于状态 \(i\) 的概率。
      状态转移概率矩阵A,观测概率矩阵B和初始状态概率\(\pi\)构成了隐马尔可夫模型的三要素,常用三元符表示隐马尔可夫模型的参数
    \[\lambda = (A,B,\pi)\]  隐马尔可夫模型有两个非常重要的假设,后面简化算法的推导都是基于这两个假设
  • 齐次马尔可夫性假设
      即假设隐马尔可夫链在任意时刻\(t\)的状态只依赖与前一时刻的状态,与其他时刻的装态和观测值无关,也与\(t\)时刻无关,即得概率简化公式如下
    \[P(q_t|y_1,y_2,...,y_{t-1},q_1,q_2,...,q_{t-1})= P(q_t|q_{t-1})\]
  • 观测独立性假设
      即假设任意时刻的观测只依赖于当前时刻马尔可夫链的状态,而与其他观测和状态无关
    \[P(y_t|y_1,y_2,...,y_{t-1},q_1,q_2,...,q_t) = P(y_t|q_t)\]  总结一下隐马尔可夫的过程,那么假设\(\lambda\)的参数已知,生成一个长度为T的时间序列的过程如下:
      (1) 按照初始状态概率\(\pi\)产生一个状态\(q_1\)
      (2)令 t = 1
      (3)按照状态\(q_t\)的观测概率矩阵B生成\(y_t\)
      (4)安装状态\(q_t\)的状态转移矩阵A产生下一个时刻的状态。
      (5)\(t= t +1\), 如果\(t < T\),转至(3),否则结束。

  大致明白隐马尔可夫模型是什么之后我们需要考虑它是干嘛的,能做什么。事实上隐马尔可夫模型有三个基本问题,解决这三个基本问题的过程也就是解决不同问题的过程,同时其问题描述也很明确,相信看完问题描述之后便对它能做什么有大致的了解。

  • 隐马尔可夫的三个基本问题

(1) 概率计算问题。给定隐马尔可夫模型的参数\(\lambda=(A,B,\pi)\)和观测序列\(Y=(y_1,y_2,...,y_t)\),计算在该模型下观测 序列\(Y\)出现的概率\(P(Y|\lambda)\)

(2) 学习问题。已知观测序列\(Y= (y_1,y_2,...,y_t)\),估计模型的参数\(\lambda=(A,B,\pi)\),使得该模型下的该观测序列发生的概率\(P(Y|\lambda)\)最大,即极大似然估计该模型参数。

(3) 预测问题,也称为解码(decoding)问题。已知模型\(\lambda=(A,B,\pi)\)和观测序列\(Y=(y_1,y_2,...,y_t)\),求使给定序列条件下状态序列的概率\(P(Q|Y)\)最大的状态序列,即给定观测序列,求最有可能生成该观测序列的状态序列。

  后面继续讨论如何计算这些问题以及如何简化这些问题。

2.\(P(Y|\lambda)\)概率计算问题

  本问题可以通过前向和后向算法进行计算,不过先来看看该问题的直接解法,以及该方法为什么不可行。前面已经说过隐马尔可夫有两个基本假设,其计算基本都是基于它们来化简的,先考虑其基本用法,即一个观测序列可以如何简化表达,以三个观测序列为例\(P(y_1,y_2,y_3)\),其中共有K个状态
\[ \begin{aligned} P(y_1,y_2,y_3) = & \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_1,y_2,y_3,q_1,q_2,q_3)\\ = &\sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|y_1,y_2,q_1,q_2,q_3)\cdot P(y_1,y_2,q_1,q_2,q_3)\\ = &\sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3)\cdot P(q_3|y_1,y_2,q_1,q_2)\cdot P(y_1,y_2,q_1,q_2)\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_1,y_2,q_1,q_2)\\ & \cdots \cdots\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_2|q_2)\cdot P(q_2|q_1) \cdot P(y_1|q_1) \cdot P(q_1)\\ =& \sum_{q_3}^K\sum_{q_2}^K\sum_{q_1}^KP(y_3|q_3) \cdot P(q_3|q_2) \cdot P(y_2|q_2)\cdot P(q_2|q_1) \cdot P(y_1|q_1) \cdot \pi(\pi_1) \end{aligned} \]  虽然这一方法在直接计算法中没有用到,但是是后面化简都会用到的,所以先写在这儿。

  • 直接计算方法

   回忆问题,给定模型参数和一个观测序列,计算这个观测序列出现的概率\(P(Y,\lambda)\),若要直接计算,需考虑我们有哪些已知条件。首先初始状态概率\(\pi\)知道,状态转移概率矩阵A也知道,那么生成和这个观测序列相同长度的状态序列的概率\(P(Q|\lambda)\)就能表示出来了
\[P(Q|\lambda)=\pi_{q_1} a_{q_1q_2}a_{q_2q_3} \cdots a_{q_{t-1}q_{t}}\]  \(P(Y|\lambda)\)不能直接表达的原因是中间还有隐变量——转移状态,在固定状态下的观测概率B是已知的,那么已经得到了一串状态序列的概率,在这串状态序列下的观测是能够表示的,这便得到了
\[P(Y|Q,\lambda) = b_{q_i}(y_1)\cdot b_{q_2}(y_2)\cdots b_{q_t}(y_t)\]  有了这两个概率,隐变量和观测变量的联合概率分布可表示为
\[ \begin{aligned} P(Y,Q|\lambda) =&P(Y|Q,\lambda) P(Q|\lambda)\\ =&\pi_{q_1}b_{q_1}(y_1)a_{q_1q_2}b_{q_2}(y_1)\cdots a_{q_{t-1}q_t}b_{q_t}(y_t) \end{aligned} \]  对于联合概率分布,可以求解其一个变量的边缘分布的和或积分得到另一个变量的分布,这是机器学习中常见的 手段,应熟练掌握,现对状态序列求和
\[ \begin{aligned} P(Y|\lambda) =& \sum_QP(Y|Q,\lambda) P(Q|\lambda)\\ =& \sum_{q_t}^K \cdots \sum_{q_1}^K\pi_{q_1}b_{q_1}(y_1)a_{q_1q_2}b_{q_2}(y_1)\cdots a_{q_{t-1}q_t}b_{q_t}(y_t) \end{aligned} \]  这个计算量是非常大的,T个观测序列,每个序列有K种可能的状态,且内部还有T个乘积需要计算,相当于T个for循环,每个循环执行K次,每次的复杂度T,那么总复杂度\(O(TK^T)\)

  • 前向算法

  为了简化,首先定义了前向概率表达,对于隐马尔可夫模型\(\lambda\),定义在时刻 t 的观测序列为\((y_1,y_2,...,y_t)\)且状态为\(q_t = i\)的概率为前向概率\(\alpha_t(i)\),即
\[ \alpha_t(i) = P(y_1,y_2,...,y_t,q_t = i |\lambda) \]  下面通过这个前向概率推导\(P(Y|\lambda)\)的递推表达式
\[ \begin{aligned} \alpha_1(i) = & P(y_1,q_1 = i | \lambda)\\ =&\pi(\pi_i)bi(y_1)\\ ,&\\ \alpha_2(i)=&P(y_1,y_2,q_2 = i)\\ =&\sum_jP(y_1,y_2,q_2 = i,q_1 = j)\\ =&\sum_jP(y_2|q_2 = i)P(q_2 = i|q_1 =j)\cdot \alpha_1(j)\\ =&P(y_2|q_2)\sum_jP(q_2 = i|q_1 = j) \cdot \alpha_1(j)\\ &\cdots\\ \alpha_t(i)=&P(y_t|q_t = i)\sum_jP(q_t = i|q_{t-1} = j) \cdot \alpha_{t-1}(j)\\ =&b_i(y_t)\sum_ja_{ji}\cdot \alpha_{t-1}(j) \end{aligned} \]  注意求第二个前向概率的时候,为了化简式子,引入了\(q_1\)但将它当作边缘概率求和去掉了。这个递推式就这样神奇的得到了 t 时刻状态为 \(q = i\) 的概率,得到t 时刻的前向概率的表达式后,根据它的定义\(\alpha_T(i) = P(y_1,y_2,...,y_T,q_t = i|\lambda)\)可知,计算\(P(Y|\lambda)\)只需要将 t 时刻的所有状态的概率求和就可以了(边缘概率)
\[P(Y|\lambda) = \sum_i^K\alpha_T(i)\]  而且这个递推式极大的简化了计算量,因为在计算下一个时刻的前向概率的时候,上一个时刻的前向概率是已经算出来了的,只需做少量乘法,最后的复杂度为\(O(KT)\)

  • 后向算法

  明白前向算法的推导过程后,后向算法的思想其实是一样的,并且得到的结果都一样,只不过后向是从后面往前面推,前向可与后向算法组合在一起表达\(P(Y|\lambda)\)
定义:
  给定隐马尔可夫模型\(\lambda\),定义在 t 时刻 且状态为\(q_t = i\)的条件下,从 t + 1 时刻到 T 时刻的观测序列的概率为后向概率,即
\[\beta_t(i) = P(y_{t+1},y_{t+2},...,y_T| q_t = i, \lambda) \]  注意观测数据是从 t + 1 时刻开始的,并且\(\beta_t(i) = 1\)
\[ \begin{aligned} \beta_T(i) = & 1\\ ,&\\ \beta_{T-1}(i)=&P(y_T|q_{T-1} = i,\lambda)\\ =&\sum_{j}^KP(y_T,q_T=j|q_{T-1} = i,\lambda)\\ =&\sum_j^KP(y_T|q_T =j)P(q_T = j|q_{T-1} =i)\\ =&\sum_j^Kb_j(y_T)a_{ij} \beta_T(j)\\ &,\\ \beta_{T-2}(i)=&P(y_{T-1},y_T|q_{T-2} = i, \lambda)\\ =&\sum_{j}^K P(y_{T-1},y_T,q_{T-1} = j|q_{T-2} = i, \lambda)\\ (乘法公式)=&\sum_{j}^K P(y_T|q_{T-1} = j)\cdot P(y_{T-1}|q_{T-1}=j)\cdot P(q_{T-1}=j|q_{T-2} = i,\lambda)\\ =&\sum_j^K \beta_{T-1}(j)\cdot b_j(y_{T-1})a_{ij}\\ &\cdots\\ \beta_t(i)=&\sum_j^K\beta_{t+1}(j)\cdot b_j(y_{t+1})\cdot a_{ij} \end{aligned} \]  同样,得到后向概率的表达式后,根据其定义\(\beta_t(i) = P(y_{t+1},y_{t+2},...,y_T| q_t = i, \lambda)\),所求序列为1-T,但t 至少为1 ,这使得该表达式缺少了第一个观测值的概率,不过这很简单,乘上\(\pi_i b_{i}(y_1)\)即可,通过后向概率得到\(P(Y|\lambda)\)
\[ P(Y|\lambda) = \sum_i^K\pi_i b_i(y_1)\beta_1(i) \]  从刚刚这个求和运算中发现后向概率的定义从 t + 1 时刻开始似乎不方便,但是当它和前向概率结合时,就会发现,应当如此!

  • 通过前向与后向概率表达一些重要概率

  (1)计算\(P(q_t = i|Y,\lambda),Y = (y_1,y_2,...y_T)\)时,即计算给定一串序列情况下其第 t 时刻的状态为 i 的几率,利用前向与后向概率,先计算t 时刻状态与观测的联合分布
\[ \begin{aligned} P(Y,q_t = i | \lambda) = &P(Y|q_t = i)\cdot P(q_t = i)\\ =& P(y_1,\cdots,y_t|q_t = i)\cdot P(y_{t+1},\cdots ,y_T|q_t = i)\cdot P(q_t = i)\\ =& P(y_1,\cdots,y_t,q_t = i)\cdot P(y_{t+1},\cdots ,y_T|q_t = i)\\ =& \alpha_t(i)\cdot \beta_t(i) \end{aligned} \]  即序列中某个时刻 t 的状态与观测的联合分布可用前向与后向拼接而成,由该联合分布可得观测的分布
\[P(Y|\lambda) = \sum_i^KP(Y,q_t = i|\lambda)=\sum_i^K\alpha_t(i)\beta_t(i)\]  再根据条件概率或乘法公式
\[P(q_t = i|Y,\lambda) =\frac {P(Y,q_t = i|\lambda)} {P(Y|\lambda)}= \frac {\alpha_t (i) \beta_t(i)} {\sum_i\alpha_t(i) \beta_t(i)}\]
  (2)给定模型参数和观测序列Y,求在时刻 t 处于状态 i 且在时刻 t + 1 处于状态 j 的概率,大概已经找到窍门了,就是通过其联合概率和观测概率
\[ \begin{aligned} P(q_t =i,q_{t+1}=j|Y,\lambda) = & \frac {P(q_t =i ,q_{t+1} = j,Y, \lambda)} {P(Y|\lambda)}\\ =& \frac {P(q_t =i ,q_{t+1} = j,Y, \lambda)} {\sum_i^K\sum_j^KP(q_t =i ,q_{t+1} = j,Y, \lambda)}\\ \end{aligned} \]其中,
\[ \begin{aligned} P(&q_t =i ,q_{t+1} = j,Y, \lambda)\\ =&P(Y|q_t=i,q_{t+1} = j)P(q_t=i,q_{t+1} = j)\\ =&P(y_T,y_{T-1},\cdots,y_{t+1}|q_t=i,q_{t+1}=j)P(y_t,\cdots,y_1|q_t=i,q_{t+1}=j)P(q_{t+1}=j,q_t=i)P(q_t=i)\\ =&P(y_T,y_{T-1},\cdots,y_{T+2}|q_{t+1}=j)P(y_{T+1}|q_{t+1} = j)P(y_T,\cdots,y_1,q_t=i)P(q_{t+1}=j,q_t = i)\\ =&\beta_{t+1}(j)b_j(y_{t+1})\alpha_t(i)a_{ij} \end{aligned} \]  此过程中应仔细考虑马尔可夫的两个基本假设,确定其中哪些变量是相互独立的,还有哪些是我们之前已经求出来的。这里以 t 和 t + 1 为界将观测量分开,这样时刻 t 和 时刻 t + 1 的状态都只能作用 于其中一边了。带入原式
\[ P(q_t =i,q_{t+1}=j|Y,\lambda) = \frac {\alpha_t(i)a_{ij}b_j(y_{t+1})\beta_{t+1}(j)} { \sum_i^K\sum_j^K\alpha_t(i)a_{ij}b_j(y_{t+1})\beta_{t+1}(j)} \]
(3)上面计算出的两个概率求和可以方便的表示一些有用的期望
   1> 在观测Y下状态 i 出现的期望
\[ \sum_t^TP(q_t=i|Y,\lambda) \]  2> 在观测Y下由状态 i 转移的期望
\[ \sum_i^{T-1}P(q_t = i | Y, \lambda) \]   3>在观测Y下由状态 i 转移到状态 j 的期望
\[ \sum_i^{T-1} P(q_t = i,q_{t+1} = j|Y, \lambda) \]

3. 学习算法

原文链接:https://www.cnblogs.com/breezezz/p/11180911.html

全部评论: 0

    我有话说: