本文是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=⟨bos⟩,v,u,n,a,⟨eos⟩
3. 观测集合V=⟨bos⟩,迈向,充满,希望,的,新,世纪,⟨eos⟩

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

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

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

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

根据前向算法可以得到观测序列的概率P(O|λ)
定义到时刻t部分观测序列为o1,o2,…,ot且状态为qi的概率为前向概率，记作

αt(i)=P(o1,o2,…,ot,it=qi|λ)

计算过程如下
(1)初值

α1(i)=πibi(o1),i=1,2,…,N

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

αt+1(i)=[N∑j=1αt(j)aji]bi(ot+1),i=1,2,…,N

(3)终止

P(O│λ)=N∑i=1[αT(i)]

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

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

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

βt(i)=P(ot+1,ot+2,…,oT|it=qi,λ)

(1)初值

α1(i)=πibi(o1),i=1,2,…,N

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

βt(i)=N∑j=1[aijbj(ot+1)]βt+1(j),i=1,2,…,N

(3)终止

P(O│λ)=N∑i=1πibi(o1)β1(i)

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

根据上面计算的例子，可以统计所有训练集语料中词性的状态转移矩阵A(43×43)，训练集、（剔除了词性的）验证集和测试集语料中词性到词语的观测概率矩阵B43×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语言模型结果对比

平均句子概率

如果一句句子中大部分的词语都有一个较高的概率，那么通过P(w1,w2,…,wn)=⊆Ni=2P(wi|wi−(n−1)…wi−1)得到的句子概率（n-gram方法）也会较高，不同句子之间进行概率比较的差距也会更明显。

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

概率差异平均排序

集合中的每句句子Sj，5种n-gram模型分别会计算出概率p0,p1,p2,p3,p4，分别与隐马尔科夫模型的概率phmm进行相减后取绝对值（|phmm−pi|），再进行排序得到顺序r0,r1,r2,r3,r4，然后对于每种n-gram模型的所有句子得到的顺序∑nj=1rijn进行平均，从而得到该方法与隐马尔科夫模型的概率差异平均排序结果，如下面2张表格所示：

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

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