半監(jiān)督分類(lèi)中的噪聲控制及相關(guān)算法

姜 震，詹永照

(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江 212013)

半監(jiān)督學(xué)習(xí)能同時(shí)利用有標(biāo)簽樣本和無(wú)標(biāo)簽樣本進(jìn)行學(xué)習(xí)，有效緩解標(biāo)簽瓶頸問(wèn)題，近年來(lái)一直是機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn).大多數(shù)半監(jiān)督分類(lèi)算法，如基于生成式模型的方法、基于低密度劃分的方法和基于圖的半監(jiān)督學(xué)習(xí)方法［1-2］等，通過(guò)將無(wú)標(biāo)簽樣本的分布信息結(jié)合到原有的模型假設(shè)中來(lái)實(shí)現(xiàn)對(duì)無(wú)標(biāo)簽樣本的利用.但是如果模型關(guān)于數(shù)據(jù)分布的假設(shè)和實(shí)際不一致，可能反而會(huì)降低學(xué)習(xí)性能［1-2］.

作為半監(jiān)督學(xué)習(xí)的另一分支，self-training類(lèi)算法［3-4］、co-training 類(lèi)算法［5-7］、tri-training［8］以及半監(jiān)督集成學(xué)習(xí)［9-11］等算法，直接利用當(dāng)前分類(lèi)器的預(yù)測(cè)結(jié)果(偽標(biāo)簽樣本)進(jìn)行迭代訓(xùn)練，不需要額外的先驗(yàn)知識(shí)進(jìn)行模型假設(shè)，高效易行.但是由于偽標(biāo)簽樣本可能預(yù)測(cè)錯(cuò)誤，即存在分類(lèi)噪聲;另一方面，偽標(biāo)簽樣本不是獨(dú)立隨機(jī)抽取的，因此還會(huì)存在分布噪聲.如何控制偽標(biāo)簽樣本中的噪聲，是這類(lèi)算法成功的關(guān)鍵.

現(xiàn)有的大多數(shù)算法［3-11］通過(guò)選擇信任度高的預(yù)測(cè)結(jié)果作為偽標(biāo)簽樣本來(lái)減少分類(lèi)噪聲，但忽略了偽標(biāo)簽樣本不是獨(dú)立隨機(jī)抽取而帶來(lái)的分布噪聲;也有少部分算法［2，10］選擇將所有預(yù)測(cè)結(jié)果都加入訓(xùn)練集來(lái)降低分布噪聲，但是這種做法是以降低偽標(biāo)簽樣本的準(zhǔn)確率為代價(jià)的.筆者在前期關(guān)于多分類(lèi)器協(xié)同訓(xùn)練的工作中［12］，考慮兼顧降低分類(lèi)噪聲和分布噪聲.但是僅通過(guò)偽標(biāo)簽樣本的類(lèi)別比例來(lái)估算和控制分布噪聲的方法較為簡(jiǎn)單.

文中擬提出一種利用混合高斯模型來(lái)表示樣本分布，進(jìn)而估算分布噪聲的方法;并基于分類(lèi)噪聲和分布噪聲下的算法可學(xué)習(xí)性和泛化誤差分析［12］，提出一種可回溯的利用偽標(biāo)簽樣本的迭代訓(xùn)練策略，而且將其進(jìn)一步與集成學(xué)習(xí)相結(jié)合，提出一種ensemble self-learning(ESL)算法;最后在文獻(xiàn)［13］所用到的6個(gè)文本數(shù)據(jù)集上進(jìn)行試驗(yàn)驗(yàn)證.

1 ensemble self-learning算法

1.1 泛化誤差與偽標(biāo)簽樣本的噪聲分析

如何選擇高質(zhì)量的偽標(biāo)簽樣本是本類(lèi)算法的關(guān)鍵.文獻(xiàn)［12］給出了利用偽標(biāo)簽樣本訓(xùn)練時(shí)噪聲影響的相關(guān)理論分析.

定理1 對(duì)于弱分類(lèi)器h1，如果向h1提供的偽標(biāo)簽樣本滿足分類(lèi)噪聲β＜l/2，分布噪聲 η≤ε+1/q(l+p，1/ε，1/(1-2β)，1/δ)，那么h1是可學(xué)習(xí)的，且有下式成立:

式中:l和p分別為有標(biāo)簽樣本和偽標(biāo)簽樣本的數(shù)量;N為假設(shè)空間的規(guī)模.取μ為令式(1)取等值的量，則式(1)可改寫(xiě)為

進(jìn)而有

根據(jù)上述定理，如果能估算出訓(xùn)練集中的分類(lèi)噪聲和分布噪聲，就可以根據(jù)樣本數(shù)量推斷出在一定信任度下的泛化誤差.這提供了評(píng)估迭代訓(xùn)練中分類(lèi)器性能的準(zhǔn)則，從而可以有效防止“差”的偽標(biāo)簽樣本加入帶來(lái)的性能下降.

分類(lèi)噪聲的估算:文中定義了一個(gè)偽驗(yàn)證集V，由L和偽標(biāo)簽樣本中信任度最高的30%組成，令A(yù)V(hi)表示hi在V上的準(zhǔn)確率，則1-AV(hi)用于估算分類(lèi)噪聲hi.

分布噪聲的估算:假設(shè)有個(gè)K類(lèi)別，文中采用K個(gè)高斯混合分布P(A)來(lái)模擬樣本空間的分布，其參數(shù)μ，σ2可以由初始的訓(xùn)練樣本來(lái)估計(jì).當(dāng)K足夠大的時(shí)候，高斯混合模型可以逼近任意分布［14］，因此分布噪聲可以由P(A)與加入偽標(biāo)簽樣本后的高斯混合分布Q(A)來(lái)估算［15］:

1.2 算法表示

假設(shè)L，U分別為有標(biāo)簽樣本集和無(wú)標(biāo)簽樣本集，h為給定的基分類(lèi)器，P為其偽標(biāo)簽樣本集，M為每次迭代訓(xùn)練加入的偽標(biāo)簽樣本的數(shù)量，H為迭代訓(xùn)練中生成的分類(lèi)器集合.則ensemble self-learning算法如下:

輸入:L，U，并給定最大迭代次數(shù)T.

步驟:初始化j=N=0;H=P=Φ;V=L.

在L上訓(xùn)練初始分類(lèi)器h(0).

Repeat tillj＜Torh不再變化.

1)將當(dāng)前分類(lèi)器h(j)加入H(j)中.

2)用H(j)分類(lèi)U中的數(shù)據(jù).

3)按照類(lèi)別比例和置信度從U中選擇個(gè)N預(yù)測(cè)結(jié)果并加入到臨時(shí)偽標(biāo)簽數(shù)據(jù)集Pi’中.

4)令P(j+1)=P'∪P(j).

5)在L∪P(j+1)上重新訓(xùn)練h(j+1).

6)若噪聲超過(guò)臨界值或根據(jù)公式(2)估算的泛化誤差上升，則令Pi(j+1)=Pi(j)，hi(j+1)=h(j).

7)令Pi'=Φ并更新偽驗(yàn)證集V.

8)N=N+m;j=j+1.

輸出:H=combine(h(0)，h(1)，…，h(j)).

為了降低偽標(biāo)簽樣本帶來(lái)的噪聲，所提出算法中主要采取了如下3種策略.

1)利用迭代訓(xùn)練中生成的分類(lèi)器構(gòu)成的集合來(lái)預(yù)測(cè)樣本標(biāo)簽，從而將自訓(xùn)練方法和集成學(xué)習(xí)結(jié)合起來(lái)，以提高偽標(biāo)簽的準(zhǔn)確率.

2)在算法中按照類(lèi)別比例(可以從L上估計(jì))來(lái)添加偽標(biāo)簽樣本.當(dāng)原始樣本存在嚴(yán)重的類(lèi)別不平衡時(shí)，有可能會(huì)導(dǎo)致預(yù)測(cè)結(jié)果向大類(lèi)別傾斜，造成某些小類(lèi)的偽標(biāo)簽樣本不足.這時(shí)候可以利用重采樣技術(shù)對(duì)小類(lèi)別的訓(xùn)練樣本過(guò)采樣，來(lái)控制類(lèi)別比例，從而減少分布噪聲.

3)根據(jù)定理1和所提出的噪聲量化方法，評(píng)估當(dāng)前噪聲下的分類(lèi)器的性能.據(jù)此及時(shí)移除有可能造成分類(lèi)性能下降的偽標(biāo)簽樣本，實(shí)現(xiàn)迭代訓(xùn)練的可回溯機(jī)制.

2 試驗(yàn)結(jié)果及分析

在6個(gè)有代表性的數(shù)據(jù)集上給出了ESL算法的試驗(yàn)結(jié)果，并與2種先進(jìn)的半監(jiān)督集成學(xué)習(xí)算法CoBC［12］和 MCSSB［13］進(jìn)行了比較.

2.1 試驗(yàn)設(shè)置

采用支持向量機(jī)(support vector machine，SVM)作為基分類(lèi)器，并參照Co-EM SVM中的策略，計(jì)算SVM的預(yù)測(cè)結(jié)果的信任度;采用SVMlight［16］來(lái)實(shí)現(xiàn)，并使用其默認(rèn)參數(shù)和線性核函數(shù).

試驗(yàn)數(shù)據(jù)集有如下6個(gè):①movie(24 841個(gè)特征，2個(gè)類(lèi))，把來(lái)自于IMDB的電影評(píng)論劃分為正面和負(fù)面的，共包含2 000個(gè)樣本;②webkb(22 824個(gè)特征，4個(gè)類(lèi))，把來(lái)自大學(xué)的網(wǎng)頁(yè)劃分為學(xué)生、課程、院系、項(xiàng)目4類(lèi)，共包含4 200個(gè)樣本;③sraa(77 494個(gè)特征，4個(gè)類(lèi))，把新聞組中的消息劃分為模擬飛行、現(xiàn)實(shí)飛行、模擬駕駛和真實(shí)駕駛，包含19 684個(gè)樣本;④sector(22 835個(gè)特征，38個(gè)類(lèi))，把網(wǎng)頁(yè)劃分到特定的工業(yè)部門(mén)，共4 582個(gè)樣本;⑤blogs(95 583個(gè)特征，4個(gè)類(lèi))，根據(jù)博客內(nèi)容劃分其發(fā)布者的年齡段，包含8 864個(gè)樣本;⑥ner(60 502個(gè)特征，9個(gè)類(lèi))，來(lái)自CoNLL 2003數(shù)據(jù)集，包含48 622個(gè)樣本.

文中隨機(jī)選取10組有標(biāo)簽樣本作為初始訓(xùn)練集，每組隨機(jī)選取2 000個(gè)當(dāng)成無(wú)標(biāo)簽樣本加以利用，最后取其運(yùn)行結(jié)果的平均值.試驗(yàn)時(shí)算法中的最大迭代次數(shù)T設(shè)置為50，m設(shè)置為100.

2.2 試驗(yàn)結(jié)果及分析

表1給出了各個(gè)算法的分類(lèi)準(zhǔn)確率，括號(hào)中的值代表有標(biāo)簽樣本的總數(shù)量.

表1 分類(lèi)準(zhǔn)確率 %

由表1可見(jiàn)，對(duì)于同樣的算法，增加有標(biāo)簽數(shù)據(jù)的數(shù)量時(shí)，得到的準(zhǔn)確率都有明顯提高.當(dāng)利用無(wú)標(biāo)簽數(shù)據(jù)輔助訓(xùn)練的時(shí)候，可發(fā)現(xiàn)絕大多數(shù)情況下，各個(gè)半監(jiān)督算法相對(duì)于基分類(lèi)器，在平均準(zhǔn)確率上都取得了不同程度的提高.特別是在movie(20)和sraa(40)上，絕大多數(shù)半監(jiān)督算法的準(zhǔn)確率甚至還高于其基分類(lèi)器在movie(50)和sraa(100)上的準(zhǔn)確度，這說(shuō)明半監(jiān)督學(xué)習(xí)中使用無(wú)標(biāo)簽數(shù)據(jù)的確有利于提高分類(lèi)器的準(zhǔn)確性.

但是無(wú)標(biāo)簽數(shù)據(jù)的使用并非總是有利的，在某些情況下，可發(fā)現(xiàn)偽標(biāo)簽數(shù)據(jù)反而會(huì)降低基分類(lèi)器的性能，比如在sector數(shù)據(jù)集上，具體情況可分析圖1.圖1給出了3個(gè)半監(jiān)督算法及其基分類(lèi)器分別在webkb(100)和sector(380)上準(zhǔn)確率的迭代變化.

圖1 迭代訓(xùn)練中的準(zhǔn)確率變化

由圖1可見(jiàn)，在結(jié)構(gòu)良好、容易劃分的webkb(100)數(shù)據(jù)集上，隨著迭代過(guò)程的進(jìn)行，3個(gè)算法的準(zhǔn)確率都在提升;而在結(jié)構(gòu)復(fù)雜的sector上，由于偽標(biāo)簽樣本的準(zhǔn)確率較低，相應(yīng)地，CoBC和MCSSB的準(zhǔn)確率都有不同程度的下降.

CoBC和MCSSB在使用偽標(biāo)簽樣本時(shí)，都沒(méi)有采用對(duì)噪聲進(jìn)行過(guò)濾的措施;文中提出的算法不僅利用信任度遞增地添加偽標(biāo)簽樣本，還能夠把不好的偽標(biāo)簽樣本及時(shí)從訓(xùn)練集中移除，因此獲得了總體上更好的分類(lèi)效果.

3 結(jié)論

文中提出的算法在75%的試驗(yàn)數(shù)據(jù)集上都取得了最好的準(zhǔn)確性以及最高的平均準(zhǔn)確率.相關(guān)試驗(yàn)表明該算法能有效控制偽標(biāo)簽樣本中的噪聲，從而提高半監(jiān)督分類(lèi)算法的泛化性能.隨著偽標(biāo)簽樣本的加入，迭代訓(xùn)練產(chǎn)生的中間分類(lèi)器的差異逐漸縮小，導(dǎo)致其集成的效果存在局限性.在今后的工作中，筆者將在集成方法上開(kāi)展進(jìn)一步的研究.

References)

［1］Mohamed Farouk Abdel Hady，F(xiàn)riedhelm Schwenker.Semi-supervised learning［J］.Handbook on Neural Information Processing Intelligent Systems Reference Library，2013，49:215-239.

［2］Jiang Zhen，Zhang Shiyong，Zeng Jianping.A hybrid generative/discriminativemethod forsemi-supervised classification ［J］.Knowledge-Based Systems，2013，37(2):137-145.

［3］Hu Wei，Chen Jianfeng，Qu Yuzhong.A self-training approach for resolving object coreference on the semantic web［C］∥Proceedings of the20th International Conference on World Wide Web.Hyderabad，India:ACM，2011:87-96.

［4］He Yulan，Zhou Deyu.Self-training from labeled features for sentiment analysis［J］.Information Processing and Management，2011，47(4):606-616.

［5］Yaslan Y，Cataltepe Z.Co-training with relevant random subspaces［J］.Neurocomputing，2010，73(10/11/12):1652-1661.

［6］Sun Shiliang，Jin Feng.Robust co-training［J］.International Journal of Pattern Recognition and Artificial Intel-ligence，2011，25(7):1113-1126.

［7］Zhang Minling，Zhou Zhihua.CoTrade:confident cotraining with data editing［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2011，41(6):1612-1626.

［8］Abdel Hady M F，Schwenker F，Palm G.Semi-supervised learning for tree-structured ensembles of RBF networks with co-training［J］.Neural Networks，2010，23(4):497-509.

［9］Zhang Minling，Zhou Zhihua.Exploiting unlabeled data to enhance ensemble diversity［J］.Data Mining and Knowledge Discovery，2013，26(1):98-129.

［10］Chen Ke，Wang Shihai.Semi-supervised learning via regularized boosting working on multiple semi-supervised assumptions［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(1):129-143.

［11］Li Yufeng，Zhou Zhihua.Towards making unlabeled data never hurt［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37(1):175-188.

［12］Jiang Zhen，Zeng Jianping，Zhang Shiyong.Inter-training:exploiting unlabeled data in multi-classifier systems［J］.Knowledge-Based Systems，2013，45(3):8-19.

［13］Druck G，Pal C，McCallum A，et al.Semi-supervised classification with hybrid generative/discriminative methods［C］∥Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Jose，USA:ACM，2007:280-289.

［14］張曉娜，何 仁，劉志強(qiáng)，等.基于空間信息高斯混合模型的運(yùn)動(dòng)車(chē)輛檢測(cè)［J］.江蘇大學(xué)學(xué)報(bào):自然科學(xué)版，2011，32(4):385-388.

Zhang Xiaona，He Ren，Liu Zhiqiang，et al.Moving vehicle detection method based on Gaussian mixture model of spatial information［J］.Journal of Jiangsu University:Natural Science Edition，2011，32(4):385-388.(in Chinese)

［15］Decatur S E.Statistical queries and faulty PAC oracles［C］∥Proceedings of the6th Annual ACM Conference on Computational Learning Theory.Santa Cruz，USA:ACM，1993:262-268.

［16］Joachims T.Making large-scale SVM learning practical［J］.General Information，1998，8(3):169-184.