自然语言处理——6.3 HMM之前向算法

作者: SpareNoEfforts | 来源:发表于2018-10-04 12:59 被阅读0次

解决问题1：快速计算观察序列概率 $p(O|\mu)$

给定模型 $\mu=(A, B, \pi)$ 和观察序列 $O＝O_1O_2 …O_T$ ，快速计算 $p(O|\mu)$ ：

1. 基本方法

对于给定的状态序列 $Q = q_1q_2…q_T$ , $p(O|\mu)$ ?

$\begin{array}{l} p(O|\mu ) = \sum\limits_Q {p(O,Q|\mu )} = \sum\limits_Q {p(Q|\mu )} \times p(O|Q,\mu )\\ p(Q|\mu ) = {\pi _{{q_1}}} \times {a_{{q_1}{q_2}}} \times {a_{{q_2}{q_3}}} \times ... \times {a_{{q_{t - 1}}{q_t}}}\\ p(O|Q,\mu ) = {b_{{q_1}}}({O_1}) \times {b_{{q_2}}}({O_2}) \times ... \times {b_{{q_t}}}({O_t}) \end{array}$

困难

如果模型 $\mu$ 有 $N$ 个不同的状态，时间长度为 $T$ ，那么有 $N^T$ 个可能的状态序列，搜索路径成指数级组合爆炸。

2. 解决方法：动态规——前向算法(The forward procedure)

1）基本思想：定义前向变量 ${\alpha _t}(i)$

${\alpha _t}(i) = p({O_1}{O_2}...{O_t},{q_t} = {S_i}|\mu )$

如果可以高效地计算 ${\alpha _t}(i)$ ，就可以高效地求得 $p(O|\mu)$ 。

因为 $p(O|\mu)$ 是在到达状态 $q_T$ 时观察到序列 $O = O_1 O_2 … O_T$ 的概率(所有可能的概率之和)：

$p(O|\mu ) = \sum\limits_Q {p({O_1}{O_2}...{O_t},{q_T} = {S_i}|\mu )} = \sum\limits_{i = 1}^N {{\alpha _T}(i)}$

动态规划计算 ${\alpha _t}(i)$ ：在时间 $t+1$ 的前向变量可以根据时间 $t$ 的前向变量 ${\alpha _t}(1),...,{\alpha _t}(N)$ 的值递推计算：
${\alpha _T}(j) = [\sum\limits_{i = 1}^N {{\alpha _T}(i)} {a_{ij}}] \times {b_j}({O_{t + 1}})$

自然语言处理——6.3 HMM之前向算法

解决问题1：快速计算观察序列概率 $p(O|\mu)$

1. 基本方法

困难

2. 解决方法：动态规——前向算法(The forward procedure)

1）基本思想：定义前向变量 ${\alpha _t}(i)$

2）算法6.1:前向算法描述：

3）算法的时间复杂性：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

NLP

自然语言处理——6.3 HMM之 前向算法

解决问题1：快速计算观察序列概率

1. 基本方法

困难

2. 解决方法：动态规——前向算法(The forward procedure)

1）基本思想：定义前向变量

2）算法6.1:前向算法描述：

3）算法的时间复杂性：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

NLP

自然语言处理——6.3 HMM之前向算法

解决问题1：快速计算观察序列概率 $p(O|\mu)$

1）基本思想：定义前向变量 ${\alpha _t}(i)$