基于場感知分解機的五筆輸入法

李澤南,劉漢明,胡珍珍,黎 姿,司馬燊,郭 港

(贛南師范大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,江西 贛州 341000)

0 引 言

20世紀(jì)80年代初期,隨著漢字編碼的發(fā)明,出現(xiàn)了中文輸入法。中文輸入一般可以分為鍵盤、手寫、語音等三種輸入方式[1],其中鍵盤輸入需要對漢字二次編碼,具有輸入不受環(huán)境制約、對系統(tǒng)性能要求低、響應(yīng)速度快等特點,是桌面計算機系統(tǒng)的主流輸入方式[2]。在漢字輸入法的發(fā)展過程中,出現(xiàn)了大量的漢字編碼方案,分為以音為主、以形為主、音形結(jié)合三類[3]。目前常用的漢字編碼方案有拼音、雙拼、五筆、筆畫等[4]。

以音為主的漢字編碼以拼音輸入法為代表,入門門檻低,通過大容量詞庫、模糊音支持、用戶詞自動添加、熱詞自動更新等一系列功能,拼音輸入法取得了極大的成功。特別是手機等無實體鍵盤設(shè)備上應(yīng)用廣泛,截至2020年底,使用拼音類手機輸入法用戶規(guī)模達(dá)到7.55億人,隨著互聯(lián)網(wǎng)的影響深化下沉,用戶規(guī)模進(jìn)一步擴大[5]。楊新濤等研究了基于深度學(xué)習(xí)的拼音輸入法,希望通過深度學(xué)習(xí)技術(shù)使?jié)h字輸入更準(zhǔn)確更高效[6]。拼音輸入法重碼率過高,特別生僻字和單字的速度遠(yuǎn)遠(yuǎn)落后于五筆輸入法[7];在線詞庫越來越大導(dǎo)致備選字詞切換速度慢,輸入法軟件本身也越來越復(fù)雜使得占用的系統(tǒng)資源越來越多。

以形為主的輸入方案體現(xiàn)了漢字的書寫、重碼率低、文字輸入效率高。王永民[8]通過長達(dá)五年的研究,在1983年發(fā)明了根據(jù)筆畫和字形特征對漢字進(jìn)行編碼的五筆字型輸入法。李亭騫等人提出的E碼漢字輸入法,根據(jù)漢字字形首尾形狀與鍵盤上的英文字母存在相似的特點實現(xiàn)漢字的輸入,降低了用戶記憶字根的難度。以形為主的輸入法在初期過于專注降低重碼率,導(dǎo)致編碼方案要么過于復(fù)雜,如五筆輸入法需要用戶記憶字根;要么碼長較長,如筆畫輸入法[9]。但五筆輸入法需要熟悉五筆字根表,入門門檻較高,隨著計算機的普及,更多的用戶需要操作簡單的輸入法[10]。加上五筆輸入法自出現(xiàn)以來基本上沒有太大的改進(jìn),使得拼音輸入法逐漸占據(jù)了如今的主導(dǎo)地位。

音形結(jié)合的輸入法試圖結(jié)合漢字的“音”與“形”,以期解決拼音碼的重碼率高和形碼難記的不足,如苗文音形編碼[11],但其要求拼音準(zhǔn)確且仍需用戶記憶字形碼。

拼音輸入法雖然入門簡單,使用者初期的使用體驗效果優(yōu),但五筆輸入法整體上仍存在優(yōu)勢,在報社等需要專業(yè)性文字錄入工作的場合仍大規(guī)模使用。特別地,計算機時代導(dǎo)致手寫漢字的機會大大減少,使人們對熟悉的字變得生疏,許多原本會寫的字變得只會讀,“提筆忘字”變得越來越常見[12],嚴(yán)重地影響了中華文化的傳承。五筆等字形編碼漢字輸入法體現(xiàn)了漢字的書寫,對減少“提筆忘字”等現(xiàn)象,促進(jìn)中華文化傳承具有重要意義。

近年來,機器學(xué)習(xí)取得的長足的發(fā)展,但機器學(xué)習(xí)用于漢字輸入法的研究較少。楊新濤等提出了基于深度學(xué)習(xí)的拼音輸入法[6],但深度學(xué)習(xí)算法復(fù)雜、對計算機硬件要求高、數(shù)據(jù)訓(xùn)練中存在過擬合[13],從而影響漢字輸入的速度。推薦系統(tǒng)根據(jù)用戶的歷史記錄,向用戶推薦感興趣的事務(wù),研究結(jié)合場感知分解機[14](Field-aware Factorization Machine,FFM)推薦算法提出了一種基于FFM的五筆輸入法(Wubi based FFM,WB-FFM)。該方法根據(jù)用戶以往的數(shù)據(jù),處理漢字?jǐn)?shù)據(jù)解決稀疏特征問題,預(yù)測用戶的需求向用戶推送候選漢字,以期進(jìn)一步提高五筆漢字輸入的效率,改善用戶體驗,增加用戶粘性,為保證中華文化的傳承載體不會退化甚至消失,對中華文化傳承也具有重要意義實驗表明,WB-FFM輸入法具有穩(wěn)健的“推薦”能力,第一候選字詞推薦準(zhǔn)確率達(dá)到98.91%,優(yōu)于現(xiàn)有典型的輸入法。

1 FFM推薦系統(tǒng)

為解決稀疏特征和特征組合的問題,Y.Juan等提出了FFM算法,它是FM(Factorization Machine)[15]模型的改進(jìn)版,以更好地適應(yīng)稀疏特征。常用漢字2 000多個,對漢字輸入來說是稀疏特征問題。

1.1 FM

FM旨在解決諸如推薦系統(tǒng)等面臨的稀疏數(shù)據(jù)下的特征組合問題。假設(shè)數(shù)據(jù)有n個特征,xi是第i個特征值,xixj表示xi和xj的組合(xi,xj≠0),ω0、ωi、ωij是模型參數(shù),則二階多項式的模型為:

(1)

在數(shù)據(jù)稀疏的情況下,因為xi,xj≠0的樣本不足,導(dǎo)致參數(shù)ωij的訓(xùn)練十分困難。

矩陣分解可有效解決參數(shù)ωij的訓(xùn)練問題。設(shè)ωij組成的矩陣為W,分解得W=VTV,那么,ωij可以看作第i、j維特征的隱向量之積,得FM模型。

(2)

其中,二次項

(3)

其中,vi,f是第i個變量的第f個因子,k?n是超參數(shù),由用戶指定。這樣,FM的復(fù)雜度可由原來的O(kn2)降為O(kn)。

1.2 FMM

Y.Juan等借鑒“場”[16]的概念提出的FFM把相同性質(zhì)的特征歸為一個“場”,同一個“場”的特征單獨One-Hot編碼。在FFM中,每一維特征xi,對特征xj(j≠i)的“場”fj,都有一個隱向量vi,fj,FFM模型為:

(4)

若f是“場”的個數(shù),則FFM的參數(shù)個數(shù)為nfk。對每個隱向量,只需要學(xué)習(xí)它的“場”的效應(yīng),使得kFFM?kFM,從而進(jìn)一步降低了算法復(fù)雜度。

1.3 FFM的優(yōu)化

在FFM領(lǐng)域中,LIBFFM作為一個廣泛使用的分解機庫,利用隨機梯度下降(SGD)優(yōu)化。

隨機梯度下降算法(Stochastic Gradient Descent,SGD)[17]源于1951年Robbins和Monro提出的隨機逼近,最初應(yīng)用于模式識別[18]和神經(jīng)網(wǎng)絡(luò)[19]。這種方法在迭代過程中隨機選擇一個或幾個樣本的梯度來替代總體梯度,從而大大降低了計算復(fù)雜度。1958年Rosenblatt等研制出的感知機采用了隨機梯度下降法的思想,即每輪隨機選取一個樣本,求其對應(yīng)損失函數(shù)的梯度,再基于給定的步長更新參數(shù)。1986年Rumelhart等分析了多層神經(jīng)網(wǎng)絡(luò)的誤差反向傳播算法,該算法每次按順序或隨機選取一個樣本來更新參數(shù),它實際上是小批量梯度下降法的一個特例。近年來,隨著深度學(xué)習(xí)的迅速興起,隨機梯度下降算法已成為求解大規(guī)模機器學(xué)習(xí)優(yōu)化問題的一類主流方法[20]。

SGD在每輪更新參數(shù)時,僅隨機抽取一個樣本計算其梯度,并以此梯度為全局梯度的估計值。SGD的參數(shù)更新公式為:

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

(5)

其中,αt為第t輪迭代的學(xué)習(xí)率,用于調(diào)整參數(shù)更新的幅度。為防止學(xué)習(xí)率過大而錯過最優(yōu)解,常將其設(shè)置為一個遞減的序列。it∈{1,2,…,n}表示第t輪迭代中按均勻分布隨機抽取的樣本序號。

FFM模型使用帶L2正則項的logistic loss作為損失函數(shù),采用SGD來優(yōu)化損失函數(shù),選取單個樣本簡化損失函數(shù),公式為:

(6)

每次迭代時選取一個樣本數(shù)據(jù)點(y,x),對式(6)中ωj1,f2和ωj2,f1求偏導(dǎo)得:

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

(7)

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

(8)

其中,k為:

(9)

加入學(xué)習(xí)率提升SGD的訓(xùn)練效率,通過Adagrad算法自動調(diào)整學(xué)習(xí)率。此時,SGD(公式(5))的更新公式為:

(10)

(11)

其中,gt,j為第t輪第j個參數(shù)的梯度,是平滑項,避免分母為0,式(11)的Gt,jj對角矩陣,對角線的值j是參數(shù)wj的平方和,隨著迭代次數(shù)的進(jìn)行,參數(shù)進(jìn)行累加,學(xué)習(xí)率逐漸減小。此時需要更新Gj1,f2與Gj2,f1,更新公式為:

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

(12)

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

(13)

最后更新模型參數(shù)為:

(14)

(15)

2 WB-FFM輸入法

FFM模型對特征數(shù)較多且稀疏問題有很好的適應(yīng)性,其根據(jù)歷史點擊率(Click-Through Rate,CTR)來提高向用戶推薦的準(zhǔn)確性,漢字輸入法在存在重碼的情況下通過候選窗口向用戶提供字詞選擇,且候選字詞也是高維、稀疏的。結(jié)合這些特點,實現(xiàn)的基于FFM的五筆輸入法,利用用戶選擇候選詞的歷史記錄向用戶推薦最可能的字詞,提高了輸入效率和用戶體驗。

2.1 訓(xùn)練集

把FFM用于五筆輸入推薦,首要的問題是如何得到訓(xùn)練集,通過提取微軟五筆輸入法(86版)的詞庫來達(dá)到這一目的。該詞庫包含了各字詞的編碼、用戶選擇次數(shù)和編碼長度,共有529 882個字詞。相對于編碼,編碼長度特征冗余,這里從數(shù)據(jù)集中去除該特征。

2.2 “場”的構(gòu)建

顯然,對訓(xùn)練集利用One-Hot[21]重構(gòu)特征后,其特征量相當(dāng)大。根據(jù)訓(xùn)練集的特點,構(gòu)建3個“場”(見表1):

表1 訓(xùn)練集的“場”

?字詞。采用One-Hot構(gòu)造特征;

?編碼。采用One-Hot構(gòu)造特征;

?選擇次數(shù),即用戶輸入某字、詞的次數(shù)?？紤]到如果對其重構(gòu)特征,需要對特征值離散化,不但會大大增加特征數(shù)量,而且會影響表示精度,所以這里不重構(gòu)特征(即1個特征)。

2.3 實 現(xiàn)

由于“場”的存在,需要把重構(gòu)特征后的數(shù)據(jù)轉(zhuǎn)化為“場標(biāo)識:特征標(biāo)識:值”格式(見表2)。當(dāng)特征是離散型時,“值”固定為1,否則是歸一化后的字詞選擇次數(shù)。

表2 特征與“場”對應(yīng)標(biāo)識

SGD訓(xùn)練FFM模型見算法1。

算法1:SGD訓(xùn)練FFM

#分別是訓(xùn)練樣本集、驗證樣本集和訓(xùn)練參數(shù)設(shè)置

輸入:(tr,va,pa)

輸出:model,Loss(損失函數(shù))

#特征數(shù)(tr.n)、場數(shù)(tr.m)和參數(shù)(pa)

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

Rtr=1,Rva=1

#歸一化的pa.norm為真,計算訓(xùn)練和驗證樣本的系數(shù)

if pa.norm then

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

end if

for it = 1,…,pa.itr do

#數(shù)據(jù)迭代,若新參數(shù)為真則打亂訓(xùn)練順序

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]*φ}

#計算樣本的訓(xùn)練誤差

Ltr=Ltr+log{1+eφ}

#單個樣本的損失函數(shù)計算梯度gΦ

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

#再根據(jù)梯度更新model參數(shù)

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

訓(xùn)練好的模型用于WB-FFM輸入法(算法2)。

算法2:基于FFM的五筆輸入法

輸入:編碼D

輸出:用戶選擇的候選字詞Z

#檢查字詞庫,在字詞庫中匹配相應(yīng)編碼的字詞

#獲取用戶庫中匹配字詞HC(點擊次數(shù))

if HC>0 then

獲取用戶庫的HC

else

HC=1//字詞點擊次數(shù)為0,HC取值默認(rèn)為1

end if

#獲取字詞數(shù)據(jù),構(gòu)建FFM數(shù)據(jù)并預(yù)測候選字詞

SelectJdates(D)

#對候選字詞進(jìn)行排序,arr字詞的相關(guān)數(shù)據(jù)

bubbleSort(arr)

#用戶點擊相應(yīng)的字詞

ifZthen

#對應(yīng)用戶庫的字詞點擊次數(shù)累加+1

HC++

else

HC=1 #結(jié)束候選

end if

#WB-FFM清除候選字詞

return重新輸入D

3 實驗結(jié)果與分析

實驗采用FM、MF[22]作為模型訓(xùn)練時的對比算法。FM采用LIBFM[23]方法實現(xiàn),LIBFM是一個廣泛使用的推薦系統(tǒng)矩陣分解庫,支持SGD等多種優(yōu)化方法,這里采用SGD,與FFM一致。MF采用LIBMF[24]方法實現(xiàn),LIBMF是一個用于潛在空間使用兩個矩陣的積來逼近一個不完整矩陣的開源工具庫;WB-FFM的FFM采用開源工具LIBFFM實現(xiàn)。實驗采用邏輯損失對模型進(jìn)行性能評價。

另外,為測試WB-FFM輸入法的性能,還選擇了QQ、微軟、極點、陳橋、搜狗和王碼等6種常用五筆輸入法以及QQ和搜狗兩種常用拼音輸入法作為對比。

3.1 訓(xùn)練集

這里使用微軟五筆輸入法86版的字庫(節(jié)3.1),既作為WB-FFM、FM和LIBMF的訓(xùn)練集,也作為WB-FFM的字庫。經(jīng)過特征重構(gòu)后,共得到729 288個特征(見表3)。

表3 數(shù)據(jù)集特征數(shù)

3.2 模型構(gòu)建

主要通過實驗的方法優(yōu)化FM、MF和FFM模型的參數(shù)。實驗基于i7-7700HQ@2.80 GHz CPU、16 GB 內(nèi)存、Windows10系統(tǒng),C語言編程。算法需要調(diào)整的參數(shù)主要有模型的迭代次數(shù)(t)、學(xué)習(xí)率(η)、場/因素個數(shù)(k)、懲罰因子(λ)等。實驗對不同算法最優(yōu)化:首先選取一個參數(shù)a作為優(yōu)化對象,其余參數(shù)設(shè)為默認(rèn)值;然后,在a的范圍內(nèi)(算法不同,范圍可能不同,以該算法最佳范圍為準(zhǔn))均勻取5個值對a進(jìn)行優(yōu)化;接著,固定a為最優(yōu)值,優(yōu)化第二個參數(shù),以此類推,優(yōu)化完所有參數(shù)(見圖1～圖3)。根據(jù)優(yōu)化后的參數(shù),測試了三種模型的性能(見表4、圖4)。

(a)η默認(rèn),調(diào)整k (b)k=30,調(diào)整η

(a)η,λ默認(rèn),調(diào)整k (b)λ默認(rèn),k=20,調(diào)整η (c)k=20,η=0.1,調(diào)整λ

(a)η,λ默認(rèn),調(diào)整k (b)λ默認(rèn),k=16,調(diào)整η (c)k=20,η=0.1,調(diào)整λ

圖4 不同模型的損失

表4 不同模型的性能比較

表4顯示,MF速度最快,這是因為該模型相比于FM和FFM來說,算法復(fù)雜度更低。另外,盡管FFM模型復(fù)雜度高于FM,但它有更小的k(表4)和更快的收斂速度(圖4),使得它的算法時間明顯小于FM。表4和圖4還顯示,FFM的對數(shù)損失明顯小于FM和MF,體現(xiàn)了該模型的優(yōu)越性。

3.3 現(xiàn)有輸入法比較

實驗隨機從已發(fā)表的文獻(xiàn)中選取科技、體育、農(nóng)業(yè)、旅游、醫(yī)療、生態(tài)環(huán)境、航天科技、非文化遺產(chǎn)、商貿(mào)、法律共10段不同類型的文字,每段文字?jǐn)?shù)量200～300字,測試包括WB-FFM在內(nèi)的9種輸入法的性能。作對照的極點、QQ五筆、搜狗五筆、陳橋、QQ拼音和搜狗拼音6種輸入法具有按輸入次數(shù)排序、按最近輸入排序或有重碼時被選擇的候選項自動調(diào)位至首位等“推薦”功能,測試前將它們的這些功能開啟。測試時每種輸入法按以上順序連續(xù)輸入10段文字,并統(tǒng)計候選字詞推薦到第一位的準(zhǔn)確率(見表5、圖5)。

圖5 第一候選準(zhǔn)確率

表5 第一候選平均準(zhǔn)確率 %

表5顯示,盡管王碼輸入法沒有“推薦”功能,但它的第一候選平均準(zhǔn)確率卻最高,這是因為10段內(nèi)容來源于公開發(fā)表的文獻(xiàn),屬于較常用的文字,該輸入法會優(yōu)先推薦常用字(類似的原因,搜狗也獲得了較高的平均準(zhǔn)確率)。從圖5中可以看出,王碼輸入法的準(zhǔn)確率曲線幾乎平直,這是沒有“推薦”功能的表現(xiàn)。微軟輸入法也沒有“推薦”功能,但它的曲線出現(xiàn)了很大的波動,這應(yīng)該是它對漢字的“理解”遠(yuǎn)不如王碼所造成的。其它7種輸入法由于具有“推薦”功能,圖5顯示它們的準(zhǔn)確率逐步上升,且QQ五筆、極點、搜狗五筆和WB-FFM最終“收斂”到了與王碼基本相同的準(zhǔn)確率。表5和圖5還顯示,五筆輸入法第一候選準(zhǔn)確率明顯高于拼音輸入法,這是由于拼音輸入法的重碼率顯著高于五筆輸入法所造成的。另外,還統(tǒng)計了QQ和搜狗兩種拼音輸入法第一候選的平均碼長,分別為4.62和4.76(對于詞組的碼長以平均計,如,“zg”為“中國”,則碼長為1),也高于五筆不高于4的碼長。

為了進(jìn)一步考察7種具有“推薦”功能的輸入法的“推薦”特性,把圖5作直線擬合,并計算對應(yīng)的斜率和方差(見表6)。表6顯示W(wǎng)B-FFM的斜率和方差都比較小。較小的斜率說明它的“推薦”比較溫和,較小的方差意味著算法穩(wěn)健性較高,可減小過擬合風(fēng)險。需要說明的是,盡管搜狗五筆的斜率和方差最小,但它的斜率幾乎為零,會導(dǎo)致“推薦”收斂過慢甚至不收斂。

表6 輸入法第一候選準(zhǔn)確率線性擬合

實驗還選取了常用、生僻等共15個不同類型的字和詞以進(jìn)一步探索7種具有“推薦”功能的輸入法的“推薦”能力。每組字、詞連續(xù)重復(fù)輸入10次,并統(tǒng)計各輸入法第一候字詞選準(zhǔn)確率(見表7、圖6)。之所以使用生僻字和詞組,是考慮到這類字和詞在各輸入法的歷史記錄基本為零。

圖6 第一候選字詞準(zhǔn)確率隨測試次數(shù)的變化

表7 輸入法第一候選字詞最終準(zhǔn)確率 %

表7顯示,無論常用或生僻字詞,WB-FFM的最終準(zhǔn)確率位列第二,僅常用字低于QQ拼音,綜合考慮圖5和表6,該輸入法整體“推薦”能力優(yōu)于現(xiàn)有方法。另外,圖6顯示了各輸入法“推薦”準(zhǔn)確率隨測試次數(shù)的增加而增加,符合推薦算法會利用歷史記錄的思想。在對常用字的“推薦”上(圖6(a)),WB-FFM并無特別之處,這是因為一般的漢字輸入法在常用字的處理上都比較成熟。但圖6(b)～(d)中,WB-FFM的準(zhǔn)確率的提升比較穩(wěn)健,明顯優(yōu)于其它輸入法,說明其“推薦”穩(wěn)健性優(yōu)于其它輸入法。

4 結(jié)束語

輸入法是人們使用計算機的最基本需求。如今,人們手寫漢字的機會大大減少,對熟悉的字變得生疏,加上拼音等易用的漢字輸入法的廣泛使用,使得“提筆忘字”等現(xiàn)象越來越嚴(yán)重。五筆字型輸入法可較好地表征漢字字型,對改善人們“提筆忘字”有一定的幫助。研究把FFM推薦算法應(yīng)用到五筆字型輸入法,以期提高第一候選字詞的推薦性能,降低五筆輸入法的使用難度,增加用戶的使用粘性。

實驗表明,提出的結(jié)合FFM算法的五筆輸入法WB-FFM的第一候選字詞的推薦準(zhǔn)確率和推薦穩(wěn)健性均高于現(xiàn)有輸入法,驗證了推薦算法在輸入中的應(yīng)用優(yōu)勢。WB-FFM良好的推薦能力和較短的碼長,增加了五筆輸入法的易用性,但與流行的拼音輸入法相比,其較高的入門門檻還有待于今后進(jìn)一步探索。