基于半監督假設的半監督稀疏度量學習

王倩影 李 煒

(河北經貿大學數學與統計學學院 河北 石家莊 050051)

0 引 言

度量學習[1]的本質是學習一個映射空間，使得同類樣本間的距離更近，異類樣本間的距離更遠。近年來，度量學習在眾多領域得到了廣泛應用，如人臉識別[2-4]、圖像檢索[5-7]等。根據不同的訓練樣本，度量學習可以分為無監督度量學習、有監督度量學習和半監督度量學習。無監督度量學習的訓練樣本為無標記數據，有監督度量學習的訓練樣本給定了正負限制的樣本對，但沒有將無標記樣本利用起來。因此人們嘗試將大量無標記樣本數據加入到有標記樣本中一起訓練來進行學習，由此產生了半監督度量學習[8]。

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

為了充分利用無標記樣本，本文從間隔損失函數入手，依據三個半監督假設，建立了半監督假設正則項，并結合稀疏正則項，提出了基于半監督假設的半監督稀疏度量學習算法。最后通過實驗驗證了本文所提算法的有效性。

1 間隔損失函數

1.1 問題描述

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

圖1 三樣本組約束示意圖

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

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

(1)

1.2 損失函數

本文參考LMNN的損失函數，對有標記樣本的損失函數定義如下：

(2)

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

2 正則化的半監督度量學習

2.1 半監督假設正則項

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

(3)

式中：

(4)

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

結合間隔損失函數和提出的正則項，我們得到一個新的度量學習方法：

(5)

式中：λ1用是來調整正則項的權重參數。

2.2 稀疏正則項

通常度量學習任務中的特征數量較多，在預測或分類時，難以對特征進行選擇，但是如果代入這些特征得到的模型是一個稀疏模型，即只有少數特征對這個模型有貢獻，絕大部分特征是沒有貢獻的，此時我們可以只關注這些對模型有貢獻的特征。L1正則化有助于生成這樣一個稀疏權值矩陣，進而用于特征提取。

目標函數變為：

(6)

式中：λ2用是來調整正則項的權重參數。

2.3 問題優化

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

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

(7)

式中：M=LLT是所要學習的度量。

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

重新整理正則項：

(8)

根據式(8)得：

tr(XUXTLLT)=tr(XUXTM)

(9)

目標函數最后變為下式：

(10)

本文所提出的半監督稀疏度量學習方法有如下優點：

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

(3) 根據流形假設，樣本間的距離要沿著流形來測量。在受到半監督學習中基于樣本圖的啟發后，我們在正則項中引入了相似度Sij，這個相似性是根據高斯核來計算的，它可以引導新的度量。

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

3 模型求解

梯度下降法是一種常用的一階優化方法，是求解優化問題最經典的方法之一。

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

(11)

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

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

重復此過程，直到滿足了所有三樣本組約束，或者達到預給定好的循環次數。算法描述如算法1所示。

算法1梯度下降算法

輸入：有標記樣本Xl

無標記本Xu

示性矩陣Y

輸出：度量M

1.初始化三樣本組約束的個數k，半正定矩陣M，最大循環次數T；

2. fort=1:Tdo

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

4. ifφ(t)為空集 then

5. break

6. else

7. 計算當前目標函數Ft的梯度

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

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

10. end for

4 實 驗

4.1 實驗設置

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

我們把類標信息分別轉化為樣本對約束和三樣本組約束。本文所提出的算法的參數依據文獻[15]進行設置。

4.2 實驗結果

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

實驗中，所有的數據都被隨機分為有標記數據集Xl和無標記數據集Xu，并且每類只給了五個有標記樣本，這些有標記樣本用來訓練度量和K近鄰分類器。每個實驗將會在同一數據集上重復30次，每次試驗都隨機地選取訓練樣本，實驗結果給出了這30次實驗結果的均值。

圖2、圖3和圖4結合1-NN分類器給出了不同度量算法的識別結果?？v坐標均為重復30次實驗所取得的平均分類錯誤率?？梢钥闯觯瑑蓚€核方法Kernel-A和Kernel-β在數據集上的表現不太穩定。本文提出的RS3ML算法與S3ML、SDA等其他算法比較，在五個數據集上的分類錯誤率均為最低。實驗結果表明，相比其他度量算法，RS3ML算法效果明顯，學習性能更優。

圖3 算法組2的錯誤率比較

圖4 算法組3的錯誤率比較

5 結 語

本文基于三個半監督假設提出了一個半監督稀疏度量學習算法。與其他方法不同的是，本文所提出的方法結合了所有三個半監督假設，充分利用了大量的未標記樣本，并利用L1范數使得度量矩陣具有稀疏性，從而減少計算機存儲負擔，提高學得模型的可解釋性。最后在公開數據上的實驗驗證了本文提出的方法的有效性。