基于邊緣Fisher分析的主動(dòng)學(xué)習(xí)方法

李慧思，洪振杰

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

基于邊緣Fisher分析的主動(dòng)學(xué)習(xí)方法

李慧思，洪振杰?

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

將邊緣Fisher分析引入到MAED算法中，通過構(gòu)建類內(nèi)緊湊圖和類間分離圖，來描述樣本點(diǎn)間的幾何特征，形成一種新的主動(dòng)學(xué)習(xí)方法．該算法利用兩個(gè)圖同時(shí)對流形數(shù)據(jù)局部結(jié)構(gòu)和類鑒別信息進(jìn)行建模，從而更好地保持了數(shù)據(jù)的內(nèi)在幾何特征．基于圖像數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，證實(shí)了該方法的有效性．

邊緣Fisher分析；類內(nèi)緊湊圖；類間分離圖；主動(dòng)學(xué)習(xí)；圖像分類

在信息處理任務(wù)中，圖像分類是一項(xiàng)很重要的工作．很多有監(jiān)督圖像分類系統(tǒng)都是建立在統(tǒng)計(jì)模型的基礎(chǔ)上，首先用戶需要手動(dòng)標(biāo)注大量的圖像樣本點(diǎn)，然后根據(jù)這些帶標(biāo)簽的樣本點(diǎn)訓(xùn)練出一個(gè)分類模型．在實(shí)際運(yùn)用中，標(biāo)注這些圖像樣本點(diǎn)往往需要花費(fèi)大量的人力物力，因此分類系統(tǒng)很難獲得足夠的帶標(biāo)簽的樣本進(jìn)行訓(xùn)練．在訓(xùn)練樣本很少的情況下，分類器的性能可能會(huì)產(chǎn)生極大的惡化．如何獲得整個(gè)數(shù)據(jù)集里最具代表性的一個(gè)子集，使得在注釋圖像樣本上花費(fèi)最少精力，并訓(xùn)練出一個(gè)好的分類器，成為圖像分類任務(wù)中的一個(gè)關(guān)鍵問題．為了解決這個(gè)問題，主動(dòng)學(xué)習(xí)已經(jīng)成為機(jī)器學(xué)習(xí)和模式識(shí)別里的一個(gè)研究熱點(diǎn)．

目前，研究人員已經(jīng)做了很多主動(dòng)學(xué)習(xí)的研究，比如支持向量機(jī)主動(dòng)學(xué)習(xí)（Support Vector Machine active learning, SVMactive）[1]和直推式實(shí)驗(yàn)設(shè)計(jì)（Transductive Experimental Design, TED）算法①Yu K, Bi J B, Tresp V. Active learning via transductive experimental design [C] // Proc. 23rd international conference on Machine learning (ICML’ 06). New York, 2006: 1081-1088.，然而這些方法都沒有把數(shù)據(jù)樣本點(diǎn)的幾何結(jié)構(gòu)考慮進(jìn)去．蔡登等人[2]基于TED算法提出了一種新的主動(dòng)學(xué)習(xí)算法用于文本分類，稱為流形適應(yīng)性實(shí)驗(yàn)設(shè)計(jì)算法（Manifold Adaptive Experimental Design，MAED）．這種算法在流形適應(yīng)性核空間中進(jìn)行主動(dòng)學(xué)習(xí)，充分考慮了數(shù)據(jù)間的內(nèi)在流形結(jié)構(gòu)．

圖形是用于數(shù)據(jù)挖掘和模式識(shí)別的一項(xiàng)強(qiáng)大的工具，而基于圖方法的性能在很大程度上依賴于構(gòu)造圖的質(zhì)量．MAED算法需要一個(gè)固定鄰居的大小來構(gòu)造一個(gè)鄰接圖，因此鄰居的大小很大程度上影響了MAED算法的效果．

在本文中，我們將邊緣Fisher分析（Marginal Fisher Analysis, MFA）[3-4]引入到MAED算法中，通過構(gòu)建類內(nèi)緊湊圖和類間分離圖，來更好地描述樣本點(diǎn)之間的幾何特征，從而形成一種新穎的主動(dòng)學(xué)習(xí)方法．這種新的算法利用兩個(gè)圖來同時(shí)對流形數(shù)據(jù)的局部結(jié)構(gòu)和類鑒別信息進(jìn)行建模，從而更好地保持?jǐn)?shù)據(jù)的內(nèi)在幾何特征．

1 相關(guān)研究

1.1 邊緣Fisher分析（MFA）

最近，Yan等人在圖嵌入框架的基礎(chǔ)上提出了一種新的流形學(xué)習(xí)算法——邊緣Fisher分析（MFA）[5]．該算法利用樣本的類別信息以及樣本之間的歐氏距離來構(gòu)建類內(nèi)緊湊圖和類間分離圖，進(jìn)而分別描述同類樣本之間的連接性和異類樣本之間的分離性．將樣本數(shù)據(jù)投影到低維空間后，使得同類的1k近鄰樣本之間的距離盡可能小，不同類別的2k近鄰樣本之間的距離盡可能大．MFA的關(guān)鍵算法步驟如下[6]：

在類內(nèi)緊湊圖中，cS用來描述兩點(diǎn)之間的連接性，定義為：

1.2 最優(yōu)化實(shí)驗(yàn)設(shè)計(jì)（OED）和直推式實(shí)驗(yàn)設(shè)計(jì)（TED）

在統(tǒng)計(jì)學(xué)里，主動(dòng)學(xué)習(xí)又被稱為實(shí)驗(yàn)設(shè)計(jì)．最優(yōu)化實(shí)驗(yàn)設(shè)計(jì)（OED）[7]是為了減少方差參數(shù)化的模型．基于OED研究，Yu等提出了TED算法①Yu K, Zhu S H , Xu W, et al. Non-greedy active learning for text categorization using convex transductive experimental design [C] // Proc. 31st Ann. Int’ l ACM SIGIR conf. research and development in information retrieval (SIGIR’ 08). New York, 2008: 635-642.，這種算法旨在最小化學(xué)習(xí)函數(shù)f的預(yù)期平方誤差．

對任意的樣本x，假設(shè)??wTy x=是它的預(yù)測值．則整個(gè)數(shù)據(jù)集X的平均預(yù)測誤差就是：

1.3 MAED算法：

在這里I是一個(gè)單位矩陣，K是核矩陣，M是一個(gè)半正定矩陣，0λ≥是調(diào)節(jié)函數(shù)光滑度的一個(gè)常數(shù)．

2 基于MFA與MAED算法的主動(dòng)學(xué)習(xí)

在MFA算法與MAED算法基礎(chǔ)上，我們提出一種新穎的主動(dòng)學(xué)習(xí)方法，稱之為邊緣實(shí)驗(yàn)設(shè)計(jì)（Fisher Experimental Design, FED）．這種算法通過構(gòu)建類內(nèi)緊湊圖和類間分離圖，來更好地描述樣本點(diǎn)之間的幾何特征，從而形成一種新穎的主動(dòng)學(xué)習(xí)方法．

2.1 基于MFA的權(quán)重矩陣

MAED算法的性能依賴于權(quán)重矩陣M的定義，由此，基于數(shù)據(jù)的范數(shù)誘導(dǎo)核的變形，反映了數(shù)據(jù)點(diǎn)的本質(zhì)幾何特性．圖中權(quán)重矩陣的選擇有很多，而且不同的圖產(chǎn)生不同的權(quán)重矩陣．

基于減式MFA的新的權(quán)重矩陣算法步驟如下：

首先，構(gòu)造類內(nèi)緊湊圖和類間分離圖[4]．設(shè)給定n個(gè)數(shù)據(jù)集其中，是高維數(shù)據(jù)．設(shè)G和PG分別表示2個(gè)具有n個(gè)頂點(diǎn)的無向圖：類內(nèi)緊湊圖和類間分離圖，其中，頂點(diǎn)i對應(yīng)于樣本數(shù)據(jù)點(diǎn)ix．

在類內(nèi)緊湊圖G中，對于任意數(shù)據(jù)點(diǎn)ix，如果ix和jx具有相同的類別，且滿足jx是ix的1k-最近鄰居，則在數(shù)據(jù)點(diǎn)ix和jx之間創(chuàng)建一條邊．

此權(quán)重矩陣?yán)脙蓚€(gè)圖（即類內(nèi)緊湊圖和類間分離圖）來同時(shí)對流形數(shù)據(jù)的局部結(jié)構(gòu)和類別信息進(jìn)行建模，對數(shù)據(jù)的幾何流形有著更為精確地描述．同時(shí)，基于目標(biāo)函數(shù)為減式的權(quán)重矩陣又可以避免奇異性帶來的困擾，減少計(jì)算難度．

2.2 基于MFA的主動(dòng)學(xué)習(xí)算法

輸出：依據(jù)樣本點(diǎn)重要性排列的樣本點(diǎn)的新順序．

相比于MAED算法，我們提出的主動(dòng)學(xué)習(xí)算法有著突出的優(yōu)勢：基于目標(biāo)函數(shù)為減式的MFA，通過構(gòu)建的類內(nèi)緊湊圖和類間分離圖來確定新的權(quán)重矩陣，此權(quán)重矩陣不僅能更精確地描述數(shù)據(jù)之間的幾何流形特征，還能避免奇異性帶來的困擾，減少計(jì)算難度．

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

將在四個(gè)基準(zhǔn)圖像數(shù)據(jù)集上進(jìn)行試驗(yàn)，這些數(shù)據(jù)集分別是美銀證券數(shù)據(jù)集（BANC）[10]，智能交通系統(tǒng)（ITS）數(shù)據(jù)集[11]，ORL數(shù)據(jù)集[12]和美國郵政總局的手寫數(shù)字?jǐn)?shù)據(jù)集USPS[13]．

3.1 數(shù)據(jù)集描述和實(shí)驗(yàn)設(shè)置

BANCA人臉數(shù)據(jù)集包含了52個(gè)人臉的520幅圖像（每個(gè)人有10幅圖像）．?dāng)?shù)據(jù)集里的所有圖像都被人為地規(guī)范化為46×56像素．

ORL數(shù)據(jù)集包括40個(gè)人的400幅圖像，其中每個(gè)人有10個(gè)不同的圖像．這個(gè)數(shù)據(jù)集里的每幅圖像都被裁剪成32×18像素的．

USPS數(shù)據(jù)集里的圖像均是8位灰度圖像，這些圖像的類別從0 – 9，每個(gè)類別有1 100個(gè)數(shù)據(jù)點(diǎn)．這個(gè)數(shù)據(jù)集里的每個(gè)數(shù)據(jù)點(diǎn)都是一個(gè)16×16的形象手寫數(shù)字，然后被轉(zhuǎn)換成一個(gè)256維的向量．我們隨機(jī)地從每類里面挑選250個(gè)數(shù)據(jù)點(diǎn)．因此，USPS數(shù)據(jù)集包含了10個(gè)類別的2 500個(gè)數(shù)據(jù)點(diǎn)．

ITS數(shù)據(jù)集包含了分屬兩個(gè)類別的2 000幅圖像．其中1 000幅圖像是關(guān)于人類行走或者跑步的，另外1 000幅圖像則是關(guān)于一個(gè)常見場景圖像道路而沒有人類活動(dòng)．每個(gè)數(shù)據(jù)點(diǎn)都是一張被裁剪成32×16的灰度圖像，然后又被轉(zhuǎn)換成一個(gè)512維的向量．

在實(shí)驗(yàn)中，利用10-折交叉驗(yàn)證法進(jìn)行評估比較計(jì)算．給定一個(gè)數(shù)據(jù)集，把它隨機(jī)分割成10個(gè)大小相等的子集．對于第k個(gè)子集，其它9個(gè)子集是作為訓(xùn)練集trainX，且第k個(gè)子集是用作測試數(shù)據(jù)testX．

將FED算法與1-最近鄰算法（1-NN）、隨機(jī)樣本法和MAED算法進(jìn)行比較．對于MAED和FED算法，根據(jù)訓(xùn)練集trainX中每個(gè)樣本點(diǎn)的重要性進(jìn)行排序．然后選擇訓(xùn)練數(shù)據(jù)集里一個(gè)給定的部分（0.α），并且假設(shè)它們的類別標(biāo)簽都是已知的，其中α從1到9進(jìn)行變化．最后，這些挑選的帶標(biāo)簽的訓(xùn)練數(shù)據(jù)被用作訓(xùn)練1-NN分類器，訓(xùn)練出的分類器用于對測試集testX進(jìn)行分類．隨機(jī)樣本法，就是隨機(jī)地在所選擇的訓(xùn)練數(shù)據(jù)集里挑選一個(gè)給定的部分（0.α），并且假設(shè)它們的類別標(biāo)簽都是已知的，我們就用這種方法作為主動(dòng)學(xué)習(xí)的基準(zhǔn)．1-NN算法知道所有訓(xùn)練集trainX的類別標(biāo)簽，然后利用訓(xùn)練集trainX對測試集testX進(jìn)行訓(xùn)練．

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

圖1 – 4中給出了四個(gè)數(shù)據(jù)集中四種主動(dòng)學(xué)習(xí)算法的平均準(zhǔn)確率．

根據(jù)圖1中所示，可以看出在BANC數(shù)據(jù)集中，當(dāng)2α≤時(shí)，F(xiàn)ED、MAED和1-最近鄰算法有著很相近的分類結(jié)果；當(dāng)3α≥時(shí)，F(xiàn)ED算法比MAED算法分類效果好，同時(shí)，MAED算法又比隨機(jī)樣本法優(yōu)秀．

圖2中給出了數(shù)據(jù)集ORL中四種算法的分類準(zhǔn)確率．可以看出，當(dāng)2α＜和8α＞時(shí)，F(xiàn)ED的分類準(zhǔn)確率非常貼近于MAED算法．特別地，當(dāng)5α=時(shí)， FED算法明顯優(yōu)越于MAED．在所有的算法中，隨機(jī)樣本法的分類準(zhǔn)確率是最低的．

圖3中所示的USPS數(shù)據(jù)集中，在8α＜時(shí)，F(xiàn)ED算法顯然優(yōu)于MAED算法，并且MAED算法在6α＜時(shí)比隨機(jī)樣本法優(yōu)秀，之后卻表現(xiàn)得比隨機(jī)樣本法差．

圖4所示的ITS數(shù)據(jù)集中，F(xiàn)ED算法優(yōu)秀于其他兩種算法．尤其當(dāng)6α=時(shí)，F(xiàn)ED算法的分類準(zhǔn)確率比MAED高出約3個(gè)百分點(diǎn)．

總的來說，1-最近鄰算法在所有的數(shù)據(jù)集中分類效果是最優(yōu)的，這正是由于在1-最近鄰算法中所有數(shù)據(jù)點(diǎn)都是帶標(biāo)簽的．

4 小 結(jié)

通過構(gòu)建類內(nèi)緊湊圖和類間分離圖來確定新的權(quán)重矩陣，此權(quán)重矩陣不僅可以避免奇異性帶來的困擾，更能精確地對數(shù)據(jù)的幾何流形結(jié)構(gòu)進(jìn)行描述，從而提升主動(dòng)學(xué)習(xí)的效率．我們提出的FED算法優(yōu)點(diǎn)在于：（1）建立了更加適應(yīng)數(shù)據(jù)集幾何結(jié)構(gòu)的圖；（2）新建的類內(nèi)緊湊圖和類間分離圖有很強(qiáng)的區(qū)分性，利于選擇重要的樣本點(diǎn)．實(shí)驗(yàn)證明FED算法在圖像數(shù)據(jù)集ORL、ITS、USPS和BANC上顯示出了很好的分類效果．

圖1 BANC數(shù)據(jù)集上的分類準(zhǔn)確率

圖3 USPS數(shù)據(jù)集上的分類準(zhǔn)確率

圖2 ORL數(shù)據(jù)集上的分類準(zhǔn)確率

圖4 ITS數(shù)據(jù)集上的分類準(zhǔn)確率

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

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

[3] 朱振鳳, 范麗亞. 基于間隔Fisher分析的幾種改進(jìn)算法[J]. 聊城大學(xué)學(xué)報(bào): 自然科學(xué)版, 2012, 25(4): 5-10.

[4] 李森, 劉希玉. MFASSC: 基于間隔Fisher分析的半監(jiān)督聚類方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(11): 4093-4096.

[5] Yan S C, Xu D, Zhang B Y, et al. Graph embedding and extension: a general framework for dimensionality reduction [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51.

[6] 黃可坤. 基于正則化邊界Fisher分析和稀疏表示分類的人臉識(shí)別方法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(6): 1723-1726.

[7] Atkinson A C, Donev A N. Optimum experimental designs, with SAS [M]. Oxford: Oxford Univ. Press, 2007: 23-30.

[8] Chung F R K. Spectral graph theory [M]. Providence, Rhode Island: American Mathematical Society, 1997: 2-14.

[9] Hastie T, Tibshirani R, Friedman J. The elements of statistical learning: data m ining, inference, and prediction [J]. The mathematical Inteligencer, 2005, 27(2): 83-85.

[10] Kim T K, Stenger B, Kittler J, et al. Incremental linear discriminant analysis using sufficient spanning sets and its applications [J]. International Journal of Computer Vision, 2011, 91(2): 216-232.

[11] Cao X B, Qiao H, Keane J. A low-cost pedestrian-detection system with a single optical camera [J]. IEEE Trans. on Intelligent Transportation Systems, 2008, 9(1): 58-67.

[12] Olivetti & Oracle Research Laboratory. The olivetti & oracle research laboratory face database of faces [EB/OL]. [2013-05-01]. http://www.camorl.co.uk/facedatabase.htm l.

[13] Hull J. A database for handw ritten text recognition research [J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 1998, 16(5): 550-554.

On Active Learning Method Based on the Margin Fisher Analysis

LI Huisi, HONG Zhenjie
(School of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035)

In this paper, a new active learning method is put forward by leading margin Fisher Analysis into MAED algorithm, and describing the geometric structure of samples with constructing within-class compact and inter-class separate graphs. This algorithm uses two graphs modeling the local structure of the manifold data and discrim ination information of the dataset simultaneously, which can keep the intrinsic geometric structure of the data better. This method is proved effectively based on the experimental results of the image data set.

Margin Fisher Analysis; Within-class Compact Graph; Inter-class Separate Graph; Active Learning; Image Classification

TP391.41

：A

：1674-3563(2014)03-0055-08

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

(編輯：封毅)

2014-01-06

溫州大學(xué)研究生創(chuàng)新基金(31606036010184)

李慧思(1989- )，女，河南濮陽人，碩士研究生，研究方向：應(yīng)用分析與最優(yōu)化理論．? 通訊作者：hong@wzu.edu.cn