基于柔性多面體的最優(yōu)核極限學(xué)習(xí)機(jī)算法

蘇一丹，麻曉璇，覃 華，王保鋒

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

極限學(xué)習(xí)機(jī)(extreme learning machine, ELM)具有學(xué)習(xí)速度快、結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，但ELM隱藏節(jié)點(diǎn)數(shù)量的選擇以及參數(shù)的隨機(jī)設(shè)置造成學(xué)習(xí)訓(xùn)練方程存在病態(tài)問(wèn)題，影響了它的穩(wěn)定性。于是出現(xiàn)了核極限學(xué)習(xí)機(jī)(kernel extreme learning machine, KELM)[1]，隨著多層特征表示的不斷發(fā)展，借助核函數(shù)的ELM層次化結(jié)構(gòu)也表現(xiàn)出了速度快、易于實(shí)現(xiàn)的優(yōu)勢(shì)[2]，并已被廣泛應(yīng)用于各個(gè)領(lǐng)域，例如，高光譜圖像分類[4]、人的行為分析[5]、損傷定位檢測(cè)[6]、航空發(fā)動(dòng)機(jī)故障診斷[7]等場(chǎng)合。多核結(jié)構(gòu)的ELM提高了學(xué)習(xí)機(jī)的泛化能力[3]，其中組合核中通常都包含有高斯核函數(shù)(Gaussian kernel function)，其核參數(shù)和懲罰參數(shù)的設(shè)定一般根據(jù)經(jīng)驗(yàn)所定，設(shè)置不當(dāng)會(huì)直接影響學(xué)習(xí)機(jī)的分類效果。對(duì)KELM參數(shù)優(yōu)化問(wèn)題，許多學(xué)者從多個(gè)角度提出了解決思路，何敏等[8]提出采用遺傳算法(genetic algorithm, GA)對(duì)KELM參數(shù)進(jìn)行優(yōu)化，Sun Hongchun等[9]提出用粒子群優(yōu)化算法(particle swarm optimization, PSO)來(lái)優(yōu)化KELM參數(shù)。PSO和GA方法是在自然進(jìn)化基礎(chǔ)上模擬個(gè)體種群的適應(yīng)性實(shí)現(xiàn)，具有簡(jiǎn)單易用等優(yōu)點(diǎn)，屬于隨機(jī)搜索優(yōu)化算法，但隨機(jī)搜索優(yōu)化算法的結(jié)果可靠性差，無(wú)法得到穩(wěn)定的解，并且不能很好解決大規(guī)模復(fù)雜問(wèn)題。蘇一丹等[10]提出的K插值單純形法來(lái)優(yōu)化KELM參數(shù)，該方法的分類精度比傳統(tǒng)的KELM平均分類精度提高了41.73%，但其只對(duì)核參數(shù)進(jìn)行了一維搜索，懲罰參數(shù)的選取依然根據(jù)經(jīng)驗(yàn)來(lái)確定，事實(shí)上懲罰參數(shù)的選取也會(huì)對(duì)KELM分類器性能和泛化能力產(chǎn)生影響，也需要優(yōu)化。

柔性多面體搜索算法[11](flexible polyhedron search algorithms, FPSA)近年出現(xiàn)多維非線性問(wèn)題優(yōu)化方法，但其初始柔性多面體設(shè)置不當(dāng)會(huì)導(dǎo)致多面體尋優(yōu)搜索收斂速度慢，陷入局部最小值。網(wǎng)格搜索算法(grid search, GS)是一種全局多維搜索方法，對(duì)初值不敏感，但全局搜索效率較柔性多面體弱，為此，本文將FPSA和GS相結(jié)合，利用兩者的優(yōu)點(diǎn)構(gòu)造最優(yōu)化算法優(yōu)化KELM的核參數(shù)和懲罰參數(shù)。首先用網(wǎng)格搜索獲取參數(shù)的初始值作為初始多面體，解決柔性多面體對(duì)初始值敏感的問(wèn)題，然后根據(jù)核極限學(xué)習(xí)機(jī)核參數(shù)和懲罰參數(shù)對(duì)分類性能影響程度的不同，給柔性多面體的變形參數(shù)中添加參數(shù)權(quán)重，通過(guò)迭代柔性多面體實(shí)現(xiàn)核極限學(xué)習(xí)參數(shù)的最優(yōu)化搜索，再用所獲最優(yōu)參數(shù)構(gòu)造最優(yōu)化核極限學(xué)習(xí)機(jī)(GSFP-KELM)。最后在UCI數(shù)據(jù)集上通過(guò)與其它同類算法相比較，驗(yàn)證所提算法的可行性。

1 核極限學(xué)習(xí)機(jī)簡(jiǎn)介

極限學(xué)習(xí)機(jī)是一種單隱藏層前饋神經(jīng)網(wǎng)絡(luò)(SLFNs)的學(xué)習(xí)算法，ELM的分類函數(shù)可表示為

f(x)=h(x)β

(1)

式中：h(xi)=[g1(xi),…,gL(xi)] 為特征映射矩陣， g(·) 為激活函數(shù)，β=[β1,…,βL]T是連接隱含層和輸出層的權(quán)重向量。極限學(xué)習(xí)機(jī)的主要訓(xùn)練目標(biāo)是計(jì)算輸出權(quán)重向量β， 即

β=H-1T

(2)

為提高ELM模型穩(wěn)定性和泛化能力，優(yōu)化輸出權(quán)重矩陣如下

(3)

式中：I是一個(gè)N維的單位矩陣，C為懲罰因子。分類函數(shù)更新為

(4)

式中：HHT被稱為ELM核矩陣，采用滿足Mercer’s條件的核函數(shù)簡(jiǎn)化ELM核矩陣的內(nèi)積計(jì)算，即

Ω=HHT;Ωi,j=h(xi)·h(xj)=K(xi,xj)

(5)

則KELM權(quán)重矩陣描述如下

(6)

相應(yīng)的KELM分類函數(shù)可使用如下公式計(jì)算

(7)

本文KELM選用的核函數(shù)為最常用的高斯核函數(shù)，其公式描述如下

(8)

式中：σ為高斯核的帶寬，也就是核參數(shù)。

綜上所述，核極限學(xué)習(xí)機(jī)存在兩個(gè)超參數(shù)，即核參數(shù)σ和懲罰參數(shù)C。σ是控制高斯核函數(shù)影響的范圍；C是用于調(diào)節(jié)訓(xùn)練樣本滿足約束條件的程度。如果兩個(gè)參數(shù)選擇不當(dāng)會(huì)影響學(xué)習(xí)機(jī)的分類性能，因此需要提供給KELM一組合適的參數(shù)組合。

2 網(wǎng)格搜索優(yōu)化柔性多面體尋優(yōu)算法

2.1 網(wǎng)格搜索優(yōu)化柔性多面體思路

首先要通過(guò)網(wǎng)格搜索算法在較大范圍內(nèi)采用大步距進(jìn)行遍歷搜索，為了給柔性多面體提供合適的初始搜索點(diǎn)，本文對(duì)核參數(shù)σ和懲罰參數(shù)C在KELM上的分類性能的影響進(jìn)行分析。如圖1所示，當(dāng)核參數(shù)σ→0時(shí)，訓(xùn)練集分類準(zhǔn)確率很高，但是構(gòu)建的分類器對(duì)測(cè)試樣本的分類效果卻很差，即產(chǎn)生了過(guò)學(xué)習(xí)狀態(tài)。隨著σ增大，測(cè)試精度逐漸提高，但σ超過(guò)一定值后訓(xùn)練精度和測(cè)試精度都逐漸下降直至趨于常數(shù)。懲罰參數(shù)C過(guò)小時(shí)KELM分類精度低，易處于欠學(xué)習(xí)狀態(tài)；隨著C逐漸增大分類精度逐漸提高并趨于穩(wěn)定。由此可見，核參數(shù)σ與懲罰參數(shù)C共同作用影響KELM分類性能，當(dāng)處于訓(xùn)練誤差為0和有足夠小的訓(xùn)練誤差交界處時(shí)測(cè)試精度較高。故初始多面體合適的范圍設(shè)置在存在一定訓(xùn)練誤差的位置。先設(shè)定目標(biāo)函數(shù)F(σi,Cj)， 即KELM訓(xùn)練誤差

(9)

式中：N為訓(xùn)練樣本總數(shù)，Perror(σi,Cj) 表示在核參數(shù)為σi以及懲罰參數(shù)為Cj時(shí)錯(cuò)誤分類的樣本數(shù)。令允許的訓(xùn)練誤差為TolFun， 默認(rèn)值設(shè)定為0.01。選取二維網(wǎng)格中滿足F(σi,Cj)>TolFun條件的網(wǎng)格點(diǎn)組合成參數(shù)集合G(σi,Cj,F(σi,Cj))。 然后再通過(guò)柔性多面體進(jìn)一步優(yōu)化。

圖1 核參數(shù)與懲罰參數(shù)在KELM上的影響

從集合G中選取合適的點(diǎn)建立初始多面體。根據(jù)Nelder-Mead定理[12]，對(duì)于雙變量函數(shù)問(wèn)題，需要構(gòu)建一個(gè)3個(gè)頂點(diǎn)的多面體，即一個(gè)三角形。初始多面體范圍設(shè)定太大或太小都會(huì)導(dǎo)致多面體收斂速度慢和易陷入局部最小值的問(wèn)題。因此本文針對(duì)網(wǎng)格范圍來(lái)優(yōu)化初始多面體設(shè)定。在集合G中選擇目標(biāo)函數(shù)值最小的參數(shù)點(diǎn)v1=(σb1,Cb2)， 對(duì)應(yīng)的網(wǎng)格坐標(biāo)為(b1,b2)。 找到該點(diǎn)的兩個(gè)參數(shù)在網(wǎng)格中前一個(gè)點(diǎn)(σb1-1,Cb2)、(σb1,Cb2-1)， 分別以v1為中心點(diǎn)計(jì)算出對(duì)稱頂點(diǎn)v2和v3， 則初始多面體定義為

Sinit=[v1T,v2T,v3T]

(10)

由圖1及上述結(jié)論來(lái)看，分類精度主要受核參數(shù)影響，懲罰參數(shù)在取一定值后趨于穩(wěn)定，而通常懲罰參數(shù)初始間距較大，如果兩個(gè)參數(shù)按照相同比例反射、擴(kuò)展、壓縮和收縮，懲罰參數(shù)會(huì)過(guò)度增大或者過(guò)度減小。本文提出采用懲罰參數(shù)與核參數(shù)的斜率比作為懲罰參數(shù)在柔性多面體變形的權(quán)重。取v1頂點(diǎn)在網(wǎng)格中縱軸方向和橫軸方向的點(diǎn)，分別擬合成二次曲線，并計(jì)算兩條曲線在v1頂點(diǎn)上的斜率，分別記為Kσ、KC。 懲罰參數(shù)權(quán)重計(jì)算為

(11)

因此，柔性多面體的變形系數(shù)權(quán)重記為w=[1wc]T。 根據(jù)原始柔性多面體變形公式更新如式(12)

vr=c+w·ρ·(c-vw) (反射Reflection)
ve=c+χ·(vr-c) (擴(kuò)張Expansion)
voc=c-γ·(vr-c) (外壓縮Outer-Contraction)
vic=c+w·γ·(c-vw) (內(nèi)壓縮Inner-Contraction)
vw=vb+w·ο·(vw-vb) (收縮Reduction)

(12)

其中，c是除去最差頂點(diǎn)vw之外剩余頂點(diǎn)的中心點(diǎn)。反射系數(shù)ρ、 擴(kuò)張系數(shù)χ、 壓縮系數(shù)γ、 收縮系數(shù)ο在Nelder-Mead中默認(rèn)值分別為ρ=1，χ=2，γ=0.5，ο=0.5[12]。

依據(jù)式(12)進(jìn)行反射、擴(kuò)張、壓縮操作獲取一個(gè)更好點(diǎn)vnew來(lái)取代最差點(diǎn)vw， 從而構(gòu)成一個(gè)新的多面體，或者通過(guò)將最差點(diǎn)vw向最好點(diǎn)vb收縮來(lái)形成新的多面體。迭代進(jìn)行上述操作，以不斷逼近最優(yōu)值，當(dāng)滿足表1終止條件[13]時(shí)停止迭代。其中，volume_ratio計(jì)算公式描述如式(13)，初值設(shè)置為1[14]

(13)

表1 迭代搜索終止條件

2.2 網(wǎng)格搜索柔性多面體算法優(yōu)化核極限學(xué)習(xí)機(jī)

核極限學(xué)習(xí)機(jī)不需要輸入核參數(shù)和懲罰參數(shù)，參數(shù)值在訓(xùn)練過(guò)程通過(guò)網(wǎng)格搜索優(yōu)化柔性多面體尋優(yōu)獲取。GSFP-KELM主要通過(guò)以下步驟實(shí)現(xiàn)：

步驟1 載入訓(xùn)練樣本和測(cè)試樣本；

步驟2 對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理；

步驟3 初始化網(wǎng)格搜索范圍與步距，用網(wǎng)格搜索算法構(gòu)造初始柔性多面體；

步驟4 設(shè)計(jì)柔性多面體變形系數(shù)權(quán)值，初始化迭代終止條件；

步驟5 通過(guò)柔性多面體迭代優(yōu)化KELM的核參數(shù)與懲罰參數(shù)；

步驟6 使用步驟5優(yōu)化的核參數(shù)和懲罰參數(shù)計(jì)算出KELM的權(quán)重矩陣，并對(duì)測(cè)試樣本進(jìn)行分類，計(jì)算出分類準(zhǔn)確率。

2.3 時(shí)間復(fù)雜度分析

網(wǎng)格搜索柔性多面體算法優(yōu)化核極限學(xué)習(xí)機(jī)執(zhí)行的時(shí)間復(fù)雜度為：首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，時(shí)間復(fù)雜度與數(shù)據(jù)樣本大小N成正比，計(jì)算時(shí)間復(fù)雜度是O(N)。 計(jì)算訓(xùn)練樣本歐式距離的時(shí)間復(fù)雜度為O(N2)。 目標(biāo)函數(shù)計(jì)算時(shí)間復(fù)雜度為O(N3)。 依次計(jì)算網(wǎng)格對(duì)應(yīng)的目標(biāo)函數(shù)值的計(jì)算時(shí)間復(fù)雜度為O(G)*O(N3)， 其中G為網(wǎng)格數(shù)。使用柔性多面體搜索最優(yōu)核參數(shù)，計(jì)算時(shí)間復(fù)雜度是O(t)*O(N3)， 其中t為柔性多面體迭代搜索次數(shù)。根據(jù)返回參數(shù)計(jì)算權(quán)重矩陣的時(shí)間復(fù)雜度為O(N3)。 計(jì)算測(cè)試樣本類別的計(jì)算時(shí)間復(fù)雜度為O(N3)。 最后計(jì)算精度計(jì)算時(shí)間復(fù)雜度為O(N)。 綜上復(fù)雜度為O(N+N2+N3+GN3+tN3+N3+N3+N)， 由此可知所提算法的計(jì)算復(fù)雜度為O(N3)。

3 仿真實(shí)驗(yàn)與分析

仿真實(shí)驗(yàn)在計(jì)算機(jī)硬件環(huán)境為Intel Pentium G640 (2.8 GHz) CPU，內(nèi)存10 GB。在Windows7 x64平臺(tái)下用MATLAB R2016a實(shí)現(xiàn)所提算法。

3.1 實(shí)驗(yàn)用數(shù)據(jù)集描述

實(shí)驗(yàn)總共使用了13個(gè)數(shù)據(jù)集，具體描述見表2。其中表中前12個(gè)標(biāo)準(zhǔn)分類數(shù)據(jù)集來(lái)源于UCI和KEEL數(shù)據(jù)儲(chǔ)存庫(kù)。表中最后1個(gè)來(lái)源于人工數(shù)據(jù)集。

表2 數(shù)據(jù)集

3.2 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證本文算法的可行性，實(shí)驗(yàn)結(jié)果與近年幾種常見智能優(yōu)化核極限學(xué)習(xí)機(jī)算法相比較：遺傳算法核極限學(xué)習(xí)機(jī)(GA-KELM)[8]、粒子群核極限學(xué)習(xí)機(jī)(PSO-KELM)[9]、K插值單純形核極限學(xué)習(xí)機(jī)(KS-KELM)[10]。使用5-fold交叉驗(yàn)證方式比較4種方法優(yōu)化的核極限學(xué)習(xí)機(jī)分類性能，并計(jì)算5次驗(yàn)證的平均測(cè)試精度和標(biāo)準(zhǔn)偏差。將網(wǎng)格搜索中核參數(shù)范圍設(shè)置為 [2-2,2-1,…,28]， 懲罰參數(shù)范圍設(shè)置為 [20,21,…,210]。

3.3 實(shí)驗(yàn)結(jié)果及分析

4種算法的計(jì)算結(jié)果見表3，表中 (σ,C) 項(xiàng)表示該算法所獲的最優(yōu)化核參數(shù)和懲罰參數(shù)；“準(zhǔn)確率”項(xiàng)是5-fold交叉驗(yàn)證的平均分類精度與標(biāo)準(zhǔn)偏差。

從表3可以看出，與GA-KELM、PSO-KELM和KS-KELM相比，本文提出的GSFP-KELM在上述數(shù)據(jù)集上都有非常好的表現(xiàn)。例如，在vehicle、wine、fertility數(shù)據(jù)集上，其它3種方法所獲取的核參數(shù)和懲罰參數(shù)都偏小，而KS-KELM由于懲罰參數(shù)受限制，所訓(xùn)練出來(lái)的核參數(shù)也相對(duì)偏小。此外，GA-KELM和PSO-KELM在對(duì)數(shù)據(jù)集ovlivetti進(jìn)行訓(xùn)練分類時(shí)均能達(dá)到100%的準(zhǔn)確率，但是在對(duì)測(cè)試集分類時(shí)準(zhǔn)確率卻很低，明顯出現(xiàn)了過(guò)擬合現(xiàn)象。而本文提出的GSFP-KELM能得出有效的測(cè)試準(zhǔn)確度。GSFP-KELM的分類精度較GA-KELM平均提高了13.61%，較PSO-KELM平均提高了7.75%，較KS-KELM平均提高了11.52%。因此，本文提出的用網(wǎng)格搜索柔性多面體算法來(lái)優(yōu)化KELM的最優(yōu)核參數(shù)以及懲罰參數(shù)是可行的。

網(wǎng)格搜索優(yōu)化柔性多面體與傳統(tǒng)柔性多面體分別在13個(gè)數(shù)據(jù)集上的運(yùn)行5-fold交叉驗(yàn)證的平均收斂迭代次數(shù)對(duì)比如圖2所示，以及平均評(píng)估目標(biāo)函數(shù)的次數(shù)對(duì)比如圖3所示。在數(shù)據(jù)集thyroid、seeds、wine和fertility上，傳統(tǒng)的柔性多面體平均迭代次數(shù)均達(dá)到了最高迭代次數(shù)，即迭代搜索陷入了局部最小值，產(chǎn)生無(wú)效的迭代而無(wú)法收斂。如圖2可以看出，本文提出的網(wǎng)格搜索優(yōu)化柔性多面體能有效避免多面體搜索陷入無(wú)效迭代過(guò)程，并且總體上網(wǎng)格搜索優(yōu)化柔性多面體收斂速度更快，能更好的逼近目標(biāo)值。如圖2和圖3可見，迭代次數(shù)與評(píng)估次數(shù)成正比，每迭代一次將至少進(jìn)行5次目標(biāo)函數(shù)的計(jì)算。傳統(tǒng)的柔性多面體則可能進(jìn)行最多8次目標(biāo)函數(shù)計(jì)算，而網(wǎng)格搜索柔性多面體最多進(jìn)行6次目標(biāo)函數(shù)計(jì)算，減少了目標(biāo)函數(shù)的計(jì)算次數(shù)。在本次實(shí)驗(yàn)中，網(wǎng)格搜索柔性多面體比傳統(tǒng)柔性多面體平均迭代次數(shù)平均減少了8.6次，平均評(píng)估次數(shù)平均減少了41.1次。因此結(jié)合網(wǎng)格搜索的初始多面體能更快的收斂，減少了無(wú)效迭代的次數(shù)，有效提高了訓(xùn)練效率。

表3 與GA-KELM、PSO-KELM和GS-KELM之間的對(duì)比：分類精度與標(biāo)準(zhǔn)偏差

圖2 網(wǎng)格搜索優(yōu)化柔性多面體法收斂迭代次數(shù)對(duì)比

圖3 網(wǎng)格搜索優(yōu)化柔性多面體法評(píng)估次數(shù)對(duì)比

表4是本文算法與近幾年出現(xiàn)的一些極限學(xué)習(xí)機(jī)算法的分類精度比較，分別是基于文化基因算法的極限學(xué)習(xí)機(jī)(M-ELM)[15]、實(shí)例克隆極限學(xué)習(xí)機(jī)(IC-ELM)[16]、基于多目標(biāo)優(yōu)化的稀疏極限學(xué)習(xí)機(jī)算法(MO-SELM)[17]。相關(guān)比較算法的分類精度取自對(duì)應(yīng)的文獻(xiàn)，表中的“—”符號(hào)表示對(duì)比的算法文獻(xiàn)中未給出該數(shù)據(jù)集的結(jié)果。從表4可看出，在數(shù)據(jù)集(segment、vowel、wilt、satellite、letter)上本文算法GSFP-KELM的分類性能均優(yōu)于其它3種算法。而在數(shù)據(jù)集iris略低于M-ELM算法，但偏差相對(duì)較小，說(shuō)明了本文提出的網(wǎng)格搜索柔性多面體算法優(yōu)化的核極限學(xué)習(xí)機(jī)是可行的。

表4 4種極限學(xué)習(xí)機(jī)的分類精度對(duì)比

4 結(jié)束語(yǔ)

本文提出了一種基于網(wǎng)格搜索柔性多面體算法的自適應(yīng)核極限學(xué)習(xí)機(jī)方法。首先使用網(wǎng)格搜索算法在全局范圍內(nèi)分析核極限學(xué)習(xí)機(jī)參數(shù)集的合適的范圍，再通過(guò)結(jié)合網(wǎng)格優(yōu)化的多面體對(duì)核極限學(xué)習(xí)機(jī)進(jìn)行局部搜索，將訓(xùn)練的參數(shù)集與核極限學(xué)習(xí)機(jī)結(jié)合為訓(xùn)練模型。實(shí)驗(yàn)與對(duì)比結(jié)果表明，GSFP-KELM具有很好的分類能力，避免了一定程度的過(guò)擬合問(wèn)題，提高了泛化能力。通過(guò)優(yōu)化的柔性多面體算法較傳統(tǒng)的柔性多面體算法收斂速度更快，變換適應(yīng)能力更強(qiáng)。