熊興良，樊明宇，洪振杰

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

基于半監(jiān)督拉普拉斯適應(yīng)實(shí)驗(yàn)設(shè)計(jì)的圖像分類

熊興良，樊明宇，洪振杰?

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

基于流形學(xué)習(xí)理論,通過改變權(quán)值的設(shè)置將類別信息加到圖構(gòu)造過程中，提出一種新的主動(dòng)學(xué)習(xí)算法．在3個(gè)真實(shí)圖像數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，新算法能夠取得較好的圖像分類效果．

主動(dòng)學(xué)習(xí)；流形學(xué)習(xí)；圖像分類

圖像分類中需要大量已標(biāo)簽樣本來訓(xùn)練分類器，而在實(shí)際應(yīng)用中標(biāo)注無類別數(shù)據(jù)樣本比較昂貴和費(fèi)時(shí)，特別是對(duì)于人臉識(shí)別問題．近來主動(dòng)學(xué)習(xí)已經(jīng)成為機(jī)器學(xué)習(xí)和模式識(shí)別[1]領(lǐng)域中的一個(gè)熱點(diǎn)，許多主動(dòng)學(xué)習(xí)技術(shù)為圖像分類和文本分類而提出，例如，直推式實(shí)驗(yàn)設(shè)計(jì)和支持向量機(jī)（SVM）[2]．以往絕大多數(shù)方法都是關(guān)于如何發(fā)現(xiàn)數(shù)據(jù)空間的判別結(jié)構(gòu)的[3-4]，對(duì)幾何結(jié)構(gòu)則很少關(guān)注．為了研究其潛在的幾何結(jié)構(gòu)，人們提出了各種各樣的流形學(xué)習(xí)算法，例如拉普拉斯特征映射、等距特征映射（ISOMAP）[3]、局部保持投影等．基于直推式實(shí)驗(yàn)設(shè)計(jì)，通過使用拉普拉斯構(gòu)圖法并在流形適應(yīng)核空間里執(zhí)行任務(wù)，以此來研究主動(dòng)學(xué)習(xí)，蔡登等人為文本分類[4]提出了一種新的稱為流形適應(yīng)實(shí)驗(yàn)設(shè)計(jì)（MAED）[4]的主動(dòng)學(xué)習(xí)算法．本文在半監(jiān)督學(xué)習(xí)[5]條件下為圖像主動(dòng)學(xué)習(xí)提出一種稱為半監(jiān)督拉普拉斯適應(yīng)實(shí)驗(yàn)設(shè)計(jì)（SSLAED）的新穎流形適應(yīng)主動(dòng)學(xué)習(xí)算法，通過半監(jiān)督方式構(gòu)圖并將圖結(jié)構(gòu)并到流形核中，從而使新的流形結(jié)構(gòu)能夠被應(yīng)用到學(xué)習(xí)過程中，傳統(tǒng)優(yōu)化實(shí)驗(yàn)設(shè)計(jì)也能夠在流形適應(yīng)核空間中執(zhí)行．很多主動(dòng)學(xué)習(xí)算法在建立本質(zhì)流形結(jié)構(gòu)并解釋其類別信息上不太理想[4]，本文所給的新算法能夠有效地解決這個(gè)問題．

1 背景知識(shí)

主動(dòng)學(xué)習(xí)最基本的目的：在歐氏空間Rm中給出一個(gè)數(shù)據(jù)集X={x1, x2,...,xn}，找出最具信息量的樣本子集Z=｛z1, z2,...,zk｝?X ，也就是說，如果給點(diǎn)zi( i=1,2,...,k )標(biāo)簽并將其用作訓(xùn)練點(diǎn)，它們應(yīng)該最能夠提高分類器的性能[4]．對(duì)于這個(gè)問題，一般做法是選擇最不確定的數(shù)據(jù)來訓(xùn)練模型或通過挖掘數(shù)據(jù)的聚類結(jié)構(gòu)來選擇最具代表性的點(diǎn)．

1.1 優(yōu)化實(shí)驗(yàn)設(shè)計(jì)與直推式實(shí)驗(yàn)設(shè)計(jì)

優(yōu)化實(shí)驗(yàn)設(shè)計(jì)（OED）[6]的研究與實(shí)驗(yàn)設(shè)計(jì)相關(guān)，它希望最小化參數(shù)模型的總體方差．基于優(yōu)化實(shí)驗(yàn)設(shè)計(jì)，人們提出直推式實(shí)驗(yàn)設(shè)計(jì)，在已標(biāo)簽和未標(biāo)簽樣本上評(píng)估期望預(yù)測(cè)誤差．相關(guān)研究表明最小化學(xué)習(xí)函數(shù)f的平均期望平方預(yù)測(cè)誤差是直推式實(shí)驗(yàn)設(shè)計(jì)最重要的部分．對(duì)于任何數(shù)據(jù)樣本x，y?=w?Tx是它的預(yù)測(cè)觀察函數(shù)，則在數(shù)據(jù)集X上的平均期望平方預(yù)測(cè)誤差可以寫成如下形式：

為了最小化平均期望平方預(yù)測(cè)誤差，需要找到一個(gè)能夠最小化（1）式的子集Z，能夠證明這是NP-hard問題，因此不可能找到全局優(yōu)化量．平均期望平方預(yù)測(cè)誤差的最小化形式也可以寫成如下：

（2）式獲得的結(jié)果是局部?jī)?yōu)化．通過輔助變量β=(β1,...,βn)引入訓(xùn)練數(shù)據(jù)集的內(nèi)在幾何關(guān)系，（2）中優(yōu)化問題可以等價(jià)地寫成如下形式：

這里α=(α,...,α)T，·表示l范數(shù)．l范數(shù)的最小化形式β可以產(chǎn)生稀疏向量β，也就

是說β的一些元素將會(huì)變?yōu)?；如果βj=0，則αi,j=0（i=1,...,n），否則目標(biāo)函數(shù)趨向無窮大，因此第j個(gè)樣本不能被選中．相關(guān)研究表明問題（3）是凸的，因此能夠獲得全局優(yōu)化量．

1.2 流形適應(yīng)實(shí)驗(yàn)設(shè)計(jì)

為了將流形結(jié)構(gòu)引入到主動(dòng)學(xué)習(xí)過程中，一般在流形適應(yīng)核空間里面執(zhí)行主動(dòng)學(xué)習(xí)任務(wù)．給出樣本x1,…,xn，令Kx=(K( x, x1),…,K( x, xn))，能夠知道可再生核是下面的形式：

其中I是單位矩陣，K是n×n核矩陣，滿足Ki,j=K( xi, xj)，M是正半定矩陣，常數(shù)λ≥0用來控制函數(shù)的平穩(wěn)性．（4）式中的關(guān)鍵問題是矩陣M的選擇，通過選擇基于拉普拉斯構(gòu)圖方法的矩陣M，MAED提出數(shù)據(jù)獨(dú)立核以及在流形適應(yīng)核空間里執(zhí)行凸直推式實(shí)驗(yàn)設(shè)計(jì)．令K( xi, xj)=φ(xi),φ(xj)，這里φ是特征映射．在Sindhwan等人提出的可再生希爾伯特核空間（RKHS）中，（3）中的凸TED優(yōu)化問題可以寫成如下形式：

這里φ(X)表示可再生核希爾伯特核空間里的數(shù)據(jù)矩陣，也就是說φ(X)=(φ(x1),...,φ(xn))．根據(jù)βj(j=1,...,n)以打亂次序的方式羅列數(shù)據(jù)樣本并選擇最近的k個(gè)點(diǎn)，當(dāng)選擇好最具信息的數(shù)據(jù)點(diǎn)后，任何分類算法都能夠被應(yīng)用到模式分類中去．顯然，MAED方法的表現(xiàn)主要取決于矩陣M的選擇．

2 半監(jiān)督拉普拉斯適應(yīng)實(shí)驗(yàn)設(shè)計(jì)

這部分具體本文的新算法．

2.1 以半監(jiān)督方式建立一個(gè)重構(gòu)圖G

1）在歐氏空間Rm中給出數(shù)據(jù)集X=｛x, x,...,x｝，對(duì)于任何已知類別的數(shù)據(jù)點(diǎn)x，首先

2）計(jì)算權(quán)值矩陣和重構(gòu)圖，權(quán)值矩陣W構(gòu)造方式如下：

這里權(quán)值Wij表示數(shù)據(jù)點(diǎn)xi的k近鄰樣本點(diǎn)xj對(duì)樣本點(diǎn)xi所做的貢獻(xiàn)．下面使用拉普拉斯構(gòu)圖方法來構(gòu)造重構(gòu)圖．在拉普拉斯構(gòu)圖方法中定義了這樣一個(gè)矩陣：L=D-W，這里D是一個(gè)滿足Dii=∑jWij的對(duì)角矩陣．對(duì)于數(shù)據(jù)集X=｛x1, x2,...,xn｝，令G=(X,L)為其重構(gòu)圖．

2.2 新主動(dòng)學(xué)習(xí)算法

應(yīng)用上面建立的圖G=(X,L)，本文的算法步驟可以總結(jié)如下：

輸入：在歐氏空間Rm中給出點(diǎn)集X=｛x1, x2,...,xn｝，這些點(diǎn)部分帶有類別標(biāo)簽信息．

1）以半監(jiān)督方式先建立一個(gè)如（6）式中的權(quán)值矩陣W，接著根據(jù)已求得的矩陣W以及拉普拉斯構(gòu)圖法構(gòu)造出重構(gòu)圖G=(X,L)；

2）由給出的核類型計(jì)算核矩陣K；

3）通過使用L來代替（4）式中的矩陣M，最終獲得如下流行適應(yīng)核：

4）令ui是核矩陣KM的第i列或者第i行向量（因KM是對(duì)稱的）．先令αi,j=1并迭代計(jì)算：

直到收斂；

5）數(shù)據(jù)選擇．當(dāng)?shù)玫溅耲(j=1,...,n)后，根據(jù)βj以打亂次序的方式羅列數(shù)據(jù)點(diǎn)并且選擇最近的k個(gè)數(shù)據(jù)點(diǎn)．

輸出：所有數(shù)據(jù)樣本根據(jù)其重要性重列，一但選擇好最具信息的數(shù)據(jù)點(diǎn)后，任何分類算法都可以應(yīng)用到模式識(shí)別任務(wù)中去．

與MAED算法相比，新主動(dòng)學(xué)習(xí)方法同樣也是基于流形假設(shè)，通過對(duì)所有數(shù)據(jù)點(diǎn)使用一個(gè)固定的k近鄰范圍來定義近鄰圖，不同之處在于本文的新算法以半監(jiān)督方式建立流形適應(yīng)核，在權(quán)值矩陣構(gòu)造方面，充分考慮到數(shù)據(jù)樣本的已知類別信息，這使得其具有更好的魯棒性．

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

在這部分，將對(duì)本文所提出的主動(dòng)學(xué)習(xí)方法（SSLAED）在3個(gè)真實(shí)數(shù)據(jù)集上的表現(xiàn)進(jìn)行評(píng)估，并與MAED、一近鄰（1-NN）、隨機(jī)樣本選擇（Random）這幾種分類方法進(jìn)行比較．其中1-NN方法知道訓(xùn)練樣本的所有類別標(biāo)簽并用訓(xùn)練數(shù)據(jù)集對(duì)測(cè)試集進(jìn)行分類；Random方法統(tǒng)一選擇樣本作為訓(xùn)練數(shù)據(jù)，本文使用這種方法作為主動(dòng)學(xué)習(xí)的基準(zhǔn)，所有主動(dòng)學(xué)習(xí)算法的效果至少要好于該基準(zhǔn)方法．

3.1 數(shù)據(jù)集描述

本文的實(shí)驗(yàn)在3個(gè)真實(shí)圖像數(shù)據(jù)集：CBCL、MNIST、USPS上進(jìn)行檢驗(yàn)和分析．

MIT CBCL[7]是一個(gè)非常著名的數(shù)據(jù)集，包含2 429張人臉圖片和4 548張非人臉圖片，每張圖片達(dá)到19×19分辨率并且被轉(zhuǎn)化成一個(gè)361維的向量．?dāng)?shù)據(jù)集包含兩種類型的數(shù)據(jù)點(diǎn)，人臉和非人臉的．

MNIST數(shù)據(jù)集（http://yann.lecun.com/exdb/mnist）是手寫數(shù)據(jù)集，包括60 000個(gè)訓(xùn)練樣本，10 000個(gè)測(cè)試樣本．

USPS數(shù)據(jù)集[8]包含數(shù)字類0到9的8位灰度級(jí)圖片，每類數(shù)字有1 100個(gè)數(shù)據(jù)點(diǎn)．這個(gè)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)是一張16×16像素的手寫數(shù)字圖片，并被轉(zhuǎn)化成一個(gè)256維的向量．

3.2 參數(shù)選擇和實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中進(jìn)行對(duì)比的算法的效果主要取決于參數(shù)的設(shè)置．MAED和SSLAED方法需要鄰域大小k作為設(shè)置的關(guān)鍵參數(shù)．實(shí)驗(yàn)表明，對(duì)于每個(gè)數(shù)據(jù)集，進(jìn)行對(duì)比算法的表現(xiàn)在大范圍鄰域內(nèi)是比較穩(wěn)定的．在本文的實(shí)驗(yàn)中，對(duì)SSLAED在所有數(shù)據(jù)集上其鄰域值k統(tǒng)一設(shè)置為5，被標(biāo)簽的訓(xùn)練數(shù)據(jù)比例α從0.1變化到0.9，并且固定參數(shù)β= 3．在下面的實(shí)驗(yàn)結(jié)果圖中，α的值采用十分制，例如圖中“2”、“4”、“6”、“8”數(shù)字分別表示0.2、0.4、0.6、0.8，也就是說，α= 2表示在數(shù)據(jù)集X中20%的數(shù)據(jù)是有標(biāo)簽的．

3.3 實(shí)驗(yàn)結(jié)果及分析

用隨機(jī)樣本方法和1近鄰方法作為基準(zhǔn)方法，在3個(gè)真實(shí)數(shù)據(jù)集上的分類結(jié)果如1、圖2、圖3所示．

圖1 數(shù)據(jù)集CBCL上的實(shí)驗(yàn)結(jié)果

圖2 數(shù)據(jù)集MNIST上的實(shí)驗(yàn)結(jié)果

如圖1、圖2、圖3所示，隨著標(biāo)簽數(shù)據(jù)的增多（圖中的α增大），分類準(zhǔn)確率逐漸變高．毫無疑問，SSLAED算法相比于MAED、Random方法在所有數(shù)據(jù)集上的表現(xiàn)要好，隨機(jī)樣本方法在大多數(shù)情況下表現(xiàn)得最差．下面對(duì)在3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果進(jìn)行具體的細(xì)節(jié)描述．

如圖1所示，在CBCL數(shù)據(jù)集上，SSLAED方法一直表現(xiàn)出遠(yuǎn)遠(yuǎn)超過MAED方法和Random方法的分類效果，隨著α的增加，當(dāng)它超過0.25時(shí)，SSLAED方法甚至能夠表現(xiàn)出比1-NN方法還要好的分類效果．值得注意的是，當(dāng)訓(xùn)練數(shù)據(jù)集較小時(shí)，SSLAED方法仍然能表現(xiàn)出較好的分類效果，特別是當(dāng)α= 0.1時(shí)，SSLAED方法的分類準(zhǔn)確率接近90%，實(shí)驗(yàn)出現(xiàn)這種結(jié)果可能是因?yàn)镾SLAED算法考慮到了部分標(biāo)簽數(shù)據(jù)的緣故．

圖3 數(shù)據(jù)集USPS上的實(shí)驗(yàn)結(jié)果

如圖2所示，在數(shù)據(jù)集MNIST中，多數(shù)情況下SSLAED方法比MAED方法的表現(xiàn)要好，而在整個(gè)范圍內(nèi)則一直比Random方法好．當(dāng)α≥0.6時(shí)，SSLAED不但比MAED和Random分類效果好而且有著高達(dá)98%以上的準(zhǔn)確率．當(dāng)訓(xùn)練樣本數(shù)據(jù)較小時(shí)，SSLAED與MAED一樣都能夠表現(xiàn)出較高的分類準(zhǔn)確率．例如，當(dāng)α= 0.1時(shí)，SSLAED有著高達(dá)97%的分類準(zhǔn)確率．

如圖3所示，在USPS數(shù)據(jù)集中SSLAED一直比MAED的分類效果好．相比于Random方法，除了α= 0.2以及α= 0.6這兩種情況，其它條件下SSLAED比Random分類準(zhǔn)確率都要高．特別是當(dāng)α＞0.8時(shí)，SSLAED分類準(zhǔn)確率高達(dá)96%以上，且超過了1-NN方法的分類準(zhǔn)確率．值得注意的是，當(dāng)訓(xùn)練數(shù)據(jù)較小時(shí)，SSLAED仍能表現(xiàn)出較好的分類效果，例如當(dāng)α= 0.1時(shí)，圖像的分類準(zhǔn)確率在88%以上．此外，當(dāng)0.1≤α≤0.5時(shí)，SSLAED對(duì)異常值不敏感．

以上已經(jīng)在CBCL，MNIST，USPS數(shù)據(jù)集上對(duì)4種算法做了對(duì)比，可以看出本文的新算法SSLAED在3種真實(shí)的數(shù)據(jù)集上效果顯著．這里有兩個(gè)原因可以解釋這點(diǎn)：首先，那些被應(yīng)用的數(shù)據(jù)集一直有部分標(biāo)簽樣本；其次，在每一類中有大量的數(shù)據(jù)點(diǎn)并且不同類別的數(shù)據(jù)相互重疊度較高．

4 小 結(jié)

本文通過在流形適應(yīng)核空間里執(zhí)行主動(dòng)學(xué)習(xí)任務(wù)，改變權(quán)值矩陣的構(gòu)造，為圖像分類提出了一種新的主動(dòng)學(xué)習(xí)算法．在3個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示了本文所給的算法比MAED、Random方法要好，特別是當(dāng)只有一小部分樣本被標(biāo)簽的情況．

[1] 張學(xué)工. 模式識(shí)別[M]. 第3版. 北京: 清華大學(xué)出版社, 2010: 1-6

[2] Tong S, Koller D. Support vector machine active learning with application to text classification [J]. Machine Learning Research, 2001, 2: 45-66.

[3] Tenenbaum J B, Silva V D, Langford J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science, 2000, 290(5500): 2319-2323.

[4] Cai D, He X F. Manifold adaptive experimental design for text categorization [J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(4): 707-719.

[5] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: a geometric framework for learning from examples [J]. Machine Learning Research, 2004, 7: 2399-2434.

[6] Atkinson A C, Donev A N, Tobias R D. Optimum experimental design, with SAS [M]. Oxford：Oxford University Press, 2007: 184-191.

[7] MIT center for biological and computation learning. CBCL face database [EB/OR]. [2012-10-02]. http://www. ai.mit.edu/projects/cbcl.

[8] Hull J J. A database for handwritten text recognition research [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence [J]. 1998, 16(5): 550-554.

On Image Classification Based on Semi-supervised Laplacian Adaptive Experimental Design

XIONG Xingliang, FAN Mingyu, HONG Zhenjie
(College of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035)

The paper puts forward a new active learning algorithm based on the theory of manifold learning by changing the setting of weights and incorporating class information into the process of graph construction. The experimental result via 3 real-world image datasets demonstrates that the new algorithm is in a position to achieve much better image classification effect.

Active Learning; Manifold Learning; Image Classification

TP391.41

A

1674-3563(2015)01-0011-06

10.3875/j.issn.1674-3563.2015.01.003 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：王一芳)

2014-02-27

熊興良(1983- )，男，湖北黃岡人，碩士研究生，研究方向：應(yīng)用分析與最優(yōu)化理論．? 通訊作者，hong@wzu.edu.cn