机器学习笔记之隐马尔可夫模型——解码问题
引言解码问题介绍解码问题分析引言
上一节介绍了使用狭义EM算法对模型参数λ\lambdaλ。本节将介绍使用维特比算法(Viterbi)处理解码问题(Decoding)
解码问题介绍
在隐马尔可夫模型中，解码问题被看做为给定长度为TTT的观测序列{o1,o2,⋯,oT}\{o_1,o_2,\cdots,o_T\}{o1,o2,⋯,oT}，目标是求解观测序列O\mathcal OO对应状态序列I\mathcal II的后验概率P(I∣O)P(\mathcal I \mid \mathcal O)P(I∣O)。即：
在解码问题中，模型参数λ\lambdaλ是已知量，通常可以省略掉。
P(I∣O)=P(i1,i2,⋯,iT∣o1,o2,⋯,oT,λ)P(\mathcal I \mid \mathcal O) = P(i_1,i_2,\cdots,i_T \mid o_1,o_2,\cdots,o_T,\lambda)P(I∣O)=P(i1,i2,⋯,iT∣o1,o2,⋯,oT,λ)
实际上，解码问题与预测问题(Prediction)是存在一些差别的：
预测问题所表达的思想是，给定长度为ttt的观测序列O={o1,o2,⋯,ot}\mathcal O = \{o_1,o_2,\cdots,o_t\}O={o1,o2,⋯,ot}作为条件，求解下一时刻的观测变量ot+1o_{t+1}ot+1或者状态变量it+1i_{t+1}it+1的后验概率。即：
预测往往是给定前面若干时刻的观测序列，求解下一时刻的相关信息。
P(ot+1∣o1,o2,⋯,ot)P(it+1∣o1,o2,⋯,ot)P(o_{t+1} \mid o_1,o_2,\cdots,o_t) \\ P(i_{t+1} \mid o_1,o_2,\cdots,o_t)P(ot+1∣o1,o2,⋯,ot)P(it+1∣o1,o2,⋯,ot)解码问题更倾向于求解一个对应时刻的状态序列而不是未来时刻信息的判断。 即给定一个观测序列，将对应时刻的状态序列求解出来。
关于隐马尔可夫模型的相关概念、模型参数表示、模型特殊性质见机器学习笔记之隐马尔可夫模型(五)学习问题——EM算法中的场景介绍。
首先，需要明确解码问题的目标：在给定观测序列O\mathcal OO的条件下，找出一组后验概率最大的、与观测序列对应时刻的状态序列I\mathcal II。
假设观测序列O\mathcal OO的长度为TTT，那么最终寻找的最优状态序列I\mathcal II的长度也是TTT。因此，可以统计一下，到底存在多少种满足条件的状态序列：
由于it(t=1,2,⋯,T)i_t(t =1,2,\cdots,T)it(t=1,2,⋯,T)的取值范围是离散的，根据状态值集合Q={q1,q2,⋯,qK}\mathcal Q = \{q_1,q_2,\cdots,q_{\mathcal K}\}Q={q1,q2,⋯,qK}，因此，可以得到KT\mathcal K^TKT个不重复的状态序列组合。
即：随着序列长度TTT的增加，状态序列组合的数量随着指数级别增长。
而解码问题就是从KT\mathcal K^TKT个排列组合中选择出一个最优组合。
解码问题分析
什么是最优组合？最优组合满足的标准是什么？通过解码问题的目标可以看出，希望找到这样一组状态序列I^\hat {\mathcal I}I^使得关于I^\hat {\mathcal I}I^的后验概率P(I^∣O,λ)P(\hat {\mathcal I} \mid \mathcal O,\lambda)P(I^∣O,λ)最大。即：
I^=argmaxIP(I∣O,λ)\hat {\mathcal I} = \mathop{\arg\max}\limits_{\mathcal I} P(\mathcal I \mid \mathcal O,\lambda)I^=IargmaxP(I∣O,λ)
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}，需要如何找出这些最优的状态值？
进行一些示例：
假设我们的状态序列I\mathcal II在ttt时刻的状态变量it=qk(k∈{1,2,⋯,K})i_t = q_k (k \in \{1,2,\cdots,\mathcal K\})it=qk(k∈{1,2,⋯,K})的条件下，此时从初始概率分布出发，要如何表示最优序列对应的概率分布结果？
基于上述假设和问题，首先观察：达到状态变量iti_tit共经过观测变量和状态变量表示如下：
o1,o2,⋯,ot,i1,i2,⋯,it−1,it=qko_1,o_2,\cdots,o_t,i_1,i_2,\cdots,i_{t-1},i_t = q_ko1,o2,⋯,ot,i1,i2,⋯,it−1,it=qk基于这些变量，我们如何描述这些变量组成序列的优劣性：基于模型参数λ\lambdaλ的联合概率分布：
P(o1,o2,⋯,ot,i1,i2,⋯,it−1,it=qk∣λ)P(o_1,o_2,\cdots,o_t,i_1,i_2,\cdots,i_{t-1},i_t = q_k \mid \lambda)P(o1,o2,⋯,ot,i1,i2,⋯,it−1,it=qk∣λ)联合概率分布结果越大，该序列就越优秀。如何获取联合概率分布的最大值？继续观察，其中o1,o2,⋯,oto_1,o_2,\cdots,o_to1,o2,⋯,ot是观测变量，是已知项；实际只有通过对状态变量的合适选择，才能够找到最优的联合概率分布结果：
记ttt时刻状态变量it=qki_t=q_kit=qk的条件下，最优概率分布结果为δt(k)\delta_t(k)δt(k)，其表达式如下：
δt(k)=maxi1,i2,⋯,it−1P(o1,o2,⋯,ot,i1,i2,⋯,it−1,it=qk∣λ)\delta_t(k) = \mathop{\max}\limits_{i_1,i_2,\cdots,i_{t-1}} P(o_1,o_2,\cdots,o_t,i_1,i_2,\cdots,i_{t-1},i_t = q_k \mid \lambda)δt(k)=i1,i2,⋯,it−1maxP(o1,o2,⋯,ot,i1,i2,⋯,it−1,it=qk∣λ)
同理，如果将ttt时刻替换为t+1t+1t+1时刻，即状态变量it+1=qji_{t+1} = q_{j}it+1=qj确定的条件下，依然从初始概率分布出发，其最优概率分布结果δt+1(j)\delta_{t+1}(j)δt+1(j)的表达式如下：
δt+1(j)=maxi1,i2,⋯,itP(o1,o2,⋯,ot,ot+1,i1,i2,⋯,it,it+1=qj)\delta_{t+1}(j) = \mathop{\max}\limits_{i_1,i_2,\cdots,i_t} P(o_1,o_2,\cdots,o_t,o_{t+1},i_1,i_2,\cdots,i_t,i_{t+1} = q_j)δt+1(j)=i1,i2,⋯,itmaxP(o1,o2,⋯,ot,ot+1,i1,i2,⋯,it,it+1=qj)
观察，δt(k)\delta_t(k)δt(k)与δt+1(j)\delta_{t+1}(j)δt+1(j)之间是否存在关联关系：
思考：如果不看δt(k),δt+1(j)\delta_t(k),\delta_{t+1}(j)δt(k),δt+1(j)是最优概率分布结果，它们只是两条序列产生的联合概率分布，δt(k),δt+1(j)\delta_t(k),\delta_{t+1}(j)δt(k),δt+1(j)之间仅相差两项：it+1=qj,ot+1i_{t+1} = q_j,o_{t+1}it+1=qj,ot+1。而ot+1o_{t+1}ot+1依然是已知项，因此δt+1(j)\delta_{t+1}(j)δt+1(j)相当于δt(k)\delta_t(k)δt(k)的状态下，继续执行了一次状态转移得到it+1=qji_{t+1} =q_jit+1=qj状态。即：
δt+1(j)=δt(k)⋅akj⋅bj(ot+1)\delta_{t+1}(j) = \delta_t(k)\cdot a_{kj} \cdot b_j(o_{t+1})δt+1(j)=δt(k)⋅akj⋅bj(ot+1)但又因为δt(k),δt+1(j)\delta_t(k),\delta_{t+1}(j)δt(k),δt+1(j)都是最优概率分布结果，有必要步骤2中执行的状态转移过程也是最优过程。
而从it→it+1=qji_t \to i_{t+1}=q_jit→it+1=qj的状态转移过程存在K\mathcal KK种情况，对应联合概率分布结果表示如下：
i=1→δt(1)⋅a1j⋅bj(ot+1)i=2→δt(2)⋅a2j⋅bj(ot+1)⋮i=K→δt(K)⋅aKj⋅bj(ot+1)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}) \\ \vdots \\ i=\mathcal K \to \delta_t(\mathcal K)\cdot a_{\mathcal K j} \cdot b_j(o_{t+1})i=1→δt(1)⋅a1j⋅bj(ot+1)i=2→δt(2)⋅a2j⋅bj(ot+1)⋮i=K→δt(K)⋅aKj⋅bj(ot+1)
从上述K\mathcal KK种结果中，必然存在一个最大值。该最大值对应的iii就是能够产生最优过程的状态值的编号：
δt+1(j)=max1≤k≤K[δt(k)⋅akj⋅bj(ot+1)]\delta_{t+1}(j) = \mathop{\max}\limits_{1\leq k \leq \mathcal K} [\delta_t(k)\cdot a_{kj} \cdot b_j(o_{t+1})]δt+1(j)=1≤k≤Kmax[δt(k)⋅akj⋅bj(ot+1)]
至此，找到δt(k)\delta_t(k)δt(k)和δt+1(j)\delta_{t+1}(j)δt+1(j)之间的关联关系。
但δt(k),δt+1(j)\delta_t(k),\delta_{t+1}(j)δt(k),δt+1(j)仅表示对应时刻最优联合概率分布，而实际需要的是一个最优序列。因此：
令ϕt+1(j)\phi_{t+1}(j)ϕt+1(j)表示从δt(k)\delta_{t}(k)δt(k)到δt+1(j)\delta_{t+1}(j)δt+1(j)选择状态转移最优的状态变量结果qkq_kqk对应的下标kkk。即：
ϕt+1(j)=argmax1≤k≤K[δt(k)⋅akj⋅bj(ot+1)]\phi_{t+1}(j) = \mathop{\arg\max}\limits_{1 \leq k \leq \mathcal K} [\delta_t(k)\cdot a_{kj} \cdot b_j(o_{t+1})]ϕt+1(j)=1≤k≤Kargmax[δt(k)⋅akj⋅bj(ot+1)]
最终得到下标序列：{ϕ1,ϕ2,⋯,ϕT}\{\phi_1,\phi_2,\cdots,\phi_T\}{ϕ1,ϕ2,⋯,ϕT}
相关参考：
机器学习-隐马尔可夫模型6-Decoding问题-Viterbi算法
