机器学习笔记只隐马尔可夫模型(三)求值问题——前向算法(Forward Algorithm)

引言

上一节对隐马尔可夫模型(Hidden Markov Model,HMM)进行了归纳介绍。本节将详细介绍使用前向算法(Forward Algorithm)对处理求值(Evaluation)问题。

回顾：隐马尔可夫模型

隐马尔可夫模型是一个动态模型(Dynamic Model)。其主要特点是系统状态(System State)任意一个状态元素(隐变量)，其取值范围是离散的。
以系统状态中$t$时刻的状态元素${\mathcal{Z}}^{(t)}$为例，存在$\mathcal{K}$个离散结果供${\mathcal{Z}}^{(t)}$进行选择。即：
Z ( t ) ∈ { z 1 , z 2 , ⋯   , z K } \mathcal Z^{(t)} \in \{z_1,z_2,\cdots,z_{\mathcal K}\} Z(t)∈{z1​,z2​,⋯,zK​}

概念介绍

隐马尔可夫模型由状态序列与观测序列两部分构成：
I = { i 1 , i 2 , ⋯   , i t , i t + 1 , ⋯   , i T } O = { o 1 , o 2 , ⋯   , o t , o t + 1 , ⋯   , o T } \mathcal I = \{i_1,i_2,\cdots,i_t,i_{t+1},\cdots,i_T\} \\ \mathcal O = \{o_1,o_2,\cdots,o_t,o_{t+1},\cdots,o_T\} I={i1​,i2​,⋯,it​,it+1​,⋯,iT​}O={o1​,o2​,⋯,ot​,ot+1​,⋯,oT​}
其中状态序列中状态变量$i_t\in \mathcal{I}$的取值范围是离散的，并且状态变量可取到的状态值集合$\mathcal{Q}$表示如下：
Q = { q 1 , q 2 , ⋯   , q K } \mathcal Q = \{q_1,q_2,\cdots,q_{\mathcal K}\} Q={q1​,q2​,⋯,qK​}
观测序列中的观测变量$o_t\in \mathcal{O}$的取值范围同样是离散的，并且观测变量可取到的观测值集合$\mathcal{V}$表示如下：
V = { v 1 , v 2 , ⋯   , v M } \mathcal V = \{v_1,v_2,\cdots,v_\mathcal M\} V={v1​,v2​,⋯,vM​}

模型参数表示

隐马尔可夫模型的模型参数$\lambda$具体包含三项：
$$\lambda =(\pi ,\mathcal{A},\mathcal{B})$$

• $\pi$称作 初始概率分布(基于状态变量)，是一个$\mathcal{K}$维向量。向量各元素表示初始状态变量$i_1$取到各离散结果$q_1,q_2,\cdots ,q_{\mathcal{K}}$ 的概率值。即：
  $$\pi ={\left(\begin{array}{c}P(i_1=q_1)\\ P(i_1=q_2)\\ ⋮\\ P(i_1=q_{\mathcal{K}})\end{array}\right)}_{\mathcal{K}\times 1}\sum _{k=1}^{\mathcal{K}}P(i_1=q_k)=1$$
• $\mathcal{A}$称作状态转移矩阵。具体表示如下：
  $$\mathcal{A}=[a_{ij}{]}_{\mathcal{K}\times \mathcal{K}}$$
  其中$a_{ij}$表示$t$时刻下的状态变量$i_t=q_i$的条件下，$t+1$时刻的状态变量$i_{t+1}=q_j$的概率。数学符号表示如下：
  a i j = P ( i t + 1 = q j ∣ i t = q i ) i , j ∈ { 1 , 2 , ⋯   , K } a_{ij} = P(i_{t+1} = q_j \mid i_t = q_i) \quad i,j \in \{1,2,\cdots,\mathcal K\} aij​=P(it+1​=qj​∣it​=qi​)i,j∈{1,2,⋯,K}
• $\mathcal{B}$称作发射矩阵。具体表示如下：
  $$\mathcal{B}=[b_j(k){]}_{\mathcal{K}\times \mathcal{M}}$$
  其中$b_j(k)$表示$t$时刻下状态变量$i_t=q_j$的条件下，$t$时刻下的观测变量$o_t=v_k$的概率。数学符号表示如下：
  b j ( k ) = P ( o t = v k ∣ i t = q j ) j ∈ { 1 , 2 , ⋯   , K } ; k ∈ { 1 , 2 , ⋯   , M } b_j(k) = P(o_t = v_k \mid i_t = q_j) \quad j \in \{1,2,\cdots,\mathcal K\};k \in \{1,2,\cdots,\mathcal M\} bj​(k)=P(ot​=vk​∣it​=qj​)j∈{1,2,⋯,K};k∈{1,2,⋯,M}

隐马尔可夫模型的核心假设

• 齐次马尔可夫假设：
  某时刻$t$条件下，状态变量$i_t$的后验概率，只和前一时刻状态变量$i_{t-1}$相关，与其他变量无关；
  数学符号表达如下：
  $$P(i_t\mid i_{t-1},\cdots ,i_1,o_{t-1},o_1)=P(i_t\mid i_{t-1})$$
• 观测独立性假设：
  某时刻$t$条件下，观测变量$o_t$的后验概率，只和 $t$时刻的状态变量$i_t$相关，与其他变量无关。
  数学符号表达如下：
  $$P(o_t\mid i_t,\cdots ,i_1,o_{t-1},\cdots ,o_1)=P(o_t\mid i_t)$$

关于$P(\mathcal{O}\mid \lambda )$求解过程中的问题

求值问题描述：已知给定参数$\lambda$的隐马尔可夫模型，求解观测序列 O = { o 1 , o 2 , ⋯   , o T } \mathcal O = \{o_1,o_2,\cdots,o_T\} O={o1​,o2​,⋯,oT​}的后验概率结果$P(\mathcal{O}\mid \lambda )$。
或者可理解为’观测序列‘ O = { o 1 , o 2 , ⋯   , o T } \mathcal O = \{o_1,o_2,\cdots,o_T\} O={o1​,o2​,⋯,oT​}通过HMM模型的计算所发生的概率。

首先，类似于高斯混合模型引入隐变量的方式，将将状态变量$\mathcal{I}$引入到$P(\mathcal{O}\mid \lambda )$：
因为'状态变量'$\mathcal{I}$的取值范围是离散的，因此积分方式是$\sum$;
P ( O ∣ λ ) = ∑ I P ( I , O ∣ λ ) = ∑ I P ( O ∣ I , λ ) P ( I ∣ λ ) P(O∣λ)=∑IP(I,O∣λ)=∑IP(O∣I,λ)P(I∣λ)

P(O∣λ)​=I∑​P(I,O∣λ)=I∑​P(O∣I,λ)P(I∣λ)​

• 观察$P(\mathcal{I}\mid \lambda )$，它是关于状态变量$\mathcal{I}$的概率分布。因此使用 状态转移矩阵$\mathcal{A}$中的元素 进行表示：
  • 将$P(\mathcal{I}\mid \lambda )$展开成$P(i_1,i_2,\cdots ,i_T\mid \lambda )$的格式，并将其看作联合概率分布的形式，分解成条件概率的形式：
    $$\begin{array}{rl}P(\mathcal{I}\mid \lambda )& =P(i_1,i_2,\cdots ,i_T\mid \lambda )\\ & =P(i_T\mid i_1,i_2,\cdots ,i_{T-1},\lambda )\cdot P(i_1,i_2,\cdots ,i_{T-1}\mid \lambda )\end{array}$$
  • 观察上述公式的后项$P(i_1,i_2,\cdots ,i_{T-1}\mid \lambda )$，它实际上就是个缩小版的$P(\mathcal{I}\mid \lambda )$，和$P(\mathcal{I}\mid \lambda )$相比，只少了一个$i_T$项。因此，可以将$P(\mathcal{I}\mid \lambda )$看成迭代式子。即：
    $$\begin{array}{rl}P(\mathcal{I}\mid \lambda )& =P(i_T\mid i_1,i_2,\cdots ,i_{T-1},\lambda )\cdot P(i_1,i_2,\cdots ,i_{T-1}\mid \lambda )\\ & =P(i_T\mid i_1,i_2,\cdots ,i_{T-1},\lambda )\cdot P(i_{T-1}\mid i_1,i_2,\cdots ,i_{T-2},\lambda )\cdot P(i_1,i_2,\cdots ,i_{T-2}\mid \lambda )\\ & =\cdots \\ & =P(i_T\mid i_1,i_2,\cdots ,i_{T-1},\lambda )\cdot P(i_{T-1}\mid i_1,i_2,\cdots ,i_{T-2},\lambda )\cdots P(i_2\mid i_1,\lambda )\cdot P(i_1\mid \lambda )\end{array}$$
  • 观察上式中的每一项，我们都可以使用 齐次马尔可夫假设 对每一项进行简化。例如：$P(i_T\mid i_1,i_2,\cdots ,i_{T-1},\lambda )=P(i_T\mid i_{T-1})$，以此类推。
    其中最后一项$P(i_1\mid \lambda )$，即初始概率分布$\pi$。最终$P(\mathcal{I}\mid \lambda )$表示如下：
    $$P(\mathcal{I}\mid \lambda )=P(i_T\mid i_{T-1})\cdot P(i_{T-1}\mid i_{T-2})\cdots P(i_2\mid i_1)\cdot \pi$$
  • 观察状态转移过程图，$P(i_T\mid i_{T-1})$使用 状态转移矩阵$\mathcal{A}$中的元素进行表示：
    $$\begin{array}{rl}P(\mathcal{I}\mid \lambda )& =a_{i_{T-1},i_T}\cdot a_{i_{T-2},i_{T-1}}\cdots a_{i_1,i_2}\cdot \pi \\ & =\pi \cdot \prod _{t=2}^T{a}_{i_{t-1},i_t}\end{array}$$
    
• 继续观察$P(\mathcal{O}\mid \mathcal{I},\lambda )$，和$P(\mathcal{I}\mid \lambda )$相似，但依据的是 观测独立性假设。
  • $P(\mathcal{O}\mid \mathcal{I},\lambda )$中的$\mathcal{O},\mathcal{I}$进行展开，得到如下形式：
    $$\begin{array}{rl}P(\mathcal{O}\mid \mathcal{I},\lambda )& =P(o_1,\cdots ,o_T\mid i_1,\cdots ,i_T,\lambda )\\ & =P(o_T\mid o_1,\cdots ,o_{T-1},i_1,\cdots ,i_T,\lambda )\cdot P(o_1,\cdots ,o_{T-1},i_1,\cdots ,i_T\mid \lambda )\end{array}$$
  • 将上式展开成迭代形式：
    $$P(\mathcal{O}\mid \mathcal{I},\lambda )=P(o_T\mid o_1,\cdots ,o_{T-1},i_1,\cdots ,i_T,\lambda )\cdot P(o_{T-1}\mid o_1,\cdots ,o_{T-2},i_1,\cdots ,i_T,\lambda )\cdots P(o_1\mid i_1,\cdots i_T,\lambda )$$
  • 根据观测独立性假设，上述迭代形式表示如下：
    $$P(o_T\mid i_T)\cdot P(o_{T-1}\mid i_{T-1})\cdots P(o_1\mid i_1)$$
  • 基于发射过程图，$P(o_T\mid i_T)$使用发射矩阵$\mathcal{B}$结果进行表示：
    $$\begin{array}{rl}P(\mathcal{O}\mid \mathcal{I},\lambda )& =b_{i_1}(o_1)\cdot b_{i_2}(o_2)\cdots b_{i_T}(o_T)\\ & =\prod _{t=1}^T{b}_{i_t}(o_t)\end{array}$$
    

至此，$P(\mathcal{O}\mid \lambda )$可以表示如下：
P ( O ∣ λ ) = ∑ I P ( O ∣ I , λ ) P ( I ∣ λ ) = ∑ I π ⋅ ∏ t = 2 T a i t − 1 , i t ⋅ ∏ t = 1 T b i t ( o t ) P(O∣λ)=∑IP(O∣I,λ)P(I∣λ)=∑Iπ⋅T∏t=2ait−1,it⋅T∏t=1bit(ot)

P(O∣λ)​=I∑​P(O∣I,λ)P(I∣λ)=I∑​π⋅t=2∏T​ait−1​,it​​⋅t=1∏T​bit​​(ot​)​
将上式中的${\sum }_{\mathcal{I}}$部分展开，展开结果如下：
$$P(\mathcal{O}\mid \lambda )=\sum _{i_1}\cdots \sum _{i_T}\left(\pi \cdot \prod _{t=2}^T{a}_{i_{t-1},i_t}\cdot \prod _{t=1}^T{b}_{i_t}(o_t)\right)$$
观察，大括号内的项均可以通过查找初始概率分布$\pi$，状态转移矩阵$\mathcal{A}$，发射矩阵$\mathcal{B}$ 得到。但括号外的${\sum }_{i_1}\cdots {\sum }_{i_T}$中的每一项由于状态变量$i_t(t=1,2,\cdots ,T)$均存在$\mathcal{K}$种选择，因此上式的时间复杂度至少为$O({\mathcal{K}}^T)$。
即：状态序列 { i 1 , i 2 , ⋯   , i T } \{i_1,i_2,\cdots,i_T\} {i1​,i2​,⋯,iT​}随着序列长度$T$的增加，时间复杂度指数级别增长。下面将介绍关于求解$P(\mathcal{O}\mid \lambda )$的优化算法——前向算法(Forward Algorithm)。

前向算法

重新观察隐马尔可夫模型的概率图形式：

• 我们记${\alpha }_t(i)$表示 在$t$时刻，状态变量$i_t=q_i$的条件下，$t$时刻之前的所有观测变量(含$t$时刻)$o_1,o_2,\cdots ,o_t$与$i_t$的联合概率分布。数学符号表示如下：
  $${\alpha }_t(i)=P(o_1,\cdots o_t,i_t=q_i\mid \lambda )$$
• 基于上式，$T$时刻的${\alpha }_T(i)$表示如下：
  即图中‘红色框’包含的变量。
  $$\begin{array}{rl}{\alpha }_T(i)& =P(o_1,\cdots o_T,i_T=q_i\mid \lambda )\\ & =P(\mathcal{O},i_T=q_i\mid \lambda )\end{array}$$
• 如果求解$P(\mathcal{O}\mid \lambda )$，只需求解${\alpha }_T(i)$，然后将$i_T$执行条件概率密度积分即可。数学符号表示如下：
  同上,$i_T$自身存在$\mathcal{K}$种选择。
  $$\begin{array}{rl}P(\mathcal{O}\mid \lambda )& =\sum _{i_T}P(\mathcal{O},i_T=q_i\mid \lambda )\\ & =\sum _{i=1}^{\mathcal{K}}P(\mathcal{O},i_T=q_i\mid \lambda )\\ & =\sum _{i=1}^{\mathcal{K}}{\alpha }_T(i)\end{array}$$

基于上述对${\alpha }_t(i)$的描述，我们尝试 观察${\alpha }_{t+1}(j)$和${\alpha }_t(i)$之间的关系。

• ${\alpha }_{t+1}(j)$具体表达如下：
  $${\alpha }_{t+1}(j)=P(o_1,\cdots ,o_t,o_{t+1},i_{t+1}=q_j\mid \lambda )$$
• 但是上式中并不包含$i_t$项，因此，使用条件概率密度积分的方式将$i_t$加到公式中：
  $$\begin{array}{rl}{\alpha }_{t+1}(j)& =\sum _{i_t}P(o_1,\cdots ,o_t,o_{t+1},i_t=q_i,i_{t+1}=q_j\mid \lambda )\\ & =\sum _{i=1}^{\mathcal{K}}P(o_1,\cdots ,o_t,o_{t+1},i_t=q_i,i_{t+1}=q_j\mid \lambda )\end{array}$$
• 但上述式子中仍包含$o_{t+1}$项。因此，使用条件概率将上式分解，提出$o_{t+1}$：
  $$\sum _{i=1}^{\mathcal{K}}\left[P(o_{t+1}\mid o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j,\lambda )\cdot P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j\mid \lambda )\right]$$
  观察中括号内的第一项，可以使用观测独立性假设进行处理。并将上式改写如下形式：
  $$\sum _{i=1}^{\mathcal{K}}\left[P(o_{t+1}\mid i_{t+1}=q_j,\lambda )\cdot P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j\mid \lambda )\right]$$
• 此时继续观察中括号内的后项：$P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j\mid \lambda )$，它和${\alpha }_t(i)$仅差一项：$i_{t+1}=q_j$。
  和$o_{t+1}$项处理方式相同，继续使用条件概率将上式分解，提出$i_{t+1}$：
  $$\begin{array}{rl}& P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j\mid \lambda )\\ & =P(i_{t+1}=q_j\mid o_1,\cdots ,o_t,i_t=q_i,\lambda )\cdot P(o_1,\cdots ,o_t,i_t=q_i\mid \lambda )\end{array}$$
  观察上述式子第一项，可以使用齐次马尔科夫假设进行处理。并将上式改写成如下形式：
  $$P(i_{t+1}=q_j\mid i_t=q_i,\lambda )\cdot P(o_1,\cdots ,o_t,i_t=q_i\mid \lambda )=P(i_{t+1}=q_j\mid i_t=q_i,\lambda )\cdot {\alpha }_t(i)$$

至此，整理${\alpha }_{t+1}(j)$和${\alpha }_t(i)$之间的关联关系：
$${\alpha }_{t+1}(j)=\sum _{i=1}^{\mathcal{K}}\left[P(o_{t+1}\mid i_{t+1}=q_j)\cdot P(i_{t+1}=q_j\mid i_t=q_i,\lambda )\cdot {\alpha }_t(i)\right]$$
如果使用模型参数进行表示：
$${\alpha }_{t+1}(j)=\sum _{i=1}^{\mathcal{K}}{b}_j(o_{t+1})\cdot a_{ij}\cdot {\alpha }_t(i)$$
最后观察它的时间复杂度：每次迭代的时间复杂度是$O(N)$，迭代$T$次的时间复杂度即$O(\mathcal{K}\times T)$。
而上述时间复杂度 描述的是${\alpha }_1(i)\to {\alpha }_T(i)$的时间复杂度，而$P(\mathcal{O}\mid \lambda )={\sum }_{i=1}^{\mathcal{K}}{\alpha }_T(i)$。因此，$P(\mathcal{O}\mid \lambda )$的时间复杂度为：$O({\mathcal{K}}^2\times T)$，相比于$O({\mathcal{K}}^T)$还是要优化一些的。

下一节将介绍： 使用后向算法处理$P(\mathcal{O}\mid \lambda )$问题。

相关参考：
机器学习-隐马尔可夫模型3-Evaluation问题-前向算法