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

沈 雅 婷

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

0 引 言

全監(jiān)督學習需要擁有大量的已標記實例，但在現(xiàn)實中獲取未標記實例不困難，通過手工標記實例卻很難。半監(jiān)督分類框架研究是機器學習中最受歡迎的領域之一，因為它利用少量的已標記實例的同時也可以運用未標記實例的信息。

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

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

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

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

1 相關工作

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

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

(1)

(2)

(3)

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

1.2 雙點平滑

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

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

(4)

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

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

(5)

通過矩陣表示可以寫為：

(6)

U=H-Q

(7)

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

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

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

2.1 算法框架

(8)

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

(9)

式(1)中第三項是對雙點具有平滑懲罰的正則化項[16]，式(8)中的第三項與其不同，它同時考慮了雙點平滑和單點平滑。

進一步將式(8)中的第三項寫成：

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

(10)

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

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

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

(11)

它可以寫成:

(1-τ)(fTLf)]

(12)

應用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表示已標記數(shù)據(jù)集，X表示整個數(shù)據(jù)集。已標記數(shù)據(jù)的類標簽向量用Yl=[y1,y2,…,yl]T表示。

通過J1對α求導后值為0求最小值，因此:

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

(15)

最后,得到:

(16)

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

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

(17)

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

進一步寫為：

(1-τ)(fTLf)]

(18)

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

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

(1-τ)(αTKLKα)]

(19)

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

應用拉格朗日乘子法后,得到:

(20)

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

進一步得出：

(21)

因此，再將J2寫成:

(22)

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

進一步得到:

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

(23)

因此有:

(24)

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

(25)

其中:

(26)

3 實驗與結(jié)果分析

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

表1 13個UCI數(shù)據(jù)集的相關信息

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

3.1 性能比較

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

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

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

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

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

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

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

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

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

參數(shù)τ對于單雙點平滑結(jié)合MR的性能表現(xiàn)很重要，因此，這里展示在6個UCI數(shù)據(jù)集上具有不同τ值的SDS_LapRlsc的性能表現(xiàn)，并以SVM作為基準。每個UCI數(shù)據(jù)集只包含10個已標記樣本。采用線性核并且τ的取值范圍為{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) 在單個數(shù)據(jù)集上的性能變化規(guī)則是不同的。具體來說，在大多數(shù)數(shù)據(jù)集上，當τ取值為0.5時可以獲得滿意的性能，要選擇最合適的τ很難，這也將是未來一項重要工作。然而，即使將數(shù)值τ固定為0.5，SDS_LapRlsc的性能已經(jīng)具有競爭力了。

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

4 結(jié) 語

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