隐马尔可夫语言模型

发表于 | 分类于

本文是2018年秋季计算语言学课程第5次作业的总结，任务为利用隐马尔科夫模型计算句子概率。

实验设置

  1. 按行分句。
  2. 计算状态转移矩阵和观测概率矩阵时考虑训练集中的单词词性。
  3. 忽略中括号及词组词性，去重后得到43个不重复的词性，作为隐藏状态。
  4. 忽略词性以及中括号，统计训练集、验证集和测试集的词语，得到55416个不重复的词语。
  5. 计算精度为小数点后1000位。

隐马尔科夫模型计算句子概率过程

以迈向/v 充满/v 希望/n 的/u 新/a 世纪/n为例，进行以下处理：

  1. 在句子首尾加上<bos>和<eos>得到新的句子<bos>/<bos> 迈向/v 充满/v 希望/n 的/u 新/a 世纪/n <eos>/<eos>
  2. 状态集合$Q={\langle bos \rangle ,v,u,n,a,\langle eos \rangle}$
  3. 观测集合$V={\langle bos \rangle,迈向,充满,希望,的,新,世纪,\langle eos \rangle}$

根据新的句子可得状态转移矩阵$A$如下：

$\langle bos \rangle$ $v$ $u$ $n$ $a$ $\langle eos \rangle$
$\langle bos \rangle$ 0 1 0 0 0 0
$v$ 0 0.5 0 0.5 0 0
$u$ 0 0 0 0 1.0 0
$n$ 0 0 0.5 0 0 0.5
$a$ 0 0 0 1.0 0 0
$\langle eos \rangle$ 0.166 0.166 0.166 0.166 0.166 0.166

同样可得观测概率矩阵$B$如下：

$\langle bos \rangle$ $迈向$ $充满$ $希望$ $的$ $新$ $世纪$ $\langle eos \rangle$
$\langle bos \rangle$ 1 0 0 0 0 0 0 0
$v$ 0 0.5 0.5 0 0 0 0 0
$u$ 0 0 0 0 1 0 0 0
$n$ 0 0 0 0.5 0 0 0.5 0
$a$ 0 0 0 0 0 1 0 0
$\langle eos \rangle$ 0 0 0 0 0 0 0 1

由于句子的开头总是$\langle bos \rangle$，因此初始状态分布$\pi = [1,0,0,0,0,0]$
这样就得到了一个隐马尔科夫模型$\lambda = (A,B,\pi)$

假设剔除词性后的观测序列(可以视为验证集和测试集中的句子)为<bos> 迈向 充满 希望 的 新 世纪 <eos>，则可以转化为向量$O=[0,1,2,3,4,5,6,7]$

前向算法

根据前向算法可以得到观测序列的概率$P(O|\lambda)$
定义到时刻$t$部分观测序列为$o_1,o_2,…,o_t$且状态为$q_i$的概率为前向概率，记作

计算过程如下
(1)初值

(2)递推，对$t=1,2,…,T-1$

(3)终止

经过计算可以得到该序列$O$的前向概率为$0.00390625$

后向算法

同样根据后向算法也可以得到观测序列的概率$P(O|\lambda)$，不同之处在于一开始不需要初始状态分布$\pi$参与计算，而是在终止时才加入初始状态分布$\pi$

定义在时刻$t$状态为$q_i$的条件下，到$t+1$到$T$的部分观测序列为$o_{t+1},o_{t+2},…,o_{T}$概率为后向概率，记作

(1)初值

(2)递推, 对$t=T-1,T-2,…,1$

(3)终止

经过计算可以得到该序列$O$的后向概率为$0.00390625$，与前向概率一致，验证了两个概率相等的结论。

根据上面计算的例子，可以统计所有训练集语料中词性的状态转移矩阵$A_(43 \times 43)$，训练集、（剔除了词性的）验证集和测试集语料中词性到词语的观测概率矩阵$B_{43 \times 55416}$（训练集中词性到词语的频数正常累加，而验证集和测试集中的新出现的词语的频数为0），从而使用前向算法和后向算法进行句子概率的计算。

N-gram语言模型结果对比及分析

隐马尔科夫模型结果

本次实验实现并测试了前向算法和后向算法，由于这2种方法得到的结果是相同的，因此最终提交了一份1.txt。可以从提交的1.txt中初步得到以下的观察结果：

  1. 总体按行分句的句子概率较小，平均句子概率在${10}^{-9}$到${10}^{-8}$数量级，有时会出现极小的概率，例如出现${10}^{-281}$数量级的情况。
  2. 有2456句句子出现概率为0的情况，考虑到计算精度已经很高（小数点后保留1000位），原因可能在于隐马尔可夫的观测概率矩阵和状态转移矩阵过于稀疏，大部分的元素都是0，对于在验证集和测试集语料中出现却未在训练集中出现的状态转移的处理能力较差，因此最终计算的概率为0的情况大概占了结果的一半左右。

而n-gram语言模型实验由于使用了各种平滑方法，对验证集和测试集的新词和低频词处理较好，没有出现句子概率为0的情况。

隐马尔科夫模型结果与N-gram语言模型结果对比

平均句子概率

方法 语料 平均句子概率 句子概率大小排序
add_one_bigram valid 4.23E-11 5
add_one_unigram valid 2.79E-07 3
back_off_trigram valid 1.06E-05 1
hmm valid 2.84E-09 4
good_turing_bigram valid 1.53E-13 6
good_turing_unigram valid 3.89E-07 2
方法 语料 平均句子概率 句子概率大小排序
add_one_bigram test 1.03E-10 6
add_one_unigram test 8.36E-07 4
back_off_trigram test 1.01E-05 2
hmm test 1.16E-08 5
good_turing_bigram test 7.07E-03 1
good_turing_unigram test 1.36E-06 3

如果一句句子中大部分的词语都有一个较高的概率，那么通过$P(w_1,w_2,…,w_n )=\subseteq_{i=2}^{N} P({w_i} | w_{i-(n-1) }…w_{i-1})$得到的句子概率（n-gram方法）也会较高，不同句子之间进行概率比较的差距也会更明显。

因此从上表中可以看出，隐马尔科夫模型计算出的平均句子概率处于中等偏低的水平，分别排在第4（valid语料）和第5（test语料）的位置，侧面反映出隐马尔科夫模型对验证集和测试集语料的适应性一般，或者说通过训练集语料构建的隐马尔科夫模型对于预测未出现在训练集中的验证集和测试集语料时，对于所预测的句子的置信度不高。

概率差异平均排序

集合中的每句句子$S_j$，5种n-gram模型分别会计算出概率$p_0,p_1,p_2,p_3,p_4$，分别与隐马尔科夫模型的概率$p_{hmm}$进行相减后取绝对值（$|p_{hmm}-p_i |$），再进行排序得到顺序$r_0,r_1,r_2,r_3,r_4$，然后对于每种n-gram模型的所有句子得到的顺序$\frac{\sum_{j=1}^{n}{r}_{ij}}{n}$进行平均，从而得到该方法与隐马尔科夫模型的概率差异平均排序结果，如下面2张表格所示：

方法 语料 概率差异排序平均值
add_one_bigram valid 1.722009569
add_one_unigram valid 1.340669856
back_off_trigram valid 1.758851675
good_turing_bigram valid 2.864114833
good_turing_unigram valid 2.314354067
方法 语料 概率差异排序平均值
add_one_bigram test 1.667934783
add_one_unigram test 1.43423913
back_off_trigram test 1.842934783
good_turing_bigram test 2.773369565
good_turing_unigram test 2.281521739

所以总体来看，add_one_unigram方法得到的概率与隐马尔科夫模型得到的概率最接近，其次时add_one_bigram方法，然后是back_off_trigram方法，之后是good_turing_unigram方法，而good_turing_bigram得到的概率与隐马尔科夫模型得到的概率相差最远。

参考资料

[1] 李航 (2012) 统计学习方法. 清华大学出版社, 北京.