楊麗明，　張思韞,　任　卓

(中國農(nóng)業(yè)大學 理學院　北京 100083)

?

一種基于分類問題的光滑極限學習機

楊麗明，張思韞,任卓

(中國農(nóng)業(yè)大學 理學院北京 100083)

極限學習機具有快速的學習速度和良好的泛化性能.光滑化是一種重要的處理非光滑問題的技術.將光滑化技術應用于極限學習機,提出了一種光滑化的極限學習機框架,并用Newton-Armijo算法來求解.該算法具有全局和二次收斂的性質.與已有的光滑支持向量機相比,該模型有更少的決策變量,并且能夠更好地解決非線性問題.數(shù)值實驗表明該算法的速度要比傳統(tǒng)的極限學習算法更快.與支持向量機相比,提出的算法有更好的或者相似的泛化性能.

極限學習機； 光滑化方法； Newton-Armijo算法； 神經(jīng)網(wǎng)絡

0　引言

極限學習機(extreme learning machine,ELM)[1-2]是一種新型單隱層前饋神經(jīng)網(wǎng)絡[3],具有結構簡單、學習速度快、良好的非線性處理能力和全局搜索性能等優(yōu)勢.不同于傳統(tǒng)的神經(jīng)網(wǎng)絡,ELM設置合適的隱層結點數(shù),其隱層輸入權向量和偏移量隨機賦值,輸出層權值可通過最小二乘法得到.研究表明ELM可以達到與支持向量機(support vector machine,SVM)相似的泛化能力[4-6],但是具有更快的訓練速度.因此,ELM作為一種新的處理大數(shù)據(jù)的重要工具已經(jīng)成為近年來的研究熱點.

光滑化方法已經(jīng)被廣泛地應用于不同的優(yōu)化問題,如連續(xù)優(yōu)化和非線性規(guī)劃等[7-8].其主要思想是產(chǎn)生一系列的光滑函數(shù)來近似原始的非光滑函數(shù).該方法的優(yōu)點在于光滑化之后高階導數(shù)的信息可以被利用.

1　ELM

考慮二分類問題.假設由N個樣本構成的訓練集{(xi,ti),xi∈Rn,ti∈{-1,1},i=1,2,…,N},其中:xi=(xi1,xi2,…,xin)∈Rn表示輸入樣本，ti表示樣本xi的標示.設隱層結點數(shù)為L,激勵函數(shù)為g(x),則ELM分類的決策函數(shù)為：

(1)

近來,文獻[2]提出了一種新的基于優(yōu)化理論和方法的ELM.在這種算法中,SVM的軟間隔思想被引入到ELM中.文獻[2]指出：SVM的最大分類間隔性質和ELM的輸出權重范數(shù)最小的性質實質上是相同的;與SVM一樣,ELM不僅最小化訓練誤差,也最大化分類間隔;在理論上,ELM特征空間中的所有訓練點能以概率1被一個經(jīng)過原點的超平面線性分開,但是在實際應用中,訓練點不能被嚴格地分開.因此,基于優(yōu)化理論的ELM(optimization theory-based ELM,OPTELM)模型可表示為如下的優(yōu)化問題：

(2)

其中:參數(shù)C是大于0的懲罰參數(shù);ξi∈R表示在ELM特征空間中樣本h(xi)∈RL的誤差且ξ=(ξ1,ξ2,…,ξN)T∈RN.這是一個二次規(guī)劃,有全局解,其分離超平面為h(x)Tβ=0經(jīng)過ELM特征空間的原點.

2　光滑的極限學習機

在這部分，我們應用光滑化方法到OPTELM上,得到基于優(yōu)化方法的光滑極限學習機(smooth ELM,SELM),并且通過Newton-Armijo算法求解SELM.

2.1光滑近似

(3)

令D為對角線元素分別為ti,i=1,2,…,N的N階對角矩陣,則問題(3)可表示為：

(4)

其中:H=(h(x1),h(x2),…,h(xN))T∈RN×L是隱層輸出矩陣,e是元素全為1的向量.式(4)是一個二次規(guī)劃,且目標函數(shù)具有嚴格凸性.因此,式(4)具有唯一全局最優(yōu)解.由Karush-Kuhn-Tucker條件(KKT條件),得到定理1.

定理1設(β*,ξ*)為問題(4)的最優(yōu)解,則ξ*可表示為ξ*=(e-DHβ*)+.

證明較簡單,故略去.因此,將式(4)中的ξ替換成(e-DHβ)+,可得無約束凸優(yōu)化問題：

(5)

其目標函數(shù)是嚴格凸的,這保證了式(5)只有唯一解.然而,它的目標函數(shù)不是二次可微的,因此不能直接應用牛頓法.

應用光滑函數(shù)p(x,λ)逼近(x)+,當參數(shù)λ→+∞時,p(x,λ)→(x)+.我們得到式(5)的光滑逼近問題，稱為SELM：

(6)

定理2[11]設A∈Rm×l,q∈Rm,考慮如下的優(yōu)化問題：

(7)

和

(8)

其中:λ>0,可得到結論(ⅰ)～(ⅱ)：

(9)

2.2求解SELM的Newton-Armijo算法

Newton-Armijo算法收斂速度快,且全局收斂,因為問題(6)的目標函數(shù)是二次可微的,因此提出了求解SELM的光滑近似問題(6)的Newton-Armijo算法.算法步驟如下：

上述算法采用一系列線性方程組來解優(yōu)化問題,學習速度快.關于其收斂性質,有定理3.

因此,求解SELM的Newton-Armijo算法全局收斂,并且經(jīng)過有限次迭代之后,搜索步變成純牛頓步,這保證了其具有二次收斂性.

3　數(shù)值實驗

3.1實驗設計

實驗在10個UCI數(shù)據(jù)集上進行,在MATLAB 7.10上實現(xiàn).選取傳統(tǒng)OPTELM[2]和光滑SVM(SSVM[11])作為基準方法進行比較.

為了綜合評估所提出方法的有效性,本文利用評價準則為：

1) 精度(accuracy, ACC),F1-measure和馬休斯相關系數(shù)(Matthews correlation coefficient,MCC).其中,ACC表示兩類樣本的識別率,F1是精確率和召回率兩個指標的調和平均值,MCC是一種綜合評價標準,其定義為[12]：

其中:TP和TN分別表示正確的正類和負類樣本數(shù),FN和FP分別表示錯誤的負類和正類樣本數(shù).ACC、MCC和F1-measure的值越大,模型越優(yōu).

2) Time,整個訓練和測試時間.

3.2實驗結果

3.2.1SELM和OPTELM的比較SELM和OPTELM都在最優(yōu)參數(shù)下分別運行了50次.兩種算法在最優(yōu)參數(shù)下的泛化性能比較見表1.

表1　SELM和OPTELM的ACC、MCC和F1比較Tab.1　Comparison between SELM and OPTELM in terms of ACC,MCC and F1　%

表1顯示,在兩個數(shù)據(jù)集上SELM的分類精度ACC低于OPTELM,其余5個數(shù)據(jù)集上SELM獲得與OPTELM相當?shù)倪\行結果.

因為算法的運行結果依賴其模型參數(shù)的選擇.則比較當C和L取相同值時,SELM和OPTELM的運行時間.其平均結果顯示在表2.

表2　參數(shù)C和L相同時SELM和OPTELM運行時間比較Tab.2　Comparison between SELM and OPTELM with respect to Time when parameters C and L were same

由于Newton-Armijo算法具有二次收斂性,因此運行速度快.與OPTELM比較，表2說明SELM明顯地縮短了運行時間.而且對于其他參數(shù)組合,SELM的運行速度也比OPTELM快.

3.2.2SELM與其他方法的比較把SELM的ACC與線性SSVM (linear SSVM)和非線性SSVM(SSVM-kernel)進行了比較.最優(yōu)參數(shù)下的平均結果見表3.表3顯示,對于所有7個數(shù)據(jù)集,SELM的分類精度明顯高于SSVM-kernel.并且,SELM和SSVM精度相當.

為了進一步驗證SELM的有效性,把該算法同其傳統(tǒng)的ELM[1]、標準的SVM[5]、l1模SVM(l1-norm SVM)[6]進行比較.結果見表4,其中SVM和l1-norm SVM的結果來自文獻[11].

表4說明,在Ionosphere和Pima兩個數(shù)據(jù)集上,SELM的表現(xiàn)明顯好于ELM,并且精度略高于SVM和l1-norm SVM.

表3　SELM、SSVM、SSVM-kernel的ACC比較Tab.3　Comparison among SELM, SSVM and SSVM-kernel in terms of ACC　%

表4　SELM的ACC與其他算法比較結果Tab.4　Comparison of ACC of SELM with other popular algorithms　%

4　結論

本文將光滑化技術應用到ELM中,提出了光滑化的ELM模型,主要貢獻可歸納如下：

1) 利用Newton-Armijo算法求解SELM的近似問題,使SELM繼承了阻尼牛頓法全局收斂的優(yōu)點.并且本文所提出的算法具有快速的二次收斂性.

2) SELM中所有網(wǎng)絡參數(shù)隨機賦值無需調整,其非線性映射具有顯式形式.

3) 與SSVM和extreme SVM[13]相比,在SELM中,分類超平面h(x)Tβ=0通過原點,不需要求解偏移量,因此,SELM應用起來更方便.

4) 同OPTELM相比,SELM有更高或類似的泛化性能,而且運行速度更快.SELM比非線性SSVM獲得更高的精度和更少的運行時間.同線性SSVM及其他傳統(tǒng)方法比較,SELM有著相當?shù)姆夯阅?

[1]HUANG G B,SIEW C K,ZHU Q Y. Extreme learning machine: theory and applications[J]. Neurocomputing, 2006,70(1/2/3)：489-501.

[2]HUANG G B,DING X,ZHOU H. Optimization method based extreme learning machine for classification[J]. Neurocomputing,2010,74(1/2/3)：155-163.

[3]MATIAS T,SOUZA F,ARAUJO R,et al. Learning of a single-hidden layer feedforward neural network using an optimized extreme learning machine[J]. Neurocomputing,2014,129(10)：428-436.

[4]LIU X Y,GAO C H,LI P. A comparative analysis of support vector machines and extreme learning machines[J]. Neural networks,2012,33(9)：58-66.

[5]魏培文,段德全,孫印杰,等. 基于SVM的生物醫(yī)學事件觸發(fā)詞識別研究[J]. 信陽師范學院學報(自然科學版),2015,28(3):446-449.

[6]ALABDULMOHSIN I,MOUSTAPHA C,GAO X,et al. Large margin classification with indefinite similarities[J]. Machine learning, 2016,103(2):215-237.

[7]CHEN C,MANGASARIAN O L. A class of smoothing functions for nonlinear and mixed complementarity problems[J]. Computational optimization and applications,1996,5(2)：97-138.

[8]CHEN X J,DU S Q, ZHOU Y. A smoothing trust region filter algorithm for nonsmooth least squares problems[J]. Science China-mathematics, 2014, 59(5):999-1014.

[9]BALASUNDARAM S,KAPIL D G. 1-norm extreme learning machine for regression and multiclass classification using Newton method[J]. Neurocomputing,2014,128(2)：4-14.

[10]王小朋,劉翔峰. 一種基于病態(tài)問題的修正牛頓法[J]. 河南科技大學學報(自然科學版),2015,36(1):86-91.

[11]LEE Y J,MANGASARIAN O L. SSVM: a smooth support vector machine[J]. Computational optimization and applications,2001,20(1)：5-22.

[12]TRIPATHY A,AGRAWAL A,RATH S K. Classification of sentiment reviews usingn-gram machine learning approach[J]. Expert systems with applications, 2016, 57(15)：117-126.

[13]LIU Q,HE Q,SHI Z. Extreme support vector machine classifier [C] //Procceedings of the 12th Pacific-Asia conference on advances in knowledge discovery and data mining. Berlin, 2008.

(責任編輯：王浩毅)

A Smooth Extreme Learning Machine for Classification

YANG Liming，ZHANG Siyun,REN Zhuo

(CollegeofScience,ChinaAgriculturalUniversity,Beijing100083,China)

Extreme learning machine (ELM) had a high learning speed and a good generalization ablity. Smoothing strategy was an important technology for non-smooth problems. By combining a smoothing technique with ELM, a smooth ELM (SELM)framework was proposed. Moreover, the Newton-Armijo algorithm was used to solve the SELM, and resulting algorithm converged globally and quadratically. The proposed SELM had less decision variables and better abitities to deal with nonlinear problems than the existing smooth support vector machine. Numerical experiments demonstrated that the speed of SELM was much faster than that of the existing ELM algorithms based on optimization theory. Compared with other popular support vector machines, the proposed SELM achieved better or similar generalization. The results demonstrated the feasibility and effectiveness of the proposed algorithm.

extreme learning machine(ELM); smooth approach; Newton-Armijo algorithm; neural networks

2016-06-25

國家自然科學基金資助項目(11471010)．

楊麗明(1963—),女,河北保定人，教授,主要從事數(shù)據(jù)挖掘和機器學習的研究,E-mail:cauyanglm@163.com．

TP391

A

1671-6841(2016)03-0051-06

10.13705/j.issn.1671-6841.2016097

引用本文:楊麗明,張思韞,任卓．一種基于分類問題的光滑極限學習機[J]．鄭州大學學報(理學版),2016,48(3)：51-56．