結(jié)合包光滑性的半監(jiān)督多示例核學(xué)習(xí)方法*

潘強(qiáng)

（珠海城市職業(yè)技術(shù)學(xué)院經(jīng)濟(jì)管理學(xué)院）

0 引言

在半監(jiān)督多示例算法研究中，獲取現(xiàn)實(shí)樣本的概念標(biāo)記需要花費(fèi)大量的人力和時(shí)間，因此在學(xué)習(xí)過程中利用未標(biāo)記樣本，能提升學(xué)習(xí)器性能的半監(jiān)督學(xué)習(xí)算法引起研究者的興趣。目前半監(jiān)督多示例學(xué)習(xí)的研究主要是使用示例層次的標(biāo)簽傳播和帶約束的優(yōu)化方法[1-3]。文獻(xiàn)[4]提出了一種示例層次的半監(jiān)督多示例學(xué)習(xí)算法，它把示例概念標(biāo)記的確定歸結(jié)為一個(gè)帶損失項(xiàng)和正則化項(xiàng)的優(yōu)化問題，在假設(shè)空間中尋找一個(gè)假設(shè)，使之同時(shí)滿足：1)訓(xùn)練誤差最小；2)假設(shè)復(fù)雜度最低；3)假設(shè)在已知的數(shù)據(jù)點(diǎn)上盡可能光滑。在第3)中的光滑性定義是指示例空間意義上的，即考慮假設(shè)在所有包中的示例上的光滑程度。該方法把在單示例半監(jiān)督學(xué)習(xí)中的基于流形正則化的方法[5]應(yīng)用到多示例學(xué)習(xí)問題中，但存在幾個(gè)不足：1)該方法所考慮的假設(shè)是以示例為變量，并不是對(duì)原問題的直接求解；2)該方法要求解一個(gè)約束條件數(shù)量較多的最優(yōu)化問題，求解的代價(jià)巨大；3)該最優(yōu)化問題不滿足Representer定理[6]的條件，無法直接轉(zhuǎn)化為標(biāo)準(zhǔn)的RKHS空間上的優(yōu)化問題。

本文提出一種直接利用未標(biāo)記包進(jìn)行半監(jiān)督多示例學(xué)習(xí)的算法，它在正則化框架中展開，直接在多示例的假設(shè)空間中尋找一個(gè)假設(shè)，滿足上述3個(gè)條件，不同的是本文并不考慮假設(shè)對(duì)于單個(gè)示例的復(fù)雜度和光滑性。實(shí)現(xiàn)包層次的半監(jiān)督學(xué)習(xí)，關(guān)鍵是定義包的光滑性。本文先用核映射的方法得到一個(gè)關(guān)于所有包（有標(biāo)記和無標(biāo)記）的相似度矩陣，然后對(duì)其表示的包計(jì)算其圖拉普拉斯，通過對(duì)文獻(xiàn)[6]工作的擴(kuò)展，得到多示例半監(jiān)督核。設(shè)有標(biāo)記多示例數(shù)據(jù)集為BL={bag1,bag2,…,bagnl} 和 未 標(biāo) 記 集 為BU={bag1,bag2,…,bagnu}，在整個(gè)包空間中通過已知的樣本（不考慮標(biāo)簽）建立一個(gè)圖拉普拉斯矩陣刻畫其分布的光滑性，通過該矩陣修改一個(gè)已經(jīng)存在的多示例核，得到一個(gè)與樣本依賴的核。形式上有：

其中，k是一個(gè)普通的多示例核；M是一個(gè)光滑性度量，由所有“看得見”的樣本 Ball決定；f是一個(gè)向量實(shí)值函數(shù)，可以認(rèn)為f借助空間的光滑性度量修改了原有多示例核的數(shù)值，使之更為準(zhǔn)確地反映數(shù)據(jù)的空間分布。

1 結(jié)合包光滑性半監(jiān)督多示例核

1.1 包空間光滑性度量

基于半監(jiān)督核[4,7]與多示例核[8-9]的研究，提出一種結(jié)合包光滑性的半監(jiān)督多示例核的概念。先定義多示例包的圖拉普拉斯，然后說明這種刻畫單示例流形的手段也適用于多示例場合。

定義1多示例樣本的圖拉普拉斯MMI

MMI= LP，其中L=D－W，W為多示例樣本的基于Heat Kernel的Gram矩陣，且有：

在定義1中，d(Bi,Bj)為兩個(gè)包之間的距離。流形是一種低維的嵌入，而這種嵌入的基礎(chǔ)是樣本點(diǎn)在空間的一種相鄰關(guān)系。但對(duì)于多示例包，距離的定義與單示例的場合不同，包之間沒有直觀的相鄰關(guān)系。在以往的研究中3種包間距離的定義列為表1。

表1 包間距離定義

在表1中，包中心距離定義為取包中所有示例的平均值作為包中心點(diǎn)，計(jì)算兩個(gè)包中心點(diǎn)的歐氏距離；包最近點(diǎn)距離為取兩個(gè)包中示例的歐氏距離中的最小值作為兩個(gè)包的距離；Min-Max距離是把包進(jìn)行Min-Max擴(kuò)展為一個(gè)2n維的向量，其中前n維為所有屬性在包中示例上取得的最小值，后n維為所有屬性在包中示例上取得的最大值，每兩個(gè)包之間使用歐氏距離計(jì)算。

以往的研究表明，包中心距離和包最近點(diǎn)距離并不能很好反映其分布規(guī)律[10]。而 Min-Max距離對(duì)包的屬性進(jìn)行了擴(kuò)展，僅考慮示例在各個(gè)屬性上取值的邊界，實(shí)質(zhì)上僅是一種數(shù)理統(tǒng)計(jì)手段。這些距離的定義均存在一個(gè)缺陷，即它們所反映的僅是每個(gè)包本身的特性，而沒有考慮到整個(gè)示例空間的分布規(guī)律。

為了進(jìn)一步在包距離中反映包的示例分布及其之間的關(guān)系，提出一種基于包概念表示的海明距離。首先在整個(gè)示例空間對(duì)示例進(jìn)行聚類，按照文獻(xiàn)[11]的觀點(diǎn)，不同的簇可以看作是整個(gè)示例空間的不同概念，然后以一個(gè)布爾向量記錄每一個(gè)包中是否包含屬于某個(gè)聚類的示例（該向量稱為概念向量），以該布爾向量作為包的表示計(jì)算海明距離作為包間距離。

定義2概念空間海明距離

在定義2中，HM為海明距離的計(jì)算函數(shù)。Concept算法把一個(gè)包表示為一個(gè)布爾向量，每一個(gè)分量表示該包是否包含屬于某個(gè)簇的示例。算法 1展示了Concept算法的計(jì)算過程。

算法1Concept（包概念向量的計(jì)算）

輸入：多示例數(shù)據(jù)集Ball，包B，聚類數(shù)目K

輸出：包B所對(duì)應(yīng)的概念向量表示C

定義2與表1中所定義的距離最大的不同之處在于它以聚類的方式考慮了整個(gè)示例空間的內(nèi)在規(guī)律性。該聚類過程是半監(jiān)督的，可以在訓(xùn)練數(shù)據(jù)集的基礎(chǔ)上引入更多的未標(biāo)記包進(jìn)行聚類，使這種示例空間的概念估計(jì)更加準(zhǔn)確。

在定義1中使用概念空間海明距離，可以得到描述包空間光滑性的圖拉普拉斯。算法2描述了包的圖拉普拉斯的計(jì)算過程。

算法2 MIGraphLaplacian（多示例樣本圖拉普拉斯的計(jì)算）

輸入：多示例數(shù)據(jù)集Ball，參數(shù)P

輸出：多示例樣本的圖拉普拉斯矩陣M

算法2的第2行初始化W為一個(gè)n×n方陣，其中n為所有包的個(gè)數(shù)。核函數(shù)選用RBF核，考慮到對(duì)于k維的包概念向量表示，其最小和最大海明距離分別為 0（全部相同）和 k（全部不同），因此第 7行RBF核的寬度參數(shù)取值為概念簇?cái)?shù)目k的一半。參數(shù)p控制光滑性表示的復(fù)雜程度[5]，恰當(dāng)設(shè)置p的值能使圖拉普拉斯矩陣M反映真正的數(shù)據(jù)流形分布。

由于正包和負(fù)包的概念構(gòu)成不同，它們與基準(zhǔn)包（訓(xùn)練集）的海明距離存在明顯的差距，這種平均距離之間的差異有助于確定一個(gè)較為準(zhǔn)確的光滑性度量，可以定性地認(rèn)為相似的包所包含的概念也應(yīng)該是比較相似的。

1.2 半監(jiān)督多示例核

通過多示例樣本的圖拉普拉斯定義，很容易計(jì)算出半監(jiān)督多示例核。在整個(gè)示例空間進(jìn)行聚類，構(gòu)造包的概念表示，計(jì)算包之間的概念空間海明距離矩陣，進(jìn)而計(jì)算出包的圖拉普拉斯，沿用單示例數(shù)據(jù)依賴核的理論[4]，可以得到半監(jiān)督多示例核。算法3描述了半監(jiān)督多示例核的計(jì)算過程。

算法3MISSLKernel（半監(jiān)督多示例核的計(jì)算）

輸入：訓(xùn)練數(shù)據(jù)集Dtrain待映射數(shù)據(jù)庫D，未標(biāo)記數(shù)據(jù)集P，多示例核k

輸出：半監(jiān)督多示例核矩陣：K：D×Dtrain

由于未標(biāo)記數(shù)據(jù)集的引入，算法3所返回的核矩陣不再僅僅依賴于訓(xùn)練數(shù)據(jù)集，由此實(shí)現(xiàn)多示例核的半監(jiān)督化。考察算法3的第2行和第6行，均需要計(jì)算兩個(gè)關(guān)于所有多示例包Dall的Gram矩陣，當(dāng)Dtrain∪D∪P的數(shù)目較大時(shí)，這兩行的計(jì)算量非常大。在一般情況下，P中的包數(shù)目會(huì)比較多，因?yàn)楂@取未標(biāo)記包會(huì)比有標(biāo)記包容易得多。由文獻(xiàn)[12]、[13]可知，要使半監(jiān)督學(xué)習(xí)有效，實(shí)際上并不需要太多的未標(biāo)記樣本，在算法中引入過多的未標(biāo)記樣本會(huì)增加復(fù)雜度甚至降低正確率。基于這樣的考慮，對(duì)未標(biāo)記數(shù)據(jù)隨機(jī)抽樣，選擇其中的q%作為PointCloud。

另一方面，考察核映射的本質(zhì)，實(shí)質(zhì)是把每一個(gè)待輸入學(xué)習(xí)器的樣本先映射到一組基樣本上，一般使用訓(xùn)練樣本充當(dāng)基準(zhǔn)樣本，即 BBase=Dtrain，在訓(xùn)練和測試的過程中，分別把有標(biāo)記樣本集 BL和待測試樣本集BU映射到基準(zhǔn)BBase上，把映射后的每一行作為原始數(shù)據(jù)的特征表示，用于訓(xùn)練和測試過程。但若訓(xùn)練數(shù)據(jù)的絕對(duì)數(shù)量較大，會(huì)導(dǎo)致映射后的數(shù)據(jù)維數(shù)過高，使訓(xùn)練和測試的復(fù)雜度大大增加。

本文提出了一種類似于文獻(xiàn)[11]的簡化策略，通過對(duì)Dtrain隨機(jī)抽樣限制其規(guī)模，然后把2p+1次抽樣訓(xùn)練的學(xué)習(xí)器集成并進(jìn)行多數(shù)投票。這是一種分治策略，訓(xùn)練若干個(gè)低維度數(shù)據(jù)集的復(fù)雜度遠(yuǎn)比訓(xùn)練一個(gè)高維度數(shù)據(jù)集要低，且在以往的研究中，這種分治后的集成被證明是有效的[11]。

2 實(shí)驗(yàn)和討論

2.1 標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)

為說明基于概念向量海明距離的半監(jiān)督多示例核的有效性，在多示例學(xué)習(xí)的標(biāo)準(zhǔn)數(shù)據(jù) Musk1和Musk2上，將本算法（MISSLK）與MIKernel算法[8]、基于表 1的 3種包間不同距離的半監(jiān)督多示例核算法[14]進(jìn)行比較測試。主要原因有：1)通過與MIKernel比較，說明PointCloud的方式對(duì)原有多示例核進(jìn)行半監(jiān)督化修改的有效性；2)與文獻(xiàn)[14]中半監(jiān)督多示例核算法的比較，說明本文的基于包概念表示的包間海明距離對(duì)于構(gòu)造半監(jiān)督多示例核的有效性。

實(shí)驗(yàn)設(shè)置如下：把數(shù)據(jù)集隨機(jī)分成10份，其中1份作為測試集，余下9份作為訓(xùn)練集和PointCloud。首先初始化PointCloud為余下的9份，而訓(xùn)練集每次增加1份。數(shù)據(jù)集隨機(jī)劃分的過程并不考慮每份中正負(fù)包比例的平衡。10份數(shù)據(jù)輪流做測試，記錄其正確率的平均值與訓(xùn)練數(shù)據(jù)比例之間的關(guān)系。Musk1和Musk2分別用k=13和k=16進(jìn)行概念簇的計(jì)算。圖拉普拉斯的指數(shù)參數(shù)取p=1.5。由于Musk1和Musk2數(shù)據(jù)集的規(guī)模都不大，因此使用全映射的方式，即不對(duì)BBase進(jìn)行隨機(jī)抽樣之后再集成。由于MIKernel并不是半監(jiān)督學(xué)習(xí)算法，所以在它的訓(xùn)練過程不使用PointCloud，每輪增加一份訓(xùn)練樣本。學(xué)習(xí)器使用Weka的J48決策樹，在Matlab中通過Spider開源項(xiàng)目調(diào)用Weka的實(shí)現(xiàn)。圖1展示了實(shí)驗(yàn)結(jié)果。

在圖1中，橫軸表示訓(xùn)練樣本的比例；縱軸表示算法在測試集上的正確率。圖中每個(gè)點(diǎn)是10次實(shí)驗(yàn)結(jié)果的平均，其方差也在圖中通過垂直的線段反映。D1、D2和D3分別代表文獻(xiàn)[14]中的基于3種不同包間距離的半監(jiān)督多示例核。從圖1中可以看到，當(dāng)訓(xùn)練過程中使用的有標(biāo)記包數(shù)量較少時(shí)，本文的半監(jiān)督算法能夠?qū)Ψ诸惼鞯恼_率有一定的正面貢獻(xiàn)；在訓(xùn)練數(shù)據(jù)比例較低的情況下，本文的方法要比MIKernel好。但當(dāng)訓(xùn)練數(shù)據(jù)比例增加時(shí)，本文的方法不如MIKernel，這種現(xiàn)象在以往的半監(jiān)督學(xué)習(xí)中也被觀察到，其原因是在訓(xùn)練數(shù)據(jù)過多時(shí)其本身確定的分布與未標(biāo)記數(shù)據(jù)可能不同，從而會(huì)在訓(xùn)練過程中引入潛在的沖突，導(dǎo)致學(xué)習(xí)器的效率下降。此外，如果隨意引入未標(biāo)記數(shù)據(jù)并不會(huì)一直提升學(xué)習(xí)器的性能，也不是學(xué)習(xí)過程中使用的數(shù)據(jù)越多效果就越好，這一點(diǎn)從圖1中正確率的波動(dòng)可以看出，但基本趨勢是有標(biāo)記的訓(xùn)練樣本越多其效果越好。總的來說，在大部分情況下，未標(biāo)記數(shù)據(jù)包的引入能夠提升學(xué)習(xí)器的泛化能力。

圖1 標(biāo)準(zhǔn)數(shù)據(jù)集分類正確率比較

2.2 圖像數(shù)據(jù)集實(shí)驗(yàn)

本文進(jìn)一步在Corel Image 2000圖像數(shù)據(jù)（簡稱Image2000）上測試本算法。為處理方便，選擇與文獻(xiàn)[2]中使用的經(jīng)過預(yù)處理的Image2000數(shù)據(jù)集。預(yù)處理過程對(duì)每幅圖像LUV顏色空間矩陣進(jìn)行分塊二維小波變換，對(duì)小波系數(shù)進(jìn)行聚類，每個(gè)簇由一個(gè)9維特征向量表示。由于文獻(xiàn)[2]采用的是對(duì)聚類數(shù)目自適應(yīng)的聚類算法，數(shù)據(jù)集中每幅圖像所包含的示例（簇）數(shù)量不一定相同。

Image2000包含20類圖像，每個(gè)類有100幅。對(duì)于每一類數(shù)據(jù)，從中隨機(jī)抽取25幅作為正例，并從其余的19類中隨機(jī)抽取50幅作為負(fù)例構(gòu)成規(guī)模為7的訓(xùn)練集；余下75幅同類圖像加上從其余類中隨機(jī)抽取150幅圖像一起構(gòu)成測試集，從而保持訓(xùn)練集和測試集中正負(fù)例的比例相同，防止學(xué)習(xí)器對(duì)數(shù)量較多的負(fù)例有過大的傾向。對(duì)于每一類，整個(gè)過程重復(fù)10次，記錄每一類的準(zhǔn)確率均值和方差。

本實(shí)驗(yàn)采用轉(zhuǎn)導(dǎo)學(xué)習(xí)的方式對(duì)PointCloud進(jìn)行構(gòu)建，即假設(shè)測試數(shù)據(jù)集在訓(xùn)練的時(shí)候就已知，將整個(gè)測試數(shù)據(jù)集和剩余的數(shù)據(jù)看作未標(biāo)記數(shù)據(jù)構(gòu)建PointCloud。由于PointCloud規(guī)模較大，本文采取對(duì)PointCloud進(jìn)行隨機(jī)抽樣后再集成的策略，限制PointCloud的規(guī)模。對(duì)PointCloud進(jìn)行隨機(jī)無回放抽樣，每輪從中抽取100個(gè)樣本，組成一個(gè)用于算法的PointCloud。共生成 3個(gè)不一樣的PointCloud，用相同的訓(xùn)練數(shù)據(jù)集訓(xùn)練3個(gè)學(xué)習(xí)器之后進(jìn)行投票集成。

在概念簇的計(jì)算中，參數(shù)k值設(shè)置為12，包的圖拉普拉斯指數(shù)參數(shù)p=5。概念簇的個(gè)數(shù)設(shè)置是根據(jù)經(jīng)驗(yàn)值得出的，由于在算法運(yùn)行過程中可能有空簇的出現(xiàn)，因此設(shè)置稍大的k值即可，并不需要事先對(duì)k值進(jìn)行精確的估算。分類器與2.1小節(jié)中的相同，均采用標(biāo)準(zhǔn)的SVM。表2記錄了20個(gè)類別在上述實(shí)驗(yàn)設(shè)置下的分類正確率和方差。

從表2中可以看出，算法對(duì)不同類別的分類正確率差異較大。這是由于不同類別的圖像所構(gòu)成的空間光滑性是不一樣的，部分類別的規(guī)律性比較明顯，因此使用半監(jiān)督學(xué)習(xí)得到的結(jié)果可能較好。對(duì)比文獻(xiàn)[2]中使用DD-SVM 對(duì)該數(shù)據(jù)集進(jìn)行學(xué)習(xí)的結(jié)果，本文的算法能夠在訓(xùn)練樣本較小（特別是正例較少）的情況下取得大致相當(dāng)?shù)慕Y(jié)果，因此可以認(rèn)為在大部分的情況下，半監(jiān)督學(xué)習(xí)發(fā)揮了作用。不同的數(shù)據(jù)集有不同的內(nèi)在分布規(guī)律，本實(shí)驗(yàn)只是使用同一種距離度量計(jì)算光滑性，因此不是最優(yōu)的。若能針對(duì)不同數(shù)據(jù)集學(xué)習(xí)一種距離度量，將會(huì)得到更好的結(jié)果。通過包光滑性被結(jié)合到半監(jiān)督多示例核中，在一定程度上提高了分類準(zhǔn)確率。通過考慮包的不同特征，可以在算法中定義不同的多示例核，基于海明距離的光滑性定義能有效地反映包層的數(shù)據(jù)分布特征。與此同時(shí)，未標(biāo)記數(shù)據(jù)的利用與多示例核的選擇是完全獨(dú)立的，使該算法框架有更廣泛的適應(yīng)性。

表2 Image2000的分類正確率

3 結(jié)論

本文提出基于半監(jiān)督核的多示例學(xué)習(xí)框架，未標(biāo)記數(shù)據(jù)通過包光滑性被結(jié)合到半監(jiān)督多示例核中，在一定程度上提高了分類準(zhǔn)確率。通過考慮包的不同特征，可以在算法中定義不同的多示例核，基于海明距離的光滑性定義能有效地反映出包層在的數(shù)據(jù)分布特征。與此同時(shí)，未標(biāo)記數(shù)據(jù)的利用與多示例核的選擇是完全獨(dú)立的，使該算法框架有更廣泛的適應(yīng)性。

[1]Rahmani R,Goldman S A. MISSL: Multiple-instance semi-supervised learning [C]//Proc 23rd Intl. Conf. Mach.Learn. ACM,New York,NY,USA,2006: 705-712.

[2]Chen Y,Wang J Z. Image categorization by learning and reasoning with regions [J]. J. Mach. Learn. Res.,2004,5:913-939.

[3]Zhu X,Ghahramani Z,Lafferty J. Semi supervised learning using gaussian fields and harmonic functions [C]//Proc 20th Intl. Conf. Mach. Learn. ACM,New York,NY,USA,2003:912-919.

[4]Yangqing Jia,Changshui Zhang. Instance-level Semisupervised Multiple Instance Learning [C]//Proc 23rd Intl. Conf. AAAI.AAAI Press,2008: 640-645.

[5]M Belkin,P Niyogi,V Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples [J]. J. Mach. Learn. Res.,2006,7:2399-2434.

[6]Cucker,F. and Smale,S. On the mathematical foundations of learning [J]. Bull. Amer. Math. Soc. (N.S.),2002,39: 1-49.

[7]Vikas Sindhwani,Partha Niyogi,and Mikhail Belkin. Beyond the point cloud: from transductive to semi-supervised learning[C]//Proc 22th Intl. Conf. Mach. Learn.,ACM,New York,NY,USA,2005: 824-831.

[8]Gartner T,Flach P A,Kowalczyk A,et al. Multi-instance kernels[C]//Proc 19th Intl. Conf. Mach. Learn. Morgan Kaufmann Publishers Inc.,San Francisco: CA,USA,179-186.

[9]Zhou Zhi-Hua,Sun Yu-Yin,Li Yu-Feng. Multi-instance learning by treating instances as non-I.I.D. samples[C]//Proc 26th Intl. Conf. Mach. Learn. Montreal,Quebec,Canada,2009:1249-1256.

[10]James Foulds,Eibe Frank. A Review of Multi-Instance Learning Assumptions[J]. Knowledge Engineering Review,2011,25(1):1-25.

[11]Zhou Zhi-Hua,Zhang Min-Ling. Solving multi-instance problems with classifier ensemble based on constructive clustering[J]. Knowl. Inf. Syst. ,2007,11(2): 155-170.

[12]Aarti Singh,Robert Nowak,Zhu Xiaojin. Unlabeled data:Now it helps,now it doesn't[C]// Proc NPIS 2008. 2008,22.

[13]Andrew Goldberg,Xiaojin Zhu,Aarti Singh,et al.Multi-manifold semi-supervised learning[C]//In Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS),2009.

[14]張鋼,印鑒,程良倫,等.半監(jiān)督多示例核[J].計(jì)算機(jī)科學(xué),2011,38(9):220-223.