基于场感知分解机的五笔输入法

李泽南,刘汉明,胡珍珍,黎 姿,司马燊,郭 港

(赣南师范大学 数学与计算机科学学院,江西 赣州 341000)

0 引 言

20世纪80年代初期,随着汉字编码的发明,出现了中文输入法。中文输入一般可以分为键盘、手写、语音等三种输入方式[1],其中键盘输入需要对汉字二次编码,具有输入不受环境制约、对系统性能要求低、响应速度快等特点,是桌面计算机系统的主流输入方式[2]。在汉字输入法的发展过程中,出现了大量的汉字编码方案,分为以音为主、以形为主、音形结合三类[3]。目前常用的汉字编码方案有拼音、双拼、五笔、笔画等[4]。

以音为主的汉字编码以拼音输入法为代表,入门门槛低,通过大容量词库、模糊音支持、用户词自动添加、热词自动更新等一系列功能,拼音输入法取得了极大的成功。特别是手机等无实体键盘设备上应用广泛,截至2020年底,使用拼音类手机输入法用户规模达到7.55亿人,随着互联网的影响深化下沉,用户规模进一步扩大[5]。杨新涛等研究了基于深度学习的拼音输入法,希望通过深度学习技术使汉字输入更准确更高效[6]。拼音输入法重码率过高,特别生僻字和单字的速度远远落后于五笔输入法[7];在线词库越来越大导致备选字词切换速度慢,输入法软件本身也越来越复杂使得占用的系统资源越来越多。

以形为主的输入方案体现了汉字的书写、重码率低、文字输入效率高。王永民[8]通过长达五年的研究,在1983年发明了根据笔画和字形特征对汉字进行编码的五笔字型输入法。李亭骞等人提出的E码汉字输入法,根据汉字字形首尾形状与键盘上的英文字母存在相似的特点实现汉字的输入,降低了用户记忆字根的难度。以形为主的输入法在初期过于专注降低重码率,导致编码方案要么过于复杂,如五笔输入法需要用户记忆字根;要么码长较长,如笔画输入法[9]。但五笔输入法需要熟悉五笔字根表,入门门槛较高,随着计算机的普及,更多的用户需要操作简单的输入法[10]。加上五笔输入法自出现以来基本上没有太大的改进,使得拼音输入法逐渐占据了如今的主导地位。

音形结合的输入法试图结合汉字的“音”与“形”,以期解决拼音码的重码率高和形码难记的不足,如苗文音形编码[11],但其要求拼音准确且仍需用户记忆字形码。

拼音输入法虽然入门简单,使用者初期的使用体验效果优,但五笔输入法整体上仍存在优势,在报社等需要专业性文字录入工作的场合仍大规模使用。特别地,计算机时代导致手写汉字的机会大大减少,使人们对熟悉的字变得生疏,许多原本会写的字变得只会读,“提笔忘字”变得越来越常见[12],严重地影响了中华文化的传承。五笔等字形编码汉字输入法体现了汉字的书写,对减少“提笔忘字”等现象,促进中华文化传承具有重要意义。

近年来,机器学习取得的长足的发展,但机器学习用于汉字输入法的研究较少。杨新涛等提出了基于深度学习的拼音输入法[6],但深度学习算法复杂、对计算机硬件要求高、数据训练中存在过拟合[13],从而影响汉字输入的速度。推荐系统根据用户的历史记录,向用户推荐感兴趣的事务,研究结合场感知分解机[14](Field-aware Factorization Machine,FFM)推荐算法提出了一种基于FFM的五笔输入法(Wubi based FFM,WB-FFM)。该方法根据用户以往的数据,处理汉字数据解决稀疏特征问题,预测用户的需求向用户推送候选汉字,以期进一步提高五笔汉字输入的效率,改善用户体验,增加用户粘性,为保证中华文化的传承载体不会退化甚至消失,对中华文化传承也具有重要意义实验表明,WB-FFM输入法具有稳健的“推荐”能力,第一候选字词推荐准确率达到98.91%,优于现有典型的输入法。

1 FFM推荐系统

为解决稀疏特征和特征组合的问题,Y.Juan等提出了FFM算法,它是FM(Factorization Machine)[15]模型的改进版,以更好地适应稀疏特征。常用汉字2 000多个,对汉字输入来说是稀疏特征问题。

1.1 FM

FM旨在解决诸如推荐系统等面临的稀疏数据下的特征组合问题。假设数据有n个特征,xi是第i个特征值,xixj表示xi和xj的组合(xi,xj≠0),ω0、ωi、ωij是模型参数,则二阶多项式的模型为:

(1)

在数据稀疏的情况下,因为xi,xj≠0的样本不足,导致参数ωij的训练十分困难。

矩阵分解可有效解决参数ωij的训练问题。设ωij组成的矩阵为W,分解得W=VTV,那么,ωij可以看作第i、j维特征的隐向量之积,得FM模型。

(2)

其中,二次项

(3)

其中,vi,f是第i个变量的第f个因子,k≪n是超参数,由用户指定。这样,FM的复杂度可由原来的O(kn2)降为O(kn)。

1.2 FMM

Y.Juan等借鉴“场”[16]的概念提出的FFM把相同性质的特征归为一个“场”,同一个“场”的特征单独One-Hot编码。在FFM中,每一维特征xi,对特征xj(j≠i)的“场”fj,都有一个隐向量vi,fj,FFM模型为:

(4)

若f是“场”的个数,则FFM的参数个数为nfk。对每个隐向量,只需要学习它的“场”的效应,使得kFFM≪kFM,从而进一步降低了算法复杂度。

1.3 FFM的优化

在FFM领域中,LIBFFM作为一个广泛使用的分解机库,利用随机梯度下降(SGD)优化。

随机梯度下降算法(Stochastic Gradient Descent,SGD)[17]源于1951年Robbins和Monro提出的随机逼近,最初应用于模式识别[18]和神经网络[19]。这种方法在迭代过程中随机选择一个或几个样本的梯度来替代总体梯度,从而大大降低了计算复杂度。1958年Rosenblatt等研制出的感知机采用了随机梯度下降法的思想,即每轮随机选取一个样本,求其对应损失函数的梯度,再基于给定的步长更新参数。1986年Rumelhart等分析了多层神经网络的误差反向传播算法,该算法每次按顺序或随机选取一个样本来更新参数,它实际上是小批量梯度下降法的一个特例。近年来,随着深度学习的迅速兴起,随机梯度下降算法已成为求解大规模机器学习优化问题的一类主流方法[20]。

SGD在每轮更新参数时,仅随机抽取一个样本计算其梯度,并以此梯度为全局梯度的估计值。SGD的参数更新公式为:

wt+1=wt-αt∇Lit(wt)

(5)

其中,αt为第t轮迭代的学习率,用于调整参数更新的幅度。为防止学习率过大而错过最优解,常将其设置为一个递减的序列。it∈{1,2,…,n}表示第t轮迭代中按均匀分布随机抽取的样本序号。

FFM模型使用带L2正则项的logistic loss作为损失函数,采用SGD来优化损失函数,选取单个样本简化损失函数,公式为:

(6)

每次迭代时选取一个样本数据点(y,x),对式(6)中ωj1,f2和ωj2,f1求偏导得:

gj1,f2=wj1,f2f(w)=λ·wj1,f2+k·wj2,f1xj1xj2

(7)

gj2,f1=wj2,f1f(w)=λ·wj2,f1+k·wj1,f2xj1xj2

(8)

其中,k为:

(9)

加入学习率提升SGD的训练效率,通过Adagrad算法自动调整学习率。此时,SGD(公式(5))的更新公式为:

(10)

(11)

其中,gt,j为第t轮第j个参数的梯度,是平滑项,避免分母为0,式(11)的Gt,jj对角矩阵,对角线的值j是参数wj的平方和,随着迭代次数的进行,参数进行累加,学习率逐渐减小。此时需要更新Gj1,f2与Gj2,f1,更新公式为:

Gj1,f2=Gj1,f2+(gj1,f2)2

(12)

Gj2,f1=Gj2,f1+(gj2,f1)2

(13)

最后更新模型参数为:

(14)

(15)

2 WB-FFM输入法

FFM模型对特征数较多且稀疏问题有很好的适应性,其根据历史点击率(Click-Through Rate,CTR)来提高向用户推荐的准确性,汉字输入法在存在重码的情况下通过候选窗口向用户提供字词选择,且候选字词也是高维、稀疏的。结合这些特点,实现的基于FFM的五笔输入法,利用用户选择候选词的历史记录向用户推荐最可能的字词,提高了输入效率和用户体验。

2.1 训练集

把FFM用于五笔输入推荐,首要的问题是如何得到训练集,通过提取微软五笔输入法(86版)的词库来达到这一目的。该词库包含了各字词的编码、用户选择次数和编码长度,共有529 882个字词。相对于编码,编码长度特征冗余,这里从数据集中去除该特征。

2.2 “场”的构建

显然,对训练集利用One-Hot[21]重构特征后,其特征量相当大。根据训练集的特点,构建3个“场”(见表1):

表1 训练集的“场”

•字词。采用One-Hot构造特征;

•编码。采用One-Hot构造特征;

•选择次数,即用户输入某字、词的次数。考虑到如果对其重构特征,需要对特征值离散化,不但会大大增加特征数量,而且会影响表示精度,所以这里不重构特征(即1个特征)。

2.3 实 现

由于“场”的存在,需要把重构特征后的数据转化为“场标识:特征标识:值”格式(见表2)。当特征是离散型时,“值”固定为1,否则是归一化后的字词选择次数。

表2 特征与“场”对应标识

SGD训练FFM模型见算法1。

算法1:SGD训练FFM

#分别是训练样本集、验证样本集和训练参数设置

输入:(tr,va,pa)

输出:model,Loss(损失函数)

#特征数(tr.n)、场数(tr.m)和参数(pa)

model=init(tr.n,tr.m,pa)

Rtr=1,Rva=1

#归一化的pa.norm为真,计算训练和验证样本的系数

if pa.norm then

Rtr=norm(tr),Rva=norm(va)

end if

for it = 1,…,pa.itr do

#数据迭代,若新参数为真则打乱训练顺序

if pa.rand then

tr.X=shuffle(tr.X)

end if

fori=1,…,tr.l do

#计算单个样本的FFM输出φ

φ=calcΦ(tr.X[i],Rtr[i],model)

eφ=exp{-tr.Y[i]*φ}

#计算样本的训练误差

Ltr=Ltr+log{1+eφ}

#单个样本的损失函数计算梯度gΦ

gΦ=-tr.Y[i]*eφ/(1+eφ)

#再根据梯度更新model参数

model=update(tr.X[i],Rtr[i],model,gΦ)

end for

#验证样本,计算样本的FFM输出并验证误差

fori=1,…,va.l do

φ=calcΦ(va.X[i],Rva[i],model)

Lva=Lva+log{1+exp{-va.Y[i]*φ}}

end for

end for

训练好的模型用于WB-FFM输入法(算法2)。

算法2:基于FFM的五笔输入法

输入:编码D

输出:用户选择的候选字词Z

#检查字词库,在字词库中匹配相应编码的字词

#获取用户库中匹配字词HC(点击次数)

if HC>0 then

获取用户库的HC

else

HC=1//字词点击次数为0,HC取值默认为1

end if

#获取字词数据,构建FFM数据并预测候选字词

SelectJdates(D)

#对候选字词进行排序,arr字词的相关数据

bubbleSort(arr)

#用户点击相应的字词

ifZthen

#对应用户库的字词点击次数累加+1

HC++

else

HC=1 #结束候选

end if

#WB-FFM清除候选字词

return重新输入D

3 实验结果与分析

实验采用FM、MF[22]作为模型训练时的对比算法。FM采用LIBFM[23]方法实现,LIBFM是一个广泛使用的推荐系统矩阵分解库,支持SGD等多种优化方法,这里采用SGD,与FFM一致。MF采用LIBMF[24]方法实现,LIBMF是一个用于潜在空间使用两个矩阵的积来逼近一个不完整矩阵的开源工具库;WB-FFM的FFM采用开源工具LIBFFM实现。实验采用逻辑损失对模型进行性能评价。

另外,为测试WB-FFM输入法的性能,还选择了QQ、微软、极点、陈桥、搜狗和王码等6种常用五笔输入法以及QQ和搜狗两种常用拼音输入法作为对比。

3.1 训练集

这里使用微软五笔输入法86版的字库(节3.1),既作为WB-FFM、FM和LIBMF的训练集,也作为WB-FFM的字库。经过特征重构后,共得到729 288个特征(见表3)。

表3 数据集特征数

3.2 模型构建

主要通过实验的方法优化FM、MF和FFM模型的参数。实验基于i7-7700HQ@2.80 GHz CPU、16 GB 内存、Windows10系统,C语言编程。算法需要调整的参数主要有模型的迭代次数(t)、学习率(η)、场/因素个数(k)、惩罚因子(λ)等。实验对不同算法最优化:首先选取一个参数a作为优化对象,其余参数设为默认值;然后,在a的范围内(算法不同,范围可能不同,以该算法最佳范围为准)均匀取5个值对a进行优化;接着,固定a为最优值,优化第二个参数,以此类推,优化完所有参数(见图1～图3)。根据优化后的参数,测试了三种模型的性能(见表4、图4)。

(a)η默认,调整k (b)k=30,调整η

(a)η,λ默认,调整k (b)λ默认,k=20,调整η (c)k=20,η=0.1,调整λ

(a)η,λ默认,调整k (b)λ默认,k=16,调整η (c)k=20,η=0.1,调整λ

图4 不同模型的损失

表4 不同模型的性能比较

表4显示,MF速度最快,这是因为该模型相比于FM和FFM来说,算法复杂度更低。另外,尽管FFM模型复杂度高于FM,但它有更小的k(表4)和更快的收敛速度(图4),使得它的算法时间明显小于FM。表4和图4还显示,FFM的对数损失明显小于FM和MF,体现了该模型的优越性。

3.3 现有输入法比较

实验随机从已发表的文献中选取科技、体育、农业、旅游、医疗、生态环境、航天科技、非文化遗产、商贸、法律共10段不同类型的文字,每段文字数量200～300字,测试包括WB-FFM在内的9种输入法的性能。作对照的极点、QQ五笔、搜狗五笔、陈桥、QQ拼音和搜狗拼音6种输入法具有按输入次数排序、按最近输入排序或有重码时被选择的候选项自动调位至首位等“推荐”功能,测试前将它们的这些功能开启。测试时每种输入法按以上顺序连续输入10段文字,并统计候选字词推荐到第一位的准确率(见表5、图5)。

图5 第一候选准确率

表5 第一候选平均准确率 %

表5显示,尽管王码输入法没有“推荐”功能,但它的第一候选平均准确率却最高,这是因为10段内容来源于公开发表的文献,属于较常用的文字,该输入法会优先推荐常用字(类似的原因,搜狗也获得了较高的平均准确率)。从图5中可以看出,王码输入法的准确率曲线几乎平直,这是没有“推荐”功能的表现。微软输入法也没有“推荐”功能,但它的曲线出现了很大的波动,这应该是它对汉字的“理解”远不如王码所造成的。其它7种输入法由于具有“推荐”功能,图5显示它们的准确率逐步上升,且QQ五笔、极点、搜狗五笔和WB-FFM最终“收敛”到了与王码基本相同的准确率。表5和图5还显示,五笔输入法第一候选准确率明显高于拼音输入法,这是由于拼音输入法的重码率显著高于五笔输入法所造成的。另外,还统计了QQ和搜狗两种拼音输入法第一候选的平均码长,分别为4.62和4.76(对于词组的码长以平均计,如,“zg”为“中国”,则码长为1),也高于五笔不高于4的码长。

为了进一步考察7种具有“推荐”功能的输入法的“推荐”特性,把图5作直线拟合,并计算对应的斜率和方差(见表6)。表6显示WB-FFM的斜率和方差都比较小。较小的斜率说明它的“推荐”比较温和,较小的方差意味着算法稳健性较高,可减小过拟合风险。需要说明的是,尽管搜狗五笔的斜率和方差最小,但它的斜率几乎为零,会导致“推荐”收敛过慢甚至不收敛。

表6 输入法第一候选准确率线性拟合

实验还选取了常用、生僻等共15个不同类型的字和词以进一步探索7种具有“推荐”功能的输入法的“推荐”能力。每组字、词连续重复输入10次,并统计各输入法第一候字词选准确率(见表7、图6)。之所以使用生僻字和词组,是考虑到这类字和词在各输入法的历史记录基本为零。

图6 第一候选字词准确率随测试次数的变化

表7 输入法第一候选字词最终准确率 %

表7显示,无论常用或生僻字词,WB-FFM的最终准确率位列第二,仅常用字低于QQ拼音,综合考虑图5和表6,该输入法整体“推荐”能力优于现有方法。另外,图6显示了各输入法“推荐”准确率随测试次数的增加而增加,符合推荐算法会利用历史记录的思想。在对常用字的“推荐”上(图6(a)),WB-FFM并无特别之处,这是因为一般的汉字输入法在常用字的处理上都比较成熟。但图6(b)～(d)中,WB-FFM的准确率的提升比较稳健,明显优于其它输入法,说明其“推荐”稳健性优于其它输入法。

4 结束语

输入法是人们使用计算机的最基本需求。如今,人们手写汉字的机会大大减少,对熟悉的字变得生疏,加上拼音等易用的汉字输入法的广泛使用,使得“提笔忘字”等现象越来越严重。五笔字型输入法可较好地表征汉字字型,对改善人们“提笔忘字”有一定的帮助。研究把FFM推荐算法应用到五笔字型输入法,以期提高第一候选字词的推荐性能,降低五笔输入法的使用难度,增加用户的使用粘性。

实验表明,提出的结合FFM算法的五笔输入法WB-FFM的第一候选字词的推荐准确率和推荐稳健性均高于现有输入法,验证了推荐算法在输入中的应用优势。WB-FFM良好的推荐能力和较短的码长,增加了五笔输入法的易用性,但与流行的拼音输入法相比,其较高的入门门槛还有待于今后进一步探索。