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)
  • 能并行的地方基本上都并行了

数据预处理

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

  首先是处理原始数据:

  • 提取出 htmltitle 域的内容;
  • 去掉 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.txtdev/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,下表单位是百分比):

$\lambda$0.000010.010000.100000.250000.500000.750000.900000.990000.99999
二元字50.358.775.981.484.585.986.586.386.1
三元字50.371.487.890.591.692.192.492.592.2
四元字50.374.786.388.088.789.289.589.789.8
二元词88.591.393.394.094.594.794.593.489.5
三元词88.791.492.292.592.892.993.092.892.4
四元词88.790.691.291.391.691.891.891.490.5

  整句准确率(下表单位是百分比):

$\lambda$0.000010.010000.100000.250000.500000.750000.900000.990000.99999
二元字0.93.320.932.539.743.945.545.545.1
三元字0.916.650.358.863.265.666.767.266.5
四元字0.930.351.855.056.557.958.559.159.1
二元词50.560.469.072.174.474.974.471.159.8
三元词51.262.365.566.467.467.867.867.567.0
四元词51.359.361.562.063.163.363.162.561.3

  用时(预处理 + 预测,下表单位是秒):

$\lambda$0.000010.100000.100000.250000.500000.750000.900000.990000.99999
二元字1+01+01+01+01+01+01+01+01+0
三元字9+279+279+249+2210+209+1810+1710+159+12
四元字24+113024+106824+84824+73224+64625+61424+60925+64224+703
二元词7+17+17+17+17+17+17+17+17+0
三元词16+2716+2615+2416+2215+2215+2215+2215+2215+22
四元词19+80119+76120+72020+70820+70720+73019+76020+82420+750

  可以明显看出规律:

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

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

拼音中文
wo men bu hui shou qu dai ban fang chan zheng de fei yong我们不会收取代办房产证的费用
zhe ge xiang mu kuai dong gong le这个项目快动工了
dang nei zheng zhi sheng huo zhan xian xin qi xiang党内政治生活展现新气象
jin dong cai nuan ji shi fou you shi wu mai ji今冬采暖季是否又是雾霾季
jie he shi ji tiao jian lv xing gao zhi yi wu结合实际条件履行告知义务
二元字三元字二元词三元词
我们不会收取大板房产证的费用我们不会收取代办房产证的费用我们不会收取带办房产证的费用我们不会收取代办房产证的费用
这个项目会动供了这个项目快动工了这个项目会动工了这个项目会动工了
党内政治生活展现新气象党内政治生活展现新气象党内政治生活展现新气象党内政治生活展现新气象
今动采暖季是否有十五卖给今冬采暖季是否有食物卖给今冬采暖季是否有十雾霾季今冬采暖及是否有是雾霾季
结合实际条件履行告之一五结合实际条件履行告知义务结合实际条件履行告知义务结合实际条件履行告知义务

  二元字模型有两个主要缺点:
  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.000010.100000.100000.250000.500000.750000.900000.990000.99999
50.371.788.391.292.393.093.293.092.7
88.792.493.994.494.794.794.593.389.6

  整句准确率:

$\lambda$0.000010.100000.100000.250000.500000.750000.900000.990000.99999
0.916.951.761.766.168.469.268.567.5
51.265.772.274.475.575.374.871.160.6

  预处理+预测时间:

$\lambda$0.000010.100000.100000.250000.500000.750000.900000.990000.99999
10+4110+3810+3510+3210+3111+2711+2611+2310+18
22+4022+3722+3322+3223+2921+2722+2522+2322+19

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

  经过我的三分调参后,我得到了可能是最佳的 $\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

欢迎留言>_<

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据