韦特比(Viterbi)算法与解码问题——隐马尔可夫疑难问题二

/ NLP / 没有评论 / 328浏览

解码问题

如果对隐马尔科夫模型不了解,请点这里

问题描述

给定隐马尔科夫模型 $h = ( A, B, \pi )$
给定观察序列 $O = ( o_1 o_2 o_3 … o_T )$
寻找一个状态转换序列 $q = (q_1 q_2 q_3 … q_T )$,使得该状态转换序列最有可能产生上述观察序列

计算方法

对每一个状态转换序列 q 计算 $P(O, q |h)$
$q^{*}$ 是使 $P(O, q |h)$ 取最大值的状态转换序列
那么 $q^{*}$ 就是能最好解释观察序列的状态转换序列,即:

$$q^{*} = \underset{q}{\mathrm{argmax}} P(O,q|h)$$

存在的问题

韦特比算法

英文名:Viterbi Algorithm

韦特比变量

$$\delta_{t}(i) = \max_{q_{1}q_{2},...,q_{t-1}} \left [ P(q_{1}q_{2}...q_{t-1}q_{t} = i,o_{1}o_{2}...o_{t} |h ) \right ]$$

$\delta_{t}(i)$ 指在时刻 t 处于状态 i ,观察到 $o_1o_2…o_t$ 的最佳状态转换序列 $q_1q_2…q_t$ 的概率。

递推公式

显然 $\delta_{1}(i) = \pi_{i}b_{i}(o1), \quad 1 \le i \le N$

若$\delta_{t}(i)(1 \le i \lt N)$已知,则

$$\delta_{t+1}(j) = \left [ \max_{1 \leq i \lt N} \ \delta_{t}(i) a_{ij} \right ] b_{j}(O_{t+1})$$

路径记录

设定 T 个数组 $Y_{1}(N), Y_{2}(N), …Y_{T}(N)$

$Y_{t}(i)$表示在时刻 t 到达状态 i 的最佳状态转换序列 t-1 时刻的最佳状态。

显然 $Y_{1}(i) = 0$

若 $\delta_{t}(i)(0 \le i \lt N)$ 已知,则

$$Y_{t+1}(j) = \underset{1 \leq i \lt N}{\mathrm{argmin}} \left [\delta_{t}(i) a_{ij} \right ]$$

终止时

$$P^{*} = \max_{1 \leq i \leq N} \left [ \delta_{T}(i) \right ] \qquad q_{t}^{*} = \underset{1 \leq i \leq N}{\mathrm{argmax}} \left [ \delta_{T}(i) \right ]$$

求解最佳路径 $q_{t}^{*} = Y_{t+1}(q_{t+1}^{*}),\quad t = T-1, T-2,...,1$