NLP复习

HMM

  • 用 $q_t$ 表示 t 时刻的状态

  • 状态集合:$S = {S_1, …, S_N}$

  • 输出符号集合:$O = {O_1, …, O_M}$
  • 状态转移矩阵:$A = a_{ij} = P(q_{t+1} = S_j | q_t = S_i)$,对 j 从 1 到 N 求和,结果为 1,因为从 i 出发总会到达 1~N 中的一个状态的
  • 可观察符号的概率分布矩阵:$B = b_j(k)$,表示在状态 j 时输出符号 $v_k$ 的概率。$b_j(k) = P(O_t = v_k | q_t = S_j)$,对 k 从 1~M求和的结果为 1,因为一个状态总有一个输出符号。
  • 初始状态概率:$\pi_i = P(q_1 = S_i)$

评估问题

给定观察序列(输出符号的集合)和模型,如何计算给定模型下此观察序列的概率 $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:

看了这个图就明白了:

前向算法

可参考这篇博客.

  • 后向概率:给定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)

搭配

参考这篇博客

Author

preccrep

Posted on

2021-10-26

Updated on

2021-10-27

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.