github.com/xalanq/pinyin-ime

环境

• CPU: i7-4810MQ 2.80GHz 8核
• RAM: DDR3 1600 16GB
• SSD: Kinston UV500 120G SSD
• rustc 1.33.0 (2aa4c46cf 2019-02-28)
• cargo 1.33.0 (f099fe94b 2019-02-12)
• 能并行的地方基本上都并行了

数据预处理

　　数据预处理非常重要，因为预测的算法大家都差不多，且原始数据噪音很多（数字、字母、标点等），所以处理数据对算法准确率影响很大。

　　首先是处理原始数据：

• 提取出 html 和 title 域的内容；
• 去掉 html 里开头的 原标题 以及和 title 重复的内容，并将 记者 栏和后面的正文用空格分开；
• 如果出现数字：若数字值不超过 1000，则翻译成日常读法（十、十一、一百零一），否则将数字直译成中文小写数字（零一二三四五六七八九）；
• 如果出现空白字符、断句标点 ，。：？！ 等则进行断句；
• 不在一、二级汉字（助教所给的文件）里的字符（包括字母、、《》“”这种非断句标点等），全部变成未知字符 _。

　　接下来是词库和拼音：

• 对于基于词的模型，我从 fighting41love/funNLP 收集了大量中文词库，然后过滤一下，保留满足汉字均为一、二级汉字，长度最长为7的所有词，总计665263个；
• 对于基于字的模型，将一、二级汉字表看做是长度为 1 的词就好啦；
• 每一个词是这样注音的（注音对模型影响相当大）：
  • 从现有词库（open-gram）已标注的拼音里，找到该词拼音（包括多个拼音）；
  • 若找不到拼音，则用 rust-pinyin 转化拼音（只取一个拼音）；
  • 最后人工筛掉单个汉字的生僻、不靠谱的拼音，比如 丁 的 zheng 读音（在 zdic.net 查询拼音，人工筛了好久QAQ）。

　　然后用 jieba-rs 对句子分词（不用 HMM，词库为自己的词库），统计 n-gram（的频率）数据。同时考虑到句子开头，我便加了一个特殊字符 ^，在预测时均已该字符作为起点。

　　由于助教未提供 dev 数据集，因此我将 2016-11.txt 这个文件单独拿出来，作为 dev 数据集，用于评估模型；剩余数据加上老师给的学生测试数据当做 train 数据集，用于训练模型。

　　具体生成 dev 数据集的细节如下：

• 先用前边的做法，将原始数据生成为仅包含一二级汉字、未知字符 _ 的句子集合；
• 丢掉长度小于 5 或者长度大于 15 或者包含未知字符 _ 的句子；
• 随机打乱句子次序，截取前 3000 个句子；
• 剩余句子里，每个句子用 jieba-rs 分词（不用 HMM，词库为自己的词库），然后每个词用词库里的第一个拼音标注，拼接起来得到整个句子的拼音。

　　报告后面评估模型的好坏，都以该 dev 集的结果为准（当然最后还是要以助教所用的 test 数据集测得的结果为准）。具体句子见 dev/input.txt 和 dev/answer.txt。

　　预处理运行效率是这样的，从助教所给的 1G 原始文件开始，只需要 3 分钟左右，可以一次性生成完上述所说的所有数据，具体可以看 main.rs 里注释掉的代码。

预测

原理

　　整体模型是 n-gram 的隐马尔科夫模型（HMM）。对于 2-gram 的词模型来说，一个句子 S 的概率就是

P(S) = P(w_0) \prod_{i=1}^{n} P(w_i | w_{i-1})

　　其中 w_0 = ^，即句子开头的特殊字符；P(w_i | w_{i-1}) = P(w_{i-1} w_i) / P(w_i)。由于 P(w_0) 都一样，因此可以视为最大化这个值

P(S) = \prod_{i=1}^{n} P(w_i | w_{i-1})

　　不过有时会出现 P(w_i | w_{i - 1}) = 0 的情况，因此需要平滑一下，新的 P(w_i | w_{i-1}) 这样得到

P(w_i | w_{i - 1}) = \lambda P(w_i | w_{i - 1}) + (1 - \lambda) P(w_i)

　　具体计算概率的方式是：

P(w_i) = \frac{n_i}{\sum_j n_j} \qquad P(w_i | w_{i - 1}) = \frac{n_{i-1,i}}{\sum_j n_{i-1,j}}

　　其中 n_i 为整个语料 w_i 的出现次数， n_{i-1,i} 为整个语料 w_{i-1} w_i 的出现次数。

　　最后一个技巧是取 log 将乘法变成加法，以降低精度损失以及加快速度，即我们要最大化

\log P(S) = \sum_{i=1}^{n} \log P(w_i | w_{i-1})

实现

　　由于加了平滑，三元模型、四元模型的整个状态图的边会变得很多，且这些边大多边权很小，直接 DP 比较蠢且慢。问题的本质是要求一个隐式状态图的最长路，故状态、边不一定要一开始就全建出来，而是应该边跑边拓展。考虑使用带剪枝的 Dijkstra 来跑最长路，下面以三元模型作为例子。

　　假如给定了一个拼音序列 s_0, s_1, \cdots, s_{m-1}，整个状态图是这样的：

• 状态是一个三元组 (pos, w_1, w_2)，其中：
  • pos 表示经过了多少个拼音，下一个词从该位置开始；
  • w_1 表示 pos 位置前的第一个词；
  • w_2 表示 pos 位置前的第二个词。
• 初始状态：(0, ^, ^)；
• 终止状态：pos = m 的状态；
• 边集：对于状态 (pos, w_1, w_2)，若以 pos 开始，存在一个词 w 匹配拼音序列 s_{pos}, s_{pos+1}, \cdots, s_{pos+|w|-1}，则有一条到状态 (pos + |w|, w, w_1) 的边，边权是 \log P(w | w_2 w_1)。

　　然后用 Dijkstra 跑最长路即可，不存边集。

　　剪枝是，当一个终止状态加入到堆里的时候，记录下该状态的概率值，将来所有小于该概率的状态都不用考虑拓展了（因为概率是递减的）。

结果

　　下面是运行之前所说的 dev 数据集的一些模型结果：

　　F1 score（wiki，具体计算方法可看eval.rs，下表单位是百分比）：

　　整句准确率（下表单位是百分比）：

　　用时（预处理 + 预测，下表单位是秒）：

　　可以明显看出规律：

1. \lambda 与 F1 或 整句准确率 的关系看起来是一个单峰函数；
2. 除了四元模型外，\lambda 越大，预测速度越快；
3. 三元字模型是最好的字模型，二元词模型是最好的词模型；
4. 好的字模型的 \lambda 往往比好的词模型的 \lambda 要大；
5. 二元字、词模型真的是运算飞快啊！

　　为何二元字模型不如三元字模型好，但二元词模型却好于三元词模型？分别取每个模型最好的结果生成的输出文件（见dev/output/文件夹）来一探究竟（取前5条结果）。

　　二元字模型有两个主要缺点：
　　1. 一是只能考虑前面的那个字，这样会导致每次做选择时，总是选择出现频率最高的那个词。比如第 5 句中，由于二元组（“一”，“五”）出现次数比（“义”，“务”）要多，因此就选择了前者；
　　2. 其次，没有出现或者出现很少的二元组的概率就只能靠平滑，而二元组后面那个字的若出现次数过多或过少，会大大影响整体概率。比如第 1 句中，二元组（“目”，“快”）、（“目”，“会”）（“会”有 kuai 这个读音）出现次数很少，而“会”的出现次数（1252393）比“快”的出现次数（362804）高得多，因此经过平滑后，前者的概率就远远小于后者。同时由于前者的其它词的概率也不够大，不足以拯救整个句子的概率，于是第 1 个句子就变成了”目会“的那个句子。

　　三元字就稍微好一些，因为长度变长，二元字的第 1 个缺点就会变弱一些（三元组（“之”，“一”，“五”）出现次数显然不会比（“知”，“义”，“务”）多）；但由于三元组变多，条件概率变小，因此二元字的第 2 个缺点会放大（从最好字模型的 $\lambda$ 取值变大也能验证此说法）。不过由于缺点 1 的减弱导致了第 2 个句子的其他部分（三元组（“动”，“工”，“了”）等）概率增大，因此整个句子的概率被救了回来，输出了正确的句子。

　　四元字同理，只是缺点 2 放大的程度超过了缺点 1 减小的程度，因此整体效果还不如三元字。

　　接下来看词模型。

　　首先词模型相比于字模型的第一个好处是，将字也视作一个词，从而字模型是词模型的子集，理论上词模型不会比字模型差；第二个好处是，词的长度是多样的，字模型的缺点 1 出现次数的问题会大大改善，这也是为什么相同元的模型下，词模型要比字模型要好的原因。

　　若语料库分词情况不理想，则缺点 1 其实也会受到影响，因此要选一个好点的分词库；同时很容易能看出，字模型的缺点 2 仍是词模型的缺点，比如说第 2 句，同样由于语料库缺少二元组（“项目”，“会”），导致比较的仍是平滑后得到的“会”和“快”的概率，于是第 2 句出现了同样问题。就算是三元词模型也拯救不了，因为（“这个”，“项目”，“快”）的出现次数和（“这个”，“项目”，“会”）的出现次数都很小，而且差的也很小，所以救不回来了。

　　由于词模型的缺点 1 固定了，而维数越高缺点 2 就越严重，因此三元、四元词模型还不如二元词模型。至于为何四元词模型的 \lambda 反而变小了，我觉得，这就涉及到我的知识盲区了.jpg

　　看这二元、三元速度都挺快，准确率也高，于是我就将这二者结合起来，形成二、三元组合词模型，结果如下：

　　F1 score：

　　整句准确率：

　　预处理+预测时间：

　　可以发现，效果更棒棒了！因此我选择二、三元组合词模型作为最终模型。

　　经过我的三分调参后，我得到了可能是最佳的 \lambda = 0.62859，F1是 94.8 %，整句准确率是 75.8 %。

改进

　　对于缺点 1，我觉得只要语料库足够贴近测试集，词模型的分词足够好，那么就能很好的解决这个缺点；对于缺点 2，我觉得能做的或许是换一种平滑方式，但暂时想不出比线性平滑更好的做法。

参考

[1] 基于统计语言模型的拼音输入法 byvoid
[2] open-gram项目简介
[3] sunpinyin/open-gram
[4] fighting41love/funNLP
[5] rust-pinyin
[6] jieba-rs
[7] zdic.net