康 昭 劉 亮 韓 蒙

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

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

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

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

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

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

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

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

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

總的來說,本文的主要貢獻(xiàn)有3個方面：

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

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

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

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

1 相關(guān)工作

1.1 轉(zhuǎn)換學(xué)習(xí)

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

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

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

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

Ravishankar等人在文獻(xiàn)[22]中提出了一種交替更新的方式解決轉(zhuǎn)換學(xué)習(xí)問題.具體算法為

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

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

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

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

1.2 半監(jiān)督學(xué)習(xí)

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

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

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

2 基于轉(zhuǎn)換學(xué)習(xí)的半監(jiān)督分類

2.1 綜合方程

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

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

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

2.2 轉(zhuǎn)換學(xué)習(xí)

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

2.3 圖構(gòu)建

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

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

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

2.4 標(biāo)簽傳播

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

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

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

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

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

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

3 對式（14）的求解

3.1 優(yōu)化步驟

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

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

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

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

由于有

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

3)更新鄰接矩陣C.當(dāng)固定矩陣T,Z,F后，式（14）轉(zhuǎn)換為：

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

對式(20)進(jìn)行求解，有

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

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

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

算法1.基于轉(zhuǎn)換學(xué)習(xí)的半監(jiān)督分類算法.

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

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

① 初始化標(biāo)簽指示矩陣Fu，t=0；

② repeat

③t=t+1；

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

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

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

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

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

3.2 復(fù)雜度分析

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

4 實 驗

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

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

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

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

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

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

5)YALEB.耶魯大學(xué)擴(kuò)充人臉數(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)有具有代表性的算法進(jìn)行了比較：

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

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

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

4)SCAN（semi-supervised classification with adaptive neighbors）算法.Nie 等人[18]提出一種基于圖的方法，使用自適應(yīng)鄰近點的方法構(gòu)造相似度矩陣，將圖構(gòu)造和標(biāo)簽傳播集合到一個框架中聯(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ù)中構(gòu)建圖.

4.3 結(jié) 果

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

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

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

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 時，不同α和β在不同標(biāo)簽比例下的實驗精度.可以發(fā)現(xiàn)，當(dāng)標(biāo)簽比例減小時，分類準(zhǔn)確率有所下降；在標(biāo)簽比例較小時，參數(shù)α和β的變化對分類結(jié)果影響較大.而圖4 給出了在α= 0.000 1,β=0.000 1 時，不同λ和μ在不同標(biāo)簽比例下的實驗精度.圖4的結(jié)果顯示，λ的變化對分類結(jié)果的影響更小，而且在μ取較小的值時性能相對好一些.

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é)

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

作者貢獻(xiàn)聲明：康昭負(fù)責(zé)論文方案設(shè)計實施、實驗結(jié)果整理與分析以及論文整體攥寫和修訂；劉亮和韓蒙負(fù)責(zé)論文撰寫與修訂.