基于近似梯度算法的Fisher線性判別分析問(wèn)題的求解研究

梁露方，胡恩良

(云南師范大學(xué) 數(shù)學(xué)學(xué)院，云南 昆明 650500)

特征提取是模式識(shí)別中最基本的研究?jī)?nèi)容之一，它可以有效地緩解模式識(shí)別領(lǐng)域中經(jīng)常出現(xiàn)的“維數(shù)災(zāi)難(curse of dimensionality)”問(wèn)題，并對(duì)后續(xù)識(shí)別性能起著重要的作用[1].“維數(shù)災(zāi)難”問(wèn)題，最早是由Richard E. Bellman[2]在思考問(wèn)題的優(yōu)化時(shí)所提出來(lái)的，而如何處理“維數(shù)災(zāi)難”成為了我們關(guān)心的話題.在高維的大數(shù)據(jù)中，并不是所有的信息都是重要信息，把信息處理后再利用會(huì)避免許多麻煩，例如：計(jì)算存儲(chǔ)量的問(wèn)題、信噪比的問(wèn)題、魯棒性的問(wèn)題等，甚至還能避免影響后續(xù)的一些結(jié)果.

在眾多的特征提取方法中，F(xiàn)isher線性判別分析(Fisher linear discriminant analysis，F(xiàn)LDA)是一種經(jīng)典的有監(jiān)督的特征提取方法，它為多種線性判別分析奠定了基礎(chǔ).FLDA最早出現(xiàn)在1936年Fisher的經(jīng)典論文[3]中，其基本思想是通過(guò)最大化Fisher準(zhǔn)則，找到最優(yōu)投影方向，使投影后的數(shù)據(jù)的類內(nèi)距離盡可能小且類間距離盡可能大，并以此達(dá)到抽取分類信息和壓縮特征空間維數(shù)的目的.目前，F(xiàn)LDA及其推廣已廣泛應(yīng)用于市場(chǎng)定位、產(chǎn)品管理、人臉識(shí)別及機(jī)器學(xué)習(xí)等領(lǐng)域.

直到現(xiàn)在，我們對(duì)FLDA的拓展研究都沒(méi)有停止.例如，2017年由Forough等[4]所寫的文章就是對(duì)Fisher線性判別分析做出的進(jìn)一步研究，其文章的核心是多類判別分析的跡比優(yōu)化，而Li等[5]也在自己的文章中提出過(guò)相似的理論.Liu等[6]的文章提出通過(guò)最大化多目標(biāo)函數(shù)的調(diào)和平均值來(lái)研究加權(quán)跡比，而為了進(jìn)一步提高性能，就將L2，L1范數(shù)強(qiáng)加到目標(biāo)函數(shù)上.此外，他們還提出了一個(gè)迭代算法來(lái)優(yōu)化目標(biāo)函數(shù)，Wei和Yang等[7-8]也提出過(guò)相似的理論.Liao等[9]提出的最壞判別特征選擇也是基于FLDA的拓展研究.

設(shè)X=[x1,…,xn]∈Rd×n為c類樣本矩陣，W=[w1,…wr]∈Rd×r為待求解的投影矩陣，Y=WTX為樣本集X投影后的表示(即Y=[y1,…,yn]∈Rr×n，yi=WTxi).根據(jù)Fisher準(zhǔn)則可知，求解投影矩陣W，等價(jià)于求解投影后的數(shù)據(jù)Y的類間散度與類內(nèi)散度比值的最大化，即

(1)

其中，類間散度矩陣Sb、類內(nèi)散度矩陣St的關(guān)系如下：

(2)

求解目標(biāo)問(wèn)題(1)等價(jià)于求解如下(3)的廣義特征值問(wèn)題：

SbW=λStW.

(3)

然而，問(wèn)題(3)的求解時(shí)間復(fù)雜度至少為Ο(d3).為了提高求解效率，我們將引入近似梯度下降(PGD, proximal gradient descent)法[10-11]來(lái)求解FLDA問(wèn)題.

1 近似梯度算法

1.1 混合凸目標(biāo)函數(shù)的PGD算法

在凸優(yōu)化問(wèn)題中，對(duì)于目標(biāo)函數(shù)是可微的時(shí)候，我們可以利用梯度下降法(GD，gradient descent)迭代求解出最優(yōu)解，而對(duì)于目標(biāo)函數(shù)是不可微的時(shí)候，則通過(guò)引入次梯度也可以迭代求解出最優(yōu)解，但是比起梯度下降法，次梯度法的速度比較緩慢.因此，針對(duì)于一些整體不可微但卻可以分解的混合目標(biāo)函數(shù)來(lái)說(shuō)，我們可以使用一種更快的算法—近似梯度法(PGD).

PGD是一種更廣泛的梯度下降方法，該方法可用于求解一些目標(biāo)函數(shù)是不可微的問(wèn)題，其基本思想是使用臨近算子得到目標(biāo)函數(shù)的近似梯度.

考慮目標(biāo)函數(shù)可以分解為如下形式的2個(gè)函數(shù)：

J(x)=f(x)+g(x).

(4)

結(jié)合近似函數(shù)，我們可以定義一個(gè)迭代過(guò)程，叫做近似梯度下降(即PGD)，其過(guò)程如下：

(5)

PGD是一種傳統(tǒng)算法的推廣，易知：①當(dāng)f(x)=0時(shí)，PGD退化為近似點(diǎn)算法；②當(dāng)g(x)=0時(shí)，PGD退化為梯度下降法；③當(dāng)g(x)=δX(x)是凸集的指示函數(shù)時(shí)，PGD退化為投影梯度下降法.

1.2 比值形式的PGD算法

對(duì)于如下的比值優(yōu)化問(wèn)題：

(6)

Radu等[12]在2016年提出過(guò)類似的近似梯度算法，其中g(shù)(x)≥0是凸函數(shù)，f(x)>0是凸函數(shù)或者凹函數(shù).在f(x)是凸函數(shù)的情形下，分式PGD算法的迭代格式為：

(7)

2 PGD算法求解FLDA問(wèn)題

根據(jù)前文可知，筆者的目的是求出經(jīng)過(guò)投影后的投影矩陣W中的各個(gè)投影方向，即W=[w1,w2,…,wr].由前面(1)式可知原目標(biāo)函數(shù)可轉(zhuǎn)化為：

(8)

(9)

2.1 子問(wèn)題(9)的求解

記

(10)

對(duì)h(w)式關(guān)于w求導(dǎo)后令其為0，得：

2.2 WTW=I的正交約束處理

證明：利用數(shù)學(xué)歸納法進(jìn)行證明

當(dāng)i=1時(shí)，Wi=[w1]，結(jié)論顯然成立；

當(dāng)i=s時(shí)，

綜上2.1和2.2所述，利用PGD求解FLDA問(wèn)題(1)可整理為如下算法1：

算法1：利用PGD求解FLDA

輸入：i=1，w0，Xi=X;輸出：近似最優(yōu)解W*.

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

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

本節(jié)將選取12個(gè)數(shù)據(jù)集(具體信息如下表1)進(jìn)行實(shí)驗(yàn).其中數(shù)據(jù)集Chessboard、Glass、Heart、Iris、Protein、Sonar、Soybean和Spiral來(lái)自于UCI-9datasets[19]；數(shù)據(jù)集Diabetes、Air、Dnatest和Normal來(lái)自于UCI8.實(shí)驗(yàn)過(guò)程中對(duì)比的方法共4種，分別是：PCA[20]、FLDA_EigDcom[3]、FLDA_DC[21]和FLDA_PGD，其中：

PCA—即PCA降維方法；

FLDA_EigDcom—即利用廣義特征分解求解FLDA；

FLDA_DC—即利用凸差(DC，Difference of Convex functions)優(yōu)化方法求解FLDA；

FLDA_PGD—即利用PGD算法優(yōu)化求解FLDA.

表1 實(shí)驗(yàn)的數(shù)據(jù)集及信息

3.2 降維效果對(duì)比

分別用PCA、FLDA_EigDcom、FLDA_DC和 FLDA_PGD 4種方法在訓(xùn)練集上得到降維矩陣，然后再對(duì)數(shù)據(jù)集進(jìn)行降維.為了測(cè)試降維效果的好壞，我們利用最近鄰分類，使用降維后的測(cè)試集上的平均分類精度作為比較標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果見(jiàn)表2.從表2可以看出，各個(gè)方法的平均分類精度都相差較小，但FLDA_PGD的平均分類精度最優(yōu)，標(biāo)準(zhǔn)差也相對(duì)較小.

從表2可以看出，在多數(shù)情形下FLDA_PGD的平均分類精度為最優(yōu)，標(biāo)準(zhǔn)差也相對(duì)較小.盡管PCA、FLDA_EigDcom、FLDA_DC和FLDA_PGD的差別較小，但多以FLDA_PGD的平均分類精度略高于另外3種方法，這說(shuō)明了FLDA_PGD算法的有效性.

表2 4種算法在各數(shù)據(jù)集上的分類精度對(duì)比

注：表中數(shù)據(jù)為平均分類精度±標(biāo)準(zhǔn)差.

3.3 時(shí)間效率對(duì)比

從表3中可看出，F(xiàn)LDA_PGD算法的執(zhí)行時(shí)間明顯少于FLDA_EigDcom和FLDA_DC的執(zhí)行時(shí)間，這表明該算法在求解FLDA問(wèn)題時(shí)效率更高.

表3 4種算法在各數(shù)據(jù)集上的執(zhí)行時(shí)間對(duì)比

注：表中時(shí)間為平均執(zhí)行時(shí)間±標(biāo)準(zhǔn)差.

4 結(jié)語(yǔ)

為了更好地求解FLDA問(wèn)題，引入近似梯度下降(PGD, proximal gradient descent)法來(lái)求解FLDA問(wèn)題，并分析了該算法的收斂性.通過(guò)在多個(gè)數(shù)據(jù)上的實(shí)驗(yàn)表明，利用PGD方法進(jìn)行實(shí)驗(yàn)大多比傳統(tǒng)方法更好，后續(xù)的平均分類精度更高.同時(shí)，實(shí)驗(yàn)結(jié)果也表明，F(xiàn)LDA_PGD算法所耗時(shí)間較少，比一些傳統(tǒng)方法(如FLDA_EigDcom和FLDA_DC)的效率更高.