基于柔性多面體的最優核極限學習機算法

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

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

0 引 言

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

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

1 核極限學習機簡介

極限學習機是一種單隱藏層前饋神經網絡(SLFNs)的學習算法，ELM的分類函數可表示為

f(x)=h(x)β

(1)

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

β=H-1T

(2)

為提高ELM模型穩定性和泛化能力，優化輸出權重矩陣如下

(3)

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

(4)

式中：HHT被稱為ELM核矩陣，采用滿足Mercer’s條件的核函數簡化ELM核矩陣的內積計算，即

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

(5)

則KELM權重矩陣描述如下

(6)

相應的KELM分類函數可使用如下公式計算

(7)

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

(8)

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

綜上所述，核極限學習機存在兩個超參數，即核參數σ和懲罰參數C。σ是控制高斯核函數影響的范圍；C是用于調節訓練樣本滿足約束條件的程度。如果兩個參數選擇不當會影響學習機的分類性能，因此需要提供給KELM一組合適的參數組合。

2 網格搜索優化柔性多面體尋優算法

2.1 網格搜索優化柔性多面體思路

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

(9)

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

圖1 核參數與懲罰參數在KELM上的影響

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

Sinit=[v1T,v2T,v3T]

(10)

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

(11)

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

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

(12)

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

依據式(12)進行反射、擴張、壓縮操作獲取一個更好點vnew來取代最差點vw， 從而構成一個新的多面體，或者通過將最差點vw向最好點vb收縮來形成新的多面體。迭代進行上述操作，以不斷逼近最優值，當滿足表1終止條件[13]時停止迭代。其中，volume_ratio計算公式描述如式(13)，初值設置為1[14]

(13)

表1 迭代搜索終止條件

2.2 網格搜索柔性多面體算法優化核極限學習機

核極限學習機不需要輸入核參數和懲罰參數，參數值在訓練過程通過網格搜索優化柔性多面體尋優獲取。GSFP-KELM主要通過以下步驟實現：

步驟1 載入訓練樣本和測試樣本；

步驟2 對數據集進行預處理；

步驟3 初始化網格搜索范圍與步距，用網格搜索算法構造初始柔性多面體；

步驟4 設計柔性多面體變形系數權值，初始化迭代終止條件；

步驟5 通過柔性多面體迭代優化KELM的核參數與懲罰參數；

步驟6 使用步驟5優化的核參數和懲罰參數計算出KELM的權重矩陣，并對測試樣本進行分類，計算出分類準確率。

2.3 時間復雜度分析

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

3 仿真實驗與分析

仿真實驗在計算機硬件環境為Intel Pentium G640 (2.8 GHz) CPU，內存10 GB。在Windows7 x64平臺下用MATLAB R2016a實現所提算法。

3.1 實驗用數據集描述

實驗總共使用了13個數據集，具體描述見表2。其中表中前12個標準分類數據集來源于UCI和KEEL數據儲存庫。表中最后1個來源于人工數據集。

表2 數據集

3.2 實驗設計

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

3.3 實驗結果及分析

4種算法的計算結果見表3，表中 (σ,C) 項表示該算法所獲的最優化核參數和懲罰參數；“準確率”項是5-fold交叉驗證的平均分類精度與標準偏差。

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

網格搜索優化柔性多面體與傳統柔性多面體分別在13個數據集上的運行5-fold交叉驗證的平均收斂迭代次數對比如圖2所示，以及平均評估目標函數的次數對比如圖3所示。在數據集thyroid、seeds、wine和fertility上，傳統的柔性多面體平均迭代次數均達到了最高迭代次數，即迭代搜索陷入了局部最小值，產生無效的迭代而無法收斂。如圖2可以看出，本文提出的網格搜索優化柔性多面體能有效避免多面體搜索陷入無效迭代過程，并且總體上網格搜索優化柔性多面體收斂速度更快，能更好的逼近目標值。如圖2和圖3可見，迭代次數與評估次數成正比，每迭代一次將至少進行5次目標函數的計算。傳統的柔性多面體則可能進行最多8次目標函數計算，而網格搜索柔性多面體最多進行6次目標函數計算，減少了目標函數的計算次數。在本次實驗中，網格搜索柔性多面體比傳統柔性多面體平均迭代次數平均減少了8.6次，平均評估次數平均減少了41.1次。因此結合網格搜索的初始多面體能更快的收斂，減少了無效迭代的次數，有效提高了訓練效率。

表3 與GA-KELM、PSO-KELM和GS-KELM之間的對比：分類精度與標準偏差

圖2 網格搜索優化柔性多面體法收斂迭代次數對比

圖3 網格搜索優化柔性多面體法評估次數對比

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

表4 4種極限學習機的分類精度對比

4 結束語

本文提出了一種基于網格搜索柔性多面體算法的自適應核極限學習機方法。首先使用網格搜索算法在全局范圍內分析核極限學習機參數集的合適的范圍，再通過結合網格優化的多面體對核極限學習機進行局部搜索，將訓練的參數集與核極限學習機結合為訓練模型。實驗與對比結果表明，GSFP-KELM具有很好的分類能力，避免了一定程度的過擬合問題，提高了泛化能力。通過優化的柔性多面體算法較傳統的柔性多面體算法收斂速度更快，變換適應能力更強。