單雙點(diǎn)平滑結(jié)合的流形正則化半監(jiān)督分類學(xué)習(xí)框架

沈 雅 婷

(南京理工大學(xué)紫金學(xué)院 江蘇 南京 210023)

0 引 言

全監(jiān)督學(xué)習(xí)需要擁有大量的已標(biāo)記實(shí)例，但在現(xiàn)實(shí)中獲取未標(biāo)記實(shí)例不困難，通過手工標(biāo)記實(shí)例卻很難。半監(jiān)督分類框架研究是機(jī)器學(xué)習(xí)中最受歡迎的領(lǐng)域之一，因?yàn)樗蒙倭康囊褬?biāo)記實(shí)例的同時(shí)也可以運(yùn)用未標(biāo)記實(shí)例的信息。

半監(jiān)督分類中兩個(gè)常見的假設(shè)，聚類假設(shè)[1]和流形假設(shè)。基于圖的半監(jiān)督分類方法，例如標(biāo)簽傳播[2]、圖切割[3]和流形正則化(MR)，這些都是采用流形假設(shè)。

基于圖的半監(jiān)督分類方法中除了MR，基本都是直推式方法[4]。MR是一種能夠預(yù)測(cè)測(cè)試樣本的歸納方法[5]。

實(shí)例的分類輸出應(yīng)該在流形圖上平滑。但是平滑是如何實(shí)現(xiàn)的呢？在學(xué)習(xí)中，MR遵循流形假設(shè)，流形假設(shè)約束流形圖上的相似實(shí)例應(yīng)該共享相似的分類輸出[6]。MR將視每個(gè)實(shí)例對(duì)為單位。因此，它是建立在流形圖上的雙點(diǎn)平滑上的。然而，平滑在本質(zhì)上是以單個(gè)實(shí)例為單位的，也就是說，平滑性應(yīng)該發(fā)生在“任何地方”，通過將每個(gè)單點(diǎn)行為與其近鄰的行為聯(lián)系起來。雖然在一些研究中認(rèn)為單點(diǎn)平滑是合理的，但在具有流形假設(shè)的MR中，它和雙點(diǎn)平滑還沒有同時(shí)實(shí)現(xiàn)。一種新的框架是單雙點(diǎn)平滑結(jié)合的MR(SDS_MR)，通過結(jié)合實(shí)例對(duì)約束[7]和單點(diǎn)局部密度來實(shí)現(xiàn)半監(jiān)督學(xué)習(xí)。通過這種方法，保留了單雙點(diǎn)的光滑性，它們都具重要性且都可作出貢獻(xiàn)。本文以實(shí)例對(duì)的約束信息和單個(gè)實(shí)例的局部密度[8]為例，當(dāng)然，這一想法也可以應(yīng)用到其他框架中。對(duì)于此問題的解決，SDS_MR的公式與MR的公式相似，因此求最優(yōu)解步驟也是相似的。最后在UCI數(shù)據(jù)集上的實(shí)證結(jié)果顯示，SDS_MR與MR相比具有一定的競(jìng)爭(zhēng)力。

為了更好地預(yù)測(cè)效果，近期有研究表明[9]對(duì)MR的改進(jìn)，獲得或多或少的改進(jìn)效果。事實(shí)上，本文提出的SDS_MR框架也可以引入到這些改進(jìn)中，有望進(jìn)一步提高預(yù)測(cè)的有效性。

1 相關(guān)工作

1.1 流形正則化半監(jiān)督分類框架(MR)

流形假設(shè)是半監(jiān)督學(xué)習(xí)中最常用的數(shù)據(jù)分布假設(shè)之一，它假設(shè)流形結(jié)構(gòu)上的相似實(shí)例應(yīng)該共享相似的分類輸出。MR是一種半監(jiān)督分類框架，它就是運(yùn)用了流形假設(shè)進(jìn)行深入研究的，近年來應(yīng)用到各種領(lǐng)域中。

(1)

(2)

(3)

式中：K:X×X→R是一個(gè)Mercer核[14]。

1.2 雙點(diǎn)平滑

雙點(diǎn)約束可以通過將實(shí)例的標(biāo)簽轉(zhuǎn)換為雙點(diǎn)約束來改進(jìn)模型中包含的信息。在一些實(shí)際應(yīng)用中，只會(huì)提前得到實(shí)例的一些標(biāo)簽之間的關(guān)系，然后可以將這些標(biāo)簽轉(zhuǎn)換為雙點(diǎn)約束信息來訓(xùn)練半監(jiān)督模型。

具體而言，如果兩個(gè)已標(biāo)記點(diǎn)的標(biāo)簽是相同的，它們就是雙點(diǎn)可關(guān)聯(lián)約束，構(gòu)成必要的關(guān)聯(lián)集MS；同理，如果兩個(gè)已標(biāo)記點(diǎn)的標(biāo)簽不同，則它們就是雙點(diǎn)不可關(guān)聯(lián)約束，構(gòu)成不可能的關(guān)聯(lián)集CS。假設(shè)分類決策函數(shù)為f(x),那么所有實(shí)例的預(yù)測(cè)值可以表示為f=[f1,f2,…,fn]T∈Rl×n,那雙點(diǎn)約束可以表示如下：

(4)

式中：i,j,p,q∈[1,n]是數(shù)據(jù)集中實(shí)例的序號(hào)；〈i,j〉表示在集合MS中任何必要的雙點(diǎn)關(guān)聯(lián)約束；〈p,q〉表示在集合CS中任何不可能的雙點(diǎn)關(guān)聯(lián)約束；|·|表示集合MS或者集合CS中的雙點(diǎn)約束的數(shù)目。

矩陣Qn×n的元素定義如下：

(5)

通過矩陣表示可以寫為：

(6)

U=H-Q

(7)

式中：H=diag(QL),L是一個(gè)維度是n×1的向量并且它的元素都為1。

2 單雙點(diǎn)平滑結(jié)合的半監(jiān)督流形正則化分類框架(SDS_MR)

MR采用雙點(diǎn)平滑約束流形圖上的相似實(shí)例共享相似的分類輸出。在本節(jié)中，提出一個(gè)單雙點(diǎn)平滑結(jié)合的MR框架，利用雙點(diǎn)平滑約束和單點(diǎn)局部密度。

2.1 算法框架

(8)

式中：第三項(xiàng)的后半部分表示雙點(diǎn)平滑約束。τ是參數(shù)，用來平衡式(8)中第三項(xiàng)中的兩部分。當(dāng)τ=0,SDS_MR將退化成MR。在式(8)中第三項(xiàng)的前半部分，N(xi)是xi的近鄰集，xj在xi的近鄰集中。p(xi)表示實(shí)例xi的局部密度，它可以根據(jù)實(shí)例與其近鄰點(diǎn)之間的歸一化距離來計(jì)算，數(shù)值越小表示實(shí)例周圍分布越密集。但是，當(dāng)實(shí)例xi在兩個(gè)類別的重疊區(qū)域，根據(jù)上述的局部密度,在xi的周圍會(huì)很密集。因此，在式(8)第三項(xiàng)的前半部分，xi將被賦予更大的重要性或更大的懲罰，但是仍然這是不可預(yù)期的。因此在計(jì)算單點(diǎn)局部密度時(shí)，不僅會(huì)考慮近鄰密度，還會(huì)考慮無監(jiān)督學(xué)習(xí)結(jié)構(gòu)[15]。

(9)

式(1)中第三項(xiàng)是對(duì)雙點(diǎn)具有平滑懲罰的正則化項(xiàng)[16]，式(8)中的第三項(xiàng)與其不同，它同時(shí)考慮了雙點(diǎn)平滑和單點(diǎn)平滑。

進(jìn)一步將式(8)中的第三項(xiàng)寫成：

2(τ(fTLPWf)+(1-τ)(fTLf))

(10)

SDS_MR框架通過采用不同的損失函數(shù)生成不同的分類器。接下來，分別使用平方損失函數(shù)[17]和鉸鏈損失函數(shù)[18]為上述框架推導(dǎo)單雙點(diǎn)平滑結(jié)合LapRlsc和單雙點(diǎn)平滑結(jié)合LapSVM。

2.2 單雙點(diǎn)平滑結(jié)合的Laplacian正則最小二乘法(SDS_LapRlsc)

利用平方損失函數(shù)，SDS_LapRlsc的公式可寫為:

(11)

它可以寫成:

(1-τ)(fTLf)]

(12)

應(yīng)用Representer定理后,式(12)問題的解可由以下形式表示：

(13)

繼續(xù)優(yōu)化函數(shù)可以表示成:

(14)

式中：α=[α1,α2,…，αl+u]T是拉格朗日乘子向量[19]。Kl=(Xl,X)H∈Rl×(l+u)和K=(X,X)H∈R(l+u)×(l+u)是核矩陣，其中Xl表示已標(biāo)記數(shù)據(jù)集，X表示整個(gè)數(shù)據(jù)集。已標(biāo)記數(shù)據(jù)的類標(biāo)簽向量用Yl=[y1,y2,…,yl]T表示。

通過J1對(duì)α求導(dǎo)后值為0求最小值，因此:

(1-τ)(KLKα)]=0

(15)

最后,得到:

(16)

2.3 單雙點(diǎn)平滑結(jié)合的Laplacian支持向量機(jī)(SDS_LapSVM)

應(yīng)用鉸鏈損失函數(shù)，SDS_LapSVM的公式可寫為:

(17)

ξi≥0，i=1,2,…,l

進(jìn)一步寫為：

(1-τ)(fTLf)]

(18)

ξi≥0,i=1,2,…,l

應(yīng)用Representer定理之后,即式(13)可以得出:

(1-τ)(αTKLKα)]

(19)

ξi≥0,i=1,2,…,l

應(yīng)用拉格朗日乘子法后,得到:

(20)

式中：βi是拉格朗日乘子。

進(jìn)一步得出：

(21)

因此，再將J2寫成:

(22)

式中：J=[I0]是一個(gè)維度為l×(l+u)的矩陣(假設(shè)前l(fā)個(gè)點(diǎn)是已標(biāo)記)，其中I是維度為l×l的單位矩陣，并且Y=diag(y1,y2,…,yl)。

進(jìn)一步得到:

(1-τ)(KLKα))-KJTYlβ=0

(23)

因此有:

(24)

將式(24)代入到簡(jiǎn)化的式(22)中,可以得到:

(25)

其中:

(26)

3 實(shí)驗(yàn)與結(jié)果分析

本節(jié)將評(píng)估SDS_MR在13個(gè)UCI數(shù)據(jù)集上的性能，并與MR進(jìn)行比較。表1給出了UCI中13個(gè)數(shù)據(jù)集的相關(guān)信息。每個(gè)數(shù)據(jù)集被隨機(jī)分成兩部分，分別用于訓(xùn)練和測(cè)試。訓(xùn)練集分別包含10個(gè)和100個(gè)已標(biāo)記樣本供選擇。然而，若選擇包含100個(gè)已標(biāo)記樣本，但是訓(xùn)練樣本數(shù)量卻小于100，那么只選擇其中一半的訓(xùn)練樣本作為已標(biāo)記樣本。重復(fù)數(shù)據(jù)劃分和訓(xùn)練過程20次并記錄其平均精確度和標(biāo)準(zhǔn)差。

表1 13個(gè)UCI數(shù)據(jù)集的相關(guān)信息

在比較實(shí)驗(yàn)中使用的是線性核。在MR和單雙點(diǎn)平滑結(jié)合MR的圖構(gòu)建中，近鄰數(shù)k都被簡(jiǎn)單地設(shè)置為10。當(dāng)已標(biāo)記樣本數(shù)為10時(shí)，記錄最佳性能時(shí)的所有正則化參數(shù)組合值，當(dāng)已標(biāo)記樣本數(shù)為100時(shí)，通過五折交叉驗(yàn)證[20]選擇出正則化參數(shù)組合值。其中參數(shù)τ值設(shè)為0.5，參數(shù)C1和C2的取值范圍為{0.01,0.1,1,10,100}。

3.1 性能比較

表2和表3分別給出了在具有10個(gè)和100個(gè)已標(biāo)記樣本的UCI數(shù)據(jù)集上的比較結(jié)果。每行給出了每個(gè)方法在對(duì)應(yīng)數(shù)據(jù)集上的性能，并且最后一行給出了每個(gè)方法在所有數(shù)據(jù)集上的平均性能。此外，在每一行中，加粗?jǐn)?shù)值表示在此數(shù)據(jù)集上的最佳精確度，并且斜體數(shù)值表示在此數(shù)據(jù)集上SDS_LapRlsc/SDS_LapSVM的性能優(yōu)于LapRlsc/LapSVM。

表2 具有10個(gè)已標(biāo)記樣本的UCI上的精確度(%)

表3 具有100個(gè)已標(biāo)記樣本的UCI上的精確度(%)

從表2和表3中，可以分析得到以下結(jié)論：

(1) 當(dāng)已標(biāo)記樣本數(shù)為10時(shí)，一共13個(gè)數(shù)據(jù)集，SDS_LapRlsc在其中12個(gè)數(shù)據(jù)集上的正確率高于LapRlsc，SDS_LapSVM在其中11個(gè)數(shù)據(jù)集上的正確率高于LapSVM。當(dāng)已標(biāo)記樣本數(shù)為100時(shí),SDS_LapRlsc在其中7個(gè)數(shù)據(jù)集上的正確率高于LapRlsc，SDS_LapSVM在其中8個(gè)數(shù)據(jù)集上的正確率高于LapSVM。因此，通過單雙點(diǎn)平滑結(jié)合，可以提高半監(jiān)督分類學(xué)習(xí)的正確率。

(2) 當(dāng)已標(biāo)記樣本數(shù)為10時(shí)，在9個(gè)數(shù)據(jù)集上，表現(xiàn)最好的不是SDS_LapRlsc就是SDS_LapSVM,當(dāng)已標(biāo)記樣本數(shù)為100時(shí)，在6個(gè)數(shù)據(jù)集上，表現(xiàn)最好的不是SDS_LapRlsc就是SDS_LapSVM。因此，與其他優(yōu)秀的半監(jiān)督分類方法進(jìn)行比較，提出的單雙點(diǎn)平滑結(jié)合MR確實(shí)具有優(yōu)勢(shì)。

(3) 當(dāng)已標(biāo)記樣本數(shù)為10時(shí)，在3個(gè)數(shù)據(jù)集上，全監(jiān)督SVM的表現(xiàn)優(yōu)于半監(jiān)督分類方法，當(dāng)已標(biāo)記樣本數(shù)為100時(shí)，在3個(gè)數(shù)據(jù)集上，全監(jiān)督SVM的表現(xiàn)優(yōu)于半監(jiān)督分類方法。從而得出，在某些情況下，半監(jiān)督分類學(xué)習(xí)可能是不安全的，比對(duì)應(yīng)的全監(jiān)督方法表現(xiàn)更糟。因此，設(shè)計(jì)性能不會(huì)比相應(yīng)的全監(jiān)督方法差的單雙點(diǎn)平滑結(jié)合MR安全學(xué)習(xí)策略是一項(xiàng)重要工作。

(4) 當(dāng)已標(biāo)記樣本數(shù)為10時(shí)，也就是說已標(biāo)記樣本更少時(shí)，單雙點(diǎn)平滑結(jié)合MR的性能改進(jìn)更明顯。原因可能是已標(biāo)記信息越少時(shí)(這里是10和100比較)，半監(jiān)督學(xué)習(xí)越有利，因?yàn)楦倪M(jìn)的空間更大。此外，通常必須要處理具有極有限已標(biāo)記樣本的半監(jiān)督分類任務(wù)，因此，單雙點(diǎn)平滑結(jié)合MR的性能改進(jìn)值得期待。

3.2不同參數(shù)τ值的性能表現(xiàn)

參數(shù)τ對(duì)于單雙點(diǎn)平滑結(jié)合MR的性能表現(xiàn)很重要，因此，這里展示在6個(gè)UCI數(shù)據(jù)集上具有不同τ值的SDS_LapRlsc的性能表現(xiàn)，并以SVM作為基準(zhǔn)。每個(gè)UCI數(shù)據(jù)集只包含10個(gè)已標(biāo)記樣本。采用線性核并且τ的取值范圍為{0,0.25,0.5,0.75,1}。最后，得到結(jié)果如圖1所示。

(a) arrhythmia

(b) biomed

(c) hepatitis

(d) house

(e) ionosphere

(f) water圖1 不同數(shù)據(jù)集上SDS_LapRlsc的性能表現(xiàn)圖

從圖1中，可以分析得到以下結(jié)論：

(1) 在單個(gè)數(shù)據(jù)集上的性能變化規(guī)則是不同的。具體來說，在大多數(shù)數(shù)據(jù)集上，當(dāng)τ取值為0.5時(shí)可以獲得滿意的性能，要選擇最合適的τ很難，這也將是未來一項(xiàng)重要工作。然而，即使將數(shù)值τ固定為0.5，SDS_LapRlsc的性能已經(jīng)具有競(jìng)爭(zhēng)力了。

(2) 當(dāng)τ取不同的值時(shí)，SDS_LapRlsc的性能通常優(yōu)于LapRlsc,說明SDS_LapRlsc的健壯性。因此，當(dāng)τ取適當(dāng)?shù)臄?shù)值時(shí)，SDS_LapRlsc能夠提供非常優(yōu)秀的分類性能。即使將τ固定為0.5，單雙點(diǎn)平滑結(jié)合MR也比MR更具優(yōu)勢(shì)。

4 結(jié) 語

在給定構(gòu)造流形圖上，實(shí)例的分類輸出在圖上是希望平滑的。但這種平滑是如何實(shí)現(xiàn)的呢？在學(xué)習(xí)中，MR實(shí)際上采用了流形假設(shè)，它視每個(gè)實(shí)例對(duì)為單位，并約束流形圖上的相似實(shí)例應(yīng)該共享相似的分類輸出。因此，它是建立在流形圖上雙點(diǎn)平滑約束。其實(shí)平滑在本質(zhì)上是以單個(gè)實(shí)例為單位的，通過將每個(gè)單點(diǎn)行為與其近鄰的行為聯(lián)系起來。因此，本文提出一種新的框架是單雙點(diǎn)平滑結(jié)合的MR(SDS_MR簡(jiǎn)稱)。最后，對(duì)UCI數(shù)據(jù)集的實(shí)證結(jié)果表明，SDS_MR與MR相比具有競(jìng)爭(zhēng)力。為了更好地預(yù)測(cè)效果，本文提出的結(jié)合單雙點(diǎn)的平滑性方法可以嘗試引入到其他學(xué)者提出的改進(jìn)的MR算法中，甚至將結(jié)合單雙點(diǎn)的平滑性方法應(yīng)用到其他先進(jìn)的分類框架中，有望進(jìn)一步提高預(yù)測(cè)的有效性。