趙彩云，吳長勤，葛 華

(安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 蚌埠 233100)

基于有效迭代算法的魯棒L1范數(shù)非平行近似支持向量機(jī)

趙彩云*，吳長勤，葛 華

(安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 蚌埠 233100)

針對(duì)魯棒L1范數(shù)非平行近似支持向量機(jī)(L1-NPSVM)求解算法無法保證獲取可靠解的問題，提出一個(gè)新穎的迭代算法來解L1-NPSVM的目標(biāo)問題。首先，根據(jù)L1-NPSVM原目標(biāo)問題對(duì)解具有規(guī)模不變性，將其轉(zhuǎn)換為一個(gè)等價(jià)的帶等式約束的最大化問題。該迭代算法在每次迭代中利用更新權(quán)機(jī)制獲取每次迭代的更新解；每次迭代中，問題歸結(jié)為解兩個(gè)快速的線性方程問題。從理論上證明了算法的收斂性。在公共UCI數(shù)據(jù)集上，實(shí)驗(yàn)顯示，所提算法不僅在分類性能上要遠(yuǎn)遠(yuǎn)好于L1-NPSVM，且具有相當(dāng)?shù)挠?jì)算優(yōu)勢。

L1-范數(shù)距離；L1范數(shù)非平行近似支持向量機(jī)；梯度上升；線性方程；分類

0 引言

在過去20年里，支持向量機(jī)(Support Vector Machine, SVM)已經(jīng)吸引了廣泛的關(guān)注[1-4]。SVM的核心思想是通過最大化兩個(gè)邊界平面(Bounding planes)間的間隔來搜尋最優(yōu)分類平面。這兩個(gè)平面各自歸屬于一個(gè)特定的類，且具有平行的特性。

近些年，近似多平面SVM技術(shù)得到了學(xué)者們廣泛研究。不同于基于兩平行平面的SVM方法，近似多平面SVM旨在為每類找一個(gè)最好的擬合平面，平面間不需要保證平行的條件。Mangasarian等[5]提出的廣義特征值近似SVM(Proximal Support Vector Machine via Generalized Eigenvalues, GEPSVM)，通過構(gòu)建帶有每個(gè)平面離本類樣本近而離它類樣本遠(yuǎn)幾何解釋的目標(biāo)問題，來找兩個(gè)擬合平面，最終，問題歸結(jié)為解兩個(gè)廣義特征值問題。GEPSVM的這些獨(dú)特性保證了它的計(jì)算優(yōu)勢以及好的分類性能，尤其在異或(Exclusive OR, XOR) 問題上, 其往往是SVM無法超越的。

隨后，許多研究人員對(duì)GEPSVM進(jìn)行了拓展。Guarracino等[6]提出了正則化的特征值分類器(Regularized Generalized Eigenvlue Classifier, ReGEC)。與GEPSVM相比，ReGEC的一個(gè)主要優(yōu)勢在于, 在二分類問題上計(jì)算時(shí)間要減少一半，因其僅要求解一個(gè)而非兩個(gè)廣義特征值問題。Jayadeva[7]模糊化GEPSVM，建立了模糊GEPSVM(Fuzzy GEPSVM, FGEPSVM)模型。 楊緒兵等[8-9]提出了基于原型超平面的多類最接近支持向量機(jī)(Mult-class Hyperplane Proximal SVM, MHPSVM)和局部化的廣義特征值最接近支持向量機(jī)(Localized Proximal Support Vector Machine via Generalized Eigenvalues, LGEPSVM), Ye等[10]和Shao等[11]提出了多權(quán)向量投影支持向量機(jī)(Multi-Weight Vector Projection Support Vector Machine, MVSVM)。 Shao等[11]改進(jìn)GEPSVM成一個(gè)差形式。這些方法大多都采用商形式?；贕EPSVM另一種拓展是對(duì)支持向量機(jī)(TWin SVM, TWSVM)[12-19]，其共同之處在于都解二次凸規(guī)劃而非廣義特征值問題。與GEPSVM相比, TWSVM除計(jì)算上存在較大劣勢外，在求解XOR問題上也不足夠理想[15]。

GEPSVM或者它的相關(guān)拓展中大多數(shù)方法對(duì)野值或噪聲存在敏感性，因其在模型中采用了L2范數(shù)平方距離[17-18]。近年，文獻(xiàn)[17-20]揭露L1范數(shù)距離對(duì)野值具較好的魯棒性。Kwak 等[20]首次將L1范數(shù)距離引入主成分分析(Principal Component Analysis, PCA)中，隨后L1范數(shù)距離被應(yīng)用于線性判別分析(Linear Discriminant Analysis,LDA)特征抽取的判別準(zhǔn)則中[18-19]。啟發(fā)于基于L1范數(shù)距離相關(guān)的特征抽取方法，Li等[17]提出了魯棒L1范數(shù)非平行近似支持向量機(jī)(L1-norm Nonparallel SVM, L1-NPSVM), 其將GEPSVM中L2范數(shù)平方距離用L1范數(shù)距離來代替，從而保證了GEPSVM對(duì)野值或噪聲的魯棒性。L1-NPSVM形式上與GEPSVM相同，即：一個(gè)商形式，但因其非凸性且目標(biāo)包含絕對(duì)值計(jì)算，使模型不易求解。為了獲得解，文獻(xiàn)[17]采用梯度上升(Gradient Ascending, GA)迭代算法。GA本質(zhì)上是與梯度下降(Gradient Descending, GD)算法相同，差異僅僅在于目標(biāo)為最大還是最小化問題。這樣需要引入一個(gè)學(xué)習(xí)率，正如文獻(xiàn)[19]所指，其還需要引入一個(gè)非凸的代替函數(shù)，因其非凸性，學(xué)習(xí)率不適當(dāng)?shù)倪x擇影響著解的最優(yōu)性。文獻(xiàn)[21]中，Kwak也進(jìn)一步指出了GD導(dǎo)致不令人滿意的結(jié)果。導(dǎo)致這樣問題還可能因?yàn)?，與GA相同，GD學(xué)習(xí)率的選擇不應(yīng)過大，否則它不收斂，且其大小也影響著其收斂速度，在保證收斂的情況下，學(xué)習(xí)率越大收斂得越快，而越小收斂得越慢[17]；L1-NPSVM算法中僅僅包含了一個(gè)參數(shù)——學(xué)習(xí)率，事實(shí)上，其在模型中起著調(diào)整模型泛化能力的作用，然而，為了保證收斂性，其學(xué)習(xí)率的選擇受到眾多限制，以至于往往無法保證獲得最優(yōu)性能。針對(duì)GEPSVM對(duì)野值或噪聲不魯棒的問題，本文同樣也展開了研究，基于L1-NPSVM目標(biāo)問題，提出一個(gè)更有效的迭代算法。該算法能保證快速地收斂，且因每次迭代解線性方程而繼承了GEPSVM的計(jì)算上的優(yōu)勢，從理論上證明了所提算法的收斂性。最后實(shí)驗(yàn)揭露所提算法的可靠性。

1 相關(guān)工作

1.1 廣義特征值近似支持向量機(jī)

首先回顧下經(jīng)典的多平面分類器GEPSVM[5]，其旨在緩解傳統(tǒng)支持向量機(jī)代價(jià)高且無法較理想地求解如XOR等較復(fù)雜的問題。為了獲得如下兩個(gè)最優(yōu)的非平行的平面:

xTw1+e1b1=0

(1)

xTw2+e2b2=0

(2)

GEPSVM建立兩個(gè)新穎的目標(biāo)問題，其要求平面離本類樣本盡可能地近, 而離它類樣本盡可能地遠(yuǎn)。這兩個(gè)問題的具體形式分別定義為:

(3)

(4)

其中δ是正則化參數(shù)。注意正則化項(xiàng)是為了改進(jìn)GEPSVM的泛化能力。

令H=[Ae1]，G=[Be2]，z1=[w1Tb1]T，z2=[w2Tb2]T。簡化上述問題(3)和(4)，得到式(5)和(6):

(5)

(6)

上述問題(5)和(6)是兩個(gè)典型的Rayleigh商問題，因此，它們的解歸結(jié)為求解兩個(gè)廣義特征值問題，即：(HTH+δI)z1=λ1GTGz1和(GTG+δI)z1=λ1HTHz1，其解為該特征方程最小特征值對(duì)應(yīng)的特征向量。給定一個(gè)測試樣本x，將其歸屬于其距最近的平面所屬的類。

1.2 魯棒L1范數(shù)非平行近似支持向量機(jī)

從GEPSVM的兩個(gè)模型(3)和(4)中可以看出，GEPSVM度量點(diǎn)到平面的距離用L2范數(shù)的平方。自然地，為了獲得目標(biāo)函數(shù)的最小值，GEPSVM不得不強(qiáng)調(diào)那些偏遠(yuǎn)于同類的樣本的作用，說明L2范數(shù)易夸大野值或噪聲的影響。平方L2范數(shù)距離度量易受野值或噪聲的影響，而L1范數(shù)距離度量具有較強(qiáng)的魯棒性[18-19]。鑒于L1范數(shù)距離的魯棒性，Li等[17]提出了L1-NPSVM, 其直接將GEPSVM原目標(biāo)問題中L2范數(shù)平方距離替換為L1范數(shù)距離，其具體形式描述為:

(7)

(8)

令gi∈R1×(n+1)和hi∈R1×(n+1)為矩陣G和H的第i行。簡化式(7)和(8)為：

(9)

(10)

(11)

其中β是學(xué)習(xí)率，一個(gè)較小的正實(shí)數(shù)，而:

(12)

2 建議的方法

實(shí)際上，L1-NPSVM將問題(9)和(10)重寫為如下兩個(gè)等價(jià)的最大化問題:

(13)

(14)

基于L1范數(shù)距離的相關(guān)工作起源于Kwak[20]提出的L1范數(shù)PCA(L1-PCA)。 近年，其思想也延伸到線性判別分析LDA中，由此出現(xiàn)了基于L1范數(shù)距離LDA(L1-LDA)[18-19]。較L1-PCA，L1-LDA面對(duì)更大的挑戰(zhàn)是如何解同時(shí)最大最小的L1范數(shù)距離的目標(biāo)問題。形式上，GEPSVM相似于LDA, 差異僅僅在于前者為實(shí)現(xiàn)分類問題計(jì)算同類和不同類點(diǎn)與平面間的距離，而后者為實(shí)現(xiàn)特征提取問題計(jì)算類間和類內(nèi)距離。同樣，L1-NPSVM形式上也與L1-LDA相同，目標(biāo)是個(gè)同時(shí)最大最小問題。當(dāng)將式(3)和式(7)以及式(13)和式(14)進(jìn)行比較可知，除L1范數(shù)距離度量，L1-NPSVM與GEPSVM問題最大不同之處還在于它不考慮正則項(xiàng)，旨在減少不定參數(shù)數(shù)目，因其包括了學(xué)習(xí)率的選擇。正則項(xiàng)的引入GEPSVM,起初目的是改進(jìn)模型的泛化能力[5]，那么，學(xué)習(xí)率的選擇對(duì)L1-NPSVM的泛化能力起著決定性的作用。

為了解L1-LDA,文獻(xiàn)[18]GD對(duì)其進(jìn)行求解。然而，后續(xù)工作[19]卻指出，因GD需要引入一個(gè)非凸的代替函數(shù)且其非凸性導(dǎo)致學(xué)習(xí)率的不適當(dāng)選擇引起L1-LDA無法獲取有效的解。在文獻(xiàn)[21]中，Kwak也進(jìn)一步指出了這樣迭代算法易導(dǎo)致不令人滿意的結(jié)果。正如上節(jié)所指出，L1-NPSVM也用不完美的GD對(duì)其目標(biāo)進(jìn)行求解。GD的不足，也可能由如下原因所致，本文直接基于L1-NPSVM問題對(duì)其分析。GD本質(zhì)上與GA相同,其學(xué)習(xí)率的選擇不應(yīng)過大，否則它不收斂，且其大小也影響著其收斂速度，在保證收斂的情況下，學(xué)習(xí)率越大收斂得越快，而越小收斂得越慢[17]。這意味著，學(xué)習(xí)率的選擇受到眾多限制，而它在L1-NPSVM充當(dāng)控泛化能力的作用，以至于往往無法保證獲得的性能是最優(yōu)的。

為了緩解GD的不足，文獻(xiàn)[19]首先將一個(gè)最小化商問題轉(zhuǎn)換為一個(gè)等價(jià)的帶約束問題，進(jìn)一步提出一個(gè)有效迭代算法對(duì)其進(jìn)行求解。這里，本文拓展該算法到解L1-NPSVM問題。本文以直接解L1-NPSVM中最大化商而非最小化商問題(13)和(14)為目的。首先，這兩個(gè)問題轉(zhuǎn)換為如下兩個(gè)等價(jià)的帶等式約束的最大化問題：

(15)

(16)

注意，z1和z2規(guī)模的變化不會(huì)導(dǎo)致原問題目標(biāo)值的變化[19]。因?yàn)?/p>

(17)

(18)

令dii=1/|giz1|，fii=1/|hiz2|，si=sign(hiz1)，ki=sign(giz1)，可以重寫問題(15)和(16)為:

(19)

(20)

(21)

(22)

(23)

s.t.z1TGTD(p)Gz1=1

(24)

s.t.z2THTF(p)Hz2=1

下面給出式(23)的緊解形式，對(duì)于問題(24)，可采用同樣的解過程。構(gòu)建問題(23)的拉格朗日函數(shù)：

(25)

其中，γ是拉格朗日乘子。對(duì)L(z1,γ)求解關(guān)于z1的導(dǎo)數(shù)，并設(shè)置其為0，可得到問題(23)的解：

(26)

將該解代入等式約束z1TGTD(p)Gz1=1中，得到：

(27)

將等式(27)代入式(26)，最終有：

(28)

用相似的程序，可以計(jì)算出式(14)的解，即每次迭代計(jì)算(24)，其解形式為：

(29)

為了描述方便，本文定義基于上述迭代算法的L1-NPSVM為L1-NPSVM2?？偟膩碚f，L1-NPSVM2的解過程如下：

步驟1 輸入數(shù)據(jù)矩陣X=[A;B]，根據(jù)其計(jì)算矩陣H和G。

步驟3 如果兩次迭代目標(biāo)值的差大于0.001或迭代次數(shù)小于50，那么執(zhí)行以下步驟：

步驟4 輸出z1和z2。

下面來證明L1-NPSVM2迭代程序的單調(diào)遞增的特性。

理論1 L1-NPSVM2在每次迭代中具有單調(diào)遞增的特性,目標(biāo)問題(13)是其單調(diào)遞增目標(biāo)函數(shù)。

(30)

其能被簡化為：

(31)

(32)

組合式(31)和(32)得到：

(33)

因?yàn)閷?duì)于任意兩個(gè)非0變量v和u，有：

(v-u)2≥0 ?v2+u2-2vu≥0 ?

(34)

(35)

因此，有：

(36)

(37)

(38)

當(dāng)?shù)仁?38)成立，其意味著L1-NPSVM2可以找到一個(gè)局部最大點(diǎn)，此時(shí),認(rèn)為算法收斂。在實(shí)際中，為了保證算法在有限步迭代，常規(guī)的方式是設(shè)置迭代終止條件為兩次迭代目標(biāo)值的差小于一個(gè)很小的值，且迭代數(shù)目應(yīng)小于給定的值。在本文算法的迭代過程中，從問題(28)和(29)看到，矩陣GTD(p)G和HTF(p)H僅能保證半正定性，以至于可能得到不精確或不穩(wěn)定的解。因此，我們通過正則化它來緩解此問題，即用GTD(p)G+δI和HTF(p)H+δI代替它。在執(zhí)行本文算法時(shí),δ被用作一個(gè)調(diào)節(jié)參數(shù)。容易驗(yàn)證，這樣與GEPSVM相同，本文實(shí)際上在原目標(biāo)問題(13)和(14)的分母中考慮了正則化項(xiàng)來保證泛化能力。對(duì)于L1-NPSVM而言，它在目標(biāo)并未考慮正則化，否則算法將存在兩個(gè)參數(shù)，一個(gè)正則化參數(shù)，另一個(gè)是學(xué)習(xí)率，即增加了參數(shù)的數(shù)目。L1-NPSVM實(shí)際上通過調(diào)整學(xué)習(xí)率來保證其泛化能力。顯然，本文算法與L1-NPSVM同樣，并未增加參數(shù)的數(shù)目，都僅包括一個(gè)參數(shù)。

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證L1-NPSVM1和L1-NPSVM2的有效性，在人工XOR數(shù)據(jù)集CompXOR和21個(gè)UCI公共數(shù)據(jù)庫上進(jìn)行實(shí)驗(yàn)。其中，CompXOR來自文獻(xiàn)[9]。實(shí)驗(yàn)環(huán)境：Windows 7操作系統(tǒng)，CUP為Intel雙核處理器 3.4 GHz，內(nèi)存為1 GB，運(yùn)行軟件為 Matlab 2014。

所有比較算法都僅有一個(gè)參數(shù)：正則化參數(shù)δ屬于GEPSVM和L1-NPSVM2，而學(xué)習(xí)率β屬于L1-NPSVM。所有的參數(shù)通過10折交叉驗(yàn)證獲取，且δ的搜索范圍設(shè)定為{2i|i=-12,-11,…,+12}。因β需要取小值保證算法的收斂性，以至于其取值范圍具有一定的限制性，為了實(shí)驗(yàn)公平性，其設(shè)置同文獻(xiàn)[17]，即在{0.000 01,0.000 05,0.000 1,0.000 5,0.001}范圍來搜索它。因?yàn)長1-NPSVM和L1-NPSVM2是兩個(gè)迭代程序，因此，需要設(shè)置它們的初始值。GEPSVM對(duì)野值或噪聲具敏感性問題，以至于分類平面漂離于理想的平面，而L1-NPSVM和L1-NPSVM2可以糾正GEPSVM分類平面的漂離問題，因此，本文設(shè)置它們的初始解為GEPSVM的解。該設(shè)置也跟隨了文獻(xiàn)[18-19]的思路。對(duì)所有實(shí)驗(yàn)，本文記錄10折交叉驗(yàn)證的平均分類精度，用配對(duì)T檢驗(yàn)以克服隨機(jī)性。置信水平設(shè)置為95%。當(dāng)p值<0.05，意味著兩個(gè)算法存在顯著的差異。

表1給出了GEPSVM、L1-NPSVM和L1-NPSVM2的分類結(jié)果。從表中，不難看到，所有算法中，GEPSVM的分類結(jié)果是最差的，其說明L1范數(shù)距離有助于提高分類器性能方面。 當(dāng)將兩個(gè)基于L1范數(shù)距離的多平面分類器L1-NPSVM和L1-NPSVM2進(jìn)行比較，可以看到，L1-NPSVM2遠(yuǎn)遠(yuǎn)好于L1-NPSVM，其驗(yàn)證了本文的迭代算法的有效性。盡管L1-NPSVM優(yōu)于GEPSVM，但優(yōu)勢是微弱的，比如在Liver上，GEPSVM得到61.98%的精度，L1-NPSVM僅得到62.86%，而L1-NPSVM2卻得到67.21%的精度。這樣的結(jié)果說明，較小的學(xué)習(xí)率可能僅僅起到對(duì)解擾動(dòng)的作用。計(jì)算效率上，三個(gè)算法執(zhí)行得都非常快，盡管GEPSVM稍快于L1-NPSVM和L1-NPSVM2。事實(shí)上，這種現(xiàn)象是因?yàn)椋煌贕EPSVM, L1-NPSVM和L1-NPSVM2是迭代算法且其記錄的時(shí)間還包括了GEPSVM計(jì)算初始解的時(shí)間。L1-NPSVM和L1-NPSVM2在計(jì)算時(shí)間上是相當(dāng)?shù)摹?/p>

為了驗(yàn)證L1-NPSVM2的魯棒性，本文在包含噪聲或野值的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。這里，本文用高斯噪聲模擬野值數(shù)據(jù)。具體地，生成滿足標(biāo)準(zhǔn)正態(tài)分布的數(shù)據(jù)0.2m個(gè)，其中m為訓(xùn)練樣本的個(gè)數(shù)，并且，標(biāo)注其正類和負(fù)類樣本各一半，然后，將這些數(shù)據(jù)并入訓(xùn)練集中。有關(guān)實(shí)驗(yàn)設(shè)置同第一個(gè)實(shí)驗(yàn)。表2顯示了GEPSVM、 L1-NPSVM和L1-NPSVM2的分類精度和計(jì)算時(shí)間。從表2中本文能得到與第一個(gè)實(shí)驗(yàn)相似的結(jié)論，即： GEPSVM劣于L1-NPSVM和L1-NPSVM2。當(dāng)比較L1-NPSVM和L1-NPSVM2，可以看到， L1-NPSVM2遠(yuǎn)遠(yuǎn)好于L1-NPSVM。在計(jì)算效率上，L1-NPSVM和L1-NPSVM2都執(zhí)行得很快；比如在大數(shù)據(jù)集Mush上，L1-NPSVM2僅僅需要約 0.95 s。

圖1給出了L1-NPSVM2在Heart、 Monk2和Cancer數(shù)據(jù)集上迭代數(shù)與目標(biāo)值的關(guān)系。這里僅僅給出執(zhí)行第一折且計(jì)算正類超平面時(shí)L1-NPSVM2的目標(biāo)值。

表1 GEPSVM, L1-NPSVM和L1-NPSVM2在原數(shù)據(jù)集上的分類性能Tab. 1 Classification results of GEPSVM, L1-NPSVM, and L1-NPSVM2 on the original datasets

注：*表示該算法與L1-NPSVM2存在顯著差異。

圖1 L1-NPSVM2在Heart、 Monk2和Cancer數(shù)據(jù)集上迭代數(shù)目與目標(biāo)值的關(guān)系Fig. 1 Objective values of L1-NPSVM2 versus the number of iterations on Heart, Monk2 and Cancer

從圖1中可以看到L1-NPSVM2能快速收斂，一般能在10次迭代后收斂。

表2 GEPSVM, L1-NPSVM和L1-NPSVM2在向數(shù)據(jù)集引入10%高斯噪聲情況下的分類性能Tab. 2 Classification results of GEPSVM, L1-NPSVM, and L1-NPSVM2 on the original datasets added by 10% Gaussian noisy data

注：*表示該算法與L1-NPSVM2存在顯著差異。

4 結(jié)語

盡管L1-NPSVM模型極具簡單，但如何解該模型是一個(gè)挑戰(zhàn)的問題。在L1-NPSVM中，作者采用已有的梯度上升算法對(duì)其求解，卻無法保證有效的解。本文提出一個(gè)有效的迭代算法，定義為L1-NPSVM2，其對(duì)L1-NPSVM的最大化目標(biāo)問題進(jìn)行求解。從理論上保證的算法存在單調(diào)性，實(shí)驗(yàn)結(jié)果說明了其在很小的迭代步數(shù)內(nèi)收斂。在公共數(shù)據(jù)集上，結(jié)果驗(yàn)證了所提算法的有效性。為了公平性，跟隨L1-NPSVM設(shè)計(jì)思路，本文僅僅給出L1-NPSVM2線性問題。在未來工作中，我們將對(duì)非線性L1-NPSVM2進(jìn)行研究。

References)

[1] SMITH R S, KITTLER J, HAMOUZ M, et al. Face recognition using angular LDA and SVM ensembles[C]// Proceedings of the 18th International Conference on Pattern Recognition. Washington, DC: IEEE Computer Society, 2006: 1008-1012.

[2] HSU C W, CHANG C C, LIN C J. A practical guide to support vector classification[EB/OL].[2016- 11- 20].http://www.csie.ntu.edu.tw/cjlin/papers/guide/guide.pdf.

[3] FRANC V, SONNENBURG S. Optimized cutting plane algorithm for large-scale risk minimization[J]. Journal of Machine Learning Research, 2009, 10: 2157-2192.

[4] CORTES C, VAPNIK V. Support vector networks[J]. Machine Learning, 1995, 20(3): 273-297.

[5] MANGASARIAN O L, WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(1): 69-74.

[6] GUARRACINO M R, CIFARELLI C, SEREF O, et al. A classification method based on generalized eigenvalue problems[J]. Optimization Method and Software, 2007, 22(1): 73-81.

[7] JAYADEVA, KHEMCHANDANI R, CHANDRA S. Twin support vector machines for pattern classification[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 2007, 29(5): 905-910.

[8] 楊緒兵，陳松燦. 基于原型超平面的多類最接近支持向量機(jī)[J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(10): 1700-1705.(YANG X B, CHEN S C. Proximal support vector machine based on prototypal multiclassfication hyperplanes[J]. Journal of Computer Research and Development, 2006, 43(10): 1700-1705.)

[9] 楊緒兵，陳松燦，楊益民. 局部化的廣義特征值最接近支持向量機(jī)[J].計(jì)算機(jī)學(xué)報(bào), 2007, 30(8): 1227-1234.(YANG X B, CHEN S C, YANG Y M. Localized generalized proximal support vector machine[J]. Chinese Journal of Computers, 2007, 30(8): 1227-1234.

[10] YE Q, YE N, YIN T. Enhanced multi-weight vector projection support vector machine[J]. Pattern Recognition Letters, 2014, 42(1): 91-100.

[11] SHAO Y, DENG N, CHEN W, et al. Improved generalized eigenvalue proximal support vector machine[J]. IEEE Signal Processing Letters, 2013, 20(3): 213-216.

[12] SHAO Y, ZHANG C. Improvements on twin support vector machines[J]. IEEE Transactions on Neural Networks, 2011, 22(6): 962-968.

[13] QI Z, TIAN Y, SHI Y. Robust twin support vector machine for pattern classification[J]. Pattern Recognition, 2013, 46(1): 305-316.

[14] KHEMCHANDANI R, SAIGAL P, CHANDRA S. Improvements on ν-twin support vector machine[J]. Neural Networks, 2016, 79: 97-107.

[15] YE Q, ZHAO C, YE N. Least squares twin support vector machine classification via maximum one-class with-in class variance[J]. Optimization Methods and Software, 2012, 27(1): 53-69.

[16] 業(yè)巧林，趙春霞, 陳小波. 基于正則化技術(shù)的對(duì)支持向量機(jī)特征選擇算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(6):1029-1037.(YE Q L, ZHAO C X, CHEN X B. A feature selection method for TWSVM via a regularization technique[J]. Journal of Computer Research and Development, 2011, 48(6):1029-1037.)

[17] LI C, SHAO Y, DENG N. Robust L1-norm non-parallel proximal support vector machine[J]. Optimization, 2016, 65(1): 1-15.

[18] WANG H, LU X, HU Z, et al. Fisher discriminant analysis with L1-norm[J]. IEEE Transactions on Cybernetic, 2014, 44(6): 828-842.

[19] ZHENG W M, LIN Z C, WANG H X. L1-norm distance kernel discriminant analysis via Bayes error bound optimization for robust feature extraction[J]. IEEE Transactions on Neural Networks,2014, 24(4):793-805.

[20] KWAK N. Principal component analysis based on L1-norm maximization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(9): 1672-1680.

[21] KWAK N. Principal component analysis by Lp-norm maximization[J]. IEEE Transactions on Cybernetics, 2014, 44(5): 594-609.

ZHAOCaiyun, born in 1982, M. S., assistant. Her research interests include computer information management system, artificial intelligence.

WUChangqin, born in 1962, associate professor. His research interests include computer information management system, artificial intelligence.

GEHua, born in 1976, M. S., lecturer. His research interests include computer information management system, artificial intelligence.

RobustL1-normnon-parallelproximalsupportvectormachineviaefficientiterativealgorithm

ZHAO Caiyun*, WU Changqing, GE Hua

(CollegeofInformationandNetworkEngineering,AnhuiScienceandTechnologyUniversity,BengbuAnhui233100,China)

Considering that robust L1-norm Non-parallel Proximal Support Vector Machine (L1-NPSVM) can not guarantee a reliable solution, a new iterative algorithm was proposed to solve the objective of L1-NPSVM. Since the objective problem of L1-NPSVM is invariant to the scale of solution, such that it can be transformed into a maximization problem with an equality constraint. And then the proposed iterative algorithm was used to solve it. The iterative algorithm in each iteration obtained updated solution of each iteration by using weight updating mechanism, and the problem was reduced to solve two fast linear equations in each iteration. The convergence of the algorithm was proved theoretically. Experiments on the common UCI datasets show that the proposed algorithm is not only superior to L1-NPSVM in classification performance, but also has considerable computational advantage.

L1-norm distance; L1-norm Non-parallel Proximal Support Vector Machine (L1-NPSVM); gradient ascending; linear equation; classification

2017- 05- 16;

2017- 06- 29。

趙彩云(1982—)，女，安徽南陵人，助教，碩士，主要研究方向：計(jì)算機(jī)信息管理系統(tǒng)、人工智能； 吳長勤(1962—)，男，安徽合肥人，副教授，主要研究方向：計(jì)算機(jī)信息管理系統(tǒng)、人工智能； 葛華(1976—)，男，江蘇沐陽人，講師，碩士，主要研究方向：計(jì)算機(jī)信息管理系統(tǒng)、人工智能。

1001- 9081(2017)11- 3069- 06

10.11772/j.issn.1001- 9081.2017.11.3069

(*通信作者電子郵箱joydezcy@126.com)

TP39

A