王 玲，李 琴，隋美玲，肖海軍

基于支持向量機(jī)的主動(dòng)學(xué)習(xí)方法及其實(shí)現(xiàn)*

王 玲1，李 琴2，隋美玲2，肖海軍2

（1.武漢職業(yè)技術(shù)學(xué)院質(zhì)量管理與教學(xué)督導(dǎo)處，湖北武漢430074；2.中國(guó)地質(zhì)大學(xué)數(shù)學(xué)與物理學(xué)院，湖北武漢430074）

根據(jù)主動(dòng)學(xué)習(xí)可以有效地減少標(biāo)注樣本的代價(jià)這一特點(diǎn)，設(shè)計(jì)了一種基于SVM的主動(dòng)學(xué)習(xí)方法.仿真實(shí)驗(yàn)中，檢驗(yàn)分類正確率和F測(cè)度這兩類評(píng)估指標(biāo)，結(jié)果表明基于SVM的主動(dòng)學(xué)習(xí)的學(xué)習(xí)效果優(yōu)于被動(dòng)學(xué)習(xí).

主動(dòng)學(xué)習(xí)；被動(dòng)學(xué)習(xí)；分類器；支持向量機(jī)

絕大部分機(jī)器學(xué)習(xí)問(wèn)題都可以歸納為兩類問(wèn)題：監(jiān)督學(xué)習(xí)（supervised learning）和非監(jiān)督學(xué)習(xí)（unsupervised learning）［1］.傳統(tǒng)的監(jiān)督學(xué)習(xí)問(wèn)題中，學(xué)習(xí)算法以外界給定的已標(biāo)注樣本集作為訓(xùn)練集，通過(guò)調(diào)整分類器的參數(shù)，從中歸納出學(xué)習(xí)模型，再將學(xué)習(xí)模型應(yīng)用于未標(biāo)注樣本集，預(yù)測(cè)出未標(biāo)注樣本的類別.監(jiān)督學(xué)習(xí)最大的特點(diǎn)就是訓(xùn)練樣本的類別是已知的，與監(jiān)督學(xué)習(xí)不同，非監(jiān)督學(xué)習(xí)事先并不知道訓(xùn)練樣本的類別.

任何一種學(xué)習(xí)都有一定的目的，對(duì)于機(jī)器學(xué)習(xí)來(lái)說(shuō)，就是要通過(guò)有限數(shù)量樣本的學(xué)習(xí)，使分類器在對(duì)無(wú)限多個(gè)模式進(jìn)行分類時(shí)所產(chǎn)生的錯(cuò)誤概率最小.盡管對(duì)于某一個(gè)任務(wù)來(lái)說(shuō)，選擇一個(gè)合適的方法能夠取得不錯(cuò)的效果，但是普遍認(rèn)為要想大幅度改進(jìn)學(xué)習(xí)效果，還是得增加訓(xùn)練樣本的數(shù)目.這是因?yàn)闃颖镜南∈栊院投鄻有詫?dǎo)致訓(xùn)練樣本不可能包含所有的可能性.然而，標(biāo)注樣本通常是一件代價(jià)極高的事情，這就使得我們不可能標(biāo)注大量的樣本.由于樣本的稀疏性，當(dāng)我們采用隨機(jī)取樣的方法選取樣本標(biāo)注后，可能存在大量已標(biāo)注的樣本，這些樣本在機(jī)器學(xué)習(xí)方法中不是很有代表性，因?yàn)榇罅康娜哂嗷蛳嗨频臉颖疽呀?jīng)標(biāo)注過(guò)了.

主動(dòng)學(xué)習(xí)［2，3］方法就是為了解決這個(gè)問(wèn)題而產(chǎn)生的，它用于標(biāo)注的樣本這樣選?。好看芜x取包含信息量最大的樣本.

1 主動(dòng)學(xué)習(xí)

主動(dòng)學(xué)習(xí)方法主要分為兩個(gè)部分：學(xué)習(xí)引擎和選擇引擎［4］.學(xué)習(xí)引擎主要負(fù)責(zé)提供一個(gè)基準(zhǔn)學(xué)習(xí)器，使用傳統(tǒng)的監(jiān)督學(xué)習(xí)方法對(duì)系統(tǒng)提供的已標(biāo)注樣本集進(jìn)行學(xué)習(xí)，從而訓(xùn)練出一個(gè)性能較好的分類器模型.選擇引擎主要負(fù)責(zé)根據(jù)樣本選取算法，選擇未標(biāo)注的樣本標(biāo)注后，再將該樣本添加到訓(xùn)練集中.學(xué)習(xí)引擎和選擇引擎交替工作，循環(huán)多次后，分類器模型經(jīng)過(guò)不斷的矯正，性能進(jìn)一步得到提升，當(dāng)滿足停止條件的時(shí)候，整個(gè)主動(dòng)學(xué)習(xí)過(guò)程結(jié)束.學(xué)習(xí)流程圖如圖1所示.

圖1 主動(dòng)學(xué)習(xí)流程圖

主動(dòng)學(xué)習(xí)一般由三部分組成［4，5］：

（1）數(shù)據(jù)：它由少部分已標(biāo)注的樣本集V和大部分未標(biāo)注的樣本集U構(gòu)成.

（2）詢問(wèn)模塊Q：它決定U中的部分?jǐn)?shù)據(jù)提取出來(lái)手動(dòng)標(biāo)注后添加到V中.

（3）分類器L：它是由已標(biāo)注樣本集作為訓(xùn)練集，從中歸納出分類器模型.

主動(dòng)學(xué)習(xí)的具體步驟如下：

（1）剛開(kāi)始拿到手的數(shù)據(jù)全部是未標(biāo)注的，從這些數(shù)據(jù)里面隨機(jī)選取M（一般取1%）交給專家手動(dòng)標(biāo)注，標(biāo)注完成后放進(jìn)訓(xùn)練集V中；

（2）根據(jù)V中的已知類別數(shù)據(jù)可以訓(xùn)練出一個(gè)分類器模型L；

（3）詢問(wèn)模塊Q決定剩下的1－M的未標(biāo)注樣本U中的部分?jǐn)?shù)據(jù)，抽取出來(lái)標(biāo)注后添加到V中；

（4）重復(fù)（2）和（3）直到候選樣本集為空集或者分類器穩(wěn)定，此時(shí)整個(gè)詢問(wèn)過(guò)程結(jié)束.

2 基于SVM的主動(dòng)學(xué)習(xí)

由于SVM具有較好的分類效果，現(xiàn)將SVM引入主動(dòng)學(xué)習(xí)中，并采用不確定取樣的詢問(wèn)準(zhǔn)則.不確定取樣選擇那些當(dāng)前分類器最不能確定其分類的樣本進(jìn)行標(biāo)注，衡量樣本的信息量采用信息熵：

信息熵最大的樣本正是當(dāng)前分類器最不能確定其類別的樣本.然而，上述公式需要一個(gè)概率輸出來(lái)表示每個(gè)樣本屬于各個(gè)類別的概率大小，但SVM卻不是一個(gè)概率輸出分類器，其決策值的絕對(duì)值是樣本點(diǎn)到分類器的距離.因此，可將決策值的絕對(duì)值作為衡量分類器在樣本上置信度的一個(gè)測(cè)度：

這里f（x）表示決策值，表示決策值為f（x）的樣本被分為1的概率為p，它能將決策值映射到概率空間中.

顯然，在SVM中使用不確定取樣時(shí)就不需要得到概率輸出，而是直接使用決策值.因?yàn)殡x分類器越近的樣本，它被誤分的可能性越大.于是，在基于SVM的主動(dòng)學(xué)習(xí)的法則中，詢問(wèn)準(zhǔn)則如下：采用SVM作為訓(xùn)練器，將決策值的絕對(duì)值作為樣本選取的度量，每次都選取決策值的絕對(duì)值最小的樣本，也就是離分類器最近的樣本.

3 仿真實(shí)驗(yàn)

對(duì)于主動(dòng)學(xué)習(xí)算法性能優(yōu)越性的評(píng)估常用的方法有兩種［5］：一種是達(dá)到一定的實(shí)驗(yàn)結(jié)果，具體表現(xiàn)為測(cè)試時(shí)分類正確率、查全率、查準(zhǔn)率、CPU時(shí)間（訓(xùn)練時(shí)間、測(cè)試時(shí)間）等，主動(dòng)學(xué)習(xí)所需要的訓(xùn)練數(shù)據(jù)要比其他方法少；另外一種是在訓(xùn)練數(shù)據(jù)相同的情況下，主動(dòng)學(xué)習(xí)的實(shí)驗(yàn)結(jié)果在各項(xiàng)指標(biāo)上要好于其他方法［6］.

3.1分類器評(píng)價(jià)指標(biāo)

樣本的真實(shí)類別為正類，預(yù)測(cè)的結(jié)果也為正類的樣本數(shù)目稱為正確正類TP（true positive）；樣本的真實(shí)類別為正類，預(yù)測(cè)結(jié)果為負(fù)類的樣本數(shù)目稱為錯(cuò)誤負(fù)類FN（false negative）；樣本的真實(shí)類別為負(fù)類，預(yù)測(cè)為正類的樣本數(shù)目稱為錯(cuò)誤正類FP（false positive）；樣本的真實(shí)類別為負(fù)類，預(yù)測(cè)為負(fù)類的樣本數(shù)目稱為正確負(fù)類TN（true negative）.混淆矩陣為：

表1 混淆矩陣

正確率（Accuracy）：

查準(zhǔn)率（Precision）：

查全率（Recall）：

F－測(cè)度：

正確率（Accuracy）的分子表示預(yù)測(cè)正確的個(gè)數(shù)，分母表示預(yù)測(cè)的總個(gè)數(shù).查準(zhǔn)率（Precision）和查全率（Recall）是信息檢索和分類任務(wù)中比較常用的評(píng)價(jià)指標(biāo)，許多學(xué)者將上面兩種指標(biāo)同時(shí)考慮［7］.這是因?yàn)?，如果采用分類正確率作為衡量指標(biāo)，而樣本分布又不平衡，假設(shè)有100個(gè)樣本，其中有99個(gè)正類、1個(gè)負(fù)類，那么分類器將樣本全部預(yù)測(cè)為正類的話其分類正確率也有99%，正確率已經(jīng)是非常高了.應(yīng)此，當(dāng)樣本分布不平衡的時(shí)候僅僅只采用分類正確率作為評(píng)價(jià)指標(biāo)是不合適的.

3.2核函數(shù)及參數(shù)選擇

實(shí)驗(yàn)中，選擇RBF作為SVM的核函數(shù)，選取訓(xùn)練數(shù)據(jù)3185個(gè)和測(cè)試數(shù)據(jù)29376個(gè).

基于網(wǎng)格搜索交叉驗(yàn)證［8］的方法來(lái)確定參數(shù)c，γ.取c＝2－10～215，設(shè)定搜索步長(zhǎng)為1；取γ＝210～2－15，搜索步長(zhǎng)為－1.圖2顯示的是通過(guò)交叉驗(yàn)證得到的c＝2048和gamma＝0.0078125是選取的最佳參數(shù)，此時(shí)的分類正確率高達(dá)97.3333%.

圖2 交叉驗(yàn)證的參數(shù)選擇

3.3實(shí)驗(yàn)步驟及實(shí)驗(yàn)結(jié)果

主動(dòng)學(xué)習(xí)實(shí)驗(yàn)步驟：

（1）在訓(xùn)練集（3185個(gè)）中隨機(jī)選取1%（32個(gè)）的樣本作為種子數(shù)據(jù)，標(biāo)注后放入V中，剩下的99%放入U(xiǎn)中；

（2）利用V中的樣本訓(xùn)練分類器模型L，RBF核在libsvm［9］上做交叉驗(yàn)證，svm light上訓(xùn)練；

（3）利用訓(xùn)練好的分類器L可分別在測(cè)試集和U中做測(cè)試；

（4）根據(jù)在U中測(cè)試結(jié)果，將決策值取絕對(duì)值后按從小到大的排序排列，提取最小的前32個(gè)樣本，標(biāo)注后添加到V中；

（5）利用新的V重新訓(xùn)練分類器模型L；

（6）重復(fù)上面的步驟3、4、5直到分類器穩(wěn)定，記錄每回合在測(cè)試集中的分類正確率和F測(cè)度，然后繪圖.

通過(guò)圖3和圖4這兩個(gè)評(píng)測(cè)指標(biāo)的對(duì)比，可以得出結(jié)論：主動(dòng)學(xué)習(xí)的性能要好于被動(dòng)學(xué)習(xí)，無(wú)論是在正確率，還是在F測(cè)度指標(biāo)上主動(dòng)學(xué)習(xí)的學(xué)習(xí)曲線都要好于被動(dòng)學(xué)習(xí).

圖3 主動(dòng)學(xué)習(xí)與隨機(jī)取樣的正確率比較

圖4 主動(dòng)學(xué)習(xí)與隨機(jī)取樣的F測(cè)度比較

4 總結(jié)

主動(dòng)學(xué)習(xí)能夠有效減少標(biāo)注樣本的代價(jià)，并且理論和實(shí)驗(yàn)均表明，基于SVM的主動(dòng)學(xué)習(xí)在實(shí)際應(yīng)用中可得到不錯(cuò)的結(jié)果.因此，將SVM引入主動(dòng)學(xué)習(xí)是一個(gè)不錯(cuò)的選擇.今后，首先可在評(píng)價(jià)準(zhǔn)則上做進(jìn)一步的研究，如可考慮訓(xùn)練時(shí)間、測(cè)試時(shí)間、正確率、F測(cè)度等多項(xiàng)指標(biāo)，避免單一評(píng)估指標(biāo)說(shuō)服力不夠的缺陷；其次，主動(dòng)學(xué)習(xí)過(guò)程中的學(xué)習(xí)尺度也是一個(gè)敏感的參數(shù)，其選擇尺度不同會(huì)給主動(dòng)學(xué)習(xí)帶來(lái)一定的影響.

［1］Cristianini N，Shawe－Taylor J.支持向量機(jī)導(dǎo)論［M］.李國(guó)正，王猛，曾華軍，譯.北京：電子工業(yè)出版社，2004.

［2］Burr Settles.Active learning literature survey.Computer Sciences Technical Report 1648［R］.University of Wisconsin Madison，2010.

［3］龍軍，殷建平，祝恩，等.主動(dòng)學(xué)習(xí)研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，2008，（S1）：300－304.

［4］Tong S.Active learning：Theory and applications［D］.Stanford：PhD Thesis of Stanford University，2001.

［5］Vlachos A.Active learning with support vectormachines［D］.Edinburgh：Master Thesis of Edinburgh University，2004.

［6］Thompson CA，CaliffM E，Mooney R J.Active learning for natural language parsing and information extraction［A］.Proceedings of the Sixteenth International Machine Learning Conference［C］.1999.

［7］Vlachos A.A stopping criterion for active learning［J］.Computer Speech and Language，2008，（3）：295－312.

［8］Hsu C，Chang C，Lin C.A practical guide to support vector classification［EB／OL］.https：／／www.cs.sfu.ca／people／Faculty／teaching／726／spring11／svmguide.pdf，2010－04－15.

［9］Chang C，Lin C.LIBSVM—A library for support vector machines［EB／OL］.http：／／www.csie.ntu.edu.tw／～cjlin／libsvm／，2013.

An Active Learning M ethod Based on Support Vector M achine

WANG Ling1，LIQin2，SUIMeiling2，XIAO Haijun2
（1.Quality Management and Teaching Supervision Division，Wuhan Polytechnic，Wuhan Hubei430074，China；2.School of Mathematics and Physics，China University of Geosciences，Wuhan Hubei430074，China）

As the active learning can reduce the costof sample labeling effectively，we design an active learningmethod which is based on SVM.The simulation experiments show that the results of active learning method are much better than those of passive learning method not only in classification accuracy but also in F－Score.

active learning；passive learning；classifier；SVM

TP301

A

1008－4681（2014）02－0035－04

（責(zé)任編校：晴川）

2014－03－10

國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)：40972205）資助項(xiàng)目.

王玲（1959－），女，湖北武漢人，武漢職業(yè)技術(shù)學(xué)院質(zhì)量管理與教學(xué)督導(dǎo)處副教授.研究方向：經(jīng)濟(jì)統(tǒng)計(jì).