陸玉清,洪 宇,陸 軍,姚建民,朱巧明

(蘇州大學(xué)江蘇省計算機信息處理重點實驗室,江蘇蘇州215006)

1 引言

拼寫錯誤是英文文本中較常見的錯誤。Kukich[1]將英文文本中的錯誤分為兩種類型,一類是上下文無關(guān)的錯誤(isolated-word error),也叫非詞錯誤,即輸入的詞是一個無效的詞,在字典中不存在。這種錯誤不需借助上下文,只要和詞典中的詞進行匹配就能發(fā)現(xiàn),例如the錯拼為teh、reluctant錯拼為 reluctent。另一類是上下文有關(guān)的錯誤(context-dependent word error),也叫真詞錯誤,即輸入的詞是和原詞相似的另一個有效詞,如：I have a peace of cake.其中peace實際上應(yīng)為piece。目前,非詞錯誤的糾錯方法已經(jīng)有很多研究,而真詞錯誤檢查及其校對要比非詞錯誤校對困難得多。因為真詞錯誤的單詞是字典中正確的詞。所以,對于錯誤使用的真詞檢查及給出的拼寫建議,主要依據(jù)對該真詞的上下文的考察。

本文研究真詞錯誤的檢查及修改的方法。對于所檢查的真詞錯誤[2]不僅包括一些“典型”的拼寫錯誤,例如同音字錯誤,如peace和piece;拼字錯誤,如在句子“I'll be ready in five minuets.”其中的minuets應(yīng)該是 minutes。同時還包括一些常見的語法錯誤,如among和between;以及代詞的使用錯誤 ,如在句子“I had a great time with his.”其中的his應(yīng)該用him代替;另外還包括跨境詞邊界錯誤,如maybe和may be。

實驗最終的研究目標(biāo)在于,基于已有的真詞錯誤檢查的研究,擴大從上下文中提取特征的范圍,同時結(jié)合目前已有的特征篩選方法,進一步對所提取的特征進行篩選,再利用Winnow分類算法對句子中出現(xiàn)的易混淆詞的使用正確與否給出判斷。

2 相關(guān)工作及系統(tǒng)框架

2.1 相關(guān)工作

Daniel Lawrence[3]、美國的 Kukich[1]、Andrew R.Golding&Dan Rose[4-5]、Lidia Mangu[6]都做了關(guān)于真詞拼寫檢查的研究。Lidia Mangu[6]使用了Bayesian和Winnow兩種分類算法,結(jié)果表明Winnow算法的分類結(jié)果優(yōu)于用Bayesian的分類結(jié)果,其中使用Winnow分類算法得到的正確率為94.01%。其在上下文中提取的特征為上下文的單詞和詞性,而沒有考慮上下文中的單詞與易混淆詞之間的搭配,即連接詞特征。Andrew R.Golding&Dan Rose[5]同樣運用了Bayesian和Winnow算法,使用的特征為上下文單詞以及上下文單詞中與易混淆詞之間的搭配,使得結(jié)果得到了改進,所研究的21組混淆集的平均正確率達94.87%。

在國內(nèi),張磊,周明[7]介紹了真詞錯誤檢查時使用的一些方法,其中提到了通過基線①基線即通過設(shè)定閾值,選取出現(xiàn)頻率較高的特征。、上下文詞和搭配來獲取特征的方法,同時詳細分析了一些特征混合模型,包括決策列表,Bayesian分類器和Winnow分類算法。張仰森,俞士汶[8]綜述了現(xiàn)有的基于上下文的文本錯誤校對方法主要有兩種：①利用文本上下文的同現(xiàn)與搭配特征;②利用規(guī)則或語言學(xué)知識。他們的工作都只進行了方法的介紹,沒有進行相關(guān)的實驗。另一方面,李斌進行了真詞錯誤檢測的實驗[9],其采用了基于混淆集的真詞錯誤檢測方法,并使用了Bayesian分類方法,但其在上下文中所提取的特征較少,只考慮到混淆集合中詞的前后各一個詞及其詞性,造成了在檢測過程中還存在一些誤判,考慮更多的特征將會得到更好的效果[6]。

2.2 系統(tǒng)框架

本文擴大了在易混淆詞的上下文中提取特征的種類和范圍,同時進一步深入地進行了特征篩選。提取的特征包括連接詞、詞性兩種句法特征,和上下文的詞作為語義特征;提取特征的范圍由原先的前后長度為1,擴展到前后長度為5。特征篩選時采用了文檔頻率和信息增益。該方法主要流程如圖1。其中真詞錯誤檢查系統(tǒng)中的語料分為兩個部分,分別為訓(xùn)練集和測試集。首先針對訓(xùn)練集中的每個句子,從易混淆詞的上下文中提取特征。在這些特征的基礎(chǔ)上,對其中的上下文單詞特征進行篩選,選取其中對分類影響較大的特征。至此,特征提取的過程結(jié)束,接著利用Winnow算法進行權(quán)重訓(xùn)練,即先對每個特征賦給初始權(quán)重,再通過Winnow算法對每一個易混淆詞的相關(guān)特征進行權(quán)重更新。最后依據(jù)訓(xùn)練得到的特征權(quán)重對測試集進行測試,得到最終的評判結(jié)果。

圖1 真詞錯誤檢查系統(tǒng)流程圖

3 基于上下文的真詞錯誤檢測方法

真詞錯誤檢查的過程被建模為詞排歧的過程。將英文文本中彼此容易混淆的詞收集在一起,形成一個混淆集[8]C={W1,W2,…,Wn}。當(dāng)在句子中遇到任意一個Wi(稱為目標(biāo)單詞)時,就要考慮混淆集C中的其他單詞是否更適于該處的上下文。該過程可以描述為,首先從目標(biāo)詞的上下文中提取有效特征,將特征用向量表示后作為分類的輸入,對目標(biāo)詞所在混淆集的所有單詞分別利用Winnow分類算法進行判定,取其中值最大的結(jié)果所對應(yīng)的單詞作為最終判定。

3.1 特征提取

采用向量空間模型表示上下文信息,將目標(biāo)單詞的上下文特征用一組向量(T1,T2,…,Tn)表示,其中Ti為第i個特征的權(quán)重。

3.1.1 句法層面特征的提取

句法層面的特征提取包括：①目標(biāo)詞前后一定范圍內(nèi)的連接詞。②目標(biāo)詞前后一定范圍內(nèi)的單詞的詞性。其中,在上下文中所提取的連接詞不僅僅限定為連詞,只要是在句子中起到連接作用的詞均為連接詞。目標(biāo)詞前后的連接詞,可以反映詞之間的有序依賴關(guān)系。例如except周圍可能出現(xiàn)的連接詞有for、that等。我們還發(fā)現(xiàn),一些單詞前后常用的連接詞并不在長度為1的范圍內(nèi),如 The insurance policy can protect you against injury.其中against是protect周圍常用的連接詞,但卻不在目標(biāo)詞protect的前后長度為1的范圍內(nèi)。因此為了盡可能多的獲取該類信息,本文中擴大了連接詞的查找范圍,在連接詞前后長度為3和5的范圍內(nèi)進行查找。

3.1.2 語義層面特征的提取及篩選

語義層面所提取的特征為目標(biāo)詞前后一定范圍內(nèi)的單詞。對于某一個易混淆詞,其前后可能出現(xiàn)的不同單詞較多,而且不同單詞出現(xiàn)的頻率差異較大。例如在實驗的訓(xùn)練語料中,易混淆詞former周圍的不同單詞數(shù)量多達360個,其中出現(xiàn)頻率最小的為1次,最大的為46次。在此我們假設(shè),出現(xiàn)頻率較低的單詞對分類的影響力較小,可以忽略不計。因此在實驗中,我們首先使用文檔頻率這一特征篩選方法,對出現(xiàn)在目標(biāo)詞前后的特征單詞進行篩選,統(tǒng)計每個單詞出現(xiàn)的頻率,通過設(shè)定閾值去除其中文檔頻率較小的特征。

對于特征單詞t和混淆集中的某一單詞C,信息增益通過考察C所在的句子中出現(xiàn)和不出現(xiàn)t的句子頻數(shù),來衡量t對于C所提供的信息的多少,定義如下[10]：

其中,P(Ci)表示某混淆集中的單詞Ci在語料中出現(xiàn)的概率,P(t)表示語料中包含特征單詞t的句子概率,P(Ci|t)表示句子中包含特征t時是單詞Ci的條件概率,P()表示語料中不包含特征t的句子概率,P表示句子中不包含特征t時是單詞Ci的條件概率,m表示該混淆集中單詞總數(shù)。根據(jù)公式(1)計算某個易混淆詞的每個特征的信息增益,進行非降次排序,選擇大于一定閾值的詞作為最終的特征集。

如果某特征僅出現(xiàn)在其中一類單詞的句子中,且該特征的文檔頻率值較小時,該特征得到的信息增益同樣較大。例如在易混淆詞alone的上下文單詞特征中有單詞Nicola(在句子中作為人名使用)出現(xiàn)1次,其信息增益值為0.012。而往往出現(xiàn)頻率較低的單詞對分類的影響較小,這就造成了所選取的部分特征對分類的準(zhǔn)確性產(chǎn)生了一定的影響。因此,在該實驗中選擇在應(yīng)用信息增益進行特征篩選之前,利用文檔頻率預(yù)先篩選出一部分特征單詞。

3.2 Winnow分類算法

Winnow算法是一種在二值屬性數(shù)據(jù)集上的線性分類算法[11]。該算法中有3個參數(shù),一個閾值參數(shù) θ,兩個權(quán)重更新參數(shù) α、β,其中 α＞1,0＜β＜1。該算法分類的步驟為,對于某易混淆詞,其周圍的n個特征單詞可以表示為一維向量X={x1,x2,…,xn},對應(yīng)的每個特征單詞的權(quán)重向量可以表示為：

其中w(i,C)為C類中特征的權(quán)重。該算法給出判定為1當(dāng)

其中xi為0或1,用于表明該特征是否出現(xiàn),wi是與xi對應(yīng)的特征的權(quán)重。訓(xùn)練是錯誤驅(qū)動的,也就是說只有對樣本分類產(chǎn)生錯誤時才會利用參數(shù)α、β調(diào)整權(quán)重向量W。

4 實驗設(shè)計與結(jié)果分析

實驗中我們選取了61組混淆集,其中混淆集單詞個數(shù)為2的有60組,單詞個數(shù)為3的為1組。從英國國家語料庫(British National Corpus)中收集了與混淆集中的單詞相關(guān)的句子約5000句,選取部分句子使用相應(yīng)混淆集中的詞進行替換,將其中的80%作為訓(xùn)練集,剩余的為測試集。在提取單詞詞性特征時,使用了斯坦福大學(xué)NLP Group開發(fā)的詞性標(biāo)注工具(Stanford Log-linear Part-Of-Speech Tagger)[12]。實驗中共收集了140個連接詞,作為在上下文中查找連接詞的“字典”。另外考慮到,所提取的連接詞與上下文特征單詞有重復(fù)的部分,此時在上下文單詞特征中刪除重復(fù)的特征單詞。實驗中Winnow算法的相關(guān)參數(shù)被設(shè)置為：α=1.3,β=0.8,θ=1.1,各個特征的初始權(quán)重為0.2。

在實驗中采用準(zhǔn)確率(p)、召回率(r)和F1測度來評價結(jié)果的好壞,這些性能評價指標(biāo)定義如下：

4.1 進行特征選擇的實驗結(jié)果與分析

為了確定最佳的連接詞特征的查找范圍,實驗中分別在距離目標(biāo)詞前后長度為1、3、5范圍內(nèi)進行查找,得到的對應(yīng)的F1值分別為20.76%、42.83%、42.57%。為了降低特征向量的維數(shù)及計算的復(fù)雜度,并希望能夠選擇一些和分類相關(guān)性大的特征來提高分類的準(zhǔn)確性,選擇長度為3范圍內(nèi)的連接詞,較選擇在1、5范圍內(nèi)的連接詞作為特征更為合適。

在前后單詞特征篩選時,首先利用了文檔頻率的方法,分別實驗了在去除詞頻小于等于2、4、5的情況下得到的正確率,如表1所示。

從表1中可以清晰地看出,DF=4時得到的正確率為70.81%,較DF=2和DF=5的情況下得到的正確率高,因為出現(xiàn)次數(shù)太少的詞(低頻詞,或者叫生僻詞)往往是表意能力很差的詞,而刪除太多的詞又會降低對語意的理解。因此下面在利用信息增益進行特征篩選時,是基于DF=4時所篩選出來的特征進行的。

從表2中可以看出,當(dāng)信息增益中所設(shè)定的閾值為0.015時得到的正確率最高為71.92%。由此,通過前面的文檔頻率和信息增益兩步篩選,得到了最終確定的特征單詞。

4.2 使用不同特征的實驗結(jié)果與討論

依據(jù)上述評價指標(biāo),得到的在利用不同特征情況下,各混淆集的正確率和召回率的結(jié)果見表3。

表1 利用DF進行特征篩選的各混淆集的實驗結(jié)果

表2 利用IG進行特征篩選的各混淆集的實驗結(jié)果

表3 利用不同特征所得到的各混淆集的實驗結(jié)果

從表3中可以看出,當(dāng)所用到的特征僅為上下文單詞時,考察的是目標(biāo)詞周圍的語義環(huán)境。例如混淆集{desert,dessert},其中desert上下文單詞特征中有：basin,river,flower等;dessert上下文單詞特征有：sweet,cheese,wine等。在上下文單詞的基礎(chǔ)上加入連接詞特征,正確率得到了較大的提高。因為對于某些單詞,特別是動詞,其前后的連接詞對于確定該單詞具有較好的效果。例如混淆集{abroad,aboard},其中abroad前后的連接詞特征有：from,on,at等;aboard前后的連接詞特征有：off,into等。在前兩個特征的基礎(chǔ)上,加入詞性特征,使得正確率得到提高,同時較大的提升了召回率。由于提取出來的詞性特征比較集中,最多的一組混淆集的詞性特征只有29個,這使得給出判定的可能性增大,進而提高了召回率。

5 總結(jié)與展望

本文擴大了在上下文中提取特征的種類和范圍。通過從易混淆詞的上下文中提取語義和句法兩個方面的特征,并能夠?qū)μ卣鬟M行有效的篩選,使得最終確定的特征為分類提供依據(jù)。實驗表明,擴大特征提取的范圍及選取有效的特征能夠使得系統(tǒng)的性能更好。本文下一步的工作是擴大語料,以能夠盡可能廣泛地收集易混淆詞的語言環(huán)境中的信息,從而得到更多的特征為分類服務(wù)。

[1]Kukich.Techniques for automatically correcting words in text[J].ACM Computing Surveys,1992,24(2)：377-439.

[2]Andrew.J.Carlson,Jeffrey Rosen,Dan Roth.Scaling Up Context-Sensitive Text Correction[C]//American Association forArtificial Intelligence(www.aaai.org),2001.

[3]Daniel Lawrence.SpellingCheckerand Corrector[S].1992.

[4]Andrew R.Golding&Dan Rose.Applying Winnow to Context-Sensitive Spelling Correction[C]//Proc.of the 13thICML,Bari,Italy,1996.

[5]Andrew R.Golding.A Winnow based approach to context-sensitive spelling correction[J].Machine Learning 34(1-3)：107-130.Roth.Special Issue on Machine Learning and Natural Language.1999.

[6]Lidia Mangu,Eric Brill.Automatic Rule Acquisition for Spelling Correction[C]//Proceeding of the 14thInternational Conference on Machine Learning,1997：187-194.

[7]張磊,周明,黃昌寧,等.中文文本自動校對[J].語言文字應(yīng)用,2001,(1)：19-26.

[8]張仰森,俞士汶.文本自動校對技術(shù)研究綜述[J].計算機應(yīng)用研究,2006,(6)：8-12.

[9]李斌,姚建民,朱巧明.英文作文的自動拼寫檢查研究[J].鄭州大學(xué)學(xué)報(理學(xué)版),2008,(3)：48-51.

[10]Y.Yang,J.P.Pedersen.A Comparative Study on Feature Selection in Text Categorization[C]//Proceedings of the 14th International Conference on Machine Learning.1997：412-420.

[11]Littlestone N.Learning quickly when irrelevant attributes abound：a new linear threshold algorithm[J].M achine Learning,1988,4(2)：285-318.

[12]KristinaToutanova.Stanford Log-linearPart-Of-Speech Tagger[DB/OL].http：//nlp.stanford.edu/software/tagger.shtml,2009-12-24/2010-3-12.