机器学习笔记之隐马尔可夫模型(六)解码问题

引言

上一节介绍了使用狭义EM算法对模型参数$\lambda$。本节将介绍使用维特比算法(Viterbi)处理解码问题(Decoding)

解码问题介绍

在隐马尔可夫模型中，解码问题被看做为 给定长度为$T$的观测序列 { o 1 , o 2 , ⋯   , o T } \{o_1,o_2,\cdots,o_T\} {o1​,o2​,⋯,oT​}，目标是求解观测序列$\mathcal{O}$对应状态序列$\mathcal{I}$的后验概率$P(\mathcal{I}\mid \mathcal{O})$。即：
在解码问题中，模型参数$\lambda$是已知量，通常可以省略掉。
$$P(\mathcal{I}\mid \mathcal{O})=P(i_1,i_2,\cdots ,i_T\mid o_1,o_2,\cdots ,o_T,\lambda )$$

实际上，解码问题与预测问题(Prediction)是存在一些差别的：

• 预测问题所表达的思想是，给定长度为$t$的观测序列 O = { o 1 , o 2 , ⋯   , o t } \mathcal O = \{o_1,o_2,\cdots,o_t\} O={o1​,o2​,⋯,ot​}作为条件，求解下一时刻的观测变量$o_{t+1}$或者状态变量$i_{t+1}$的后验概率。即：
  预测往往是给定前面若干时刻的观测序列，求解下一时刻的相关信息。
  $$\begin{gathered} P(o_{t+1}\mid o_1,o_2,\cdots ,o_t) \\ P(i_{t+1}\mid o_1,o_2,\cdots ,o_t) \end{gathered}$$
• 解码问题更倾向于求解一个对应时刻的状态序列而不是未来时刻信息的判断。 即给定一个观测序列，将对应时刻的状态序列求解出来。

关于隐马尔可夫模型的相关概念、模型参数表示、模型特殊性质 见机器学习笔记之隐马尔可夫模型(五)学习问题——EM算法中的场景介绍。

首先，需要明确解码问题的目标：在给定 观测序列$\mathcal{O}$ 的条件下，找出一组后验概率最大的、与观测序列对应时刻的状态序列$\mathcal{I}$。

假设观测序列$\mathcal{O}$的长度为$T$，那么最终寻找的最优状态序列$\mathcal{I}$的长度也是$T$。因此，可以统计一下，到底存在多少种满足条件的状态序列：

由于$i_t(t=1,2,\cdots ,T)$的取值范围是离散的，根据状态值集合 Q = { q 1 , q 2 , ⋯   , q K } \mathcal Q = \{q_1,q_2,\cdots,q_{\mathcal K}\} Q={q1​,q2​,⋯,qK​}，因此，可以得到 ${\mathcal{K}}^T$个不重复的状态序列组合。
即：随着序列长度$T$的增加，状态序列组合的数量随着指数级别增长。

而解码问题就是从${\mathcal{K}}^T$个排列组合中选择出一个最优组合。

解码问题分析

什么是最优组合？最优组合满足的标准是什么？通过解码问题的目标可以看出，希望找到这样一组状态序列$\hat{\mathcal{I}}$使得关于$\hat{\mathcal{I}}$的后验概率$P(\hat{\mathcal{I}}\mid \mathcal{O},\lambda )$最大。即：
$$\hat{\mathcal{I}}=\underset{\mathcal{I}}{\mathrm{argmax}}P(\mathcal{I}\mid \mathcal{O},\lambda )$$

I ^ = { i ^ 1 , i ^ 2 , ⋯   , i ^ T } \hat {\mathcal I} = \{\hat i_1,\hat i_2,\cdots,\hat i_T\} I^={i^1​,i^2​,⋯,i^T​}，需要如何找出这些最优的状态值？
进行一些示例：

• 假设我们的状态序列$\mathcal{I}$在$t$时刻的状态变量 i t = q k ( k ∈ { 1 , 2 , ⋯   , K } ) i_t = q_k (k \in \{1,2,\cdots,\mathcal K\}) it​=qk​(k∈{1,2,⋯,K})的条件下，此时从初始概率分布出发，要如何表示最优序列对应的概率分布结果？

  • 基于上述假设和问题，首先观察：达到状态变量$i_t$共经过观测变量和状态变量 表示如下：
    $$o_1,o_2,\cdots ,o_t,i_1,i_2,\cdots ,i_{t-1},i_t=q_k$$
  • 基于这些变量，我们如何描述这些变量组成序列的优劣性：基于模型参数$\lambda$的 联合概率分布：
    $$P(o_1,o_2,\cdots ,o_t,i_1,i_2,\cdots ,i_{t-1},i_t=q_k\mid \lambda )$$
  • 联合概率分布结果越大，该序列就越优秀。如何获取联合概率分布的最大值？继续观察，其中$o_1,o_2,\cdots ,o_t$是观测变量，是已知项；实际只有通过对状态变量的合适选择，才能够找到最优的联合概率分布结果：
    记 $t$时刻状态变量$i_t=q_k$的条件下，最优概率分布结果为${\delta }_t(k)$，其表达式如下：
    $${\delta }_t(k)=\underset{i_1,i_2,\cdots ,i_{t-1}}{\max }P(o_1,o_2,\cdots ,o_t,i_1,i_2,\cdots ,i_{t-1},i_t=q_k\mid \lambda )$$

• 同理，如果将$t$时刻替换为$t+1$时刻，即状态变量$i_{t+1}=q_j$确定的条件下，依然从初始概率分布出发，其最优概率分布结果${\delta }_{t+1}(j)$ 的表达式如下：
  $${\delta }_{t+1}(j)=\underset{i_1,i_2,\cdots ,i_t}{\max }P(o_1,o_2,\cdots ,o_t,o_{t+1},i_1,i_2,\cdots ,i_t,i_{t+1}=q_j)$$

观察，${\delta }_t(k)$与${\delta }_{t+1}(j)$之间是否存在关联关系：

• 思考：如果不看${\delta }_t(k),{\delta }_{t+1}(j)$是最优概率分布结果，它们只是两条序列产生的联合概率分布，${\delta }_t(k),{\delta }_{t+1}(j)$之间仅相差两项：$i_{t+1}=q_j,o_{t+1}$。
• 而$o_{t+1}$依然是已知项，因此${\delta }_{t+1}(j)$相当于${\delta }_t(k)$的状态下，继续 执行了一次状态转移 得到$i_{t+1}=q_j$状态。即：
  $${\delta }_{t+1}(j)={\delta }_t(k)\cdot a_{kj}\cdot b_j(o_{t+1})$$
• 但又因为${\delta }_t(k),{\delta }_{t+1}(j)$都是最优概率分布结果，有必要 步骤2中执行的状态转移过程也是最优过程。
  而从$i_t\to i_{t+1}=q_j$的状态转移过程存在$\mathcal{K}$种情况，对应联合概率分布结果表示如下：
  $$\begin{gathered} i=1\to {\delta }_t(1)\cdot a_{1j}\cdot b_j(o_{t+1}) \\ i=2\to {\delta }_t(2)\cdot a_{2j}\cdot b_j(o_{t+1}) \\ ⋮ \\ i=\mathcal{K}\to {\delta }_t(\mathcal{K})\cdot a_{\mathcal{K}j}\cdot b_j(o_{t+1}) \end{gathered}$$
  从上述$\mathcal{K}$种结果中，必然存在一个最大值。该最大值对应的$i$就是能够产生最优过程 的状态值的编号：
  $${\delta }_{t+1}(j)=\underset{1\le k\le \mathcal{K}}{\max }[{\delta }_t(k)\cdot a_{kj}\cdot b_j(o_{t+1})]$$

至此，找到${\delta }_t(k)$和${\delta }_{t+1}(j)$之间的关联关系。
但${\delta }_t(k),{\delta }_{t+1}(j)$仅表示对应时刻最优联合概率分布，而实际需要的是一个最优序列。因此：
令${\varphi }_{t+1}(j)$表示从${\delta }_t(k)$到${\delta }_{t+1}(j)$选择状态转移最优的状态变量结果$q_k$对应的下标$k$。即：
$${\varphi }_{t+1}(j)=\underset{1\le k\le \mathcal{K}}{\mathrm{argmax}}[{\delta }_t(k)\cdot a_{kj}\cdot b_j(o_{t+1})]$$

最终得到下标序列： { ϕ 1 , ϕ 2 , ⋯   , ϕ T } \{\phi_1,\phi_2,\cdots,\phi_T\} {ϕ1​,ϕ2​,⋯,ϕT​}

相关参考：
机器学习-隐马尔可夫模型6-Decoding问题-Viterbi算法