梁志貞 張 磊

如今利用現(xiàn)代設(shè)備采集高維數(shù)據(jù)變得方便和容 易,但是獲得的高維數(shù)據(jù)可能包含不相關(guān)和冗余的信息.這不僅增加了學(xué)習(xí)模型的計算量和存儲量,而且可能導(dǎo)致學(xué)習(xí)模型的性能下降.為了解決這些問題,線性降維[1-4]通常用于從數(shù)據(jù)中提取重要和有用的信息.線性降維的目的是通過優(yōu)化一些準(zhǔn)則函數(shù)對原始特征空間進(jìn)行適當(dāng)?shù)木€性變換.主成分分析(Principal component analysis,PCA)和線性判別分析(Linear discriminant analysis,LDA)是兩種流行的線性降維方法.由于PCA 和LDA 的簡單性和有效性,它們已經(jīng)被廣泛應(yīng)用于許多領(lǐng)域,如人臉識別[5]、手寫體字符識別[6]和缺陷診斷[7]等.

當(dāng)樣本的類別信息可用時,通常情況下LDA在提取數(shù)據(jù)的鑒別特征方面比PCA 更有效.線性判別分析的目標(biāo)是在變換空間中通過最大化類間距離和最小化類內(nèi)距離來尋找投影矩陣.從概率的觀點(diǎn)來看,假設(shè)每類樣本服從高斯分布且具有不同的類中心以及相同的協(xié)方差,則從Bayes 最優(yōu)準(zhǔn)則可推導(dǎo)出LDA.

為了改善線性判別分析的特征提取性能,各種LDA 的改進(jìn)算法[8-10]已經(jīng)被提出.使用最優(yōu)向量替換各類中心[8]能提高LDA 的類信息鑒別能力.分?jǐn)?shù)階的LDA[11]通過在一系列分?jǐn)?shù)階中引入加權(quán)函數(shù)來改善LDA,但這增加了獲得投影向量的代價.與Bayes 錯誤率相關(guān)的近似成對精度準(zhǔn)則[12]在原空間計算各類的權(quán)重,從而改善LDA 的性能.幾何平均[13],調(diào)和平均[14]以及加權(quán)調(diào)和平均[15]被用來定義判別分析的準(zhǔn)則函數(shù).最不利情況下的線性判別分析[16]考慮了最近的兩個類中心和具有最大方差的類來尋找投影方向.基于最大-最小距離的目標(biāo)函數(shù)[17]探索了最近的數(shù)據(jù)對的性質(zhì)來取得投影方向.Wasserstein 判別分析[18]利用正則化Wasserstein 距離獲取類之間的全局和局部信息并優(yōu)化目標(biāo)函數(shù)取得最佳投影方向.

線性判別分析存在小樣本的奇異性[19]以及非線性數(shù)據(jù)特征提取[20-21]等問題.為了克服LDA 的小樣本奇異性問題,典型的方法包括PCA+LDA,正則化LDA,偽逆LDA 以及張量判別分析[22]等.為了有效地處理非線性數(shù)據(jù),各種線性判別分析已被拓寬到基于核函數(shù)的判別分析[7,20-21].當(dāng)訓(xùn)練集隨著新數(shù)據(jù)的加入而變化時或處理的數(shù)據(jù)量大時,各種增量學(xué)習(xí)[23-24]或在線學(xué)習(xí)方式被用來獲得鑒別分析的投影方向.文獻(xiàn)[24] 提出了兩種形式的增量LDA :序列增量LDA 和塊增量LDA,它們能有效地獲取大數(shù)據(jù)流的特征空間.

數(shù)據(jù)在采集或傳輸過程中可能受到污染,這使得處理的數(shù)據(jù)包含噪聲或離群點(diǎn).但經(jīng)典線性判別分析對噪聲數(shù)據(jù)具有敏感性,即獲得的投影方向偏離真正的投影方向.為了降低LDA 對噪聲數(shù)據(jù)的敏感性,許多工作致力于用魯棒的目標(biāo)函數(shù)替換LDA的原有目標(biāo)函數(shù)[25-26].已有的諸多研究發(fā)現(xiàn),基于L1范數(shù)的目標(biāo)函數(shù)比基于L2范數(shù)的目標(biāo)函數(shù)在抑制異常點(diǎn)或噪聲方面更有效[27-29].因此基于L1范數(shù)的判別分析方法近年來備受關(guān)注.L1范數(shù)的LDA[28]的類內(nèi)距離和類間距離的定義依賴于L1范數(shù),這在某種程度上能抑制噪聲.L1范數(shù)的核LDA 不僅能抑制噪聲,而且能捕捉數(shù)據(jù)的非線性鑒別特征[28].L1范數(shù)的兩維LDA[30]拓寬了L1范數(shù)的LDA,這種方法可直接處理圖像數(shù)據(jù),而不需要把圖像轉(zhuǎn)化為向量形式.通常L1范數(shù)的判別分析通過貪婪算法獲取多個投影方向,而非貪婪迭代算法[31]被用來直接獲取L1范數(shù)的LDA 的多個投影向量.廣義彈性網(wǎng)[32]通過Lp范數(shù)定義的目標(biāo)函數(shù)來改善判別分析抑制噪聲的能力,而通過優(yōu)化Bhattacharyya 的L1范數(shù)誤差界[33]可設(shè)計出新的鑒別分析模型.最近提出的基于L21范數(shù)的LDA 方法[34]通過同時優(yōu)化類中心和投影方向從而在噪聲數(shù)據(jù)方面表現(xiàn)出良好的性能.

在大多數(shù)判別分析中,通常假定類內(nèi)各個樣本以相等的概率(均勻分布)取得的,但是位于類中心附近的樣本一般遠(yuǎn)遠(yuǎn)多于位于類邊界附近的樣本.為了增加類內(nèi)樣本采樣的多樣性,可令類內(nèi)樣本的采樣概率在均勻分布的概率附近變化,這種變化有利于區(qū)分類中心附近的樣本或類邊界附近的樣本.不確定優(yōu)化中的不確定集能描述概率分布的變化范圍.因此本文借助KL 散度定義的不確定集對類內(nèi)樣本信息進(jìn)行概率建模.此外,為了更好描述各類中心的信息,本文也利用KL 散度定義的不確定集對其進(jìn)行概率建模.基于此,本文提出了基于KL散度不確定集的線性判別分析方法,從而進(jìn)一步改善已有線性判別分析方法.與以往的方法不同,本文不僅考慮了一般范數(shù)的目標(biāo)函數(shù),而且利用不確定集對訓(xùn)練樣本信息進(jìn)行了刻畫.本文采用的不確定集為圍繞均勻分布的KL 散度球且約束中的不確定集被轉(zhuǎn)化為目標(biāo)函數(shù)的正則化項.本文的主要貢獻(xiàn)表現(xiàn)為:

1) 提出了正則化對抗LDA 和正則化樂觀LDA.正則化對抗LDA 優(yōu)先考慮了難以區(qū)分的樣本,而正則化樂觀LDA 優(yōu)化考慮了易于區(qū)分的樣本.

2) 采用了廣義Dinkelbach 算法求解正則化對抗LDA 或正則化樂觀LDA.對正則化對抗LDA運(yùn)用投影梯度法求解優(yōu)化子問題,而對正則化樂觀LDA 運(yùn)用交替優(yōu)化求解優(yōu)化子問題.

3) 在數(shù)據(jù)集上表明了當(dāng)數(shù)據(jù)沒有被污染時,兩種判別分析模型取得可競爭的性能,但在污染數(shù)據(jù)的情況下,正則化樂觀LDA 取得更好的性能.這也從另一方面說明了本文提供兩種模型的目的,即如果在某些驗(yàn)證數(shù)據(jù)集上正則化樂觀LDA 的最好性能明顯優(yōu)于正則化對抗LDA 的最好性能,那說明訓(xùn)練集包含離群點(diǎn).因此通過檢查正則化對抗LDA和正則化樂觀LDA 的性能可判斷訓(xùn)練集是否包含離群點(diǎn).

1 相關(guān)工作

1.1 最不利情況的線性判別分析

在文獻(xiàn)[16]中,類間離差矩陣(1)被改寫成下面形式:

其中W是一個d×m投影矩陣以及Im表示單位矩陣.在投影空間中,模型(4)通過優(yōu)化距離最近的兩個類中心和具有最大類內(nèi)距離的類取得最優(yōu)投影矩陣.這種方法實(shí)際上尋找不利區(qū)分樣本的最優(yōu)投影方向.這種設(shè)計思想來源于分類器的設(shè)計.在分類器設(shè)計中,設(shè)計的分類器對難以分類的樣本(邊界樣本)進(jìn)行優(yōu)先考慮,即賦予較大的采樣概率,從而使設(shè)計的分類器具有更好的泛化性能.模型(4)通過優(yōu)先考慮難以區(qū)分的樣本取得最優(yōu)投影矩陣.Zhang和Yeung[16]提出了兩種算法求解模型(4).一種方法是將(4)轉(zhuǎn)化為度量學(xué)習(xí)問題,另一種方法是設(shè)計了一種基于約束的凹凸優(yōu)化算法.

1.2 基于L1 范數(shù)的線性判別分析

在文獻(xiàn)[28]中,下面優(yōu)化模型被用來取得投影矩陣W:

其中 ‖·‖1表示向量的L1范數(shù),li表示第i類樣本的集合.優(yōu)化問題(5)的目標(biāo)函數(shù)關(guān)于變量W是非平滑和非凸的.文獻(xiàn)[28]首先利用梯度上升法取得一個投影向量,然后設(shè)計了一個貪婪方法來取得多個投影向量.

1.3 基于L21 范數(shù)的線性判別分析

為了改善線性判別分析模型在投影空間的鑒別能力,文獻(xiàn)[34]提出了下面的優(yōu)化模型:

與以前的一些模型不同,式(6)的類平均mi(i=1,···,c)是優(yōu)化變量.模型(6)的目標(biāo)函數(shù)實(shí)際上對不同樣本采用了L1范數(shù),而對每個樣本的約簡特征采用了L2范數(shù),這通常被稱為L21范數(shù)的線性判別分析.如果數(shù)據(jù)包含離群點(diǎn),基于算術(shù)平均取得的類中心可能偏離樣本的真正類中心,而優(yōu)化的類中心接近真正的類中心.模型(6)比模型(5)包含更多的優(yōu)化變量.文獻(xiàn)[34]設(shè)計了一個有效的框架求解模型(6).

2 基于不確定集的正則化線性判別分析

2.1 正則化對抗LDA

為了度量兩個具有公共支集的離散概率分布之間的差異,文獻(xiàn)[35]定義了KL 散度.假設(shè)給定兩個離散概率分布p=(p1,···,pn)和q=(q1,···,qn),那么這兩個概率分布之間的KL 散度被定義為:

如果兩個離散概率分布相同,則KL 散度的值為零.由于KL 散度不滿足三角不等式,它實(shí)際上不是一個真正的距離度量.注意到KL 散度是非對稱的,即KL(p|q)KL(q|p).KL 散度是非負(fù)的,即KL(p|q)≥0.在魯棒優(yōu)化中,基于KL 散度的不確定集被定義為[36-37]:

式(8)的不確定集表明,離散概率分布p在給定的離散概率分布q附近變化,其變化范圍由一個非負(fù)參數(shù)ε控制.參數(shù)ε越大,不確定集的變化范圍越大.單個p是不確定集內(nèi)的一個具體的概率分布.

為了探索樣本的類間信息,模型(4) 試圖在低維投影空間中最大化最近的兩個類中心,而且它利用L2范數(shù)定義了類間距離.在Ls范數(shù)的距離測度下,與式(4) 相似的類間信息的優(yōu)化問題在WTW=Im約束條件下被寫成下面形式:

模型(9)不僅引入了優(yōu)化變量pij,而且在投影后的類間距離使用了Ls范數(shù).如果s=1,那么使用了L1范數(shù)定義了類間距離.如果s=2,那么使用了L2范數(shù)定義了類間距離.模型(9)說明了優(yōu)化變量pij在概率單純形內(nèi)變化,即在這個單純形中尋找距離最近的類中心對,并試圖取得最優(yōu)投影矩陣.因此在提取鑒別特征時,距離最近的兩個類中心所起的作用最大.顯然,它忽略了其他類中心的信息,使得這種模型利用類中心的信息不完整.為了解決這個問題,本文首先將離散概率分布pij看作類中心mi和mj之間的采樣概率,然后將離散概率分布pij限制在一定的范圍內(nèi),使得模型變得更加靈活.這里使用式(8)定義的不確定集,這個不確定集是由離散概率分布定義的.因此根據(jù)KL 散度定義的不確定集和各類中心信息,以下優(yōu)化問題被提出:

模型(12)采用了Lr范數(shù)定義類內(nèi)距離,參數(shù)r是正的實(shí)數(shù).模型(4)中分式的分母考慮了低維空間中具有最大類內(nèi)距離的類,而模型(12)考慮了每一類中遠(yuǎn)離其類中心的那些樣本,那些樣本可能位于類之間的交界處.換言之,它搜索一些樣本,使它們在類內(nèi)信息中起主導(dǎo)作用.這樣uik可看成第i類的第k個樣本的采樣概率.通過將uik限制在一個不確定集內(nèi),使樣本的采樣概率發(fā)生變化.根據(jù)(12)和不確定集可定義如下的優(yōu)化問題:

式(19)和(20)實(shí)際上求解模型(14)的內(nèi)層優(yōu)化問題.利用式(19)和(20),優(yōu)化模型(14)被改寫成下面形式:

模型(21)僅包含優(yōu)化變量W.它是一個非常復(fù)雜的非線性優(yōu)化問題.從模型(21)的約束來看,它屬于Stiefel 流形上的優(yōu)化問題[41].

2.2 求解優(yōu)化模型(21)

算法1 把比率優(yōu)化問題(21)歸結(jié)為兩個函數(shù)差的優(yōu)化問題.文獻(xiàn)[27]已采用這種思想求解L1范數(shù)的LDA,從而避免矩陣逆的計算,這也克服小樣本的奇異性問題.文獻(xiàn)[27]的方法實(shí)際上是廣義Dinkelbach 算法的一種形式.這樣本文的算法也不會出現(xiàn)矩陣逆計算問題.如果KL 散度的值不為0,F1(W,pij)作為式(14)的分母也不為零.這些因素促使了提出的算法克服了小樣本的奇異性問題.

2.3 正則化樂觀判別分析

正則化對抗判別分析探索了不確定集中的對抗概率分布,這實(shí)際上優(yōu)化考慮了訓(xùn)練集中位于類邊界附近的樣本(遠(yuǎn)離類中心的樣本).然而當(dāng)數(shù)據(jù)集包含離群點(diǎn)時,這些離群點(diǎn)可能遠(yuǎn)離各類中心.在這種情況下,優(yōu)先考慮類中心附近的樣本是有益的,即對接近類中心附近的樣本分配大的采樣概率.不同于第2.1 節(jié)中的模型,本小節(jié)試圖在不確定集中尋找另外一種概率分布,這對應(yīng)于優(yōu)先考慮類中心附近的樣本點(diǎn).因此借助不確定集以及類內(nèi)和類間信息可定義以下優(yōu)化問題:

模型(23)優(yōu)先考慮了距離大的類中心對,這實(shí)際上優(yōu)先考慮區(qū)分性比較好的類.因?yàn)镵L(p|q)取非負(fù)值,這不能從H1(W,pij)的定義得出其非負(fù)性.對于模型(24),它優(yōu)先考慮區(qū)分性比較好的樣本,即對類中心附近的樣本賦予大的采樣概率和類邊界附近的樣本賦予小的采樣概率.當(dāng)處理的數(shù)據(jù)包含異常點(diǎn)或噪聲時,它優(yōu)先考慮了那些可能不是異常點(diǎn)的樣本,即對異常點(diǎn)賦予小的采樣概率.因?yàn)镵L 散度是非負(fù)的,從式(24)知,H2(W,uik)不小于零.根據(jù)(23)和(24)可建立以下單目標(biāo)函數(shù):

從(23),(24)和(25)知,外層優(yōu)化(優(yōu)化W)和內(nèi)層優(yōu)化(優(yōu)化uik,pij)的目標(biāo)有一致的性質(zhì).根據(jù)不確定規(guī)劃中的樂觀模型的概念,本文將模型(25)稱為正則化樂觀LDA(Regularized optimistic LDA,ROLDA).內(nèi)層優(yōu)化取得的概率分布被稱為不確定集的樂觀概率分布.模型(25)利用不確定集優(yōu)先考慮類中心附近的樣本點(diǎn).對訓(xùn)練集而言,模型(25)優(yōu)先考慮了區(qū)分性好的類和樣本.如果數(shù)據(jù)集包含異常點(diǎn)或噪聲,那么這些異常點(diǎn)或噪聲可能遠(yuǎn)離類中心且具有較低的采樣概率.因此模型(25)在某種程度上能抑制異常點(diǎn)或噪聲.模型(25)是非凸優(yōu)化問題,同樣地也采用了廣義Dinkelbach 算法求解模型(25).求解式(25)涉及下面優(yōu)化子問題:

模型(29)屬于約束的最小化問題.因?yàn)榧s束集是閉有界集且目標(biāo)函數(shù)是連續(xù)的,模型(29)存在解.注意到優(yōu)化變量uik,pij以及W的約束是獨(dú)立的,這樣交替優(yōu)化算法能有效地求解模型(29).模型(22)僅涉及優(yōu)化變量W且目標(biāo)函數(shù)是復(fù)雜的非線性優(yōu)化問題,但模型(29)涉及三組優(yōu)化變量,每一組優(yōu)化變量對應(yīng)一個優(yōu)化子問題.算法3 概括了求解模型(29)的過程.

算法3.求解式(29)的交替優(yōu)化算法

如果s=r=2,算法1 中的步驟a) 可通過特征值分解取得投影矩陣W.在其他情況下,可通過在Stiefel 流形上的梯度下降法取得投影矩陣W.不同于正則化對抗LDA 的求解,如果采用Stiefel流形上的梯度下降法取得W[41],此時函數(shù)的梯度并不包含指數(shù)函數(shù),這實(shí)際上把指數(shù)函數(shù)放在了pij和uik的更新上.在s=r=2 情況下,取得W的計算復(fù)雜度為 O (d3).當(dāng)樣本的維數(shù)較大時,執(zhí)行特征值分解可能比較耗時,那么可采用流形上的梯度下降法取得W.采用Stiefel 流形上的梯度下降法取得W的復(fù)雜度為 O (Tg(c2dm+ndm)),其中Tg為梯度下降法的迭代次數(shù).更新pij和uik的計算復(fù)雜度分別 為 O (c2dm) 和 O (ndm).這 樣如果s=r=2 且 采用特征值分解取得投影矩陣W,那么算法的計算復(fù)雜度為 O (T3(c2dm+ndm+d3)),其中T3為算法3的迭代次數(shù).如果采用Stiefel 流形上的梯度下降法取得投影矩陣W,那么算法3 的計算復(fù)雜度為O(T3(c2dm+ndm+Tg(c2dm+ndm))).

2.4 與其他線性判別分析的關(guān)系

從式(17)和(18)可得到如下推論.

推論1 說明了當(dāng)參數(shù)η和λi趨向正無窮大時,pij和事先定義的qij一致,以及uik和事先定義的vik一致.在這種情況下,根據(jù)qij和vik定義可得出pij=2/(c(c-1)) 和uik=1/ni.此時正則化對抗LDA 退化為不同范數(shù)的LDA.即當(dāng)s=r=2 時,模型(14)成為L2范數(shù)的LDA;當(dāng)s=r=1 時,模型(14) 成為L1范數(shù)的LDA.當(dāng)參數(shù)η和λi趨向0 時,模型(14)變成了最強(qiáng)對抗概率分布下的線性判別分析.這樣參數(shù)η和λi的變化為模型(14)和各種范數(shù)的LDA 建立了聯(lián)系.因此RALDA 推廣了以前的模型.

從式(27)和(28)可知:當(dāng)參數(shù)η和λi趨向正無窮大時,pij=2/(c(c-1)) 和uik=1/ni.此時正則化樂觀L D A 退化為不同范數(shù)的L D A.即s=r=2時,模型(25) 成為L2范數(shù)的LDA;當(dāng)s=r=1時,模型(25)成為L1范數(shù)的LDA.當(dāng)參數(shù)η和λi趨向0 時,模型(25)變成了最樂觀概率分布下的線性判別分析.從式(17) 和(18),以及式(27)和(28)可知,RALDA 和ROLDA 中的pij和uik是不同的.從(17)可知類邊界附近的樣本具有大的采樣概率;從(28)可知類中心附近的樣本具有大的采樣概率.這樣模型(14)優(yōu)先考慮那些不利區(qū)分的樣本,而模型(25)優(yōu)先考慮了那些有利區(qū)分的樣本.盡管這兩種模型的機(jī)制是不同的,但是當(dāng)參數(shù)趨向無窮時,它們是等價的.

3 實(shí)驗(yàn)結(jié)果

本節(jié)通過在數(shù)據(jù)集上的一系列實(shí)驗(yàn)來評估所提出模型的有效性.當(dāng)涉及到分類問題時,本文采用了最近鄰分類器且度量準(zhǔn)則采用了歐氏范數(shù).為了進(jìn)行比較,本文編程實(shí)現(xiàn)了幾種魯棒的特征提取方法,包括L1-LDA[6]、最不利LDA (Worst-case LDA,WLDA[16])、LDA-L1[28]和L21-LDA[34].L1-LDA 和LDA-L1 的參數(shù)設(shè)置與文獻(xiàn)[34]中的相同.注意到提出的模型涉及多個參數(shù).為了簡單起見,令參數(shù)λ=λ1=···=λc,即所有的類都被賦予了相同的參數(shù)λ,這樣模型的參數(shù)被約簡為兩個參數(shù)λ和η,兩個參數(shù)取自集合{10-3,10-2,10-1,1,10,102,103}.對于參數(shù)r和s,本文只考慮參數(shù)取特殊值的情況,即把s=r=1 和s=r=2 的RALDA 分別簡記為L1RALDA 和L2RALDA,以及 把s=r=1 和s=r=2的ROLDA 分別簡記為L1ROLDA 和L2ROLDA.迭代方法的初始解采用了LDA 的正交化投影矩陣.實(shí)驗(yàn)環(huán)境是一臺內(nèi)存為8 GB 的奔騰1.6 GHz 計算機(jī)和Matlab (7.0.0)編程語言.

3.1 人臉和物體數(shù)據(jù)集的實(shí)驗(yàn)

本小節(jié)在四個人臉數(shù)據(jù)庫(Yale、ORL、UMIST 和AR)上和一個物體數(shù)據(jù)庫(COIL)上測試了提出的模型.ORL 人臉數(shù)據(jù)庫包含40 個人,每個人都有10 幅不同的圖像,所有的圖像都是在一個均勻背景下拍攝的.UMIST 人臉數(shù)據(jù)庫包含20 個人的564 幅人臉圖像,每個人都有不同的種族、性別和外貌,例如不同的表情、照明、戴眼鏡/不戴眼鏡、留胡須/不留胡須、不同的發(fā)型.耶魯大學(xué)的人臉數(shù)據(jù)庫包含15 個人的165 幅灰度圖像,其人臉圖像涉及光照條件和面部表情的變化.AR 人臉數(shù)據(jù)庫包含4 000 多幅彩色人臉圖像,每個人有不同的面部表情、光照條件和遮擋.AR 人臉圖像在兩個不同的時間段拍攝且時間間隔是兩周,每階段獲取每個人的13 幅圖像.COIL 數(shù)據(jù)庫包含1 440 幅灰度圖像和20 個物體的黑色背景,每個物體有72 幅不同的圖像.為了提高計算效率,將所有圖像歸一化為 32×32 大小的灰度圖像.

考慮到提出的算法是一種迭代算法,第一組實(shí)驗(yàn)測試了算法的收斂性.實(shí)驗(yàn)數(shù)據(jù)來自Yale 數(shù)據(jù)集.我們隨機(jī)選取每個人的四幅圖像組成訓(xùn)練集,其它圖像用于測試.假設(shè)約簡維數(shù)為14.訓(xùn)練集中有一半的樣本被矩形噪聲污染.矩形噪聲包含等概率的白點(diǎn)和黑點(diǎn),它們在圖像中的位置是隨機(jī)的且塊的大小是 32×32 像素.在實(shí)施算法2 時,令β=0.5.圖1 列出了L2RALDA,L1RALDA,L2ROLDA和L1ROLDA 四種方法的收斂性.為了簡單性,在這組實(shí)驗(yàn)中令λ=η.

從圖1 可知,四種算法的目標(biāo)函數(shù)值隨著迭代次數(shù)的增加而遞減.當(dāng)?shù)螖?shù)超過某一數(shù)值時,目標(biāo)函數(shù)值幾乎保持穩(wěn)定.文獻(xiàn)[27]指出:當(dāng)出現(xiàn)小樣本的奇異性問題時,采用梯度上升法求解L1范數(shù)的判別分析(目標(biāo)函數(shù)為最大化問題)可能使得目標(biāo)函數(shù)值發(fā)生振蕩現(xiàn)象.在這組實(shí)驗(yàn)中,圖像的維數(shù)遠(yuǎn)遠(yuǎn)大于訓(xùn)練樣本的個數(shù),這存在奇異性問題,但圖1 顯示了提出的算法的目標(biāo)函數(shù)值并沒有出現(xiàn)振蕩的情況,這意味著提出的算法在某種程度上避免了小樣本的奇異性問題.從圖1 可觀察到基于L1范數(shù)的模型比基于L2范數(shù)的模型一般需要更多的迭代次數(shù),這是因?yàn)榛贚1范數(shù)的模型有不可微的目標(biāo)函數(shù).注意到不同的參數(shù)也影響算法的收斂速度.因此在后面的實(shí)驗(yàn)中,本文設(shè)定算法的停止條件為最大迭代次數(shù)為50 或目標(biāo)函數(shù)值的相對改變不超過 10-4.

圖1 L2RALDA,L1RALDA,L2ROLDA 和L1ROLDA 的收斂性分析Fig.1 Convergence analysis of L2RALDA,L1RALDA,L2ROLDA and L1ROLDA

在約簡的參數(shù)下提出的模型有兩個重要參數(shù)λ和η.這組實(shí)驗(yàn)探索了參數(shù)λ和η對識別性能的影響.對于圖像識別問題,為了降低計算代價,采用主成分分析降維但保持圖像的百分之九十九的能量.對于耶魯數(shù)據(jù)集,隨機(jī)選取每個人的四幅圖像組成訓(xùn)練集,其他樣本用于測試.假設(shè)約簡維數(shù)為14,固定r=s=1 或r=s=2,參數(shù)λ和η從集合{10-3,10-2,10-1,1,10,102,103}中取值.因此每個參數(shù)取七個值.實(shí)驗(yàn)結(jié)果來自十次的平均實(shí)驗(yàn).圖2顯示了每種算法隨參數(shù)變化的錯誤率.在圖2 的每個子圖中,其中x軸表示對數(shù)尺度的參數(shù)λ,y軸表示對數(shù)尺度的參數(shù)η,以及z軸表示算法的錯誤率.

從圖2 可看出,模型的錯誤率隨著參數(shù)的變化而變化.當(dāng)參數(shù)λ和η取較小值時,L1ROLDA 的錯誤率較低.對于L2ROLDA,如果參數(shù)η取較大值且參數(shù)λ取較小值,則分類性能較好.對于L1RALDA,如果參數(shù)η取較小值且參數(shù)λ取較大值,則在很大范圍內(nèi)獲得較低的錯誤率.對于L2RALDA,其參數(shù)也影響算法的性能.這組實(shí)驗(yàn)表明了L1ROLDA和L1RALDA 的作用機(jī)理是不同的.因此在實(shí)際應(yīng)用中需要選擇合適的參數(shù)才能獲得最佳的分類性能,這可通過交叉驗(yàn)證等方法來獲得最佳參數(shù).

圖2 L2RALDA,L1RALDA,L2ROLDA 和L1ROLDA 的錯誤率與參數(shù)的關(guān)系Fig.2 Error rates of L2RALDA,L1RALDA,L2ROLDA and L1ROLDA versus the parameters

為了比較各種模型的特征提取性能,在Yale、ORL、UMIST 和COIL 數(shù)據(jù)集上隨機(jī)選取每個人的4 幅圖像構(gòu)成訓(xùn)練集,其余圖像用作測試目的.為了評價算法的魯棒性,在Yale、ORL、UMIST 和COIL 數(shù)據(jù)集上人工模擬了遮擋圖像,那就是訓(xùn)練集中有一半的樣本被矩形噪聲污染.矩形噪聲包含等概率的白點(diǎn)和黑點(diǎn),它們在圖像中的位置是隨機(jī)的,塊的大小是 20×20 像素.由于AR 數(shù)據(jù)集包含實(shí)際遮擋的情況,本文考慮了120 個人的兩種遮擋情況:其一是太陽鏡遮擋,其二是圍巾遮擋.在AR數(shù)據(jù)集上,對于太陽鏡遮擋,從第一時間段的7 幅無遮擋圖像中隨機(jī)選擇3 幅圖像,然后將這些圖像與隨機(jī)選擇的3 幅太陽鏡遮擋的圖像構(gòu)成訓(xùn)練集.第二時間段得到的7 幅無遮擋的圖像被用做測試集.因此每個人的訓(xùn)練樣本數(shù)為6.對于圍巾遮擋,從第一時間段的7 幅無遮擋圖像中隨機(jī)選擇3 幅圖像,然后將這些圖像與隨機(jī)選擇的3 幅圍巾遮擋圖像構(gòu)成訓(xùn)練集,第二時間段得到的7 幅無遮擋的圖像被用做測試集.

圖3 顯示了在Yale 數(shù)據(jù)庫上幾種算法的錯誤率隨約簡特征變化的情況.表1 列出了各種方法的最好性能.另外表1 中給出了各個人臉數(shù)據(jù)集上和COIL 數(shù)據(jù)集上的最好性能.每種方法的參數(shù)在額外的五次運(yùn)行上得到.表1 的實(shí)驗(yàn)結(jié)果來自20 次隨機(jī)運(yùn)行的平均,其中C-表示污染的數(shù)據(jù)集.

圖3 數(shù)據(jù)集上不同方法隨維數(shù)變化的錯誤率Fig.3 Error rates of various methods with varying dimensions on the Yale database

從圖3 可知,隨著約簡維數(shù)的增加各種方法的錯誤率下降,但過多的特征反而使得錯誤率上升.這表明特征的維數(shù)是一個重要的參數(shù).從表1 可看出,對于原圖像集,L1RALDA 在ORL 和UMIST數(shù)據(jù)集上可獲得很好的分類效果,這表明在適當(dāng)?shù)臈l件下,優(yōu)先考慮邊界點(diǎn)的判別分析算法是合理的.當(dāng)部分圖像被污染后,L1ROLDA 在大多數(shù)情況下優(yōu)于其他方法.在實(shí)際遮擋的AR 數(shù)據(jù)上,圍巾遮擋比太陽鏡遮擋導(dǎo)致更大的錯誤率.

同其他方法比較,L1ROLDA 不僅采用了L1范數(shù)的損失函數(shù),而且考慮了樣本的采樣概率,其采樣概率在不確定集中自適應(yīng)地變化,從而得到較好的效果.從表1 可知,當(dāng)部分圖像被污染后,各種方法錯誤率的標(biāo)準(zhǔn)偏差一般大于原始圖像上各種方法錯誤率的標(biāo)準(zhǔn)偏差.這表明污染的數(shù)據(jù)使得各種方法的性能具有更大的不確定性.

表1 各種方法在原始數(shù)據(jù)集和污染數(shù)據(jù)集上的平均錯誤率(%)和標(biāo)準(zhǔn)偏差Table 1 Average error rates (%) of various methods and their standard deviations on the original and contaminated data sets

這組實(shí)驗(yàn)比較了各種算法在五個圖像數(shù)據(jù)集上的時間消耗.提出算法的停止條件如前面所述.在ORL,UMIST,Yale 和COIL 數(shù)據(jù)集上假定約簡維數(shù)為40.由于AR 數(shù)據(jù)集包含更多的類數(shù),其約簡維數(shù)設(shè)定為80.圖4 顯示了各種算法在五個數(shù)據(jù)集上的運(yùn)行時間(單位:秒).

從圖4 可看出,WLDA 的運(yùn)行時間遠(yuǎn)遠(yuǎn)高于其它算法的運(yùn)行時間,這是因?yàn)檫@種方法采用了二階錐規(guī)劃.L1-LDA 和LDA-L1 都采用了貪婪算法取得多個投影向量,它們的運(yùn)行時間相差不大.在Yale 和ORL 數(shù)據(jù)集上,L21LDA 的運(yùn)行時間是最少的,但在UMIST 和COIL 數(shù)據(jù)集上,L2ROLDA需要的時間最少.由于在AR 數(shù)據(jù)集上的約簡維數(shù)為80 且類數(shù)較多,每種方法的訓(xùn)練時間明顯大于在其他數(shù)據(jù)集上的訓(xùn)練時間.一般來說,L1RALDA和L1ROLDA 訓(xùn)練時間分別大于L2RALDA 和L2ROLDA 的訓(xùn)練時間,這是因?yàn)長1RALDA 和L1ROLDA 采用了L1范數(shù)導(dǎo)致其目標(biāo)函數(shù)是不可微的,而L2RALDA 和L2ROLDA 的目標(biāo)函數(shù)是可微函數(shù).

圖4 五個圖像數(shù)據(jù)集上各種算法的運(yùn)行時間Fig.4 Running time of various methods on five image data sets

3.2 UCI 數(shù)據(jù)集上的實(shí)驗(yàn)

這組實(shí)驗(yàn)使用的數(shù)據(jù)集來自UCI 機(jī)器學(xué)習(xí)庫.這些數(shù)據(jù)集已被廣泛用于評估一些學(xué)習(xí)算法的性能.本文在8 個數(shù)據(jù)集上測試了提出的模型.這8個數(shù)據(jù)集分別是Australia (690 樣本/14 特征/2 類),Diabetes (768/8/2),German (1 000/24/2),Heart (270/13/2),Liver(345/6/2),Sonar(208/60/2),WPBC (198/33/2)和Waveform (5 000/21/3).不同于圖像數(shù)據(jù)集,對于這些數(shù)據(jù)集,訓(xùn)練樣本的維數(shù)遠(yuǎn)遠(yuǎn)小于訓(xùn)練樣本的個數(shù),即小樣本的奇異性問題不會出現(xiàn).每個數(shù)據(jù)集樣本的屬性被轉(zhuǎn)化為[-1,1]區(qū)間.對于每個數(shù)據(jù)集,隨機(jī)選取70%的樣本構(gòu)成訓(xùn)練集,剩下的樣本作為測試集.除了原始數(shù)據(jù)集,我們也模擬了訓(xùn)練集中樣本的某些特征被污染的情況.具體來說,訓(xùn)練集中一半樣本的50% 特征被替換為由-1 和1 組成的隨機(jī)噪聲.

每種方法的參數(shù)在訓(xùn)練集上通過五疊交叉驗(yàn)證方法學(xué)習(xí)得到.實(shí)驗(yàn)性能取自十次隨機(jī)實(shí)驗(yàn)的平均結(jié)果.為了比較兩種算法在同一個數(shù)據(jù)集上的性能,在顯著性水平0.05 的情況下計算L1ROLDA 和其他算法的配對t檢驗(yàn)的p-值.如果p-值大于0.05時,這表明L1ROLDA 和其他算法沒有顯著的差別.當(dāng)p-值小于0.05 時,這表明L1ROLDA 和其他算法存在顯著差別.表2 和表3 列出在原始數(shù)據(jù)集和污染數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,其實(shí)驗(yàn)結(jié)果包括平均正確率(Average correct rates,ACR)和標(biāo)準(zhǔn)偏差(standard deviations,SD)以及L1ROLDA 和其他方法的配對t檢驗(yàn)的p-值.

從表2 可知,L21-LDA 在Diabetes 數(shù)據(jù)集上取得最好的性能,L1RALDA 在German 和WPBC 數(shù)據(jù)集上取得最好的性能,L1ROLDA 在Australian,Heart 和Waveform 數(shù)據(jù)集上取得最好的性能,L1-LDA 在Liver 數(shù)據(jù)集上取得最好的性能,這表明了沒有一種方法在這些數(shù)據(jù)集上取得一致好的性能.從表3 可知,當(dāng)特征被污染后,每種方法的性能都會存在某種程度的下降.一般來說基于L2范數(shù)方法不比基于L1范數(shù)方法好.從表2 和表3的p-值可知,L1ROLDA 和其它方法是否存在明顯的差別.例如:從p-值可知在特征沒有被污染的情況下,L1ROLDA 和L21LDA 在German 和Heart數(shù)據(jù)集上存在統(tǒng)計意義上的差別,但當(dāng)特征被污染后,L1ROLDA 和L21LDA 在Australian,German,Heart,Liver 和Waveform 數(shù)據(jù)集上存在統(tǒng)計意義上的差別.

表2 各種方法在原始數(shù)據(jù)集上的平均正確率(ACR(%)),標(biāo)準(zhǔn)偏差(SD)和 p-值Table 2 Average correct rates (ACR(%)),standard deviations (SD),and p-values of various methods on the original data sets

表3 各種方法在污染數(shù)據(jù)集上的平均正確率(ACR(%)),標(biāo)準(zhǔn)偏差(SD)和 p-值Table 3 Average correct rates (ACR(%)),standard deviations (SD),and p-values of various methods on the contaminated data sets

當(dāng)特征被污染后,L1ROLDA 方法在多數(shù)情況下優(yōu)于其他方法,這是因?yàn)樵诓淮_定集下,優(yōu)先考慮了那些有利區(qū)分的樣本,這些樣本可能不是污染的數(shù)據(jù)點(diǎn),而對離群點(diǎn)賦予較低的采樣概率.因此當(dāng)數(shù)據(jù)被污染后,應(yīng)當(dāng)優(yōu)先選擇L1ROLDA 方法.實(shí)際上,當(dāng)測試RALDA 和ROLDA 時,如果在驗(yàn)證數(shù)據(jù)集上ROLDA 的性能遠(yuǎn)遠(yuǎn)好于RALDA 的性能,那么說明訓(xùn)練集包含離群點(diǎn).在這種情況下,我們可采用一些去離群點(diǎn)的方法去除訓(xùn)練集中的離群點(diǎn),然后再執(zhí)行特征提取算法.

盡管配對t檢驗(yàn)?zāi)鼙容^兩種算法在同一個數(shù)據(jù)集上的性能差別,但是它不能取得多種算法在多個數(shù)據(jù)集上的性能排序問題.由于在多個數(shù)據(jù)集上測試了多種方法,本文采用Friedman 檢驗(yàn)[40]評估多種算法的性能.在Friedman 檢驗(yàn)中,如果零假設(shè)成立,即假設(shè)所有的算法在性能上是相等的,Friedman 統(tǒng)計量可用概率分布來計算.本文使用關(guān)鍵差別(Critical difference,CD)圖[40]比較不同算法的性能.圖5 表示了在原始數(shù)據(jù)和污染數(shù)據(jù)上的性能分析的CD 圖.CD 圖的平均秩提供了算法的性能的排序.平均秩越小,算法的性能越好.從圖5(a)可知,L1ROLDA 給出了最小的平均秩,但是L21-LDA 的平均秩和L1ROLDA 的平均秩相差不大.WLDA 有最大的平均秩.從圖5(b)可知,當(dāng)數(shù)據(jù)被污染后,L1ROLDA 仍然取得了最小的平均秩,但L21-LDA 的平均秩明顯大于L1ROLDA 的平均秩.總的來說,由于采用了L1范數(shù)和優(yōu)先考慮了類中心附近的樣本,當(dāng)數(shù)據(jù)被污染后,正則化樂觀線性判別分析取得最好的性能.

圖5 不同方法性能的顯著性分析Fig.5 Performance significance analysis of various methods

4 結(jié)論

本文提出了基于不確定集和混合范數(shù)的線性判別分析方法.不同于以前的方法,本文借助Kullback-Leibler 不確定集描述樣本的變化信息,這樣可探索不確定集中的概率分布.由于樣本或類中心的采樣概率在不確定集中靈活變化,從而使得模型適應(yīng)數(shù)據(jù)的內(nèi)在特性.模型是比率優(yōu)化和非凸優(yōu)化問題.廣義Dinkelbach 算法被用來求解優(yōu)化模型.本文利用投影梯度法或交替優(yōu)化技術(shù)求解算法的優(yōu)化子問題.這樣算法的收斂性直接來自廣義Dinkelbach算法的收斂性.在圖像數(shù)據(jù)集和UCI 數(shù)據(jù)集上做了一系列實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明:在沒有污染的數(shù)據(jù)集上,由于RALDA 考慮了類邊界附近的樣本,RALDA應(yīng)當(dāng)被優(yōu)先考慮,但在污染數(shù)據(jù)集上,ROLDA 應(yīng)當(dāng)被優(yōu)先考慮.由于本文簡化了模型中一些參數(shù),這些參數(shù)對模型的性能會產(chǎn)生一定的影響.今后我們將重點(diǎn)研究如何自動學(xué)習(xí)多個參數(shù),并將本文的基本思想推廣到其它基于核函數(shù)的非線性判別分析和張量判別分析.