基于改進Tri-training算法投票機制的中文問句分類

王 雷,孫中全

(滁州職業(yè)技術(shù)學(xué)院,安徽 滁州 239000)

0 引言

問答系統(tǒng)由問句分類、信息檢索、答案抽取三大部分組成,問句分類作為問答系統(tǒng)的初始環(huán)節(jié),其能否正確地對問句進行分類會直接影響到后續(xù)的答案抽取環(huán)節(jié)[1],從而直接影響問答系統(tǒng)的性能。目前,問句分類的方法主要有兩大類[2-3]:(1)基于人工規(guī)則的方法;(2)基于機器學(xué)習的方法。其中,基于機器學(xué)習的方法是目前問句分類的主流。機器學(xué)習方法[4]包括監(jiān)督學(xué)習、無監(jiān)督學(xué)習和半監(jiān)督學(xué)習。在問句分類方面,監(jiān)督學(xué)習的方法主要利用已標記樣本,忽略未標記樣本對于問句分類的意義,分類正確率難以提升,且分類靈活性較低。半監(jiān)督學(xué)習是一種綜合利用已標記樣本和未標記樣本進行學(xué)習的方法,能獲得較好的學(xué)習泛化能力和學(xué)習效果。目前該類方法開始應(yīng)用于問句分類中,在英文問句分類方面,AFRA等[5]采用基于機器學(xué)習的方法,使得孟加拉問題分類取得了很好的效果;SAEEDEH[6]將無監(jiān)督潛在狄利克雷分配方法用于問題分類;FAIZ等[7]利用問題分類和答案抽取方式,搭建了烹飪問答系統(tǒng);SEYHUMS等[8]基于Word2vec特征的深度學(xué)習方法用于問題分類研究。在中文問句分類方面,YU等[9]利用半監(jiān)督學(xué)習中的Co-training算法將中文問句進行分類,張志滿[10]利用深度學(xué)習算法將健康領(lǐng)域的中文問句進行分類。在半監(jiān)督學(xué)習的諸多分類算法中Tri-training算法[11]不僅在其他知識領(lǐng)域得到了很好的應(yīng)用,而且在自然語言處理領(lǐng)域有良好的分類效果。其中,任正雄等[12]提出了一種基于Tri-training的制冷系統(tǒng)半監(jiān)督故障診斷方法,改善了制冷系統(tǒng)故障診斷性能;董昊旻等[13]利用半監(jiān)督學(xué)習下的Tri-training算法,有效地提高了駕駛風格分類的準確率;高嘉偉等[14]提出一種基于Tri-training的半監(jiān)督多標記學(xué)習文檔分類算法,在文檔分類中取得了良好的效果;李帥克等[15]基于Tri-training算法來保證自動標注數(shù)據(jù)的質(zhì)量,進而提升跨領(lǐng)域依存句法分析性能。因此本文將Tri-training算法應(yīng)用于中文問句分類。

原始Tri-training算法在三個分類器均給出了不相同的分類結(jié)果時,會默認第一個分類器給出的結(jié)果為分類器模型的最終結(jié)果,則會出現(xiàn)以點代全的問題。針對此問題,本文通過對Tri-training算法[16]的理論分析,受于重重等[17]提出的DSCC(semi-supervised collaboration classification algorithm with enhanced difference)算法的啟發(fā),提出一種基于平時優(yōu)秀的投票機制的Tri-training算法。

1 Tri-training分類算法投票機制的改進

1.1 算法描述

在三個分類器均給出了不同的結(jié)果時,原始的Tri-training算法默認第一個分類器給出的結(jié)果為分類器模型最終結(jié)果,本文基于統(tǒng)計學(xué)思想,提出一種改進的投票機制算法,通過找出平時優(yōu)秀的分類器給出的結(jié)果,作為分類器模型的最終分類結(jié)果。基本流程如圖1所示。

圖1 改進的Tri-training算法流程

該算法的核心思想是對于完成迭代訓(xùn)練得到的最新訓(xùn)練集樣本,在給出分類結(jié)果以后,對每個分類器進行一個正確分類數(shù)的統(tǒng)計,記為Ci。所謂的正確分類數(shù),即分類模型在迭代訓(xùn)練和測試分類的過程中,每個分類器分類正確的中文問句數(shù)。哪個分類器分類正確的中文問句數(shù)越多,就稱這個分類器最好或者最優(yōu)秀,即為平時優(yōu)秀的投票機制。改進Tri-training算法的投票機制詳細步驟如下:

輸入:有標記樣本集L,未標記樣本集U,測試集T,分類器H

輸出:測試集T通過分類模型分類之后的分類精度

1)根據(jù)L訓(xùn)練分類器

2)利用分類采樣方法將L分為3份,形成3個有標記樣本集Li(i=1,2,3)

3)用Li(i=1,2,3)分別去訓(xùn)練3個分類器Hi(i=1,2,3)

即Hi(i=1,2,3)←Learn(Li)

4)設(shè)定分類器初始分類錯誤率ei←0.5

5)對未標記樣本集進行預(yù)測分類。對于一個分類器而言,如果另外兩個分類器對未標記樣本預(yù)測分類結(jié)果一致,即將此樣本加入到該分類器的有標記樣本集中,并且對該分類器進行迭代訓(xùn)練

6)重復(fù)3) ～ 5) 步驟,直至分類錯誤率ei不再發(fā)生變化,即分類器迭代訓(xùn)練結(jié)束

7)設(shè)定分類器正確分類數(shù)Ci(i=1,2,3),將正確數(shù)最大的分類器記為最優(yōu)秀分類器

8)用迭代訓(xùn)練好的分類器將測試集中樣本分類,測算分類器的分類正確率

9)算法結(jié)束

1.2 算法分析

1.2.1 改進投票機制的Tri-training算法原理

該投票機制的核心思想是對于完成迭代訓(xùn)練得到的最新訓(xùn)練集樣本,在給出分類結(jié)果以后,對每個分類器進行一個正確分類數(shù)的統(tǒng)計,記為Ci。所謂的正確分類數(shù),即為分類模型在迭代訓(xùn)練和測試分類的過程中,每個分類器分類正確的中文問句數(shù)。哪個分類器分類正確的中文問句數(shù)越多,就稱這個分類器最好或者最優(yōu)秀。那么在分類模型中,三個分類器給出不同的分類結(jié)果時,就可以根據(jù)這個正確分類數(shù),選出最優(yōu)秀的分類器給出的結(jié)果作為分類結(jié)果,而不是默認第一個分類器的結(jié)果作為分類結(jié)果。

關(guān)于Tri-training算法投票機制的改進方面,于重重等[17]研究了改進的投票機制方法,提出了一種基于分類準確率的投票法。這種投票機制是在分類結(jié)果各不相同時,用分類器模型中每一個分類器分別對最初始的樣本訓(xùn)練集進行分類測試,將每個分類器分類結(jié)果的錯誤率記為ei,最后將錯誤率最低的那個分類器的結(jié)果作為分類器模型的預(yù)測結(jié)果。本文將對原始投票機制、基于分類準確率的投票機制和基于平時優(yōu)秀思想的投票機制這三類方法進行實驗驗證,在分類結(jié)果數(shù)據(jù)對比下驗證方法有效性。

1.2.2 改進投票機制的Tri-training算法有效性分析

針對改進投票機制的Tri-training算法,本文針對以下兩方面的進行有效性分析。

1.2.2.1 不會出現(xiàn)“以點代全”的情況

由前文可知,原始Tri-training算法的分類器模型中的投票機制已描述得很清楚。在三個分類器給出的結(jié)果中,有相同的分類結(jié)果出現(xiàn)時,毫無疑問,這個相同的分類結(jié)果就是原始Tri-training算法分類器模型的給出的最終分類結(jié)果。若在三個分類器均給出了不相同的結(jié)果,原始的Tri-training算法會默認第一個分類器給出的結(jié)果為分類器模型的最終結(jié)果。那么,這種情況屬于以點代全的情況。在正常情況下,第一個分類器給出的結(jié)果不可能每次都是正確的,而且其分類精度也不一定比另外兩個分類器的分類精度高。這就很可能在一定程度上降低分類器模型的分類精度。這一點也是本文改進原始Tri-training算法中投票機制的最終出發(fā)點。基于統(tǒng)計學(xué)的原理,在分類器模型進行迭代訓(xùn)練和測試分類的過程中,對每個分類器進行一個分類正確數(shù)的統(tǒng)計,記為Ci。即在程序中添加一個計數(shù)器,此計數(shù)器用來在三個分類器給出不相同的結(jié)果時,選出最優(yōu)秀的分類器,用其給出的結(jié)果作為分類器模型的分類結(jié)果,這就避免了上面所述的以點代全的現(xiàn)象。

1.2.2.2 對分類結(jié)果的選擇和程序時間復(fù)雜度的控制

于重重等[17]提出的基于分類準確率的投票機制是在三個分類器給出不相同的結(jié)果時,用分類器模型中每一個分類器分別對初始樣本訓(xùn)練集進行分類測試,將每個分類器分類結(jié)果的錯誤率記為ei,最后將錯誤率最低的那個分類器的結(jié)果作為分類器模型的分類結(jié)果。這種投票機制雖然避免了以點代全的情況,但并不是最可取的方法,而且這種投票機制因需讓每個分類器分別對初始的樣本訓(xùn)練集進行分類測試,這同時就會增加算法的復(fù)雜度和時間開銷。本文提出的改進的投票機制方法,只需在程序中增加一個計數(shù)器,用來記錄每個分類器分類出的正確問句數(shù),根據(jù)分類正確數(shù)可以選出平時最優(yōu)秀的分類器。因此,相對于基于分類準確率的投票方法,其算法的復(fù)雜度和時間的開銷都會相對小一點。

本文的投票機制可以處理原始投票機制和基于分類準確率投票機制存在的一些不足之處,比原始投票機制和基于分類準確率投票機制具有更合理的選擇性,同時比基于分類準確率投票機制有更佳的判斷、更高的效率及更低的時間開銷。

2 基于改進Tri-training算法的中文問句分類

基于改進Tri-training算法建立半監(jiān)督分類模型。模型主要包括原始數(shù)據(jù)導(dǎo)入、數(shù)據(jù)預(yù)處理、協(xié)同訓(xùn)練和分類結(jié)果輸出四個部分,其流程如圖2所示。

2.1 數(shù)據(jù)預(yù)處理

一般來說,中文問句集不是分類算法中所用分類器需要的數(shù)據(jù)格式。對于中文來說,中文問句包含詞袋、詞性、命名實體和依存關(guān)系等基本特征。數(shù)據(jù)預(yù)處理部分主要是將中文問句中的基本特征提取出來,并選擇合適的基本特征將中文問句中所包含的屬性進行量化,形成分類器所需的數(shù)據(jù)格式。本文利用程序?qū)崿F(xiàn)數(shù)據(jù)預(yù)處理,在建立的中文問句分類模型中,選用中文問句的詞袋這一基本特征,旨在驗證改進Tri-training算法對于中文問句分類的有效性。對于中文問句中不同的基本特征組合,不再一一驗證。

2.2 協(xié)同訓(xùn)練

協(xié)同訓(xùn)練部分利用數(shù)據(jù)預(yù)處理得到的中文問句集,對分類器進行訓(xùn)練、測試。本文在基于類別分類采樣的Tri-training算法基礎(chǔ)上,運用三個分類器協(xié)同訓(xùn)練。基于類別分類采樣方法將有標記樣本集中的每一類中文問句提取出來,然后分別對提取出來的每類問句進行隨機采樣,形成三個有標記的樣本集。用形成的三個有標記樣本集分別去訓(xùn)練三個分類器,再利用訓(xùn)練得到的三個分類器協(xié)同對未標記樣本集中的樣本進行標記。對于一個分類器而言,如果另外兩個分類器對這些沒有標記的樣本標記了相同的分類結(jié)果,這些樣本則被當作已標記樣本,加入到該分類器有標記樣本集中參加對該分類器進行迭代訓(xùn)練。對每個分類器而言,均如此進行迭代訓(xùn)練,直至分類器不再更新,則迭代訓(xùn)練結(jié)束。

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

3.1 實驗數(shù)據(jù)

本文實驗數(shù)據(jù)主體來自哈爾濱工業(yè)大學(xué)的中文問句集[18]。該問句集分為六大類,共包含6 266個已標記好問句類別的問句。在該問句集的基礎(chǔ)上,又利用網(wǎng)絡(luò)資源通過人工方式將每類問句數(shù)量進行擴展,擴展的總問句數(shù)為4 000個。將擴展的中文問句加入到哈爾濱工業(yè)大學(xué)的中文問句集中,形成新的中文問句集。

3.2 實驗設(shè)置

3.2.1 樣本集分配

針對哈爾濱工業(yè)大學(xué)的中文問句集,選用其中25%的數(shù)據(jù)作為測試樣本集,剩余75%的數(shù)據(jù)作為訓(xùn)練集,其中,訓(xùn)練樣本集中未標記樣本的比率r依次選用20%、40%、60%、80%。將本文擴展的問句集加入到哈爾濱工業(yè)大學(xué)的中文問句集,形成一個新的問句集,再將此問句集按照哈工大中文問句集的樣本分配比例進行實驗數(shù)據(jù)分配。

3.2.2 分類器選擇

本實驗選用了三個SVM分類器,旨在驗證基于問句類別的分類采樣方法對問句分類的影響。對于其他不同分類器的組合用法對分類實驗的效果影響,李心磊等[19]已經(jīng)通過實驗驗證。

3.2.3 評價指標

本實驗共有如下兩個評價指標。

(1)對分類結(jié)果進行測試時,采用分類正確率A作為評價標準,其定義如下:

其中,N為測試集中正確分類的問句數(shù),M為測試集中總的問句數(shù)。

(2)對幾個分類算法運行時間進行比較時,該實驗的評價標準為算法的運行時間T(單位為s)。

3.3 問句分類實驗及結(jié)果分析

3.3.1 在中文問句集中不同分類算法的比較

采用圖2所示的分類模型,利用中文問句集進行實驗。分別得出在四種不同的未標記比率下,原始投票機制的Tri-training算法、基于分類準確率投票機制的Tri-training算法以及基于平時優(yōu)秀投票機制的Tri-training算法在此問句集上的分類精度(表1)。其中T1代表原始投票機制的Tri-training算法,T2代表基于分類準確率投票機制的Tri-training算法,T3代表平時優(yōu)秀投票機制的Tri-training算法。

表1 三種算法在四種不同未標記比率下的分類精度

3.3.2 在中文問句集中不同分類算法所需時間開銷的比較

在前文建立分類模型的基礎(chǔ)上,本文在算法的程序代碼中添加一個程序運行計時器,用來記錄三種算法分類完成所需的時間開銷。在三種算法分類完成時,分別記錄三種算法在分類時所需的時間開銷。實驗結(jié)果如表2所示。

表2 三種算法在四種不同未標記比率下分類時所需時間開銷

根據(jù)表1試驗結(jié)果可以看出,基于分類準確率的投票機制算法和基于平時優(yōu)秀的投票機制算法的分類精度,均高于原始的投票機制算法的分類精度,當r=80%時,分別高出0.13%和0.15%。雖然改進的投票機制算法比原始的投票機制算法的分類精度沒有明顯提高,但其也可以避免以點代全的情況。從實驗數(shù)據(jù)也可以看出,基于分類準確率投票機制的Tri-training算法和平時優(yōu)秀投票機制的Tri-training算法的分類精度相差不大。出現(xiàn)以上這兩種情況,也是不難理解的。本文分析可能有兩種原因:一是最優(yōu)秀的分類器恰好就是第一個分類器;二是中文問句集的規(guī)模還不夠大。

根據(jù)表2實驗結(jié)果可以看出,原始的投票機制算法的運行時間開銷最小。基于平時優(yōu)秀投票機制的Tri-training算法相對于基于分類準確率投票機制的Tri-training算法的運行時間開銷明顯要少一點,其平均少了7 s。雖然基于平時優(yōu)秀投票機制的Tri-training算法花了一點運行開銷時間,但是也避免了以點代全的情況。總而言之,該算法的提出還是有價值的。

因此,改進原始的投票機制算法對于中文問句分類而言,其分類精度能夠得到一定程度的提高。基于平時優(yōu)秀投票機制的Tri-training算法與基于分類準確率投票機制的Tri-training算法相比較而言,雖然兩種算法的分類精度相差不大,但前者相比后者的時間開銷少一點。所以基于平時優(yōu)秀投票機制的Tri-training算法還是具有一定優(yōu)勢的。

4 結(jié)語

本文提出了基于平時優(yōu)秀投票機制的Tri-training算法,建立了半監(jiān)督協(xié)同分類模型,利用人工擴展的問句集進行分類實驗。實驗結(jié)果表明,基于平時優(yōu)秀投票機制的Tri-training算法和基于分類準確率投票機制的Tri-training算法,較原始Tri-training算法的分類精度,當r=80%時,分別提高了0.15%和0.13%;且基于平時優(yōu)秀投票機制的Tri-training算法,相對于基于分類準確率投票機制的Tri-training算法的運行時間開銷平均少了7 s。本文算法的分類實驗主要是在哈爾濱工業(yè)大學(xué)的中文問句集基礎(chǔ)上展開的,對于更大規(guī)模的中文問句集而言,算法是否有效,還有待驗證。希望本文算法能夠為其他分類領(lǐng)域研究提供參考。