顿搜
飞过闲红千叶，夕岸在哪
类目归类
韦特比(Viterbi)算法与解码问题——隐马尔可夫疑难问题二
09/14
解码问题
如果对隐马尔科夫模型不了解，请点这里问题描述
给定隐马尔科夫模型 $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$
