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

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

自然语言处理——6.3 HMM之前向算法
自然语言处理——6.4 HMM之后向算法
NLP第8课：从自然语言处理角度看 HMM 和 CRF
自然语言处理N天-Day0801从自然语言处理角度看HMM和CR
NLP第8课：从自然语言处理角度看 HMM 和 CRF
自然语言处理中的分词算法实现
HMM学习最佳范例七：前向-后向算法4
【NLP】用于语音识别、分词的隐马尔科夫模型HMM
条件随机场模型简单介绍(2)
HMM之前向算法

解决问题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}})$

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

3）算法的时间复杂性：

自然语言处理——6.3 HMM之前向算法
解决问题1：快速计算观察序列概率给定模型和观察序列，快速计算： 1. 基本方法对于给定的状态序列 ,? 困难...
自然语言处理——6.4 HMM之后向算法
1. 基本思想定义后向变量是在给定了模型和假定在时间状态为的条件下，模型输出观察序列的概率： ……（公式6....
NLP第8课：从自然语言处理角度看 HMM 和 CRF
近几年在自然语言处理领域中，HMM（隐马尔可夫模型）和 CRF（条件随机场）算法常常被用于分词、句法分析、命名实体...
自然语言处理N天-Day0801从自然语言处理角度看HMM和CR
近几年在自然语言处理领域中，HMM（隐马尔可夫模型）和 CRF（条件随机场）算法常常被用于分词、句法分析、命名实体...
NLP第8课：从自然语言处理角度看 HMM 和 CRF
近几年在自然语言处理领域中，HMM（隐马尔可夫模型）和 CRF（条件随机场）算法常常被用于分词、句法分析、命名实体...
自然语言处理中的分词算法实现
最近实现的3种中文分词算法基于最大匹配（前向匹配、后向匹配、双向匹配） HMM n-gram 基于最大匹配算法（...
HMM学习最佳范例七：前向-后向算法4
七、前向-后向算法(Forward-backward algorithm) 隐马尔科夫模型（HMM）的三个基本问题...
【NLP】用于语音识别、分词的隐马尔科夫模型HMM
大家好，今天介绍自然语言处理中经典的隐马尔科夫模型(HMM)。HMM早期在语音识别、分词等序列标注问题中有着广泛的...
条件随机场模型简单介绍(2)
隐马尔可夫模型介绍 HMM的3个基本问题: 1/概率计算:前向算法,后向算法 2/学习问题:已知状态序列的时候可以...
HMM之前向算法
HMM基于两大假设：（1）齐次马尔科夫假设：存在于状态之间，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前...

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