基于半監(jiān)督假設(shè)的半監(jiān)督稀疏度量學(xué)習(xí)

王倩影 李 煒

(河北經(jīng)貿(mào)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 河北 石家莊 050051)

0 引 言

度量學(xué)習(xí)[1]的本質(zhì)是學(xué)習(xí)一個(gè)映射空間，使得同類樣本間的距離更近，異類樣本間的距離更遠(yuǎn)。近年來，度量學(xué)習(xí)在眾多領(lǐng)域得到了廣泛應(yīng)用，如人臉識別[2-4]、圖像檢索[5-7]等。根據(jù)不同的訓(xùn)練樣本，度量學(xué)習(xí)可以分為無監(jiān)督度量學(xué)習(xí)、有監(jiān)督度量學(xué)習(xí)和半監(jiān)督度量學(xué)習(xí)。無監(jiān)督度量學(xué)習(xí)的訓(xùn)練樣本為無標(biāo)記數(shù)據(jù)，有監(jiān)督度量學(xué)習(xí)的訓(xùn)練樣本給定了正負(fù)限制的樣本對，但沒有將無標(biāo)記樣本利用起來。因此人們嘗試將大量無標(biāo)記樣本數(shù)據(jù)加入到有標(biāo)記樣本中一起訓(xùn)練來進(jìn)行學(xué)習(xí)，由此產(chǎn)生了半監(jiān)督度量學(xué)習(xí)[8]。

由于現(xiàn)實(shí)應(yīng)用中存在大量無標(biāo)記樣本，半監(jiān)督度量學(xué)習(xí)是當(dāng)前的一個(gè)研究熱點(diǎn)。Joachims等[9]依據(jù)半監(jiān)督支持向量機(jī)(S3VM)提出了基于標(biāo)記切換的組合優(yōu)化算法，使S3VM在數(shù)據(jù)集上取得了不錯(cuò)的效果。Chapelle等[10-11]提出了半監(jiān)督學(xué)習(xí)有關(guān)高維數(shù)據(jù)的三個(gè)假設(shè)：光滑假設(shè)、聚類假設(shè)和流形假設(shè)，并據(jù)此提出了低密度分割算法，得到了很好的分類效果。現(xiàn)今對半監(jiān)督度量學(xué)習(xí)方法的研究只利用了三個(gè)半監(jiān)督假設(shè)中的一項(xiàng)或兩項(xiàng)，沒有一個(gè)方法滿足所有的三個(gè)半監(jiān)督假設(shè)。而且在大數(shù)據(jù)時(shí)代，數(shù)據(jù)呈現(xiàn)出維度高的特點(diǎn)，常見的度量學(xué)習(xí)方法基于原始特征產(chǎn)生度量，使得度量矩陣很復(fù)雜。利用高維數(shù)據(jù)的潛在稀疏性建立稀疏正則化模型，可以有效地處理高維數(shù)據(jù)。文獻(xiàn)[12]據(jù)此提出了基于L1正則化的模型lasso。但目前存在的稀疏正則化模型沒有結(jié)合半監(jiān)督度量學(xué)習(xí)中的三個(gè)半監(jiān)督假設(shè)，把無標(biāo)記樣本充分利用起來。

為了充分利用無標(biāo)記樣本，本文從間隔損失函數(shù)入手，依據(jù)三個(gè)半監(jiān)督假設(shè)，建立了半監(jiān)督假設(shè)正則項(xiàng)，并結(jié)合稀疏正則項(xiàng)，提出了基于半監(jiān)督假設(shè)的半監(jiān)督稀疏度量學(xué)習(xí)算法。最后通過實(shí)驗(yàn)驗(yàn)證了本文所提算法的有效性。

1 間隔損失函數(shù)

1.1 問題描述

在學(xué)習(xí)一個(gè)度量時(shí)，樣本對的限制是指兩個(gè)給定的樣本是否在同一類，若在一類則稱為一個(gè)正約束，若不在一類則稱為一個(gè)負(fù)約束。所要學(xué)習(xí)的度量是要使得屬于同一類的兩個(gè)樣本距離更近，屬于不同類的兩個(gè)樣本距離更遠(yuǎn)。三樣本為一組的約束是對樣本對約束的拓展。在三樣本組約束(xi,xj,xk)中，(xi,xj)之間的距離要求比(xi,xk)之間的距離小。因此，若(xi,xj)是一個(gè)正約束，(xi,xk)是一個(gè)負(fù)約束，則(xi,xj,xk)就是一個(gè)三樣本組約束。但反之不成立，即并不能由(xi,xj)之間的距離比(xi,xk)之間的距離小，得到(xi,xj)屬于同一類，(xi,xk)屬于不同類的結(jié)果。當(dāng)給定一些三樣本組約束時(shí)，我們將要學(xué)習(xí)一個(gè)滿足如下條件的度量：如圖1所示，對每一個(gè)三樣本組約束學(xué)習(xí)的度量要使得(xi,xj)之間的距離小于(xi,xk)之間的距離。

圖1 三樣本組約束示意圖

類標(biāo)信息可以轉(zhuǎn)化成三樣本組約束。每個(gè)三樣本組約束由三個(gè)樣本(xi,xj,xk)組成，其中，xi是所要討論的樣本。希望學(xué)習(xí)得到這樣的距離DM(xi,xj)和DM(xi,xk)滿足：

φ={(xi,xj,xk)|DM(xi,xj)

(1)

1.2 損失函數(shù)

本文參考LMNN的損失函數(shù)，對有標(biāo)記樣本的損失函數(shù)定義如下：

(2)

文獻(xiàn)[13-14]證明了該損失函數(shù)的有效性，但此函數(shù)在運(yùn)用過程中對噪聲數(shù)據(jù)較為敏感，容易出現(xiàn)過擬合現(xiàn)象，并且沒有將無標(biāo)記樣本利用起來。為了解決這些問題，引入半監(jiān)督假設(shè)正則項(xiàng)將無標(biāo)記樣本充分利用起來，過擬合通常發(fā)生在特征(參數(shù))較多的時(shí)候，引入L1正則項(xiàng)，L1正則化會產(chǎn)生稀疏解，部分分量會變成0，相當(dāng)于對原始特征做了特征提取。

2 正則化的半監(jiān)督度量學(xué)習(xí)

2.1 半監(jiān)督假設(shè)正則項(xiàng)

數(shù)據(jù)分布可以由樣本及其近鄰所反映，因此我們可以通過樣本間的相似度以及區(qū)域密度來描述樣本及其近鄰間的關(guān)系。若給定樣本集X=[x1,x2,…,xn]，以及與其相對應(yīng)的相似矩陣S=[Sij]，本文根據(jù)三個(gè)半監(jiān)督假設(shè)來建立正則項(xiàng)。提出的正則項(xiàng)為：

(3)

式中：

(4)

N(i)是xi由歐氏距離確定的鄰域點(diǎn)的集合，在正則項(xiàng)中引入的Sij是xi和xj之間的相似度。根據(jù)聚類假設(shè)，引入密度指標(biāo)βi∈R+，它是一個(gè)有關(guān)樣本xi密度的函數(shù)。

結(jié)合間隔損失函數(shù)和提出的正則項(xiàng)，我們得到一個(gè)新的度量學(xué)習(xí)方法：

(5)

式中：λ1用是來調(diào)整正則項(xiàng)的權(quán)重參數(shù)。

2.2 稀疏正則項(xiàng)

通常度量學(xué)習(xí)任務(wù)中的特征數(shù)量較多，在預(yù)測或分類時(shí)，難以對特征進(jìn)行選擇，但是如果代入這些特征得到的模型是一個(gè)稀疏模型，即只有少數(shù)特征對這個(gè)模型有貢獻(xiàn)，絕大部分特征是沒有貢獻(xiàn)的，此時(shí)我們可以只關(guān)注這些對模型有貢獻(xiàn)的特征。L1正則化有助于生成這樣一個(gè)稀疏權(quán)值矩陣，進(jìn)而用于特征提取。

目標(biāo)函數(shù)變?yōu)椋?/p>

(6)

式中：λ2用是來調(diào)整正則項(xiàng)的權(quán)重參數(shù)。

2.3 問題優(yōu)化

學(xué)習(xí)一個(gè)度量，我們可以看成是學(xué)習(xí)一個(gè)映射，把特征空間中的樣本映射到另外一個(gè)新的空間中，新空間中的歐式距離即為所求的度量。具體地，學(xué)習(xí)一個(gè)馬氏矩陣M等價(jià)于學(xué)習(xí)一個(gè)線性映射LT:Rm→Rr，其中L=[l1,l2,…,lr]∈Rm×r。因此，我們可以這樣計(jì)算兩個(gè)樣本間的距離：

(xi-xj)TM(xi-xj)=

(7)

式中：M=LLT是所要學(xué)習(xí)的度量。

為了簡化目標(biāo)函數(shù)，我們引入一個(gè)新的記號。對于要研究的樣本xi，引入權(quán)重矩陣W(i)，這是一個(gè)對角陣：

重新整理正則項(xiàng)：

(8)

根據(jù)式(8)得：

tr(XUXTLLT)=tr(XUXTM)

(9)

目標(biāo)函數(shù)最后變?yōu)橄率剑?/p>

(10)

本文所提出的半監(jiān)督稀疏度量學(xué)習(xí)方法有如下優(yōu)點(diǎn)：

(2) 聚類假設(shè)表明分界線(面)應(yīng)該從低密度區(qū)域穿過，也就是說分布在高密度區(qū)域的樣本點(diǎn)之間的距離應(yīng)較小。式(6)正則項(xiàng)中的βi可以保證分布在高密度區(qū)域樣本點(diǎn)之間的距離被最小化，如果這些樣本之間存在較大的距離將會受到較大的懲罰。

(3) 根據(jù)流形假設(shè)，樣本間的距離要沿著流形來測量。在受到半監(jiān)督學(xué)習(xí)中基于樣本圖的啟發(fā)后，我們在正則項(xiàng)中引入了相似度Sij，這個(gè)相似性是根據(jù)高斯核來計(jì)算的，它可以引導(dǎo)新的度量。

(4) 引入稀疏正則項(xiàng)，本文引入的的L1正則項(xiàng)使得度量矩陣具有稀疏性，有助于了解不同原始特征的重要程度，滿足應(yīng)用對可理解性的需求。

3 模型求解

梯度下降法是一種常用的一階優(yōu)化方法，是求解優(yōu)化問題最經(jīng)典的方法之一。

Ft=λ2tr(M(t))+λ1tr(XUXTM(t))+

(11)

式中：|{φ(t)}|指集合{φ(t)}中元素的個(gè)數(shù)，M(t+1)則可以通過M(t)向Ft的梯度相反方向移動一個(gè)步長得到，即:

M(t+1)=M(t)-γ▽Ft

重復(fù)此過程，直到滿足了所有三樣本組約束，或者達(dá)到預(yù)給定好的循環(huán)次數(shù)。算法描述如算法1所示。

算法1梯度下降算法

輸入：有標(biāo)記樣本Xl

無標(biāo)記本Xu

示性矩陣Y

輸出：度量M

1.初始化三樣本組約束的個(gè)數(shù)k，半正定矩陣M，最大循環(huán)次數(shù)T；

2. fort=1:Tdo

3. 根據(jù)M(t)、Y和Xl確定不滿足約束的三樣本組集合φ(t)

4. ifφ(t)為空集 then

5. break

6. else

7. 計(jì)算當(dāng)前目標(biāo)函數(shù)Ft的梯度

8. 更新M，M(t+1)=M(t)-γ▽Ft

9. 將M(t+1)投影到半正定矩陣子空間中得到半正定度量

10. end for

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

在本節(jié)中，將把本文提出的基于半監(jiān)督假設(shè)的半監(jiān)督稀疏度量學(xué)習(xí)算法(RS3ML)與S3ML、半監(jiān)督判別分析(SDA)、LRML、基于核方法的半監(jiān)督度量學(xué)習(xí)算法Kernel-A和Kernel-β進(jìn)行分析比較，通過比較結(jié)果來測試本文所提方法的有效性。實(shí)驗(yàn)中，以歐氏距離作為比較的基準(zhǔn)。

我們把類標(biāo)信息分別轉(zhuǎn)化為樣本對約束和三樣本組約束。本文所提出的算法的參數(shù)依據(jù)文獻(xiàn)[15]進(jìn)行設(shè)置。

4.2 實(shí)驗(yàn)結(jié)果

從University of California Irvine(UCI) machine learning repository中選出五個(gè)數(shù)據(jù)集對各種算法進(jìn)行1-NN的分類實(shí)驗(yàn)。五個(gè)數(shù)據(jù)集分別為Wine、Iris、Dermatology、Glass Identification(Glass)、Balance Scale(Balance)。其中：Wine數(shù)據(jù)集中記錄的是意大利同一地區(qū)三種不同的葡萄酒品種的相關(guān)信息，Balance中記錄的是天平的重量和距離，Dermatology數(shù)據(jù)集用于判定鱗狀疾病的類型，Glass數(shù)據(jù)集記錄的是不同類型的玻璃的氧化物含量的數(shù)據(jù)，Iris中包含的是不同種類鳶尾花的一些信息。各個(gè)數(shù)據(jù)集的基本信息如表1所示。

實(shí)驗(yàn)中，所有的數(shù)據(jù)都被隨機(jī)分為有標(biāo)記數(shù)據(jù)集Xl和無標(biāo)記數(shù)據(jù)集Xu，并且每類只給了五個(gè)有標(biāo)記樣本，這些有標(biāo)記樣本用來訓(xùn)練度量和K近鄰分類器。每個(gè)實(shí)驗(yàn)將會在同一數(shù)據(jù)集上重復(fù)30次，每次試驗(yàn)都隨機(jī)地選取訓(xùn)練樣本，實(shí)驗(yàn)結(jié)果給出了這30次實(shí)驗(yàn)結(jié)果的均值。

圖2、圖3和圖4結(jié)合1-NN分類器給出了不同度量算法的識別結(jié)果。縱坐標(biāo)均為重復(fù)30次實(shí)驗(yàn)所取得的平均分類錯(cuò)誤率。可以看出，兩個(gè)核方法Kernel-A和Kernel-β在數(shù)據(jù)集上的表現(xiàn)不太穩(wěn)定。本文提出的RS3ML算法與S3ML、SDA等其他算法比較，在五個(gè)數(shù)據(jù)集上的分類錯(cuò)誤率均為最低。實(shí)驗(yàn)結(jié)果表明，相比其他度量算法，RS3ML算法效果明顯，學(xué)習(xí)性能更優(yōu)。

圖3 算法組2的錯(cuò)誤率比較

圖4 算法組3的錯(cuò)誤率比較

5 結(jié) 語

本文基于三個(gè)半監(jiān)督假設(shè)提出了一個(gè)半監(jiān)督稀疏度量學(xué)習(xí)算法。與其他方法不同的是，本文所提出的方法結(jié)合了所有三個(gè)半監(jiān)督假設(shè)，充分利用了大量的未標(biāo)記樣本，并利用L1范數(shù)使得度量矩陣具有稀疏性，從而減少計(jì)算機(jī)存儲負(fù)擔(dān)，提高學(xué)得模型的可解釋性。最后在公開數(shù)據(jù)上的實(shí)驗(yàn)驗(yàn)證了本文提出的方法的有效性。