半監(jiān)督學(xué)習(xí)存在的問題和對(duì)策分析研究 教育教學(xué)專業(yè)

摘要 半監(jiān)督學(xué)習(xí)利用大量未標(biāo)記數(shù)據(jù)結(jié)合少量標(biāo)記數(shù)據(jù)提升學(xué)習(xí)性能。本文涉及幾種半監(jiān)督分類方法的評(píng)價(jià)。文章由三個(gè)主要部分組成。首先，介紹半監(jiān)督學(xué)習(xí)的定義和基本假設(shè)；第二部分為本文的主體部分，介紹了四種半監(jiān)督學(xué)習(xí)方法：弱監(jiān)督學(xué)習(xí)、生成模型、直推式支持向量機(jī)、基于圖的方法，結(jié)合數(shù)據(jù)集對(duì)其優(yōu)勢(shì)和缺陷進(jìn)行評(píng)價(jià)；在第三部分中，本文從理論上分析了未標(biāo)記數(shù)據(jù)對(duì)分類性能提升的作用。關(guān)鍵詞：半監(jiān)督學(xué)習(xí)分類生成模型直推式支持向量機(jī)基于圖的方法Abstract Semi-supervisedlearningusesalargeamountofunlabeleddata,togetherwiththelabeleddatatobuildabetterclassifier.Thispaperisconcernedwiththeevaluationofseveralsemi-supervisedmethods.Therearethreemajoringredients.Thefirstisanintroductiononthedefinitionandsomepopularassumptionsofsemi-supervisedlearning.Thesecond,whichisthemainingredientofthispaper,studiesthefourmainsemi-supervisedmethods,includingweaklysupervisedmethods,generativemodel,transductivesupportvectormachineandgraph-basedmethods.Someexperimentsondatasetsofthesemethodshavebeencarriedout,tocharacterizetheiradvantagesandlimitations.Thethirdingredientpresentthetheoreticalanalysisofhowunlabeleddatacanbeusedsuccessfullyforclassification.Keywords:semi-supervisedleaning,classification,generativemodel,transductivesupportvectormachine,graph-basedmethod

第一章前言1.1研究背景與意義1.1.1半監(jiān)督學(xué)習(xí)的定義為定義半監(jiān)督學(xué)習(xí)，首先我們需要明確監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的含義。首先給出一些基本的定義REF_Ref513594746\r[1]REF_Ref513594746\r\h。樣例x通常指一個(gè)D維向量x={x1,x2,?,xd}，它的每一維稱為一個(gè)特征，D即為特征向量的維數(shù)。訓(xùn)練集xi,yii=1n則是由n個(gè)樣本點(diǎn)組成的集合，它是學(xué)習(xí)過程的輸入值。標(biāo)簽y與樣 監(jiān)督學(xué)習(xí)是指，通過給定的有標(biāo)記訓(xùn)練集xi,yii=1l，訓(xùn)練一個(gè)從輸入X到輸出Y的映射f。監(jiān)督學(xué)習(xí)根據(jù)標(biāo)簽y的類型可分為兩類。如果y是離散值，則為分類問題，此時(shí)f是一個(gè)分類器；否則為回歸問題，f則為回歸函數(shù)。無監(jiān)督學(xué)習(xí)的輸入是一個(gè)未標(biāo)記數(shù)據(jù)集xii=1半監(jiān)督學(xué)習(xí)是一種介于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)之間的學(xué)習(xí)方法REF_Ref513594846\r[2]。對(duì)于半監(jiān)督分類問題，它綜合利用標(biāo)記數(shù)據(jù)集xi,yii=1l和未標(biāo)記數(shù)據(jù)集xi根據(jù)學(xué)習(xí)目的，半監(jiān)督學(xué)習(xí)可分為兩種類型：純半監(jiān)督學(xué)習(xí)和直推式半監(jiān)督學(xué)習(xí)。前者的目標(biāo)是利用給定訓(xùn)練集xi,yii=1l,xii=l+1u1.1.2半監(jiān)督學(xué)習(xí)的動(dòng)機(jī)傳統(tǒng)的監(jiān)督學(xué)習(xí)需要一定規(guī)模的標(biāo)記訓(xùn)練集，然而，實(shí)際問題中標(biāo)簽的獲取代價(jià)很高。相比于難以獲得的標(biāo)記數(shù)據(jù)，我們更容易獲取大量無標(biāo)記數(shù)據(jù)。例如，在文本分類問題中，根據(jù)內(nèi)容對(duì)文檔進(jìn)行人工標(biāo)記很費(fèi)時(shí)，但未標(biāo)注的文檔容易獲得。半監(jiān)督學(xué)習(xí)的動(dòng)機(jī)在于，有效利用大量相對(duì)廉價(jià)的未標(biāo)記數(shù)據(jù)提升學(xué)習(xí)性能。 半監(jiān)督學(xué)習(xí)通常需要依賴某些基本假設(shè)。常用的假設(shè)有以下三種：平滑假設(shè)REF_Ref513594746\r[1]，即當(dāng)樣本x1,x2在樣本分布密集的區(qū)域內(nèi)距離低密度分離假設(shè)REF_Ref513594746\r[1]，要求決策邊界位于樣本分布稀疏的區(qū)域。低密度分離假設(shè)的等價(jià)表述為聚類假設(shè)，即位于同一聚類的樣本有相同標(biāo)簽。聚類假設(shè)也可被視為平滑假設(shè)的一個(gè)特例，因?yàn)橥ǔ颖炯械膮^(qū)域組成一個(gè)聚類。在聚類假設(shè)下，未標(biāo)記數(shù)據(jù)指導(dǎo)分類器識(shí)別數(shù)據(jù)密集和稀疏的區(qū)域，使決策平面穿過低密度區(qū)域。流形假設(shè)REF_Ref513595235\r[3]，這一假設(shè)認(rèn)為在一個(gè)小的局部鄰域內(nèi)，樣本有相似的性質(zhì)，因而有相似的輸出，在分類問題中則是有相同的標(biāo)簽。在流形假設(shè)下，未標(biāo)記數(shù)據(jù)讓數(shù)據(jù)空間變得更加密集，從而準(zhǔn)確反映空間的局部特征。流形假設(shè)可以看作是從局部角度描述的聚類假設(shè)。三種假設(shè)本質(zhì)上是一致的，區(qū)別在于關(guān)注的角度不同。流形假設(shè)可以應(yīng)用于半監(jiān)督回歸，因此更為普遍。1.2研究成果回顧最早在分類問題中使用未標(biāo)記數(shù)據(jù)的是自訓(xùn)練方法REF_Ref512851555\r[4]。自訓(xùn)練在學(xué)習(xí)過程中反復(fù)利用某種監(jiān)督學(xué)習(xí)方法，是一種包裹算法。它將標(biāo)記數(shù)據(jù)集作為初始訓(xùn)練集，在每一步迭代中通過決策函數(shù)將部分未標(biāo)記數(shù)據(jù)聯(lián)同新給定的標(biāo)簽并入訓(xùn)練集，在新的訓(xùn)練集上再次訓(xùn)練分類器。 之后提出的是直推式學(xué)習(xí)的概念REF_Ref513632422\r[5]，它基于Vapnik原理，即不在解決問題的過程中解決更復(fù)雜的問題。直推式學(xué)習(xí)只預(yù)測(cè)已有未標(biāo)記數(shù)據(jù)的標(biāo)簽，對(duì)新的樣本不具備預(yù)測(cè)能力。 半監(jiān)督學(xué)習(xí)在20世紀(jì)70年代取得重要發(fā)展。對(duì)于高斯混合分布模型或混合多項(xiàng)分布模型REF_Ref513632581\r[6]，利用EM算法可在由標(biāo)記和未標(biāo)記數(shù)據(jù)集組成的訓(xùn)練集上對(duì)模型參數(shù)進(jìn)行最大似然估計(jì)。更進(jìn)一步地，每個(gè)分類可以對(duì)應(yīng)多個(gè)混合成分。 20世紀(jì)90年代，由于自然語言處理和文本分類對(duì)利用未標(biāo)記數(shù)據(jù)提升分類性能的需求，半監(jiān)督學(xué)習(xí)成為熱點(diǎn)問題。我們通常認(rèn)為，“半監(jiān)督學(xué)習(xí)”這一術(shù)語在1992年首次出現(xiàn)REF_Ref513594746\r[1]。 目前主要的半監(jiān)督學(xué)習(xí)方法有協(xié)同訓(xùn)練REF_Ref513633015\r[7]、生成模型REF_Ref513633030\r[6]、直推式支持向量機(jī)REF_Ref513633085\r[8]和基于圖的方法REF_Ref513633095\r[9]。 1.3論文的章節(jié)安排 在第二章中，我們將介紹兩種弱監(jiān)督學(xué)習(xí)方法：自訓(xùn)練和協(xié)同訓(xùn)練，并在標(biāo)準(zhǔn)數(shù)據(jù)集上對(duì)其分類性能進(jìn)行簡單評(píng)測(cè)。 在第三章中我們將介紹生成模型的原理，并具體介紹了基于混合多項(xiàng)分布的樸素貝葉斯模型，以及如何在標(biāo)簽缺失的情況下用EM算法進(jìn)行參數(shù)估計(jì)。同時(shí)，我們將其應(yīng)用在文本分類問題中，在20Newsgroups數(shù)據(jù)集上對(duì)比了樸素貝葉斯和半監(jiān)督樸素貝葉斯模型的分類準(zhǔn)確度。 在第四章中我們將介紹直推式支持向量機(jī)的理論，在滿足低密度分離假設(shè)的數(shù)據(jù)集和隨機(jī)選取的數(shù)據(jù)集上，將其分類準(zhǔn)確度與支持向量機(jī)進(jìn)行比較。 在第五章中，我們將給出三種基于圖的半監(jiān)督學(xué)習(xí)方法，在正則化框架下完成其理論推導(dǎo)，并在圖像數(shù)據(jù)集USPS和文本數(shù)據(jù)集20Newsgroups的一個(gè)子集上觀測(cè)其分類性能。 在第六章中，我們基于PAC框架，對(duì)半監(jiān)督學(xué)習(xí)進(jìn)行簡單的理論分析。 在結(jié)論部分，我們對(duì)全文內(nèi)容進(jìn)行總結(jié)，并提及半監(jiān)督學(xué)習(xí)在未來的發(fā)展方向。

第二章弱監(jiān)督學(xué)習(xí)自訓(xùn)練和協(xié)同訓(xùn)練在分類器的學(xué)習(xí)過程中，通過自助法利用未標(biāo)記樣本擴(kuò)大訓(xùn)練集的規(guī)模，但依然使用監(jiān)督式的分類器，因此又稱為“弱監(jiān)督學(xué)習(xí)”REF_Ref513633165\r[10]。本章余下部分將介紹這兩種學(xué)習(xí)方式，給出實(shí)驗(yàn)結(jié)果和評(píng)價(jià)。2.1自訓(xùn)練? 自訓(xùn)練是一種簡單高效的半監(jiān)督學(xué)習(xí)方法。它不需要任何對(duì)于輸入數(shù)據(jù)的假設(shè)，它所基于的假設(shè)是，對(duì)于每一次預(yù)測(cè)，置信度高的樣本有更大的可能性獲得正確分類。自訓(xùn)練的學(xué)習(xí)步驟如下：給定有標(biāo)簽的訓(xùn)練集L，無標(biāo)記樣本集U；在L上訓(xùn)練初始分類器；利用初始分類器對(duì)U中全部數(shù)據(jù)進(jìn)行標(biāo)記，將置信度最高的數(shù)據(jù)及其新獲得的標(biāo)簽移入L中，從而完成對(duì)L的更新；在新獲得的L上重新訓(xùn)練分類器，如此迭代，直到所有的無標(biāo)記數(shù)據(jù)都獲得標(biāo)記為止；最后，原始的標(biāo)記數(shù)據(jù)集與獲得標(biāo)簽的無標(biāo)記數(shù)據(jù)集將共同作為訓(xùn)練集，訓(xùn)練出最終的分類器，對(duì)新的樣本仍可進(jìn)行分類。上述訓(xùn)練過程中對(duì)分類器的類型沒有任何限制。由此看出，自訓(xùn)練是一種包裹算法，即它在中間步驟中可以對(duì)分類方法進(jìn)行開放性的選擇。自訓(xùn)練通過在每次迭代中從未標(biāo)記數(shù)據(jù)集中選取樣本并入標(biāo)記數(shù)據(jù)集，解決了標(biāo)記樣本數(shù)量有限的問題。然而，由于訓(xùn)練初始分類器的樣本很少，對(duì)未標(biāo)記樣本容易出現(xiàn)錯(cuò)誤分類，錯(cuò)誤在迭代過程中累積，因此無法直接判斷自訓(xùn)練相比監(jiān)督學(xué)習(xí)能否提升分類性能。為評(píng)估自訓(xùn)練在數(shù)據(jù)集上的表現(xiàn)，我們選取了9組標(biāo)準(zhǔn)數(shù)據(jù)集，隨機(jī)抽取百分之十的數(shù)據(jù)作為標(biāo)記樣本，使用十折交叉驗(yàn)證法，隱去訓(xùn)練集中未標(biāo)記樣本的標(biāo)簽，對(duì)測(cè)試集中的標(biāo)簽則予以保留。本章實(shí)驗(yàn)使用KEEL軟件REF_Ref513633445\r[11]。這里我們選用的分類方法是k最近鄰(k=3)。此時(shí)自訓(xùn)練步驟中第2步的具體過程為：（1）對(duì)于U中任意未標(biāo)記樣本xU，選取歐氏距離最近的3個(gè)標(biāo)記樣本點(diǎn)，3個(gè)點(diǎn)投票決定它的標(biāo)簽。若三點(diǎn)標(biāo)簽不同，則選取其中距離最近的點(diǎn)并采納標(biāo)簽；（2）取三個(gè)樣本點(diǎn)中與xU標(biāo)簽相同的點(diǎn)，計(jì)算它們到xU的平均距離作為置信度。取置信度最高的xU并入L中。數(shù)據(jù)集信息如表1所示：數(shù)據(jù)集樣例數(shù)目維數(shù)類別bupa34562cleveland303135ecoli33678haberman30632iris15043monk241062pima76882vehicle846184wisconsin69992表SEQ表格\*ARABIC1在這些數(shù)據(jù)集上分別采用監(jiān)督式3NN和自訓(xùn)練3NN方法，分類準(zhǔn)確度如圖1所示。圖圖SEQ圖\*ARABIC1從圖中看出，在大部分?jǐn)?shù)據(jù)集上，自訓(xùn)練(3NN)相比3NN方法對(duì)分類準(zhǔn)確度沒有明顯提升。在kNN算法中，未標(biāo)記點(diǎn)的標(biāo)簽依靠近鄰點(diǎn)確定，據(jù)此推測(cè)，對(duì)于使用kNN分類器的自訓(xùn)練方法，當(dāng)數(shù)據(jù)集呈現(xiàn)出明顯分類時(shí)，由于沒有離群點(diǎn)的干擾，kNN方法錯(cuò)誤率低，自訓(xùn)練由于自主擴(kuò)大了訓(xùn)練集可以獲得更準(zhǔn)確的分類。我們對(duì)使用自訓(xùn)練方法后分類準(zhǔn)確度有大幅變化的haberman和iris數(shù)據(jù)集的前三個(gè)維度做可視化處理，如圖2所示。圖圖SEQ圖\*ARABIC2左圖的haberman數(shù)據(jù)集沒有明顯的聚類特征，因此容易出現(xiàn)誤分類，自訓(xùn)練過程中錯(cuò)誤累積。右圖的iris數(shù)據(jù)集類別間分界明顯，通過自訓(xùn)練方法擴(kuò)大了訓(xùn)練集的規(guī)模，獲得了更好的分類精度。事實(shí)上，文獻(xiàn)REF_Ref513633587\r[12]的結(jié)論表明沒有一種自訓(xùn)練方法適合所有數(shù)據(jù)集，選用了某種分類器（kNN，決策樹，支持向量機(jī)等）的自訓(xùn)練方法可能會(huì)在某一數(shù)據(jù)集上準(zhǔn)確分類，但在其他數(shù)據(jù)集上會(huì)降低原有分類器的性能。2.2協(xié)同訓(xùn)練協(xié)同訓(xùn)練的基本思想是將數(shù)據(jù)特征劃分為兩個(gè)不相交的子集，子特征集又稱為視圖。在兩個(gè)視圖上分別訓(xùn)練分類器，對(duì)于每一個(gè)分類器而言，選取置信度最高的未標(biāo)記樣本，在另一個(gè)分類器的訓(xùn)練集中移入該樣本。具體步驟如下：將L據(jù)特征分為互不相交的L1,L2，在其上分別訓(xùn)練分類器通過h1將U中置信度最高的樣本移入L2，通過h2將置信度最高的樣本移入L1；在新的L1,L重復(fù)2,3步直到U中沒有樣本。協(xié)同訓(xùn)練依賴于兩個(gè)重要的假設(shè)：（1）在有足夠多的標(biāo)記樣本時(shí)，每個(gè)視圖對(duì)于作出好的分類是充分的；（2）在給定標(biāo)簽的前提下，兩個(gè)視圖條件獨(dú)立。第一個(gè)假設(shè)是顯然的，因?yàn)樵谌我灰晥D上訓(xùn)練一個(gè)不好的分類器沒有意義。第二個(gè)假設(shè)則是為了一個(gè)視圖可以為另一個(gè)視圖提供更多信息量。如果兩個(gè)視圖完全相關(guān)，協(xié)同訓(xùn)練則退化為自訓(xùn)練。已有研究表明REF_Ref513633015\r[7]，當(dāng)滿足假設(shè)時(shí)，協(xié)同訓(xùn)練相對(duì)單視圖訓(xùn)練一定可以提升分類性能。協(xié)同訓(xùn)練的提出背景為網(wǎng)頁分類，兩個(gè)視圖分別為網(wǎng)頁本身的信息和它的超鏈接所包含的信息。然而，在多數(shù)實(shí)際問題中，我們很難將特征劃分為滿足條件的兩個(gè)子集。我們利用隨機(jī)分割特征的方式對(duì)表1中的數(shù)據(jù)集采用協(xié)同訓(xùn)練(3NN)，從圖3可以看出，當(dāng)假設(shè)條件不滿足時(shí)，協(xié)同訓(xùn)練表現(xiàn)糟糕。圖圖SEQ圖\*ARABIC32.3本章小結(jié) 在本章中，我們?cè)?個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上運(yùn)行了使用3NN分類器的自訓(xùn)練和協(xié)同訓(xùn)練方法，結(jié)合前文分析，得到結(jié)論如下：自訓(xùn)練是最簡單的半監(jiān)督學(xué)習(xí)方法，作為一種包裹算法，它可以結(jié)合使用任何一種分類器。但是在自訓(xùn)練早期出現(xiàn)的錯(cuò)誤分類會(huì)在迭代過程中不斷增強(qiáng)，導(dǎo)致其分類性能不如在少量標(biāo)記數(shù)據(jù)集上訓(xùn)練出的監(jiān)督式分類器。 協(xié)同訓(xùn)練同樣是包裹算法，它的主要缺陷在于，它所依賴的假設(shè)條件在實(shí)際應(yīng)用中難以滿足。并且在訓(xùn)練前期分類器較弱時(shí)，會(huì)將錯(cuò)誤標(biāo)簽引入另一個(gè)分類器中，從而產(chǎn)生噪聲。第三章生成模型 給定訓(xùn)練集T=L∪U，生成模型假定樣本都生成于一個(gè)潛在的模型，即它需要學(xué)習(xí)的是“生成數(shù)據(jù)的機(jī)制”。它通過觀察大量樣本估計(jì)條件分布p(x|y)與先p得出判斷準(zhǔn)則。 在半監(jiān)督學(xué)習(xí)中，我們首先由標(biāo)記數(shù)據(jù)獲得聯(lián)合分布px 本章余下部分安排如下：首先闡述樸素貝葉斯模型的原理，在此基礎(chǔ)上介紹半監(jiān)督樸素貝葉斯模型，接下來在文本數(shù)據(jù)集20newsgroup上比較二者的分類準(zhǔn)確度，最后總結(jié)本章。3.1監(jiān)督學(xué)習(xí)的樸素貝葉斯模型本節(jié)我們將介紹基于混合多項(xiàng)分布的樸素貝葉斯模型。首先給出混合模型的定義。混合模型用來描述不規(guī)則的概率分布。它通過混合多個(gè)形式相同的概率密度函數(shù)組成一個(gè)密度函數(shù)：p其中每個(gè)概率密度函數(shù)稱為一個(gè)混合成分；Θ=πk,θkk=1c為模型的參數(shù)集合，θkp給定訓(xùn)練集T=xi,yii=1l，其中y={1,?,c}。我們的目標(biāo)是訓(xùn)練出分類器，將新給定的x歸入某一類，即計(jì)算出在樸素貝葉斯模型中，我們假設(shè)x的每一特征條件獨(dú)立，則有p根據(jù)貝葉斯定理我們得到：P此時(shí)在每一類中，x符合多項(xiàng)分布：

x其中N=i=1p它的對(duì)數(shù)似然為log其中C為常數(shù)。 由此，在pxy此時(shí)問題轉(zhuǎn)化為求解pxy和 令Py=k=πL取對(duì)數(shù)似然：log則最大似然問題轉(zhuǎn)化為兩個(gè)約束優(yōu)化問題：max和max使用拉格朗日乘子法解得：πk可以看出P(y=k)與P(xi=(xi1,?,xid)|y=k)δ此時(shí)參數(shù)估計(jì)可寫為：π此時(shí)對(duì)于新給定的x，我們通過下式判斷它的類別：y3.2半監(jiān)督樸素貝葉斯與EM算法在半監(jiān)督學(xué)習(xí)中，我們希望利用大量的未標(biāo)記數(shù)據(jù)提升分類準(zhǔn)確度，這意味著，模型參數(shù)的選取建立在整個(gè)數(shù)據(jù)集上。給定訓(xùn)練集L=xi,yilogL此時(shí)U中樣本的標(biāo)簽為隱變量，將其記為z，用zk表示y=ki=l+1在對(duì)數(shù)函數(shù)中有求和形式，因此似然函數(shù)的最大化不能通過求導(dǎo)直接完成，我們可以通過最大化它的下界增大似然函數(shù)。假設(shè)Qi為隱變量z的某個(gè)分布函數(shù)，則有i=l+1根據(jù)k=1ci=l+1欲使i=l+1nlogPxQ結(jié)合Qi的歸一Q即Qizk實(shí)際上是每個(gè)樣本的后驗(yàn)概率γik=Py=kxi;Θ，γik在實(shí)際應(yīng)用中，為了簡化計(jì)算，我們選擇用最大后驗(yàn)為U中樣本賦予標(biāo)簽，即不考慮未標(biāo)記樣本分入其他類別的概率，然后在全部訓(xùn)練集上通過式(3.15)計(jì)算新參數(shù)。綜上所述，半監(jiān)督樸素貝葉斯模型訓(xùn)練步驟如下：在L上訓(xùn)練樸素貝葉斯模型，得到初始參數(shù)集Θ0（E步）利用當(dāng)前的分類器給U中的樣本加上標(biāo)簽，記錄后驗(yàn)概率γik（M步）在L∪U上利用最大似然法重新訓(xùn)練分類器；重復(fù)第2,3步，直到似然函數(shù)不再上升。3.3實(shí)驗(yàn)結(jié)果及分析半監(jiān)督樸素貝葉斯常用于文本分類，即給定文檔判斷它的所屬類別。將全部文本中所有的詞歸納為字典，用x代表文檔的詞頻向量，其中x的第j個(gè)分量為為字典中第j個(gè)詞出現(xiàn)的次數(shù)。假設(shè)文檔中任意單詞出現(xiàn)的位置是獨(dú)立的，不受文檔內(nèi)容影響，則對(duì)于每一類文本，x符合多項(xiàng)分布。 我們選用的數(shù)據(jù)集為20newsgroup，包含20類新聞文檔，由約20000個(gè)文檔組成。前期處理工作包括：(1)去除文檔的開頭、結(jié)尾和引用部分；(2)去除停用詞（語氣詞、助詞等）；(3)當(dāng)一個(gè)詞在少于五個(gè)文檔中出現(xiàn)時(shí)，忽略這個(gè)詞。我們?nèi)∫欢ū壤奈臋n作為標(biāo)記數(shù)據(jù)集，在標(biāo)記數(shù)據(jù)集上使用監(jiān)督樸素貝葉斯模型，在全部數(shù)據(jù)集上使用半監(jiān)督樸素貝葉斯模型，比較兩種方法的分類準(zhǔn)確度，結(jié)果如圖4所示。圖4圖4 從圖中可以看出，在標(biāo)記比例很少的時(shí)候，半監(jiān)督樸素貝葉斯的分類準(zhǔn)確度明顯高于樸素貝葉斯模型。在擁有2%時(shí)的標(biāo)簽時(shí)，分類準(zhǔn)確度達(dá)到50%；在擁有10%的標(biāo)簽時(shí)，分類準(zhǔn)確度達(dá)到60%。在擁有較多標(biāo)簽時(shí)，監(jiān)督和半監(jiān)督分類效果沒有明顯差異。3.4 本章小結(jié)本章介紹了基于混合多項(xiàng)分布的樸素貝葉斯模型和其對(duì)應(yīng)的半監(jiān)督學(xué)習(xí)方法，根據(jù)兩種方法在20newsgroups數(shù)據(jù)集上的運(yùn)行結(jié)果可以看出，在標(biāo)簽數(shù)目很少時(shí)，半監(jiān)督樸素貝葉斯模型在文本分類中相較于監(jiān)督學(xué)習(xí)有更準(zhǔn)確的分類。生成模型的優(yōu)勢(shì)在于：（1）可以用標(biāo)記數(shù)據(jù)確定初始值；（2）當(dāng)對(duì)潛在模型的假設(shè)正確時(shí)，它利用少量標(biāo)記數(shù)據(jù)即可取得很好的分類效果。然而，實(shí)際應(yīng)用中，由于標(biāo)記數(shù)據(jù)的稀缺，我們難以判斷模型是否正確，甚至得到無用的模型。例如在圖5中，樣本符合高斯混合分布，正確分類如圖5(b)所示，但由于圖5(a)所表示的分布似然函數(shù)值更大，根據(jù)未標(biāo)記數(shù)據(jù)擬合出的結(jié)果為圖5(a),此時(shí)錯(cuò)誤率會(huì)達(dá)到50%。另一方面，迭代過程中的似然函數(shù)計(jì)算時(shí)間開銷很大。圖圖5abab第四章直推式支持向量機(jī)直推式支持向量機(jī)是建立在監(jiān)督學(xué)習(xí)方法支持向量機(jī)上的一種半監(jiān)督學(xué)習(xí)方法，本章將首先闡釋支持向量機(jī)的工作原理，在這一基礎(chǔ)上介紹直推式支持向量機(jī)，然后給出實(shí)驗(yàn)結(jié)果，結(jié)合數(shù)據(jù)集特征進(jìn)行分析評(píng)價(jià)。在本章中只考慮二分類問題。4.1支持向量機(jī)的原理與求解支持向量機(jī)(SVM)是一種應(yīng)用廣泛的分類方法，它的基本原理是，在保證正確分類的前提下，最大化分隔平面之間的距離。下面我們將從線性可分和線性不可分兩種情況，對(duì)SVM進(jìn)行介紹。線性可分對(duì)于D維訓(xùn)練集T={xiw令fx=wTx+b，則超平面可表示為fx=0。該邊界將特征空間分為f>0與f<0兩部分，前一部分對(duì)應(yīng)于標(biāo)簽如圖6所示是一個(gè)二維線性可分?jǐn)?shù)據(jù)集，在分界線wTx+b=0的法方向w已給定的前提下，顯然看出能夠完成分類的直線不唯一。我們作出兩種極端情況下的分類直線l1,圖6圖6對(duì)于法向量w的選取，如前文所述，我們應(yīng)當(dāng)使極端情況下取得的兩個(gè)分隔平面之間的距離達(dá)到最大。不妨設(shè)兩個(gè)分隔平面的方程為：w我們注意到成比例地改變w,bw 此時(shí)分隔平面的距離為2|mins.t.求解上述優(yōu)化問題等同于求解它的對(duì)偶問題：mins.t.得到解α*后，計(jì)算wb此時(shí)決策函數(shù)為f可以看出，決策函數(shù)的表達(dá)式只依賴于α*中非零元素所對(duì)應(yīng)的樣本點(diǎn)，直觀上，也正是這些點(diǎn)位于分隔平面上，我們把此類樣本點(diǎn)稱為支持向量，支持向量機(jī)因此線性不可分 在實(shí)際應(yīng)用中，訓(xùn)練集普遍是線性不可分的。即我們需要“軟化”對(duì)超平面分類性能的要求，即允許有不滿足優(yōu)化問題(4.4)的樣本點(diǎn)存在。我們通過引入松弛變量ξ構(gòu)造線性不可分支持向量機(jī)的優(yōu)化問題：mins.t.ξ其中C>0是懲罰參數(shù)。我們需要做到在間隔盡量大的情況下盡可能減少誤分類樣本點(diǎn)的數(shù)量，C在這兩者之間取得平衡。這一問題的求解方法與線性可分支持向量機(jī)類似。4.2直推式支持向量機(jī) 如前文所述，我們通過利用有標(biāo)記樣本訓(xùn)練支持向量機(jī)。直推式支持向量機(jī)(TSVM)則是在這一基礎(chǔ)上，結(jié)合未標(biāo)記數(shù)據(jù)，調(diào)整決策邊界。 假定數(shù)據(jù)集T=L∪U，其中L={xi,yi}i=1 對(duì)于線性可分?jǐn)?shù)據(jù)集，圖7可以體現(xiàn)出TSVM的意義：使超平面對(duì)于整個(gè)數(shù)據(jù)集（包括標(biāo)記和未標(biāo)記樣本）間隔最大。它可以寫成如下的優(yōu)化問題：mins.t.其中，yj圖7 圖7對(duì)于線性不可分?jǐn)?shù)據(jù)集，類似于支持向量機(jī)，我們同樣采用引入松弛變量的方法，得到的優(yōu)化問題如下：mins.t.ξξ訓(xùn)練TSVM意味著需要求解優(yōu)化問題（4.11）。在測(cè)試集規(guī)模很小(u≤10)的情況下，我們可以枚舉出yi*的全部可能取值，找到問題的最優(yōu)解。對(duì)于規(guī)模較大的數(shù)據(jù)集，一種普遍使用的方法是SVM在訓(xùn)練集L上利用支持向量機(jī)方法訓(xùn)練出超平面<w使用在步驟1中訓(xùn)練出的超平面對(duì)U進(jìn)行分類，記錄其中正負(fù)類別的樣例數(shù)量為n+給參數(shù)C+,C當(dāng)U中的樣例xm,xn滿足交換條件時(shí)，交換它們的標(biāo)簽，完成所有交換后，重新在整個(gè)數(shù)據(jù)集C重復(fù)該步驟直到滿足C± 步驟4中重新訓(xùn)練的支持向量機(jī)對(duì)應(yīng)優(yōu)化問題:min交換條件指的是ym SVMlight的核心步驟在于通過交換測(cè)試集中的樣本標(biāo)簽，提升了原本僅在訓(xùn)練集上訓(xùn)練出的支持向量機(jī)的分類性能。不妨假定1由上式看出，在標(biāo)簽交換過程中，目標(biāo)函數(shù)值不斷減小。 在無標(biāo)記數(shù)據(jù)集樣本數(shù)目有限（u<∞）的情況下，它們可能的標(biāo)簽最多有2u種組合，因此標(biāo)簽交換的次數(shù)一定是有限的。又因?yàn)镃-,C+都以C4.3實(shí)驗(yàn)結(jié)果及分析TSVM需要滿足低密度分離假設(shè)，我們選取滿足6個(gè)二分類數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中的三個(gè)滿足假設(shè)，數(shù)據(jù)集信息如表2所示。數(shù)據(jù)集樣例數(shù)維數(shù)特征breast_cancer7709未知g241c1500241滿足假設(shè)g241n1500241滿足假設(shè)german350020未知heart250013未知reuters600—滿足假設(shè)表SEQ表格\*ARABIC2注：reuters數(shù)據(jù)集為索引表示，無法確定維數(shù)。對(duì)于上述數(shù)據(jù)集，我們?cè)诿恳活愔懈魅?個(gè)樣本作為標(biāo)記數(shù)據(jù)，使用TSVM和傳統(tǒng)的SVM方法進(jìn)行訓(xùn)練，參數(shù)C的選取范圍是{0.001,0.005,0.1,0.5,1}REF_Ref513636180\r[13],在三個(gè)滿足假設(shè)的數(shù)據(jù)集上，訓(xùn)練結(jié)果如圖8(a)所示；在三個(gè)特征未知的數(shù)據(jù)集上，訓(xùn)練結(jié)果如圖8(b)所示。可以看出，當(dāng)數(shù)據(jù)集滿足低密度假設(shè)時(shí)，相對(duì)于在少量標(biāo)記樣本上訓(xùn)練出的支持向量機(jī)，直推式支持向量機(jī)的分類準(zhǔn)確度有明顯提高；當(dāng)假設(shè)不滿足時(shí)，兩種方法沒有明顯差異。SEQ_\*alphabeticaSEQ_\*alphabeticb圖SEQ_\*alphabeticaSEQ_\*alphabeticb圖84.4本章小結(jié)本章在支持向量機(jī)的基礎(chǔ)上闡述了直推式支持向量機(jī)的基本原理，并在兩類數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，當(dāng)?shù)兔芏确蛛x假設(shè)滿足時(shí)，相對(duì)支持向量機(jī)，直推式支持向量機(jī)對(duì)分類正確率有明顯提升，體現(xiàn)出其潛在的應(yīng)用價(jià)值。直推式支持向量機(jī)是支持向量機(jī)的推廣，這意味著它理論結(jié)構(gòu)清晰，且與支持向量機(jī)同樣有廣泛的應(yīng)用。盡管如此，它依然面臨著兩方面的問題（1）計(jì)算困難。本章中介紹的計(jì)算方法是SVM（2）直推式支持向量機(jī)依賴于低密度分離假設(shè)，即真實(shí)的分界面應(yīng)該穿過特征空間的低密度區(qū)域，當(dāng)數(shù)據(jù)集不滿足這一假設(shè)時(shí)，可能無法取得好的分類效果?？紤]如圖9所示的極端情況，直推式支持向量機(jī)的分界線落在低密度區(qū)域，恰好與真實(shí)分界線垂直。此時(shí)，基于少量標(biāo)記樣本的支持向量機(jī)的分界線更接近正確分類。圖9圖9第五章基于圖的半監(jiān)督學(xué)習(xí)方法 基于圖的半監(jiān)督學(xué)習(xí)方法為直推式學(xué)習(xí)方法，它的基本思想為，將訓(xùn)練集中的每個(gè)樣本點(diǎn)看作圖上的結(jié)點(diǎn)，樣本間的相似度為對(duì)應(yīng)邊的權(quán)重，構(gòu)造出一幅圖。信息在圖上從標(biāo)記樣本流向未標(biāo)記樣本，從而使未標(biāo)記樣本獲得標(biāo)簽。 我們通過一個(gè)簡單的文本分類的例子說明這一思想。假設(shè)我們的訓(xùn)練集中有兩類文本，我們通過詞頻提取出每個(gè)樣本的關(guān)鍵詞，如下表所示，其中x1文檔關(guān)鍵詞xxxxxxxxa○a○○a○○a○○?b○○b○○b○○b○ 接下來，我們?cè)诒碇锌吹?，類別信息逐步從已標(biāo)記樣本向未標(biāo)記樣本傳遞，完成對(duì)未標(biāo)記樣本的分類。文檔關(guān)鍵詞xxxxxxxxa○a○○a○○a○○?b○○b○○b○○b○圖的建立 在實(shí)際問題中，圖的建立可能需要一些專業(yè)背景知識(shí)。下面我們給出理論上構(gòu)建圖的常用方法。 給定訓(xùn)練集L=xi,yii=1l,U=xjw當(dāng)歐氏距離‖xi-xj‖增大時(shí)，相似度減小。易得，xi=xj時(shí) 根據(jù)圖中邊的連接情況，我們將其分為全連接圖和稀疏圖。 全連接圖是指每一對(duì)結(jié)點(diǎn)之間都有邊相連。全連接圖構(gòu)造容易，但由于沒有反映出樣本特征，分類效果差，因此很多情況下我們需要構(gòu)造稀疏圖。 稀疏圖分為kNN圖與?NN圖。在kNN圖中，對(duì)于結(jié)點(diǎn)i，記它的k個(gè)最近鄰點(diǎn)組成的集合為N(i)，若j∈N(i)，則i,j間有邊相連。k對(duì)樣本密度具有自適應(yīng)性，在樣本密集的區(qū)域圖半徑較小，在樣本稀疏的區(qū)域圖半徑較大。?NN圖則是指，給定閾值?>0，當(dāng)結(jié)點(diǎn)i,j間的距離di,j≤?，i,j相連。顯然，由于在稀疏圖中，每個(gè)結(jié)點(diǎn)只與滿足條件的結(jié)點(diǎn)相連，因此權(quán)重矩陣相對(duì)全連接圖更為稀疏，計(jì)算速度快。它的缺點(diǎn)在于，如果權(quán)重計(jì)算方式改變，結(jié)點(diǎn)之間的連接關(guān)系也隨之變化。 本章接下來介紹三種基于圖的方法：最小割、標(biāo)記傳播法和LLGC，本質(zhì)上它們的不同之處在于損失函數(shù)和正則項(xiàng)的不同。后兩種方法常應(yīng)用于圖像分類和文本分類，本文將其應(yīng)用于圖像數(shù)據(jù)集USPS和文本數(shù)據(jù)集20newsgroup，給出實(shí)驗(yàn)結(jié)果并做出總結(jié)。5.1最小割最小割REF_Ref513636359\r[14]是最早提出的基于圖的半監(jiān)督學(xué)習(xí)方法，常用于二分類問題。它需要找到一組權(quán)重和最小的邊集，將整張圖分割為兩個(gè)子圖，一部分只包含正標(biāo)記，另一部分只包含負(fù)標(biāo)記。此時(shí)，我們將包含正標(biāo)記的子圖中所有未標(biāo)記點(diǎn)賦予正標(biāo)記，其余未標(biāo)記點(diǎn)賦予負(fù)標(biāo)記。不妨設(shè)二值分類函數(shù)為f(x)，實(shí)際上，當(dāng)fxi=f(xj)i,j:f(5.2)式在最小割方法中被稱為分割圖的尺寸。 下面我們從結(jié)構(gòu)化風(fēng)險(xiǎn)最小化的角度考慮最小割問題。首先，對(duì)已標(biāo)記樣本，必然有fxL此處我們定義∞?0=0。當(dāng)滿足fxi=Ω它表示在圖上相近的樣本有相同的標(biāo)簽。 此時(shí)最小割方法的結(jié)構(gòu)風(fēng)險(xiǎn)最小化問題可寫為：min由于f的取值僅限于-1和1，（5.5）是一個(gè)整數(shù)規(guī)劃問題。 最小割方法的缺點(diǎn)在于可能不存在唯一解。在圖（10）所示的鏈?zhǔn)綀D中，兩端分別為正、負(fù)結(jié)點(diǎn)，則我們斷開圖上的任意一條邊，都可以得到最小割的一組最優(yōu)解。圖10圖105.2標(biāo)簽傳播法相比于最小割，標(biāo)簽傳播法擁有唯一解且適用于多分類問題。對(duì)于訓(xùn)練集T=L∪U，標(biāo)簽y∈{1,?,l}。我們?cè)赥上構(gòu)建kNN圖，相似度為w其中σ為帶寬參數(shù)。 我們定義概率轉(zhuǎn)移矩陣P如下：p定義(l+u)*C維類別矩陣Y:初始化F0標(biāo)簽傳播：F←PF;修正F的前L行：FL重復(fù)2，3步直至f收斂。在第2步中，所有結(jié)點(diǎn)向相鄰節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播；第3步是為了固定原始的標(biāo)記樣本。迭代停止后，我們通過下式?jīng)Q定未標(biāo)記樣本的標(biāo)簽：y收斂性的證明 已知F=FLFU，由于FLP則fUF由此可得：F因?yàn)镻是行歸一化矩陣，PUU是P?γ<1,因此j=1u則PUUn→0，由此可得PUUnFUF這是標(biāo)簽傳播法的唯一解。f直觀上可以用圖上的隨機(jī)游走來解釋。根據(jù)標(biāo)簽傳播法的步驟，我們得到：f假定一個(gè)粒子的當(dāng)前位置為結(jié)點(diǎn)i，在下一時(shí)間點(diǎn)，它隨機(jī)地移動(dòng)到它的相鄰結(jié)點(diǎn)中的一個(gè)，移動(dòng)到相鄰結(jié)點(diǎn)j的概率為wijP當(dāng)粒子移動(dòng)到了某一有標(biāo)簽的結(jié)點(diǎn)時(shí)，隨機(jī)游走終止。正則化框架文獻(xiàn)REF_Ref513634892\r[13]在二分類情況下說明了標(biāo)簽傳播法的唯一解恰是正則化框架下的最優(yōu)解，以下我們將該結(jié)論推廣到多分類問題中。我們首先定義分類函數(shù)f:L∪U→RCE 接下來我們定義拉普拉斯矩陣L。令D為權(quán)重和對(duì)角矩陣，即DiiL=D-W#此時(shí)能量函數(shù)可寫為E此時(shí)優(yōu)化問題寫為：min類似于上一節(jié)，對(duì)F和F則有tr根據(jù)?解得F可以看出解（5.23）與我們?cè)谏弦还?jié)中得到的解相同。 標(biāo)記傳播法的結(jié)構(gòu)風(fēng)險(xiǎn)最小化問題可寫為：min這一形式與最小割方法類似，不同點(diǎn)在于，分類函數(shù)為實(shí)值函數(shù)，相當(dāng)于是最小割的松弛形式，它確保了優(yōu)化問題有閉合解。5.3局部和全局一致法最小割法和標(biāo)簽傳播法會(huì)保留原有標(biāo)記樣本的標(biāo)簽，因此屬于硬分類方法。相對(duì)應(yīng)地，局部和全局一致法（LLGC）屬于軟分類方法，“全局一致”意為分類函數(shù)在整個(gè)訓(xùn)練集上光滑，即不要求原有標(biāo)簽保持不變，當(dāng)訓(xùn)練集中存在噪聲時(shí)，這種方法可以一定程度上削弱噪聲的影響。在LLGC中，所有變量的定義與標(biāo)簽傳播法中相同。它的步驟如下REF_Ref513636379\r[16]：初始化F0=Y，F(xiàn)←αSF+1-αY，其中重復(fù)第2步直到收斂，令F*為F迭代的極限，則樣本x在第2步中，αSF是為了讓每一結(jié)點(diǎn)收到來自相鄰結(jié)點(diǎn)的信息，1-αY下面我們證明迭代的收斂性。根據(jù)第2步，我們有F=由于P=D-1W=D-1/2SDlim最終我們得到F正則化框架LLGC的正則項(xiàng)和經(jīng)驗(yàn)損失函數(shù)之和可寫為：Q此時(shí)得到的分類矩陣為：F=注意到QF?Q解得F令α=11+μ，可以看出這里解出的5.4實(shí)驗(yàn)結(jié)果及分析基于圖的半監(jiān)督方法所依賴的假設(shè)是流形假設(shè)，即樣本特征相似時(shí)標(biāo)簽相同。在這一假設(shè)下，類別信息從標(biāo)記樣本向未標(biāo)記樣本傳遞。除了在之前提到的文本分類，圖像識(shí)別同樣適用于這一假設(shè)，圖11展示了手寫數(shù)字識(shí)別的原理。我們將在文本數(shù)據(jù)集和圖像數(shù)據(jù)集上分別觀測(cè)標(biāo)記傳播法和LLGC的分類性能。本章中使用的軟件為SemiLREF_Ref513636677\r[17]。圖11圖11文本分類 我們選用在3.3節(jié)中使用的20news數(shù)據(jù)，由于基于圖的方法時(shí)間開銷較大，這里選取數(shù)據(jù)集中的四個(gè)分類。數(shù)據(jù)處理方式與之前相同。圖的建立與參數(shù)的選取文獻(xiàn)中的通常做法REF_Ref513636415\r[15]REF_Ref513636379\r[16]，建立10NN圖，取帶寬參數(shù)σ=0.15標(biāo)簽傳播法,σ=1.5LLGC，隨機(jī)取一定比例的標(biāo)簽，重復(fù)實(shí)驗(yàn)十次取平均值，得到的分類錯(cuò)誤率如圖所示。由于訓(xùn)練集不存在噪聲，兩種方法的錯(cuò)誤率接近。兩種方法僅需5%的標(biāo)記數(shù)據(jù)就可以將錯(cuò)誤率控制在10%左右，在該數(shù)據(jù)集上表現(xiàn)出不錯(cuò)的分類性能。圖12圖12圖像分類 這里我們使用256位的手寫數(shù)字?jǐn)?shù)據(jù)集USPS的訓(xùn)練集部分，共有7291個(gè)樣本，帶寬參數(shù)為σ=1.25標(biāo)簽傳播法,σ=5LLGC，實(shí)驗(yàn)方法與文本分類相同。結(jié)果如圖13所示。實(shí)驗(yàn)結(jié)果表明，當(dāng)有5%的標(biāo)記數(shù)據(jù)時(shí)，兩種方法的錯(cuò)誤率都降至55.5本章小結(jié) 本章介紹了三種主要的基于圖的方法：最小割、標(biāo)簽傳播法和LLGC，后兩者由于收斂到唯一解而具備應(yīng)用價(jià)值。根據(jù)這兩種方法在USPS數(shù)據(jù)集和20newsgroup數(shù)據(jù)集的表現(xiàn)，基于圖的半監(jiān)督學(xué)習(xí)在擁有少量標(biāo)記時(shí)可以有較高的分類正確率，因而在醫(yī)學(xué)圖像處理、文本分類、圖像分割等領(lǐng)域有著廣泛的應(yīng)用前景。但它主要存在以下問題： （1）標(biāo)記樣本的選擇。在上述兩個(gè)實(shí)驗(yàn)中，我們選取標(biāo)記樣本時(shí)保證每一類中至少有一個(gè)標(biāo)記樣本，當(dāng)類別數(shù)量較多時(shí)，這一條件不易滿足。 （2）計(jì)算代價(jià)高。對(duì)于由n個(gè)d維樣本的組成的數(shù)據(jù)集，構(gòu)造kNN圖的時(shí)間復(fù)雜度為On2d+O(第六章理論分析在前幾章中我們討論了幾種半監(jiān)督學(xué)習(xí)方法；關(guān)于半監(jiān)督學(xué)習(xí)是否能夠利用未標(biāo)記樣本提升學(xué)習(xí)性能，則需要更具普遍性的理論分析。在本章中我們將基于相容性概念和PAC框架介紹半監(jiān)督學(xué)習(xí)的計(jì)算理論。我們首先介紹監(jiān)督學(xué)習(xí)中的PAC框架，再將其推廣到半監(jiān)督學(xué)習(xí)中。簡單起見，本章只討論二分類問題。6.1監(jiān)督學(xué)習(xí)的PAC界按照在第一章中對(duì)監(jiān)督學(xué)習(xí)的定義，訓(xùn)練集的取值范圍為集合X，標(biāo)簽Y={-1,1}。令p(x,y)為樣本和標(biāo)簽的聯(lián)合概率分布，用D表示這一分布，給定訓(xùn)練集T=xi,e評(píng)價(jià)分類函數(shù)f的標(biāo)準(zhǔn)應(yīng)當(dāng)是最小化真實(shí)誤差，然而由于p(xe假設(shè)我們找到了使訓(xùn)練誤差為0的函數(shù)，即e此時(shí)依然無法得出真實(shí)誤差ef 我們注意到fT是訓(xùn)練集上的隨機(jī)變量，考慮事件{efT>?}P接下來，我們將尋找這一概率的上界。我們?cè)谟?xùn)練集上通過某種學(xué)習(xí)方法訓(xùn)練出滿足條件（6.4）的函數(shù)fTP由于訓(xùn)練集同樣符合分布D，當(dāng)滿足條件eff∈F:e最終我們得到P即

P上述推導(dǎo)說明，訓(xùn)練誤差為0的fT可能（至少有1-Fe-?l的概率）是大約正確（定理1F為有限維。給定?>0,δ>0，當(dāng)l滿足條件l≥時(shí)，?f∈F,etrainf=0，有至少證明帶入δ=F6.2半監(jiān)督學(xué)習(xí)的PAC界如果半監(jiān)督學(xué)習(xí)可以利用更少的標(biāo)記數(shù)據(jù)達(dá)到式（6.9）中的表現(xiàn)，則它是有意義的。為了使l減小，我們需要減小|F|。即，我