半監督有局部差異的圖嵌入算法*

梁興柱， 林玉娥， 林玉榮

(1.安徽理工大學 計算機科學與工程學院, 安徽 淮南 232011；2.哈爾濱工業大學 航天學院，黑龍江 哈爾濱 150001)

0 引 言

對于人臉識別任務，如何將高維的數據樣本降成一個低維的樣本是取得良好識別結果的關鍵一步，這就需要相應的特征提取算法，目前主要包括二大類特征提取算法，一類是屬于無監督的算法，如主成分分析(PCA)[1]和局部保持投影(LPP)[2]算法；另一類是有監督算法，如線性判別分析(LDA)[1]。通常在人臉識別任務中，當標注類別的樣本充足時，有監督算法能夠獲得更好的識別結果。而其中的LPP算法雖然也是無監督算法，但從理論上講較PCA算法更適合分類，并且也比較容易擴展成為有監督算法，因此，該算法一經提出就受到了廣泛的關注。如文獻[3]提出的有監督LPP，通過利用樣本標簽來提高算法的識別性能；但是LPP在保持圖像之間的局部結構時，使得鄰域內的樣本投影后比較接近，當鄰域內的樣本過于接近時，容易造成鄰域內樣本之間的差異信息丟失，即過學習問題，使得分類性能不夠好，因此,文獻[4]則結合信息理論，提出了有監督局部差異投影(SLSDP)算法，并取得了較好的識別結果。

雖然有監督算法能夠獲得較好的識別性能，但是在現實問題中，更多時候能夠獲得大量樣本，而有類別標簽的樣本卻是少量的，因此，半監督學習算法運用而生。這類算法的目標就是充分利用這些有標簽和無標簽的數據樣本來增加分類精確度。如文獻[5]對LDA擴展提出的半監督判別分析(SDA),但是該算法沒有用到樣本的局部信息，因此，文獻[6]和文獻[7]分別提出了利用局部信息的半監督算法，但這種只強調局部信息，容易出現過學習問題，且其目標函數存在著小樣本問題。本文受文獻[4]啟發，提出了一種半監督有局部差異的圖嵌入算法(SLDGEA)。SLDGEA同時考慮使用有標簽樣本和無標簽樣本，在最小化訓練樣本近鄰相似散度的同時，最大化訓練樣本近鄰差異散度，對于兩部分樣本所起作用的大小，可通過參數來調整。最后人臉庫上的實驗結果表明了該算法的有效性。

1 相關算法介紹

1.1 局部保持投影算法

假設X=[x1…xi…xN]表示全體訓練樣本集，N表示樣本數目，n表示樣本的維數，LPP算法的思想是使得樣本降維后在低維空間里盡可能地保持原來的鄰近關系。設G={X,S}為無向有權圖，每個樣本點xi為圖中的一個頂點，S為相似度矩陣，Sij表示樣本i和j的相似度可按下式計算

(1)

其目標是最小化下式

trWTXLXTW,

(2)

(3)

上述近鄰關系是按式(1)來確定的，屬于無監督算法，當式(1)中的權值Sij加入訓練樣本的類別信息，則上面的就有監督算法，有監督算法的Sij計算公式如下

Sij=

(4)

式(3)即是LPP算法的目標函數，同時式(3)也提供了一個統一的線性圖嵌入框架，可以通過選擇不同的L和D，得到不同的線性特征提取算法，如LPP,UDP和MFA，以及SLSDP算法。

1.2 SLSDP算法

無論是LPP還是有監督的LPP算法，都僅強調了保持圖像之間的局部結構，從而將造成鄰域內樣本之間的差異信息丟失，即過學習問題，從而將使算法性能下降，SLSDP則解決了這一問題。修改上述圖嵌入算法框架相應的L和D，則有SLSDP算法的目標函數，其意義是使得所求的W能夠有效地保持了圖像空間的局部結構的同時，最大化訓練樣本的近鄰差異信息，即

(5)

上式中的近鄰系數Sij根據式(4) 計算，差異系數Bij由下式計算

(6)

詳細求解可參見文獻[4]。

2 SLDGEA

本文所提出的算法實際上是對圖嵌入算法框架的擴展，故此稱之為SLDGEA，其思想是充分利有標簽和無標簽的訓練樣本來構造目標函數，從而使得求出的投影矩陣更有效，達到提高分類效果的目標。首先給出SLDGEA的目標函數。

假設有樣本X，其前N個數據樣本為有類別標簽的,后M個點是不帶類別標簽，X={XN,XM}={x1,…,xN,xN+1,…,xN+M}，本文算法就是利用這兩部分樣本來構造目標函數，其意義是要保證在低維子空間中保持原有樣本的近鄰結構，同時保證樣本的差異性，因此,要求所求的基向量w應同時滿足

w=arg minwTGLw,

(7)

w=arg maxwTGBw,

(8)

式中GL=XLSXT稱之為近鄰相似散度矩陣，GB=XLBXT稱為近鄰差異散度矩陣，考慮到樣本部分有標簽，部分無標簽，因此,wTGLw和wTGBw又要分解成如下形式

wTGLw=wTGL1w+αwTGL2w,

(9)

wTGBw=wTGB1w+βwTGB2w.

(10)

式(9)和式(10)的右邊第一部分GL1和GB1是利用有標簽樣本計算出來的，第二部分GL2和GB2是利用無標簽樣本計算出來的，α,β∈[0,1]是調節因子，用來控制無標簽樣本在目標函數中所起作用的大小，對于式(7)和式(8)可以寫成一式，因此，綜合式(7)和式(8)，加上正交約束條件，可得到SLDGEA的目標函數，而為了避免已有半監督算法的小樣本問題，這里采用差形式的目標函數，即

(11)

對于上式的求解，根據Lagrange乘子法構造函數

(12)

(GB-GL)wi=λiwi,i=1,2,…,l.

(13)

最后選擇對應前d(通常d

3 實驗結果與討論

本文為了驗證提出SLDGEA的性能，分別在ORL (http:∥www.cl.cam.ac.uk/ research/dtg/attarchive/facedatabase.html)和UMIST (http:∥images.ee.umist.ac.uk/danny/database.html)人臉庫上進行了實驗。采用最近鄰算法進行分類。ORL人臉庫是由劍橋大學AT&T實驗室創建的，有40個人的400幅圖像，每人10幅，每幅圖像尺寸為112×92。UMIST 人臉庫是由英國曼徹斯特大學創建的，包括20人的共564幅圖像，每人19～48幅不等，由于該庫人臉樣本數目不等，因此,實驗中選用UMIST 的子庫進行分析。該子庫由20人組成，每個人含有15張不同姿勢的照片，共300張，每幅圖像尺寸為112×92。

將本文SLDGEA與經典SDA[5]和SLDA[6]在提取不同特征數目下識別性能進行了比較,分別選擇ORL和UMIST人臉庫前5幅圖像作為訓練樣本，剩余作為測試樣本，對于SLDGEA的參數設置α=0.5，β=0.5，對于有類別的近鄰定為ss=2～7(ss表示不同有標簽訓練樣本數目，如表1和表2中)，無標簽樣本的近鄰定為5。對于3種算法，無標簽樣本數目，統一定為每類3個，3種算法提取的最大特征數目為C(與樣本類別數目一致)個，實驗結果如圖1和圖2所示。本文進一步在2個人臉庫上，每人隨機選擇T幅圖像作為訓練樣本，T的取值分別為2～6(ORL)和3～7(UMIST，由于該人臉庫每類樣本數目較多，故開始測試時多選一個)，剩余圖像作為測試樣本。取10次平均識別結果作為每種算法的識別結果，實驗結果如表1與表2所示。

圖1 ORL人臉庫識別率隨特征數目變化的結果

圖2 UMIST人臉庫識別率隨特征數目變化的結果

圖1和圖2的結果表明了3種算法隨著提取特征數目變化其相應識別性能的變化趨勢。SLDGEA在2個人臉庫上都取得了優于SLDA和SDA的識別結果，在大約與樣本類別一致的特征數目時取得了較穩定的識別結果。這說明本文算法，即在保持局部結構的同時，保持樣本的差異性所提取的特征是有效的。另外,也可看出，3種算法的識別率并不是一直在增加，有時會出現一些小的波動，但在大約靠近C個特征數目時，都達到了較穩定的識別結果。

表1 ORL人臉庫的識別結果

表2 UMIST人臉庫上的識別結果

表1和表2的結果進一步表明：本文提出的半監督算法在保持局部結構的同時，考慮保持樣本的差異性是有效的、可行的，明顯優于另外2種方法。在每類樣本數目少的ORL上時，當有3個標注標簽的樣本即可取得較好的效果，在UMIST上，在4個樣本時可取得較理想的效果。

4 結束語

本文結合局部差異算法，提出了一種SLDGEA。該算法的特點是能夠同時利用有標簽和無標簽樣本，同時能夠保持圖像之間的差異信息，能夠避免過學習問題。另外，SLDGEA有效地解決了小樣本問題，這是因為其采用了差形式的目標函數，因此,無需對矩陣進行求逆計算。實驗結果表明了該方法的有效性,在具有較少的標注樣本時，SLDGEA也能取得較滿意的結果，更適合現實的應用。和已有的經典算法相比，其識別率也有顯著的提高，在ORL人臉庫上5個訓練樣本時，其識別率提高了2.25 %，在UMIST人臉庫上6個訓練樣本時,其識別率提高了2.23 %。

參考文獻:

[1] Belhumeur P N ,Hespanha J P ,Kriegam D J.Eigenfacesvs.fisherfaces:Recognition using class specific linear projec-tion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(7):711-720.

[2] He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacianfaces [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[3] Zhang H,Sun S,Jing Z,et al.Local structure based supervised feature extraction[J].Pattern Recognition,2006,39(8):1546-1550.

[4] 高全學,謝德燕,徐 輝,等.融合局部結構和差異信息的監督特征提取算法[J].自動化學報,2010,36(8):1107-1114.

[5] Cai Deng,He Xiaofei,Han Jiawei.Semi-supervised discriminant analysis[C]∥Proc of IEEE International Conference on Compu-ter Vision,Rio de Janeiro,Brazil,2007.

[6] 姜 偉,楊炳儒.半監督局部判別分析[J].計算機工程,2011,37(8):153-154,157.

[7] 談 銳，陳秀宏.半監督的局部保留投影降維方法[J].計算機工程,2012,38(6):181-183.