NLP复习

评估问题

给定观察序列(输出符号的集合)和模型，如何计算给定模型下此观察序列的概率 $P(O | \lambda)$

前向算法、后向算法、前向-后向算法

前向算法

前向变量：HMM在时间 t 输出序列 O1…Ot，并且位于状态 i 的概率 $\alpha_t(i) = P(O_1O_2…O_t, q_t = S_i |\lambda)$

就是当给出模型参数的时候，计算一个观测序列和第 t 时刻为状态 $S_i$ 的联合概率，是一个递推的过程

初始状态下与模型无关，模型是在求后来状态时用上的。所以给定 O1…OT：

$$\alpha_1(i)=P(O_1,q_1=S_i|\lambda)=P(O_1,q_1=S_i)=P(q_1=S_i)P(O_1|q_1=S_i)=\pi_i b_i(O_1)$$ $$P(O|\lambda)=\sum_{i=1}^N(\alpha_T(i))$$

看了这个图就明白了：

可参考这篇博客.

• 后向概率：给定HMM模型 $\lambda$，在时刻 t 状态为 $S_i$ 的条件下，从 t+1 到 T 的部分观测序列的概率

解码问题

给定观察序列和模型，如何计算状态序列使得该状态序列能最好地解释这个观察序列：$Q^* = argmax_Q{P(Q | O, \lambda)}$

就是说，给定N个状态q1…qN，要找它们的一个排列使得给定顺序的M个输出组成的序列在模型下被最好解释。

即，对于每一个输出Oi，可以有N个可能的状态。

因此，复杂度是 $N^M$.

要用好一点的算法：Viterbi

基于Viterbi变量的动态规划算法

Viterbi变量：在时间 t 沿状态序列 q1…qt 且 qt = Si 产生出O1…Ot的最大概率

Viterbi 变量说明的是，从初始状态到 t 时刻的状态 Si 的所有路径中，必有一条路径，能够使得你观察到 O1O2…Ot 序列的概率最大，也即这条路径最好的解释了 O1O2…Ot 序列的出现。

这一部分看书吧，参照李航《统计学习方法》。

学习问题

给定观察序列，如何调节模型参数使得 $P(O | \lambda)$ 最大

如果产生观察序列O的状态序列已知，则可以使用最大似然估计来计算HMM的参数

期望值最大化算法(Expectation-Maximization, EM)

搭配

参考这篇博客