自然语言处理——6.5 Viterbi搜索算法

2018-10-04 本文已影响8人 SpareNoEfforts

解决问题2：如何发现“最优”状态序列、能够“最好地解释”观察序列

解释不是唯一的，关键在于如何理解“最优”的状态序列？

1. 解释1

一种解释是：状态序列中的每个状态都单独地具有概率，对于每个时刻 $t(1 \le t \le T)$ ，寻找 $q_t$ 使得
${\gamma _t}(i) = p({q_t} = {S_i}|O,\mu )$ 最大

问题

每一个状态单独最优不一定使整体的状态序列最优，可能两个最优的状态 ${{\hat q}_t}$ 和 ${{\hat q}_{t+1}}$ 之间的转移概率为0，即 ${a_{{{\hat q}_t}{{\hat q}_{t + 1}}}} = 0$

2. 解释2

在给定模型 $\mu$ 和观察序列 $O$ 的条件下求概率最大的状态序列：
$\hat Q = \mathop {\arg \max }\limits_Q p(Q|O,\mu )$
Viterbi 算法: 动态搜索最优状态序列。
定义：Viterbi 变量是在时间 $t$ 时，模型沿着某一条路径到达 $S_i$ ，输出观察序列 $O＝O_1O_2 …O_t$ 的最大概率为：
${\delta _t}(i) = \mathop {\max }\limits_{{q_1}{q_2},...,{q_{t - 1}}} p({q_1}{q_2},...,{q_t} = {S_{i,}}{O_1}{O_2}...{O_t}|\mu )$ …… (公式6.22)