面向Kullback-Leibler 散度不確定集的正則化線性判別分析

梁志貞 張 磊

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

1.2 基于L1 范數的線性判別分析

在文獻[28]中,下面優化模型被用來取得投影矩陣W:

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

1.3 基于L21 范數的線性判別分析

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

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

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

2.1 正則化對抗LDA

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

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

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

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

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

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

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

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

2.2 求解優化模型(21)

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

2.3 正則化樂觀判別分析

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

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

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

模型(29)屬于約束的最小化問題.因為約束集是閉有界集且目標函數是連續的,模型(29)存在解.注意到優化變量uik,pij以及W的約束是獨立的,這樣交替優化算法能有效地求解模型(29).模型(22)僅涉及優化變量W且目標函數是復雜的非線性優化問題,但模型(29)涉及三組優化變量,每一組優化變量對應一個優化子問題.算法3 概括了求解模型(29)的過程.

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

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

2.4 與其他線性判別分析的關系

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

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

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

3 實驗結果

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

3.1 人臉和物體數據集的實驗

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

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

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

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

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

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

圖2 L2RALDA,L1RALDA,L2ROLDA 和L1ROLDA 的錯誤率與參數的關系Fig.2 Error rates of L2RALDA,L1RALDA,L2ROLDA and L1ROLDA versus the parameters

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

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

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

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

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

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

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

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

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

3.2 UCI 數據集上的實驗

這組實驗使用的數據集來自UCI 機器學習庫.這些數據集已被廣泛用于評估一些學習算法的性能.本文在8 個數據集上測試了提出的模型.這8個數據集分別是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).不同于圖像數據集,對于這些數據集,訓練樣本的維數遠遠小于訓練樣本的個數,即小樣本的奇異性問題不會出現.每個數據集樣本的屬性被轉化為[-1,1]區間.對于每個數據集,隨機選取70%的樣本構成訓練集,剩下的樣本作為測試集.除了原始數據集,我們也模擬了訓練集中樣本的某些特征被污染的情況.具體來說,訓練集中一半樣本的50% 特征被替換為由-1 和1 組成的隨機噪聲.

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

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

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

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

當特征被污染后,L1ROLDA 方法在多數情況下優于其他方法,這是因為在不確定集下,優先考慮了那些有利區分的樣本,這些樣本可能不是污染的數據點,而對離群點賦予較低的采樣概率.因此當數據被污染后,應當優先選擇L1ROLDA 方法.實際上,當測試RALDA 和ROLDA 時,如果在驗證數據集上ROLDA 的性能遠遠好于RALDA 的性能,那么說明訓練集包含離群點.在這種情況下,我們可采用一些去離群點的方法去除訓練集中的離群點,然后再執行特征提取算法.

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

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

4 結論

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