机器学习笔记之隐马尔可夫模型(四)求值问题——后向算法(Backward Algorithm)

引言

上一节介绍了基于隐马尔可夫模型使用前向算法处理求值问题，本节将介绍另一种求值问题方法——后向算法(Backward Algorithm)。

回顾：前向算法

关于隐马尔可夫模型的基础概念、模型参数相关的数学符号表示见机器学习笔记之隐马尔可夫模型(二)背景介绍一节。

求值问题

求值问题(Evaluation)本质上是在给定隐马尔可夫模型参数$\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 )$。

前向算法

前向算法(Forward Algorithm)的逻辑如下图所示。

其核心思想是当前$t$时刻状态变量$i_t=q_i$的条件下，$i_t$与初始时刻到当前时刻的观测变量 { o 1 , ⋯   , o t } \{o_1,\cdots,o_t\} {o1​,⋯,ot​}的联合概率分布$P(o_1,\cdots ,o_t,i_t=q_i\mid \lambda )$与$t+1$时刻的联合概率分布$P(o_1,\cdots ,o_t,o_{t+1},i_{t+1}=q_j\mid \lambda )$之间的关联关系。

基于齐次马尔可夫假设与观测独立性假设，记：
$$\begin{gathered} {\alpha }_t(i)=P(o_1,\cdots ,o_t,i_t=q_i\mid \lambda ) \\ {\alpha }_{t+1}(j)=P(o_1,\cdots ,o_t,o_{t+1},i_{t+1}=q_j\mid \lambda ) \end{gathered}$$
${\alpha }_t(i)$与${\alpha }_{t+1}(j)$之间关联关系表示如下：
$$\begin{array}{r}{\alpha }_{t+1}(j)=\sum _{i=1}^{\mathcal{K}}[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)]\end{array}$$
至此，从${\alpha }_0(i)$开始，执行$T$次迭代，得到最终结果${\alpha }_T(i)$。最终对$P(\mathcal{O}\mid \lambda )$进行求解：
$$P(\mathcal{O}\mid \lambda )=\sum _{i=1}^{\mathcal{K}}{\alpha }_T(i)$$

因此，$P(\mathcal{O}\mid \lambda )$的时间复杂度为$O({\mathcal{K}}^2\times \mathcal{T})$。

后向算法

整体逻辑

后向算法的逻辑如下图所示(蓝色部分)：

后向算法的核心思想共包含两项：

• 给定隐马尔可夫模型的参数$\lambda$条件下，$t+1$时刻到最终时刻的观测变量 { o t + 1 , ⋯   , o T } \{o_{t+1},\cdots,o_{T}\} {ot+1​,⋯,oT​}关于$t$时刻状态变量$i_t=q_i$的条件概率分布$P(o_{t+1},\cdots ,o_T\mid i_t=q_i,\lambda )$与$t$时刻的条件概率分布$P(o_t,\cdots ,o_T\mid i_{t-1},\lambda )$之间的关联关系。数学符号表达如下：
  $$\begin{gathered} {\beta }_t(i)=P(o_{t+1},\cdots ,o_T\mid i_t=q_i,\lambda ) \\ {\beta }_{t-1}(i)=P(o_t,\cdots ,o_T\mid i_{t-1}=q_j,\lambda ) \\ {\beta }_t(i)\stackrel{\text{?}}{\leftrightarrow }{\beta }_{t-1}(i) \end{gathered}$$

• 该算法的迭代方式是 从后向前迭代。即初始状态是${\beta }_T(i)$：
  $${\beta }_T(i)=P(i_T=q_i,\lambda )$$
  通过$T$次迭代，得到迭代的尽头${\beta }_1(i)$：
  $${\beta }_1(i)=P(o_2,\cdots ,o_T\mid i_1=q_i,\lambda )$$
  只要找出${\beta }_1(i)$和$P(\mathcal{O}\mid \lambda )$之间的关联关系，即可通过${\beta }_1(i)$求解$P(\mathcal{O}\mid \lambda )$：
  $${\beta }_1(i)\stackrel{\text{?}}{\leftrightarrow }P(\mathcal{O}\mid \lambda )$$

${\beta }_1(i)$和$P(\mathcal{O}\mid \lambda )$之间的关联关系

观察：最终迭代求解的${\beta }_1(i)$和$P(\mathcal{O}\mid \lambda )$有什么联系：

• 将$P(\mathcal{O}\mid \lambda )$展开：
  $$P(\mathcal{O}\mid \lambda )=P(o_1,o_2,\cdots ,o_T\mid \lambda )$$
• 使用条件概率密度积分将状态变量$i_1=q_i$引进来：
  $i_1$是状态变量，存在$\mathcal{K}$种选择。
  $$\begin{array}{rl}P(\mathcal{O}\mid \lambda )& =\sum _{i_1}P(o_1,\cdots ,o_T,i_1=q_i,\lambda )\\ & =\sum _{i=1}^{\mathcal{K}}P(o_1,\cdots ,o_T,i_1=q_i,\lambda )\\ & =\sum _{i=1}^{\mathcal{K}}\left[P(o_1,\cdots ,o_T\mid i_1=q_i,\lambda )\cdot P(i_1=q_i,\lambda )\right]\end{array}$$
  观察$P(i_1=q_i,\lambda )$，它是模型参数$\lambda$中的初始概率分布$\pi$，因此，上式可转化如下：
  $$P(\mathcal{O}\mid \lambda )=\sum _{i=1}^{\mathcal{K}}\left[P(o_1,\cdots ,o_T\mid i_1=q_i,\lambda )\cdot \pi \right]$$
• 观察上式，想办法把${\beta }_1(i)$给凑出来。针对$P(o_1,\cdots ,o_T\mid i_1=q_i,\lambda )$，首先使用条件概率将$o_1$分离出来：
  $$\sum _{i=1}^{\mathcal{K}}\left[P(o_1\mid o_2,\cdots ,o_T,i_1=q_i,\lambda )\cdot P(o_2,\cdots ,o_T\mid i_1=q_i,\lambda )\cdot \pi \right]$$
  关于括号中的第一项，使用 观测独立性假设 进行简化：
  实际上，在整个推导过程中，$\lambda$是可加可不加的，因为在‘求值问题’中，$\lambda$是已知的常量。
  $$\sum _{i=1}^{\mathcal{K}}[P(o_1\mid i_1=q_i,\lambda )\cdot P(o_2,\cdots ,o_T\mid i_1=q_i,\lambda )\cdot \pi ]$$
  观察括号中的第二项，它实际上就是${\beta }_1(i)$。而第一项使用发射矩阵$\mathcal{B}$中的元素进行表示即：$b_i(o_1)$。
  至此，已经找到了$P(\mathcal{O}\mid \lambda )$和${\beta }_1(i)$之间的关联关系：
  $$P(\mathcal{O}\mid \lambda )=\sum _{i=1}^{\mathcal{K}}\left[b_i(o_1)\cdot \pi \cdot {\beta }_1(i)\right]$$

${\beta }_t(i)$和${\beta }_{t-1}(j)$之间的关联关系

观察${\beta }_t(i)$和${\beta }_{t-1}(j)$的展开结果：
$$\begin{gathered} {\beta }_t(i)=P(o_{t+1},\cdots ,o_T\mid i_t=q_i,\lambda ) \\ {\beta }_{t-1}(i)=P(o_t,\cdots ,o_T\mid i_{t-1}=q_j,\lambda ) \end{gathered}$$

• 首先观察${\beta }_{t-1}(j)$，结合图像分析，状态变量$i_{t-1}$与观测变量$o_t,\cdots ,o_T$之间是不关联的，一个朴素思想是：引入状态变量$i_t$，将$i_{t-1},o_t,\cdots ,o_T$关联起来：
  
  $$\begin{array}{rl}{\beta }_{t-1}(j)& =\sum _{i_t}P(o_t,\cdots ,o_T,i_t=q_i\mid i_{t-1}=q_j,\lambda )\\ & =\sum _{i=1}^{\mathcal{K}}P(o_t,\cdots ,o_T,i_t=q_i\mid i_{t-1}=q_j,\lambda )\end{array}$$
• 想办法凑出$i_t$和$i_{t-1}$之间的条件关系。即使用条件概率将$o_t,\cdots ,o_T$与$i_t=q_i$分离出来：
  $$\begin{array}{rl}& \sum _{i=1}^{\mathcal{K}}[P(o_t,\cdots ,o_T\mid i_t=q_i,i_{t-1}=q_j,\lambda )\cdot P(i_t=q_i\mid i_{t-1}=q_j,\lambda )]\\ & =\sum _{i=1}^{\mathcal{K}}[P(o_t,\cdots ,o_T\mid i_t=q_i,i_{t-1}=q_j,\lambda )\cdot a_{ij}]\end{array}$$
• 观察括号中的第一项，从概率图阻断的角度观察，亦或从观测独立的角度观察，状态变量$i_{t-1}$不可能与任意一个观测变量$o_t,\cdots ,o_T$存在关系。因此，第一项可表示为：$P(o_t,\cdots ,o_T\mid i_t=q_i)$。对应结果整理如下：
  $i_{t-1}$和后续观测变量结点均属于‘顺序结构’。由于$i_t$的阻塞性，$o_1,\cdots ,o_T$均与$i_{t-1}$条件独立。传送门
  $${\beta }_{t-1}(j)=\sum _{i=1}^{\mathcal{K}}[P(o_t,\cdots ,o_T\mid i_t=q_i,\lambda )\cdot a_{ij}]$$
• 基于上式，凑出观测独立性假设步骤。将$o_t$提到前面，则有：
  $$\sum _{i=1}^{\mathcal{K}}[P(o_t\mid o_{t+1},\cdots ,o_T,i_t=q_i,\lambda )\cdot P(o_{t+1},\cdots ,o_T\mid i_t=q_i,\lambda )\cdot a_{ij}]$$
• 根据 观测独立性假设，第一项$P(o_t\mid o_{t+1},\cdots ,o_T,i_t=q_i,\lambda )=P(o_t\mid i_t=q_i,\lambda )$。并且第二项就是之前定义的${\beta }_t(i)$。最终迭代结果整理如下：
  $$\begin{array}{rl}{\beta }_{t-1}(j)& =\sum _{i=1}^{\mathcal{K}}P(o_t\mid i_t=q_i,\lambda )\cdot {\beta }_t(i)\cdot a_{ij}\\ & =\sum _{i=1}^{\mathcal{K}}{b}_i(o_t)\cdot {\beta }_t(i)\cdot a_{ij}\end{array}$$

至此，得到了${\beta }_{t-1}(j)$和${\beta }_t(i)$之间的递归关系。
观察后向算法 需要的时间复杂度：

• 得到${\beta }_1(i)$需要的时间复杂度是$O(\mathcal{K}\times T)$；
• 通过公式：$P(\mathcal{O}\mid \lambda )={\sum }_{i=1}^{\mathcal{K}}\left[b_i(o_1)\cdot \pi \cdot {\beta }_1(i)\right]$需要的时间复杂度是$O(\mathcal{K})$
• 因此后向算法的时间复杂度和前向算法相同，均是$O({\mathcal{K}}^2\times T)$。

下一节将介绍隐马尔可夫模型的参数$\lambda$求解问题

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