基于轉換學習的半監(jiān)督分類

康 昭 劉 亮 韓 蒙

1 （電子科技大學計算機科學與工程學院 成都 611731）2 （電子科技大學公共管理學院 成都 611731） （zkang@uestc.edu.cn）

傳統(tǒng)的監(jiān)督分類只能使用已標記的數(shù)據(jù)進行訓練，而標記樣本通常需要耗費大量時間或精力.同時，未標記數(shù)據(jù)相對容易收集，因此發(fā)展能處理它們的算法尤為重要.半監(jiān)督學習試圖處理有大量未標數(shù)據(jù)的問題，旨在通過學習大量未標記數(shù)據(jù)和小部分有標簽數(shù)據(jù)來構建更好的分類器.相對而言，半監(jiān)督學習只需要較少的人力就能達到更高的準確性，在近年來受到了廣泛的關注.

在眾多半監(jiān)督分類方法[1-6]中，基于圖方法[7-11]的研究是近年來機器學習與模式識別領域的研究熱點之一.這類方法通過定義一個圖，然后基于圖上的局部平滑程度來推斷缺失的標簽，即若2個樣本越相似，它們具有相同標簽的可能性就越大.劉鈺峰等人[12]在相似樣本的類別也相似的一致性假設下，提出圖正則化框架對異構圖信息網絡進行半監(jiān)督分類.

總的來說，這些方法通常由2步組成.首先，從所有的數(shù)據(jù)點中構造圖，其節(jié)點是數(shù)據(jù)集中有標簽和無標簽數(shù)據(jù)樣本，而邊反映數(shù)據(jù)間的相似性；其次，假定圖上的標簽平滑性，利用標簽傳播方法[13]來推斷所有的標簽.因此，有大量的算法關注于構建圖或標簽傳播，Jebara等人[14]提出了一種基于b-matching的圖構造方法；Cheng等人[15]通過將每個數(shù)據(jù)點分解為稀疏線性組合來衡量數(shù)據(jù)點之間的相似性，從而構造圖的相似度矩陣；Li等人[16]提出了一種基于低秩子空間的圖構造方法；Wang等人[17]提出了一種基于線性鄰域的標簽傳播方法.

盡管現(xiàn)有的算法已經在各種實際應用中取得了不錯的效果，但它們依然在某些方面受到限制:

1) 大多數(shù)圖都是直接基于原始數(shù)據(jù)上構建的.但由于原始數(shù)據(jù)的污染，建立的圖可能無法準確反映樣本之間的潛在關系.而圖的質量對于后續(xù)任務的執(zhí)行至關重要[18-19].

2) 現(xiàn)有方法通常將圖的構造與標簽傳播視為2個單獨的步驟，這樣可能會產生低質量圖導致的次優(yōu)解.即在第1步中構建的圖對于后續(xù)任務處理可能并不是最優(yōu)的.

面對上述2個限制，本文提出了一種基于轉換學習的半監(jiān)督分類（semi-supervised classification based on transformed learning，TLSSC）算法.該算法是一個統(tǒng)一的聯(lián)合優(yōu)化框架，會根據(jù)分類結果更新其他變量.該框架由3個部分組成：1）使用轉換學習將原始數(shù)據(jù)映射到轉換空間中；2）借鑒數(shù)據(jù)自表示思想，在轉換空間上學習一個圖；3）在圖上進行標簽傳播.

數(shù)據(jù)自表示的主要策略是將每個數(shù)據(jù)點表示為其他數(shù)據(jù)點的線性組合，線性權重將構成相似度矩陣.該思想在子空間聚類問題上取得了巨大成功.研究發(fā)現(xiàn)，即使數(shù)據(jù)不能在原始域中被分割聚類，變換后的數(shù)據(jù)點也能夠被聚類成獨立的子空間[20].因此，本文利用轉換學習將數(shù)據(jù)映射到轉換空間中，并在轉換空間中應用數(shù)據(jù)自表示進行圖的構造.

總的來說,本文的主要貢獻有3個方面：

1）提出了一種用于半監(jiān)督分類的轉換學習方式.這種方式將數(shù)據(jù)映射到一個轉換空間，再對轉換空間中的數(shù)據(jù)進行處理，這為表征學習提供了一個新的策略.

2）提出了一種基于轉換學習的半監(jiān)督分類算法框架.該框架將數(shù)據(jù)映射、圖構造和標簽傳播集成到一個統(tǒng)一的框架中，進行聯(lián)合優(yōu)化.

3）在數(shù)據(jù)集上進行了大量廣泛的實驗.與現(xiàn)有具有代表性的半監(jiān)督分類算法相比，本文提出的算法在某些方面展現(xiàn)了其優(yōu)越性.

為避免混淆，此處將給出本文主要使用的符號.將半監(jiān)督分類問題的訓練數(shù)據(jù)矩陣表示為X=(x1,···,xl,···,xl+u)T，其中l(wèi)+u=N，l和u分別是有標簽和無標簽數(shù)據(jù)的數(shù)目，xi∈Rn為數(shù)據(jù)樣本(數(shù)據(jù)點)，n為特征數(shù).c為數(shù)據(jù)的類別總數(shù)，Y為標簽矩陣，當?shù)趇個樣本屬于第j個類別時yij=1，否則yij=0.向量xi=(xi1,xi2,···,xin)∈ Rn的 ?2-范數(shù)定義為

1 相關工作

1.1 轉換學習

傳統(tǒng)的字典學習是一個合成過程，它通過從數(shù)據(jù)中學習一個字典矩陣，利用字典矩陣A對數(shù)據(jù)進行合成.在數(shù)學上，可以這樣表示：

而轉換學習是字典學習的分析形式，它通過學習一個轉換矩陣，將原始數(shù)據(jù)投影到轉換空間內.在數(shù)學上，可以這樣表示：

其中T是轉換矩陣，X是數(shù)據(jù)矩陣，Z是相關系數(shù)矩陣.Ravishankar等人[21]提出了一種轉換學習的公式：

其中參數(shù) λ和 μ為正數(shù).? logdetT能夠保證學習到的轉換矩陣是滿秩的，防止產生退化解，即T= 0，Z= 0.正則化項能夠平衡尺度，否則 ? logdetT項可以無限增加，產生另一個極端退化解.

Ravishankar等人在文獻[22]中提出了一種交替更新的方式解決轉換學習問題.具體算法為

通過軟閾值函數(shù)直接求解Z：

其中“·”表示元素積.對于更新轉換矩陣T，可以發(fā)現(xiàn)式(4)中各項的梯度都非常容易計算，求導結果為

在最初關于轉換學習的文獻[22]中，提出了一種基于非線性共軛梯度技術來解決轉換矩陣的更新問題.接著，在文獻[23]中，通過一些線性代數(shù)技巧，證明了該迭代更新算法的收斂性.

該算法首先進行霍爾茨基分解，XXT+λI是正定對稱矩陣，其中I為單位矩陣；接著進行奇異值分解；最后一步對轉換矩陣T進行更新.可以發(fā)現(xiàn)，L是一個下三角矩陣，因此L?1很容易計算，這極大地減少了計算量，提高了運算效率.由于代價函數(shù)是一個單調遞減函數(shù)，并存在下限，因此代價函數(shù)收斂，它的閉式解存在.

1.2 半監(jiān)督學習

近年來，基于圖的半監(jiān)督分類吸引了廣泛關注.例如，Zhu等人[24]設計了一種基于高斯場和諧波函數(shù) (Gaussian field and harmonic function, GFHF)的半監(jiān)督分類算法，它利用圖上的高斯隨機場上的諧波特性進行半監(jiān)督分類.盡管該算法已經取得了廣泛的普及，但其分類性能很大程度上仍然取決于輸入圖.

有一些半監(jiān)督分類算法關注構造圖的魯棒性對于分類性能的影響.例如，Nie等人[25]提出了一種基于最小化譜嵌入的 ?1-范數(shù)的半監(jiān)督分類算法；古楠楠等人[26]提出了一種基于放射子空間稀疏表示的圖構造方法，這種方法能夠快速對新來樣本點進行分類，并且繼承了稀疏表示的能夠自適應進行鄰域選擇以及具有較高判別性的優(yōu)點.

盡管文獻[25?26]所提的算法在很多方面已經取得了成效，可以避免直接從嘈雜數(shù)據(jù)中構造圖，但由于圖構建和標簽傳播是分開進行的，其分類性能仍然可能受到影響.

2 基于轉換學習的半監(jiān)督分類

2.1 綜合方程

本文提出的算法使用轉換學習將原始數(shù)據(jù)映射到轉換空間中，并在轉換空間上學習一個圖，最后在圖上進行標簽傳播.

本文提出的框架其綜合表述為

其中，T是轉換矩陣，Z表示系數(shù)矩陣，C代表一個建立在轉換空間上的圖的鄰接矩陣，F(xiàn)表示標簽指示矩陣.α和 β 是參數(shù)，用于平衡式（8）的3個函數(shù) Φ ()， ? ()，Θ()部分之間的作用.本文將會詳細討論問題(8)中的各項.

2.2 轉換學習

本文已經在1.1節(jié)討論了轉換學習的現(xiàn)有概念.為了在轉換空間中構建一個圖并進行標簽傳播，首先需要從原始數(shù)據(jù)中學習到一個轉換空間：

2.3 圖構建

式（9）在原始數(shù)據(jù)X中學習了系數(shù)矩陣Z，本節(jié)將在系數(shù)矩陣Z上建立一個圖，Z中每個樣本（即每行）對應該圖中一個節(jié)點.2節(jié)點之間的相似度很高(或者相關性很強)，則對應的節(jié)點之間將存在1條邊，這條邊的權重正比于樣本之間的相似度(或相關性).

定義圖的鄰接矩陣C=(Cij)，其中Cij表示第i行和第j行之間的相似度.本文借鑒數(shù)據(jù)自表示的思想來建立相似度矩陣[27]，其核心思想是數(shù)據(jù)來自多個子空間，每個樣本都可以用同一個子空間的樣本的線性組合來表示.數(shù)學上，通過式（10）求解：

因此，式(8)的第2項可以表示為

2.4 標簽傳播

式(11)自動地從數(shù)據(jù)中學到了一個圖，但本文不能保證它對接下來的分類是最優(yōu)的.理想情況下，如果數(shù)據(jù)中有c類的話，圖C應該恰好擁有c個連通成分.使用 σi表示拉普拉斯矩陣L中第i個最小的特征值.由于L是一個半正定矩陣，所以 σi>0.為了解決這個問題，可以采用定理1：

定理1.圖C的連通分量c的個數(shù)等于其拉普拉斯矩陣L的零特征值的重數(shù)[28].

在半監(jiān)督學習中，矩陣F可以被分解成F=(Fl;Fu)=(Yl;Fu).根據(jù) Nie等人[18]提出的理論，式（12）的等號右邊其實就是半監(jiān)督分類的標簽傳播目標函數(shù).因此，式（8）的第3項可以表示為

2.5 統(tǒng)一聯(lián)合優(yōu)化目標函數(shù)

根據(jù)式（9）（11）（13），TLSSC 目標函數(shù)可寫為

可以觀察到，式（14）將轉換學習、圖構建和標簽傳播整合到一個統(tǒng)一的框架中，矩陣T,Z,C,F的聯(lián)合優(yōu)化有助于實現(xiàn)整體的最優(yōu)解.系數(shù)矩陣Z建立在轉換空間中.

3 對式（14）的求解

3.1 優(yōu)化步驟

本節(jié)基于一種交替迭代的策略來求解式（14），即固定某一個變量的同時確定另一個變量.

1)更新轉換矩陣T.當固定矩陣Z,C,F后，式（14）變?yōu)橐韵滦问剑?/p>

如第1節(jié)中所述，式（15）可以通過非線性共軛梯度技術來解決.

2)更新系數(shù)矩陣Z.當固定矩陣Z,C,F后，式（14）轉換為：

由于有

因此式（18）仍可以用軟閾值函數(shù)進一步求解.

3)更新鄰接矩陣C.當固定矩陣T,Z,F后，式（14）轉換為：

式（19）可以通過逐列來求解，即

對式(20)進行求解，有

4)更新標簽指示矩陣F.固定矩陣T,Z,C后，式（14）轉換為：

將上述步驟1）~4）迭代多次，直至F的變化程度小于閾值 ε.最后，未標記的數(shù)據(jù)點的標簽可以通過以下決策函數(shù)得到：

完整的基于轉換學習的半監(jiān)督分類算法如算法1所示.

算法1.基于轉換學習的半監(jiān)督分類算法.

輸入；數(shù)據(jù)矩陣X，標簽矩陣Yl，參數(shù) α ，β，λ，μ；

輸出：未標記數(shù)據(jù)的標簽.

① 初始化標簽指示矩陣Fu，t=0；

② repeat

③t=t+1；

④ 更新轉換矩陣Tt根據(jù)式（16）；

⑤ 更新系數(shù)矩陣Zt根據(jù)式（18）；

⑥ 更新相似度矩陣Ct根據(jù)式（21）；

⑦ 更新標簽矩陣Ft根據(jù)式（23）；

⑧ until ∥Ft?Ft?1∥2F< ?.

3.2 復雜度分析

本文提出的基于轉換學習的半監(jiān)督算法是采用交替迭代的更新策略，給定數(shù)據(jù)矩陣X∈ Rn×N，固定矩陣Z,C,F，更新轉換矩陣T∈ Rm×n，目標方程的各項梯度表達式如式（16）所示.為估算轉換學習更新的成本，首先假定XXT已經預先計算，式（16）中的梯度包括了矩陣乘積TXXT和ZXT.計算T(XXT)需要n3次乘加運算，矩陣乘積ZXT在每次更新都會計算，并且當Z是稀疏的且有Nm個非零元素時m=αn（一般 α ?1），計算ZXT需要 αNn2次乘加操作.接下來式(6)中剩下的梯度計算主要由C3n3決定（矩陣求逆過程），其中C3是一個常數(shù).因此，轉換學習更新步驟的計算成本大約為 αNn2+(1+C3)Ln3，其中L通常是固定的共軛梯度步數(shù).假設 (1 +C3)nL<αN，那么每次轉換學習更新的成本可以縮放為O(Nn2).每次更新系數(shù)矩陣Z∈ Rm×N，使用了 ?1?范數(shù)，并且使用軟閾值求解Z，需要進行O(nN)次操作，同時計算TX（在閾值設定之前）需要O(Nn2)次操作，子空間矩陣計算ZC需要O(N3)次操作，每次更新系數(shù)矩陣復雜度為nN+Nn2+N3，n

4 實 驗

4.1 數(shù)據(jù)集

為了評價本文算法的分類性能，本節(jié)在以下3個標準數(shù)據(jù)集和2個擴充數(shù)據(jù)集上進行了分類實驗.

1)YALE人臉數(shù)據(jù)庫.由耶魯大學計算視覺與控制中心創(chuàng)建，包含15位志愿者的165張圖片，每個對象采集的樣本包含11張有明顯的光照變化的近額圖像.圖1(a)展示了一些示例圖片.

2)JAFFE人臉數(shù)據(jù)集.包含10位日本女性志愿者的213張圖片，每個對象的樣本包含7種不同的面部表情.圖1(b)展示了一些示例.

3)COIL20圖像數(shù)據(jù)集.由哥倫比亞大學圖像庫發(fā)布，包含20個物體在360°旋轉中不同角度成像的圖片，每個對象包含72種姿勢.圖1(c)展示了一些示例.

4)COIL100圖像數(shù)據(jù)集.包含100個物體，每個物體72張圖片在360°旋轉中不同角度成像的圖片.

5)YALEB.耶魯大學擴充人臉數(shù)據(jù)庫，總樣本數(shù)2 414張，共38類，每類大約64張圖片，每張圖片在不同的光照條件和不同的面部表情下拍攝.

Fig.1 Sample images of three datasets圖1 3個數(shù)據(jù)集樣本的示例

4.2 對比算法

本節(jié)將TLSSC與4種現(xiàn)有具有代表性的算法進行了比較：

1)LGC（learning with local and global consistency）算法.由Zhou等人[30]提出，是一種廣泛使用的半監(jiān)督分類算法.

2)GFHF（Gaussian fields and harmonic functions）算法.它是除了LGC外的另一個流行的標簽傳播算法.

3)S2LRR（semi-supervised low-rank representation）算法.Li等人[31]提出了一種基于自表達的方法來構建半監(jiān)督學習圖.相似度矩陣和類別指示矩陣交替迭代更新，從而達到互相學習和提高.基于低秩假設，得到 S2LRR 模型.

4)SCAN（semi-supervised classification with adaptive neighbors）算法.Nie 等人[18]提出一種基于圖的方法，使用自適應鄰近點的方法構造相似度矩陣，將圖構造和標簽傳播集合到一個框架中聯(lián)合優(yōu)化.

在上述4種算法中，LGC與GFHF均以拉普拉斯矩陣作為輸入.為了使其獲得更好的性能，本文基于7種核矩陣計算拉普拉斯矩陣，其中7種核矩陣包含4個形式分別為t∈{0.1,1,10,100}的高斯核、1個形式為K(x,y)=xTy的線性核，以及2個形式為K(x,y)=(α+xTy)2， α ∈{0,1}的多項式核.另外2種算法則直接從原始數(shù)據(jù)中構建圖.

4.3 結 果

所有算法均選擇10%，30%，50%有標簽的數(shù)據(jù)，重復實驗20次，將分類準確度(accuracy，Acc)和標準差記錄于表1中.所有算法都選擇了在最好參數(shù)下的結果，LGC和GFHF算法選擇了在最好的核矩陣下產生的結果.結果顯示，當標簽比例增大時，所有方法的分類準確度都有所上升，在大多情況下，TLSSC算法的分類性能比其他現(xiàn)有算法更好，尤其在YALE數(shù)據(jù)集上得到了大量的提升.另外，相對于緊密相關的S2LRR算法，TLSSC在大部分情況下也大大提升了分類性能，尤其是在YALE和COIL100數(shù)據(jù)集上.

圖2展示了鄰接矩陣C在3個數(shù)據(jù)集上的分布，可以發(fā)現(xiàn)C幾乎可以被視作為塊對角矩陣，這符合本文的預期，說明了在數(shù)據(jù)集上學到的圖能很好地反映樣本間的關系.

Table 1 Experimental Results of Classification Accuracy for Each Algorithm on Benchmark Data Sets表1 各種算法在數(shù)據(jù)集上的Acc實驗結果 %

Fig.2 Distribution of the adjacency matrix Con 3 datasets圖2 鄰接矩陣 C在3個數(shù)據(jù)集上的分布

4.4 參數(shù)敏感性

為了測試TLSSC算法對參數(shù)α，β，λ，μ的敏感性，文本以JAFFE數(shù)據(jù)集為例，在圖3中給出了在λ=0.000 1，μ= 0.000 01 時，不同α和β在不同標簽比例下的實驗精度.可以發(fā)現(xiàn)，當標簽比例減小時，分類準確率有所下降；在標簽比例較小時，參數(shù)α和β的變化對分類結果影響較大.而圖4 給出了在α= 0.000 1,β=0.000 1 時，不同λ和μ在不同標簽比例下的實驗精度.圖4的結果顯示，λ的變化對分類結果的影響更小，而且在μ取較小的值時性能相對好一些.

Fig.3 Influence of α and β on Acc in JAFFE dataset圖3 α和β在JAFFE數(shù)據(jù)集上Acc的影響

Fig.4 Influence of λ and μ on Acc in JAFFE dataset圖4 λ和μ在JAFFE數(shù)據(jù)集上Acc的影響

5 總 結

本文提出了一種基于轉換學習的半監(jiān)督分類算法，該算法提出了一個統(tǒng)一聯(lián)合優(yōu)化框架.該框架首先利用轉換學習，將原始數(shù)據(jù)映射到一個數(shù)據(jù)平面(轉換空間)；接著借鑒數(shù)據(jù)自表示思想，在轉換空間中構建了一個圖，并在圖上進行標簽傳播.該框架集成了轉換學習、圖構建和標簽傳遞3個步驟，聯(lián)合統(tǒng)一優(yōu)化有利于獲得全局最優(yōu)解.實驗表明，本文提出的TLSSC算法在大部分情況下優(yōu)于其他現(xiàn)有分類算法，證明了該算法的有效性.

作者貢獻聲明：康昭負責論文方案設計實施、實驗結果整理與分析以及論文整體攥寫和修訂；劉亮和韓蒙負責論文撰寫與修訂.