拼音输入法

人工智能导论课程作业

[TOC]

---

概述

1. 实现基于隐马尔可夫模型和维特比算法的拼音输入法

2. 训练集使用了网络学堂提供的训练集，在此基础上又自己寻找了一部分稍偏向日常用语的网络资源进行了训练

3. 在网络学堂提供的测试集当中达到了句44%、字85%的正确率

4. 在命令行中运行viterbi.py并指定输入输出文件，运行命令如下：

   python viterbi.py input.txt output.txt
   

原理与实现

抽象模型

求使得 $P(s) = ΠP(w_i|w_{i−1}) $最大的句子。

二元模型当中，将每个单独的拼音作为一个节点$P(w_i)$，通过统计二元词汇出现频率作为$P(w_i|w_{i-1})$ ，通过动态规划(维特比算法)的方式求出$P(s)max$，得出生成的语句。

在三元模型当中，对于词组abc，ab作为一个节点$P(w_{i-1})$，c作为节点 $P(wi)$，$P(w_{i-1})$代表两个汉字，$P(wi)$代表一个汉字。其他与二元模型同理。

算法实现细节

字典集

• 对语料进行中文过滤、分词与词频统计
  • 分词之后得到的词语长度如果>3，例如abdc，那么在统计2元字典集时作为3个词：ab,bc,cd，在统计3元字典集时作为2个词：abc,bcd
• 由于给出的语料偏向新闻方面，因此自己在网络上收集了其他的语料并进行了处理
• 如上得到的字典集存在可能的问题是，在二元和三元字典集当中可能会统计入奇怪且无意义的词。因此对字典集进行筛选，二元字典集当中出现次数少于20、三元字典集中出现次数少于10的词语会被删掉。
• 最终得到的文件为：
  • word1_b.txt
  • word2_b.txt
  • word3_b.txt

对概率取对数

由于每个词语本身的概率较小，为了减小误差和抖动，在计算初始概率及转移概率时均对概率取对数并取相反数。

相应地，在进行状态转移时最优的选择是值最小的节点。

---

案例分析与优化

通过一些简单的案例进行测试，并对输入法进行了一定优化

优化算法为三元

小花帽（小花猫）

在二元字典集当中，“花帽”出现的次数为2692，花猫出现的次数为832；在一元字典集中，“猫”的出现次数为295127，“帽”的出现次数为355838。因此在二元方式当中，“小花”和“花猫”之间缺少联系，且“花帽”“帽”的次数均高于“花猫”和“猫”，因此自然会得出“小花帽”的结果。

而在三元字典集当中，“小花猫”出现353次，并没有“小花帽”出现。

因此对算法进行优化，使用三元viterbi算法，在优化后可以得出正确结果。

经过测试，优化并加入平滑后的字句正确率都有明显提升（分别为0.85、0.44）

调整训练集

中华人民工鹤椁（中华人民共和国）

与此同时，输入“中华人民”和“共和国”都可以正常显示。检查训练得到的字典，发现没有“民共和”或“人民共”之类的词，说明在训练集上出现了一定的问题。为此重新进行分词和训练，同时，将训练集进行优化，去除二元及三元中出现次数过少的词语，防止过度拟合。在优化训练集后则可以正确显示“中华人民共和国”。

调整参数的值

调整lamda1的值

在二元情况下，针对不同的lamda以及网络学堂上提供的样例进行了测试**（共563句，5662字）**，结果如下：

lamda1	正确句子数	句子正确率	正确字数	字正确率
0	129	0.24067164179104478	4390	0.7753444012716355
0.05	130	0.24253731343283583	4431	0.782585658777817
0.1	131	0.24440298507462688	4444	0.7848816672553868
0.2	134	0.25	4480	0.7912398445778877
0.25	136	0.2537313432835821	4486	0.7922995407983044
0.3	134	0.25	4468	0.7891204521370541

可以看出，在lamda=0.25左右时，字、句正确率均达到最高，当lamda继续增大时（即过度平滑时）lamda会继续降低。和其他同学交流后发现，和他们得到的数据相比，我的lamda取值偏大。原因在于我在计算概率时取了对数，而利用lamda进行平滑时仍然使用了和概率相乘的方式。

花开花落骅墁舔（花开花落花满天）

在优化为3元之后，出现了以上的错误句子。而分析情况后发现，“花开花落”可以正确显示，“花满天”也可以正确显示，“落花”也可以正确显示，然而“花落花”和“落花满”都无法正确显示。因此得出结论，在三元模型当中的lamda也取了一个不是特别合适的值，因此需要调整lamda的值，用二元进行平滑。

在平滑之后，有很大的改进，结果为花开花落花漫天。为此检查字典集，发现在一元字典集当中，“满”的出现概率高于“漫”，在二元字典集当中，“满天”也高于“漫天”。但是在三元字典集当中有"花漫天"而没有“花满天”，因此输出结果为“花漫天”。

调整lamda2的值

由于时间所限，在lamda1固定（0.25）的情况下调整lamda2。发现lamda2在取大约0.1时，样例的正确率取最大值。但是只要进行了平滑，lamda2具体取值多少产生的影响并不大，是否进行平滑产生的影响才大。

原因在于，假设一个三元组在训练集当中曾经出现，但是后两个字的二元组以及单字出现频率都很低；另一个三元组没有出现过，但后两个字的二元组以及单字在训练集中出现频率较高。而由于对概率取了对数，那么出现概率的影响会被进一步放大，因此只要加上一点点系数就可以对结果产生影响。（共563句，5662字）

lamda2	正确句子数	句子正确率	正确字数	字正确率
0.0（未平滑）	183	0.3414179104477612	3793	0.6699046273401625
0.05	238	0.44402985074626866	4832	0.8534086895090074
0.1	241	0.4496268656716418	4841	0.8549982338396327
0.15	240	0.44776119402985076	4834	0.8537619215824797
0.20	239	0.4458955223880597	4825	0.8521723772518545

优化后得到的最终结果

正确例子

由于加入了更加偏向日常用语的数据集，因此在新闻类和日常用语类当中都有一定的正确率

新闻类

中华人民共和国中央人民政府

以习近平同志为总书记的党中央

走中国特色社会主义道路

互联网产业有巨大潜力

中国贫困地区实现网络服务全覆盖

走出清华大学特色的世界一流大学道路

日常用语类

一只漂亮的小花猫

一只可爱的大黄狗

哲学是一切学科的基础

预计下周有大暴雨

高考成绩在今天上午公布

我经常去健身房锻炼

名牌大学的研究生

错误例子

北京 市 一个美丽的城市（北京 是 一个美丽的城市）

在三元字典集当中有“北京市”，根据算法会优先使用三元字典集当中的词语。对于此类句子，如果想要得出正确结果，需要对句子结构做出一定分析。类似的问题还有：

郑和下西洋 味 青花瓷的迅速崛起提供了历史契机（郑和下西洋 为 青花瓷的迅速崛起提供了历史契机）

弹簧 的长裙和蓬松的头发（淡黄 的长裙和蓬松的头发）

“弹”为多音字，因此出现更多的“弹tan簧”被当作“淡dan黄”给出了更高的概率估计。类似的问题还出现在：

yin xing 银行

网络上 握 重拳出击（网络上 我 重拳出击）

由于使用了三元模型，“握重拳”之间的关联比“我重拳”要更大一些，因此给出了如上的结果。不过似乎“网络上握重拳出击”本身也是一个合理的句子，因此不必对此例子过度拟合。

---

致谢

感谢我的小伙伴们在算法思路、数据集等方面对我的诸多帮助：

xy、yyr、@xy-plus、tzy