徐海龍，別曉峰，馮 卉，吳天愛

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051）

一種基于QBC的SVM主動(dòng)學(xué)習(xí)算法

徐海龍，別曉峰，馮 卉，吳天愛

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051）

針對(duì)支持向量機(jī)（souport vector machine，SVM）訓(xùn)練學(xué)習(xí)過程中樣本分布不均衡、難以獲得大量帶有類標(biāo)注樣本的問題，提出一種基于委員會(huì)投票選擇（query by committee，QBC）的SVM主動(dòng)學(xué)習(xí)算法QBC-ASVM，將改進(jìn)的QBC主動(dòng)學(xué)習(xí)方法與加權(quán)SVM方法有機(jī)地結(jié)合應(yīng)用于SVM訓(xùn)練學(xué)習(xí)中，通過改進(jìn)的QBC主動(dòng)學(xué)習(xí)，主動(dòng)選擇那些對(duì)當(dāng)前SVM分類器最有價(jià)值的樣本進(jìn)行標(biāo)注，在SVM主動(dòng)學(xué)習(xí)中應(yīng)用改進(jìn)的加權(quán)SVM，減少了樣本分布不均衡對(duì)SVM主動(dòng)學(xué)習(xí)性能的影響，實(shí)驗(yàn)結(jié)果表明在保證不影響分類精度的情況下，所提出的算法需要標(biāo)記的樣本數(shù)量大大少于隨機(jī)采樣法需要標(biāo)記的樣本數(shù)量，降低了學(xué)習(xí)的樣本標(biāo)記代價(jià)，提高了SVM泛化性能而且訓(xùn)練速度同樣有所提高。

主動(dòng)學(xué)習(xí)；支持向量機(jī)；委員會(huì)投票選擇算法；分類

0 引 言

經(jīng)典的支持向量機(jī)（support vector machine，SVM）訓(xùn)練算法都是基于大量帶有類標(biāo)記樣本的監(jiān)督學(xué)習(xí)方法，而在很多的實(shí)際應(yīng)用中，對(duì)樣本集進(jìn)行類別標(biāo)記存在著代價(jià)昂貴、枯燥乏味或是異常困難等問題，而獲取未被標(biāo)注的樣本則相對(duì)容易，同時(shí)大量未標(biāo)注樣本含有豐富的有助于學(xué)習(xí)器的信息，如有效地利用未標(biāo)注樣本無疑將在一定程度上提高學(xué)習(xí)算法的性能［1］。

面對(duì)上述這種情況，傳統(tǒng)的監(jiān)督學(xué)習(xí)方法，即被動(dòng)學(xué)習(xí)要構(gòu)建分類正確率滿足要求的分類器將是十分困難的。對(duì)此，機(jī)器學(xué)習(xí)領(lǐng)域中的主動(dòng)學(xué)習(xí)（active learning，AL）可以有效解決SVM訓(xùn)練過程中的這一類問題［1-5］，在學(xué)習(xí)過程中，學(xué)習(xí)機(jī)器可以根據(jù)學(xué)習(xí)進(jìn)程主動(dòng)選擇對(duì)分類器性能最有利的樣本作為候選樣本，若候選樣本是未標(biāo)記的樣本，則將候選樣本提交領(lǐng)域?qū)＜疫M(jìn)行類別標(biāo)記，然后將這些樣本加入到已有的訓(xùn)練樣本集中，加入的新樣本將能夠最大程度地提高SVM對(duì)未標(biāo)記樣本軟分類的準(zhǔn)確性，這樣在訓(xùn)練樣本集較小的情況下以盡可能少的標(biāo)記樣本訓(xùn)練獲得分類正確率較高的SVM分類器，從而降低構(gòu)建高性能SVM分類器的代價(jià)。

根據(jù)在主動(dòng)學(xué)習(xí)進(jìn)程中選擇“最有利”樣本策略或方法的不同，不同樣本選擇策略對(duì)應(yīng)不同的主動(dòng)學(xué)習(xí)算法，如文獻(xiàn)［4］提出的誤差減少的抽樣即期望錯(cuò)誤率縮減方法，該方法選擇這些能使當(dāng)前分類器對(duì)測(cè)試樣本集分類誤差最小的樣本作為“最有利”或“最富有信息”的樣本，雖然這種方法分類準(zhǔn)確率高，但是選擇了過多的冗余樣本，而且在每次選擇樣本之前都必須搜索整個(gè)樣本空間，才能確定選擇哪些樣本作為候選標(biāo)記樣本，因而存在著訓(xùn)練學(xué)習(xí)時(shí)間長(zhǎng)、計(jì)算復(fù)雜度高等問題。文獻(xiàn)［6］提出的不確定性抽樣（uncertainty based sampling，UBS）樣本選擇方法，即不確定度縮減方法，其選擇當(dāng)前分類器最不能確定其分類的樣本作為候選標(biāo)記樣本，但此方法易于選擇這些“奇異點(diǎn)樣本”——這些樣本具有較高的分類不確定性，而將這些“奇異點(diǎn)樣本”加入訓(xùn)練樣本集會(huì)使得分類器的分類誤差加大從而產(chǎn)生誤差傳播問題。文獻(xiàn)［7- 8］提出了基于委員會(huì)投票的樣本選擇方法（query by committee，QBC），這種方法根據(jù)已標(biāo)記樣本集訓(xùn)練兩個(gè)或多個(gè)分類器組成“委員會(huì)”，利用委員會(huì)中各個(gè)“委員”對(duì)未標(biāo)記樣本進(jìn)行標(biāo)記投票，然后選擇投票結(jié)果最不一致的樣本作為候選標(biāo)記樣本，但此方法同樣可能選擇奇異點(diǎn)，對(duì)此，文獻(xiàn)［9- 10］也對(duì)QBC做了相應(yīng)的改進(jìn)，如文獻(xiàn)［10］中采用了改進(jìn)的QBC和代價(jià)敏感支持向量機(jī)（cost-sensitive SVM，CS-SVM），減少了樣本的標(biāo)記代價(jià)，對(duì)樣本分布不均衡中不同類的樣本賦予不同的誤分代價(jià)。

針對(duì)上述主動(dòng)學(xué)習(xí)存在的這些問題，受文獻(xiàn)［2，10］啟發(fā)，提出基于改進(jìn)的加權(quán)SVM和改進(jìn)的QBC主動(dòng)SVM（QBC based-active SVM，QBC-ASVM）訓(xùn)練算法，減少樣本分布不均衡對(duì)SVM主動(dòng)學(xué)習(xí)性能的影響，抑制由于將“不確定性”樣本加入訓(xùn)練樣本集而產(chǎn)生的誤差傳播問題以及選擇過多冗余樣本，以盡可能少的標(biāo)記樣本獲得較高的SVM分類準(zhǔn)確率。

1 改進(jìn)的加權(quán)SVM

在SVM主動(dòng)學(xué)習(xí)的初始階段，存在標(biāo)記樣本少且樣本分布不均勻等問題，如使用標(biāo)準(zhǔn)的SVM，SVM訓(xùn)練學(xué)習(xí)中產(chǎn)生的最優(yōu)分界面將向間隔區(qū)域中樣本較少的類別方向偏移，這種偏差行為將導(dǎo)致SVM動(dòng)學(xué)習(xí)中可能采樣到重復(fù)的、相似的、無意義以及孤立的樣本。為此SVM主動(dòng)學(xué)習(xí)算法中訓(xùn)練初始SVM分類器時(shí)，使用如下一種改進(jìn)的加權(quán)SVM［11］，對(duì)不同類別或不同樣本采用不同的權(quán)重系數(shù)，以提高分類性能。其原始最優(yōu)化問題為：

式中，si表示對(duì)不同樣本的權(quán)重；λi為類yi的權(quán)重，其余參數(shù)同SVM廣義最優(yōu)分類超平面目標(biāo)函數(shù)。

隨著SVM主動(dòng)學(xué)習(xí)的進(jìn)程，為了能反映主動(dòng)學(xué)習(xí)選擇的未標(biāo)記樣本對(duì)SVM訓(xùn)練的貢獻(xiàn)，減少樣本分布不均衡對(duì)SVM學(xué)習(xí)性能的影響，受Co-EM SVM算法［2，10］啟發(fā)，在SVM主動(dòng)學(xué)習(xí)算法循環(huán)遞推學(xué)習(xí)中的基分類器采用如下一種改進(jìn)的加權(quán)SVM，其原始最優(yōu)化問題可以描述為

式中，si，表示對(duì)不同樣本的權(quán)重；λi為類的權(quán)重；Cs表示主動(dòng)學(xué)習(xí)所選擇的未標(biāo)記樣本對(duì)分類器訓(xùn)練的貢獻(xiàn)；為領(lǐng)域?qū)＜覍?duì)樣本的標(biāo)記，其余參數(shù)與式（1）及Co-EM SVM算法［2］同。

式（2）給出的改進(jìn)的加權(quán)SVM的對(duì)偶問題為

式（3）中，加權(quán)SVM的權(quán)重系數(shù)的確定可以采取如下方法：

首先，在SVM主動(dòng)學(xué)習(xí)訓(xùn)練的初始階段，令正負(fù)類樣本的類別權(quán)重參數(shù)λi與初始訓(xùn)練集中的正負(fù)類樣本數(shù)成反比，同時(shí)每個(gè)樣本的權(quán)重參數(shù)si都取相同的值，即si＝1／n，在此基礎(chǔ)上構(gòu)造初始的分類器；

式中，f（x）為SVM分類判別函數(shù)選擇距離超平面最近的m個(gè)樣本，即最有可能成為支持向量的樣本作為SVM訓(xùn)練的增量樣本，對(duì)標(biāo)記后將其加入到訓(xùn)練樣本集中，在新的訓(xùn)練樣本集中。使用分類器尋找此時(shí)位于分類間隔中的正負(fù)類樣本，然后令分類間隔中的樣本的權(quán)重參數(shù)大于分類間隔外的樣本的權(quán)重參數(shù)，并令正負(fù)類樣本的類別權(quán)重參數(shù)與分類間隔中的正負(fù)類樣本數(shù)成反比，然后進(jìn)行SVM主動(dòng)學(xué)習(xí)進(jìn)程，并訓(xùn)練。

式（3）中，參數(shù)Cs的初始值可以設(shè)置一個(gè)很小的數(shù)，在每次SVM訓(xùn)練學(xué)習(xí)迭代中讓其加倍，直到達(dá)到1；其余參數(shù)可以采用類似文獻(xiàn)［2］中方法進(jìn)行確定。

2 SVM主動(dòng)學(xué)習(xí)中概率度量和差異性度量方法

在SVM主動(dòng)學(xué)習(xí)算法中，需要對(duì)樣本的類標(biāo)記輸出度量其標(biāo)記置信度，而經(jīng)典SVM的決策函數(shù)是“硬輸出”，對(duì)SVM概率輸出的研究，學(xué)者們也做了相關(guān)的研究。為了簡(jiǎn)化計(jì)算同時(shí)又不影響度量效果，對(duì)算法中需要樣本類標(biāo)記的概率值度量置信度的問題，根據(jù)文獻(xiàn)［12］中的分析討論，可用式（4）即樣本與最優(yōu)分類面之間距離的遠(yuǎn)近作為樣本屬于不同類別的概率度量，受文獻(xiàn)［13- 14］中方法的啟發(fā)，算法中采用式（5）來度量樣本的類標(biāo)記置信度。

式中，｜f（xi）｜／‖ω‖的意義同式（4），則根據(jù)式（4）易知0.5≤conf（xi）≤1，其值隨f（xi）的變化如圖1所示。從圖1可以看出，conf（xi）越接近于0.5，表示樣本xi的標(biāo)記最不確定，所包含的信息越大，其相應(yīng)的類標(biāo)記置信度也較低；同時(shí)conf（xi）越接近于1，表示樣本xi屬于正類或負(fù)類的標(biāo)記很確定，也即屬于某類的置信度較高。

圖1 置信度隨樣本距超平面距離變化趨勢(shì)圖

在SVM主動(dòng)學(xué)習(xí)中，為了減少重復(fù)樣本或相似度高的樣本的選擇，為此在角度多樣性主動(dòng)學(xué)習(xí)算法的基礎(chǔ)上［15］，使用式（6）給出的一種基于余弦函數(shù)度量候選樣本xi與當(dāng)前已標(biāo)注樣本L的差異性：

式中，n表示樣本集L的樣本數(shù)；dcos（xi，xj）為樣本xi與xj的相似性，使用式（7）來度量。

式中，Φ（xi）和Φ（xj）分別為樣本xi與xj經(jīng)過非線性映射Φ，映射到某一特征空間H后對(duì)應(yīng)的坐標(biāo)，K（·，·）是SVM核函數(shù)。

在SVM主動(dòng)學(xué)習(xí)中，為了綜合考慮用式（4）距離度量候選樣本到分類超平面“不確定性”以及所選樣本與已標(biāo)記樣本的多樣性，將式（6）修正為：

式中，d為式（4）的樣本xi到分類超平面的距離；λcos為平衡因子（如均衡考慮可取0.5），即平衡樣本到分類超平面的距離和訓(xùn)練樣本集的多樣性，以選擇距離分類超平面最近并且與當(dāng)前訓(xùn)練集中的樣本具有最大差異性的“富有代表性”的樣本來訓(xùn)練SVM分類器。

3 改進(jìn)的QBC主動(dòng)學(xué)習(xí)算法

QBC主動(dòng)學(xué)習(xí)方法將訓(xùn)練的兩個(gè)或多個(gè)分類器組成一個(gè)“委員會(huì)”，利用委員會(huì)中各個(gè)“委員”對(duì)未標(biāo)記樣本進(jìn)行標(biāo)記投票，然后選擇投票結(jié)果“最不一致”的樣本作為候選樣本進(jìn)行類別標(biāo)記。根據(jù)度量投票結(jié)果“最不一致”方法的不同，當(dāng)前主要有兩種QBC方法：一種是由McCallum和Nigam［16］提出的采用相對(duì)熵（Kullback-Leibler divergence，KL-d）度量投票結(jié)果差異的方法，另一種是Argamon-Engelson和Dagan［17］提出的采用投票熵（vote entropy，VE）度量投票的不一致性的方法。

這兩種QBC主動(dòng)學(xué)習(xí)方法中，若采用相對(duì)熵來度量各個(gè)委員對(duì)某樣本類標(biāo)記投票“最不一致”，則相對(duì)熵值越大，說明委員會(huì)中成員對(duì)此樣本的類標(biāo)記投票結(jié)果差異就越大。但是采用這種度量法會(huì)漏選一些委員會(huì)成員類投票不一致的樣本，這些樣本正是基于QBC主動(dòng)學(xué)習(xí)方法所要選擇的樣本；而如采用投票熵度量投票的不一致性，投票熵值越大，委員會(huì)成員的投票差異越大，雖然選擇了投票不一致的樣本，但是這種方法沒有考慮各個(gè)委員對(duì)樣本的類條件概率值——Pj（C｜xi），這同樣會(huì)導(dǎo)致漏選一些有助于學(xué)習(xí)器訓(xùn)練，即“最有利”或“最富有信息”的樣本。表1和表2分別為3個(gè)SVM基分類器h1、h2以及h3組成的委員會(huì)，在實(shí)驗(yàn)中對(duì)3個(gè)樣本x1、x2、x3基于兩類問題（c1與c2）采用這兩種度量方法的結(jié)果。

表1 QBC委員會(huì)分對(duì)樣本的類投票結(jié)果

表2 3個(gè)樣本的類投票熵和相對(duì)熵

從表2可以看出，樣本x1與x2的相對(duì)熵值相當(dāng)，如按相對(duì)熵法度量則兩個(gè)樣本將被選擇為候選樣本，而樣本x1的投票熵為0即投票一致，這樣以投票熵度量法則樣本則將被漏選；同時(shí)對(duì)樣本x3來說如以投票熵度量投票不一致性將被選擇為候選樣本，而如以相對(duì)熵度量則可能被漏選；由此可見，委員會(huì)成員中存在對(duì)樣本x1與x3分類不確定性相當(dāng)高的成員，而根據(jù)主動(dòng)學(xué)習(xí)原理及思想，被分類器分類不確定的樣本所含的信息量是豐富的［1，12］，對(duì)其的標(biāo)記將有利于分類器的訓(xùn)練，應(yīng)當(dāng)被選擇為候選樣本。對(duì)于QBC主動(dòng)學(xué)習(xí)方法存在的這種問題，文獻(xiàn)［9］中也做了相關(guān)討論，并采用投票熵與相對(duì)熵互補(bǔ)法來解決此類問題。然而QBC算法在實(shí)際應(yīng)用中易受樣本分布不均勻的影響，如某些孤立樣本點(diǎn)，其具有較高的分類不確定性將容易被選擇為候選樣本，而這些樣本點(diǎn)的加入將極大影響分類器的性能，造成誤差的傳播，影響主動(dòng)學(xué)習(xí)的性能。

為此，針對(duì)QBC方法存在的以上問題，結(jié)合第1節(jié)和第2節(jié)討論的一些方法，在基于QBC的SVM主動(dòng)學(xué)習(xí)算法中，給出以下的改進(jìn)：

（1）QBC委員會(huì)由3個(gè)SVM分類器h1、h2、h3組成，同時(shí)在主動(dòng)學(xué)習(xí)的初始階段QBC各委員使用式（1）來訓(xùn)練學(xué)習(xí)確立，隨著學(xué)習(xí)的進(jìn)程各委員使用第1節(jié)給出的改進(jìn)加權(quán)SVM來訓(xùn)練各個(gè)委員，以使QBC迭代訓(xùn)練的初始分類器具有較強(qiáng)魯棒性，減少誤差傳播的影響。

（3）在通過QBC方法選擇候選樣本時(shí)，采用如下方法：

①首先根據(jù)式（9）計(jì)算樣本xi的投票熵VE：

式中，V（ck，xi）為委員會(huì)成員對(duì)樣本xi屬于類別ck的投票數(shù)目。

②然后選擇投票熵VE較大或大于某閾值VEth的樣本，即投票最不一致的樣本；而對(duì)VE小于某個(gè)閾值VEth或等于0的樣本，即投票一致的樣本，則計(jì)算根據(jù)式（10）計(jì)算其相對(duì)熵KL－d（xi）：

式中，K是委員會(huì)中成員的數(shù)目；C是樣本xi所有可能的類別集合C＝｛ck｝，而Pavg（C｜xi）是所有委員會(huì)中成員相對(duì)樣本xi的類條件概率的平均值即

D［·‖·］是兩個(gè)條件概率分布的信息度量，如對(duì)P1（C）、P2（C）則有

③根據(jù)式（8）計(jì)算樣本xi的相似度dcos（xi，L），若其相對(duì)熵KL-d（xi）大于給定的閾值KL-dth并且dcos（xi，L）小于某個(gè)閾值Qdth，即其投票最不一致且訓(xùn)練樣本集中不存在這些樣本或較少，則將其加入候選樣本集，以避免單獨(dú)使用投票熵或相對(duì)熵方法造成信息量豐富樣本的漏選，同時(shí)豐富訓(xùn)練樣本集，使訓(xùn)練樣本集保持多樣化，減少孤立樣本點(diǎn)被選擇為候選樣本的概率，加快主動(dòng)學(xué)習(xí)迭代進(jìn)程。

4 QBC-ASVM算法描述

Qth表示進(jìn)行QBC主動(dòng)學(xué)習(xí)的類標(biāo)記置信度閾值；

Qdth表示主動(dòng)學(xué)習(xí)中候選樣本與訓(xùn)練樣本集中對(duì)應(yīng)類的樣本相似度閾值；

VEth表示投票熵閾值；

KL-dth表示相對(duì)熵閾值；

4.2 算法過程

輸入已標(biāo)記樣本集L（至少正負(fù)樣本各一個(gè)），未標(biāo)記樣本集U，每次采樣的樣本數(shù)m，SVM訓(xùn)練算法Learn、IncLearn，閾值Tth、Qth、Tdth、Qdth、VEth、KL-dth，終止條件Sstop。

輸出分類器fsvm，預(yù)標(biāo)記樣本。

初始化初始的訓(xùn)練樣本集記為＝L，對(duì)樣本集進(jìn)行BootstrapSample采樣3次，記每次的樣本集為Si，根據(jù)式（1）給出的加權(quán)SVM訓(xùn)練3個(gè)初始SVM分類器：＝Learn（Si），并令初始集成分類器為

步驟1當(dāng)進(jìn)行第t（t＝1，2，…）次訓(xùn)練時(shí)，判斷SVM分類器是否達(dá)到終止條件Sstop，若滿足則輸出fsvm＝結(jié)束訓(xùn)練，否則轉(zhuǎn)到步驟2。

步驟2判斷U是否為空，若是，輸出fsvm＝結(jié)束訓(xùn)練；否則，先對(duì)未標(biāo)記樣本用集成分類器進(jìn)行預(yù)標(biāo)記，然后據(jù)式（5）選擇m個(gè)類標(biāo)記置信度小于閾值，即當(dāng)前分類器相對(duì)不確定的樣本，并記為。

步驟3令第t次QBC主動(dòng)學(xué)習(xí)選擇的待標(biāo)記樣本集為空集，由、組成QBC委員會(huì)，對(duì)UQ中每個(gè)樣本xi，根據(jù)式（9）計(jì)算樣本xi的投票熵VE（xi）。

步驟4判斷VE（xi）是否大于VEth，如果大于則更新待標(biāo)記樣本集X＝X∪xi；如果VE（xi）小于VEth或者VE（xi）等于零，則根據(jù)式（8）計(jì)算樣本xi與當(dāng)前已標(biāo)記樣本L的相似度dcos（xi，L），根據(jù)式（10）計(jì)算樣本xi的相對(duì)熵KL-d（xi），如果KL-d（xi）大于閾值KL-dth并且dcos（xi，L）小于相似度閾值Qdth，則更新待標(biāo)記樣本集X＝X∪xi。

步驟5由領(lǐng)域?qū)＜褽user對(duì)中每個(gè)樣本進(jìn)行正確標(biāo)記，記標(biāo)記后的集合為。

步驟6在標(biāo)記樣本集及增量樣本集上進(jìn)行SVM增量訓(xùn)練＝incLearn）（i＝1，2，3），增量訓(xùn)練后將已標(biāo)記樣本集從未標(biāo)記樣本集U刪除U＝U－，將標(biāo)記后的樣本加入標(biāo)記樣本集

步驟7令i分別等于1、2以及3，估計(jì)的訓(xùn)練誤差εi＝MeasureError（），采用AdaBoost中的方法計(jì)算權(quán)重

根據(jù)SVM主動(dòng)學(xué)習(xí)理論及QBC-ASVM算法描述可知，影響SVM主動(dòng)學(xué)習(xí)性能的因素除了關(guān)鍵的候選標(biāo)記樣本選擇策略外，還受其他的因素影響，如主動(dòng)學(xué)習(xí)算法的終止條件Sstop，即SVM主動(dòng)學(xué)習(xí)中需要估計(jì)什么時(shí)候SVM能到達(dá)最好的性能水平，以便停止標(biāo)記樣本并終止主動(dòng)學(xué)習(xí)進(jìn)程，避免花費(fèi)大量的樣本選擇及標(biāo)記代價(jià)而取的較小的性能提高，為此在QBC-ASVM算法中采用如下終止策略：

（1）在QBC-ASVM主動(dòng)學(xué)習(xí)過程中對(duì)第t次選擇候選標(biāo)記樣本時(shí)，在專家對(duì)其進(jìn)行標(biāo)記的同時(shí)，使用前次SVM分類器計(jì)算其分類正確率并記為ηk－1；

（2）統(tǒng)計(jì)QBC-ASVM主動(dòng)學(xué)習(xí)第t次選擇的最不確定性樣本數(shù)記為Sk；

（3）當(dāng)ηk達(dá)到學(xué)習(xí)器要求的某個(gè)閾值時(shí)并且其性能曲線呈現(xiàn)“rise-peak-flat”，即隨著SVM主動(dòng)學(xué)習(xí)進(jìn)程，ηk在達(dá)到某個(gè)值后在一段時(shí)間里（可以SVM主動(dòng)學(xué)習(xí)連續(xù)幾次采樣為判斷）并沒有明顯的提升（實(shí)際應(yīng)用中可以ηk的變化率作為判斷）并且Sk呈現(xiàn)減少的趨勢(shì)，則終止SVM主動(dòng)學(xué)習(xí)。

5 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證算法的正確性和有效性，通過實(shí)驗(yàn)比較了QBCASVM、隨機(jī)采樣Random、Active_Training、Active（VE）、Active（KL-d）算法的分類性能，其中Active（VE）、Active（KL-d）為QBC-ASVM算法中除步驟4分別僅采用投票熵、相對(duì)熵法度量法，Active_Training算法為未使用第1節(jié)給出的改進(jìn)加權(quán)SVM，其余算法步驟同QBC-ASVM算法；實(shí)驗(yàn)中的數(shù)據(jù)使用UCI數(shù)據(jù)庫中的breast-cancer-wisconsin、ionosphere、house-votes-84、hepatitis、credit-approval以及glass數(shù)據(jù)集。

在算法實(shí)驗(yàn)中，BootstrapSample采樣隨機(jī)地選擇2%的樣本作為SVM訓(xùn)練的初始樣本，其余98%的樣本去掉類別標(biāo)記作為候選的未標(biāo)記樣本集。算法中SVM核函數(shù)采用高斯核函數(shù)，參數(shù)值為2；每次采樣數(shù)m初始值設(shè)為8，對(duì)其調(diào)整按照隨著分類器性能達(dá)到預(yù)定指標(biāo)進(jìn)行減1，以減少每次樣本采樣數(shù)。為保證主動(dòng)學(xué)習(xí)選擇“最不確定性”的樣本，同時(shí)不漏選“富有信息”的樣本，取閾值Qth＝0.6、VEth＝0.55、KL-dth＝0.045，同樣，為了避免選擇重復(fù)類似的樣本，保證選擇的樣本具有代表性，取閾值Qdth＜0.5較為合適，算法中取Qdth＝0.45。

為了說明問題，對(duì)每個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)重復(fù)5次然后取其平均值，表3給出各算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的分類正確率性能比較，其中std為實(shí)驗(yàn)中相應(yīng)數(shù)值結(jié)果的標(biāo)準(zhǔn)差，底紋加黑數(shù)值為標(biāo)記樣本個(gè)數(shù)。其余算法對(duì)應(yīng)的樣本數(shù)為選擇的候選樣本并經(jīng)領(lǐng)域?qū)＜疫M(jìn)行標(biāo)記。

表3 各算法標(biāo)記樣本數(shù)與分類正確率性能比較

由表3以及圖2和圖3給出的各算法在數(shù)據(jù)集breast-cancer-wisconsin、hepatitis上的性能變化趨勢(shì)圖可以看出，QBC-ASVM、Active_Training、Active（VE）以及Active（KL-d）4種算法相比隨機(jī)采樣算法Random，在學(xué)習(xí)訓(xùn)練獲得相同的SVM分類正確率時(shí)，其使用的標(biāo)記樣本數(shù)都明顯少于后者，這種現(xiàn)象尤其在訓(xùn)練學(xué)習(xí)的初始階段更明顯；同時(shí)對(duì)QBC-ASVM算法來說，在達(dá)到相同的分類正確率時(shí)相比僅采用投票熵或相對(duì)熵度量的方法Active（VE）或Active（KL-d），后兩者分別需要多標(biāo)記7.6%、7.8%的樣本；同時(shí)可以看出，在訓(xùn)練達(dá)到相同的分類正確率時(shí)，相比Active_Training算法，采用第1節(jié)給出的改進(jìn)的加權(quán)SVM的QBC-ASVM、Active（VE）以及Active（KL-d）算法所標(biāo)記的樣本少于Active_Training算法，尤其在訓(xùn)練的初始階段Active_Training算法呈現(xiàn)時(shí)高時(shí)低現(xiàn)象，即相比其他3種算法，標(biāo)記了更多的樣本，而分類正確率提高不明顯，這說明了Active_Training算法在算法的初始階段，由于樣本分布不均衡，可能采樣到孤立點(diǎn)導(dǎo)致分類正確率變化。

圖2 各算法在數(shù)據(jù)集breast-cancer-wisconsin上的實(shí)驗(yàn)比較

圖3 各算法在數(shù)據(jù)集hepatitis上的實(shí)驗(yàn)比較

從圖2和圖3可以看出來，QBC-ASVM算法在標(biāo)記大概60個(gè)樣本、Active（VE）以及Active（KL-d）算法在標(biāo)記90多個(gè)樣本時(shí)，其分類正確率都已達(dá)90%多，隨著學(xué)習(xí)的進(jìn)程，各算法的性能曲線都趨于“平穩(wěn)”，這個(gè)時(shí)候應(yīng)該根據(jù)第4節(jié)中給出的終止主動(dòng)學(xué)習(xí)策略終止主動(dòng)學(xué)習(xí)進(jìn)程，避免花費(fèi)大量的樣本選擇及標(biāo)記代價(jià)而取的較小的性能提高。

6 結(jié) 論

本文在研究分析傳統(tǒng)SVM訓(xùn)練算法存在的局限性——即傳統(tǒng)的SVM訓(xùn)練方法都是基于大量帶有類標(biāo)記樣本的監(jiān)督學(xué)習(xí)以及現(xiàn)有主動(dòng)學(xué)習(xí)在SVM訓(xùn)練中所存在的一些問題的基礎(chǔ)上，針對(duì)大量標(biāo)記樣本難以獲得或標(biāo)注代價(jià)高，學(xué)習(xí)中樣本分布不平衡等問題，提出了改進(jìn)的QBC主動(dòng)學(xué)習(xí)方法，將其應(yīng)用于SVM訓(xùn)練學(xué)習(xí)過程中，通過實(shí)驗(yàn)驗(yàn)證了算法的有效性和可行性，這種方法可以有效減小主動(dòng)學(xué)習(xí)算法的采樣次數(shù)，降低標(biāo)注代價(jià)。

［1］Long J，Yin J P，Zhu E，et al.A committee-based mis-classification sampling algorithm in active learning［J］.Computer Engineering&Science，2008，30（4）：69- 72.（龍軍，殷建平，祝恩等.主動(dòng)學(xué)習(xí)中一種基于委員會(huì)的錯(cuò)誤分類采樣算法［J］.計(jì)算機(jī)工程與科學(xué)，2008，30（4）：69- 72.）

［2］Zhao W Z，Ma H F，Li Z Q，et al.Efficient active leaning for semi-supervised document clustering［J］.Journal of Software，2012，23（6）：1486- 1499.（趙衛(wèi)中，馬慧芳，李志清，等.一種結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督文檔聚類算法［J］.軟件學(xué)報(bào)，2012，23（6）：1486- 1499.）

［3］Xu J，Shi P F.Active learing with labled and un Labeled samples for content-based image retrieval［J］.Journal of Shanghai Jiaotong University，2004，38（12）：2068- 2072.（徐杰，施鵬飛.圖像檢索中基于標(biāo)記與未標(biāo)記樣本的主動(dòng)學(xué)習(xí)算法［J］.上海交通大學(xué)學(xué)報(bào)，2004，38（12）：2068- 2072.）

［4］Cohn D A，Ghahramani Z，Jordan M I.Active learning with statistical models［J］.Journal of Artificial Intelligence Research，1996，4：129- 145.

［5］Roy N，McCallum A K.Toward optimal active learning through sampling estimation of error reduction［C］∥Proc.of the 18th International Conference on Machine Learning，2001：441- 448.

［6］Lewis D D，Gale W.A sequential algorithm for training text classifiers［C］∥Proc.of the 17th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval，1994：3- 12.

［7］Seung H S，Opper M，Sompolinsky H.Query by committee.［C］∥Proc.of the 15th Annual ACM Workshop on Computational Learning Theory，1992：287- 294.

［8］Freund Y，Seung H S，Samir E，et al.Selective sampling using the query by committee algorithm［J］.Machine Learning，1997，28（2／3）：133- 168.

［9］Zhao Y，Mu Z C，Dong J，et.al.A credit risk evaluation model for telecom clients based on query-by-comtitee mehtod of active learning［J］.Journal of University of Science and Technology Beijing，2007，29（4）：442- 445.（趙悅，穆志純，董潔，等.基于QBC主動(dòng)學(xué)習(xí)方法建立電信客戶信用風(fēng)險(xiǎn)等級(jí)評(píng)估模型［J］.北京科技大學(xué)學(xué)報(bào)，2007，29（4）：442- 445.）

［10］Tang M Z，Yang C H，Gui W H.Fault detection based on modified QBC and CS-SVM［J］.Control and Decision，2012，27（10）：1489-1493.（唐明珠，陽春華，桂衛(wèi)華.基于改進(jìn)的QBC和CS-SVM的故障檢測(cè)［J］.控制與決策，2012，27（10）：1489- 1493.）

［11］Lin C F，Wang S D.Fuzzy support vector machine［J］.IEEE Trans.on Neural Networks，2001，13（2）：464- 471.

［12］Xu H L，Wang X D，Liao Y，et al.Incremental training algorithm of SVM based on active learning［J］.Control and Decision，2010，25（2）：282- 286.（徐海龍，王曉丹，廖勇，等.一種基于主動(dòng)學(xué)習(xí)的SVM增量訓(xùn)練算法［J］.控制與決策，2010，25（2）：282- 286.）

［13］Hu Z P.An active learning strategy of SVM via optimal selection of labeled data［J］.Signal Processing，2008，24（1）：105- 107.（胡正平.基于最佳樣本標(biāo)記的主動(dòng)支持向量機(jī)學(xué)習(xí)策略［J］.信號(hào)處理，2008，24（1）：105- 107.）

［14］Zhang X，Xiao X L，Xu G Y.Probabilistic outputs for support vector machines based on the maximum entropy estimation［J］.Control and Decision，2006，21（7）：767- 770.（張翔，肖小玲，徐光祐.基于最大熵估計(jì)的支持向量機(jī)概率建模［J］.控制與決策，2006，21（7）：767- 770.）

［15］Panda N，Goh K S，Chang E Y.Active learning in very large databases［J］.Multimedia Tools and Applications Archive，2006，31（3）：249- 267.

［16］McCallum A K，Nigam K.Employing EM and pool-based active learning for text classification［C］∥Proc.of the 15th International Conference on Machine Learning，1998：350- 358.

［17］Argamon-Engelson S，Dagan I.Committee-based sample selection for probabilistic classifiers［J］.Journal of Artificial Intelligence Research，1999，11：335- 360.

Active learning algorithm for SVM based on QBC

XU Hai-long，BIE Xiao-feng，F(xiàn)ENG Hui，WU Tian-ai
（College of Air and Missile Defense，Air Force Engineering University，Xi’an 710051，China）

To the problem that large-scale labeled samples is not easy to acquire and the class-unbalanced dataset in the course of souport vector machine（SVM）training，an active learning algorithm based on query by committee（QBC）for SVM（QBC-ASVM）is proposed，which efficiently combines the improved QBC active learning and the weighted SVM.In this method，QBC active learning is used to select the samples which are the most valuable to the current SVM classifier，and the weighted SVM is used to reduce the impact of the unbalanced data set on SVMs active learning.The experimental results show that the proposed approach can considerably reduce the labeled samples and costs compared with the passive SVM，and at the same time，it can ensure that the accurate classification performance is kept as the passive SVM，and the proposed method improves generalization performance and also expedites the SVM training.

active learning；support vector machine（SVM）；query by committee（QBC）；classification

TP 181

A

10.3969／j.issn.1001-506X.2015.12.31

徐海龍（1981- ），男，講師，博士，主要研究方向?yàn)槟Ｊ阶R(shí)別、支持向量機(jī)、目標(biāo)分配。

E-mail：xhl_81329＠163.com

別曉峰（1979- ），男，講師，博士，主要研究方向?yàn)槟繕?biāo)分配、作戰(zhàn)評(píng)估與仿真。

E-mail：58719591＠qq.com

馮 卉（1982- ），女，講師，碩士，主要研究方向?yàn)槟繕?biāo)識(shí)別、目標(biāo)分配、作戰(zhàn)評(píng)估與仿真。

E-mail：fenghui_yy＠126.com

吳天愛（197-7- ），女，講師，博士研究生，主要研究方向?yàn)槟繕?biāo)識(shí)別、目標(biāo)跟蹤。

E-mail：wuyh7277＠163.com

1001-506X（2015）12-2865-07

2014- 12- 10；

2015- 04- 12；網(wǎng)絡(luò)優(yōu)先出版日期：2015- 07- 06。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150706.1606.008.html

國家自然科學(xué)基金（61273275）資助課題