基于改進烏鴉搜索算法的極限學習機分類方法

霍閃閃,蘇 兵,王章權,孫 萍

(1. 常州大學計算機與人工智能學院,江蘇 常州 213164;2. 浙江樹人大學信息科技學院,浙江 杭州 310015)

1 引言

經過幾十年的發展,神經網絡理論在人工智能等研究領域取得了廣泛的成功。其中,極限學習機(Extreme Learning Machine,ELM)[1]因其良好的插值能力[2]、通用逼近能力[3]和分類能力[4]而被廣泛地應用于疾病診斷、交通標志識別、圖像質量評估等多個領域。不同于傳統神經網絡,ELM在訓練前只需設置隱含層神經元個數,通過隨機生成連接輸入層和隱含層之間的輸入權重和隱含層神經元閾值,求解Moore-Penrose廣義逆運算就能得到最優輸出權重,極大地提高了算法的收斂速度[5]。但是ELM隨機生成輸入權重和閾值的方法導致部分隱含層神經元的作用很小,從訓練樣本中提取的信息不足以概括和反映數據的內在規律從而出現欠擬合問題,為解決欠擬合問題需要采用更多的隱含層神經元個數[6],在降低響應速度的同時增加了計算復雜度和內存消耗[7],因此需要對ELM輸入權重和閾值兩個參數進行優化改進[8],以實現網絡模型優化。

目前常用群智能優化算法[9]、增量法和剪枝法去優化ELM模型,但增量法和剪枝法針對如何設計合適隱含層神經元個數選取準則、閾值選取準則等沒有固定規律可循,導致得到的ELM模型不夠稀疏,因此所提算法采用群智能優化算法去改進ELM模型。

針對ELM參數優化問題,Zhao等人[10]利用改進布谷鳥搜索算法對ELM中的輸入權重和隱含層閾值進行優化,并對一些預測問題進行了研究,取得了較為理想的預測結果。Zhang等人[11]利用人工蜂群算法優化ELM的隱含層神經元個數。Zhu等人[12]利用混沌搜索策略鯨魚優化算法優化ELM的隱含層神經元個數。上述論文均利用群智能優化算法對ELM隱含層的神經元參數進行尋優,減少了隱含層冗余神經元,提高模型穩定性,但同時引入了大量需要被優化的超參數,增加了算法的計算復雜度[13],削弱了ELM訓練速度快的優勢。

2016年伊朗學者Askarzadeh提出的烏鴉搜索算法(Crow Search Algorithm,CSA)[14]在全局搜索性能方面優于其它優化算法,并且CSA與GA、PSO等優化算法相比,只需要設置飛行長度(flight length,fl)和感知概率(Awareness Probability,AP)兩個參數,相對消耗更少的計算時間,具有靈活性強、精度高且易于實現等優點[15],適合于ELM模型優化[16]。標準CSA算法通過位置迭代更新來獲得烏鴉個體最優藏食位置,達到模型參數尋優的目的。為了保證具有較好尋優性能,要求在位置迭代更新前期,算法具有較好的全局搜索性能,避免陷入局部最優;在位置迭代更新后期,算法具有較好局部搜索性能,提高收斂速度。Shi等人[17]通過引入自適應慣性權重,在算法前期使用較大慣性權重增強全局搜索性能,在后期減小慣性權重避免過度搜索,提高收斂性能。Khalilpourazari 等人[18]引入正弦余弦局部優化算子,在全局遵循最優解優先規則,避免陷入局部最優,并設定特定的烏鴉移動方式,在局部提高收斂性能。上述算法通過引入額外的參數來優化模型的全局和局部搜索性能,但均使用固定AP值的選擇搜索機制,而AP值直接影響搜索機制搜索性能(AP值較大,模型趨向全局搜索;AP值較小,模型趨向局部搜索),基于固定AP值的搜索方法難以滿足CSA位置迭代更新的要求。

綜上,本文提出一種基于改進烏鴉搜索算法的極限學習機分類算法:提出基于參數動態遞變的優化烏鴉位置迭代更新方法,設計AP值動態遞變函數,使得AP值在迭代前期保持較大值,保證算法可以趨向全局搜索,而隨迭代過程逐漸減小,保證算法在迭代后期可以趨向局部搜索;并在全局搜索過程中,提出采用萊維飛行搜索方法替換傳統的隨機位置搜索方法,避免了盲目搜索,提高收斂速度,并在局部搜索過程中,提出采用多個體變因子加權學習方法,使用多個體學習方法代替傳統的單個體學習方法,增強了種群多樣性,提高局部極值逃逸能力。提出一種基于鄰代維度交叉的最優個體更新方法,通過綜合歷代最優解維度信息實現較好分量的最大化保留,通過計算適應度值實現最優迭代位置更新,相比僅考慮相鄰兩代信息實現最優迭代位置更新的方法,提高了最優個體藏食位置質量,增強算法尋優性能。

2 基于改進烏鴉搜索算法的極限學習機

2.1 極限學習機模型

作為一種求解單隱含層神經網絡訓練框架[19],ELM網絡結構與單隱層前饋神經網絡(Single Layer Feedforward Neural Network,SLFN)一樣,只是在訓練階段不再采用基于梯度下降的算法(后向傳播),而是隨機生成輸入權重和閾值,采用Moore-Penrose(MP)廣義逆矩陣理論計算輸出權重。理論研究表明,ELM隨機生成輸入權重和隱含層閾值的方法,使其具有極快學習速度的同時仍保持SLFN的通用逼近能力。ELM網絡結構如圖1所示。

圖1 ELM網絡結構圖

訓練ELM模型時,設定訓練集為{Xi,ti|Xi∈RD,ti∈Rm,i=1,2,…,N}(Xi表示第i個樣本,ti表示第i個樣本對應的標記,N為輸入樣本數量,D、L、M分別為神經網絡輸入層、隱含層和輸出層的節點數量,wi為連接輸入層與隱含層之間的輸入權重,bi為隱含層閾值,βi為連接隱含層與輸出層之間的輸出權重。ELM訓練分為兩個階段:隨機特征映射和線性參數求解:

1)隨機特征映射:隨機生成輸入權重wi和閾值bi,采用非線性映射激活函數將輸入數據映射到隱含層,獲得隱含層輸出矩陣H,計算公式為

H(x)=[h1(x),h2(x),…,hL(x)]

(1)

hi(x)=g(wix+bi),wi∈RD,bi∈R

(2)

其中H(x)=[h1(x),h2(x),…,hL(x)]是經由上述非線性映射獲得的隱含層輸出矩陣,hi(x)是第i個隱含層節點的輸出,g(·)是非線性激活函數,一般使用Sigmoid函數,Sigmoid函數映射圖像如圖2所示

圖2 Sigmoid函數曲線圖

g(x)=(1+exp(-(wTx+b)))-1

(3)

2)線性參數求解:“廣義”的單隱含層前饋神經網絡ELM的輸出fL(x)是:

其中T為目標輸出矩陣。

(4)

(5)

采用Moore-Penrose(MP)廣義逆矩陣方法可以推導出輸出權重β的值為

(6)

其中H?為輸出矩陣H的逆矩陣。

2.2 基于改進烏鴉搜索算法的極限學習機

基于改進烏鴉搜索算法的極限學習機(ICSA-ELM)用改進烏鴉搜索算法(ICSA)對ELM的輸入權重w和閾值b進行尋優,通過將w和b作為ICSA算法的藏食位置實現參數的最佳取值。主要內容包括:基于參數動態遞變的優化烏鴉位置迭代更新方法和基于鄰代維度交叉的最優個體更新方法,前者通過保持全局和局部搜索性能的平衡,避免局部極值,提高收斂速度;后者通過綜合歷代維度信息改善最優個體質量,增強算法尋優性能。

2.2.1 基于參數動態遞變的優化烏鴉位置迭代更新方法

首先設計AP值動態遞變函數,滿足ICSA位置迭代更新的要求;在全局搜索過程中,采用萊維飛行搜索方法,提高收斂速度;在局部搜索過程中,采用多個體變因子加權學習方法,增強了種群多樣性,增強局部最優值逃逸能力。

1)AP值動態遞變函數

為了滿足CSA位置迭代更新的要求,需要動態調整感知概率AP值,使其滿足凸型遞減曲線形狀,構造基于迭代次數動態遞變的AP函數,數學表達為

(7)

其中iter為迭代次數。

2)萊維飛行搜索方法

在位置迭代更新過程中,當烏鴉j感知到被烏鴉i跟蹤時(即在r

(8)

(9)

其中α為步長縮放因子,控制烏鴉i搜索范圍;rα為區間(0,1)區間內的隨機數;γ、σ服從標準正態分布;Γ(x)=(x-1)!;s為取值范圍在[1, 2]之間的常數,xi,iter+1為烏鴉i在第iter+1次迭代下的個體最優藏食位置。

3)多個體變因子加權學習方法

在位置迭代更新過程中,當烏鴉j未感知到被烏鴉i跟蹤時(即在r>AP狀態下),烏鴉i會跟隨烏鴉j飛行,即執行局部搜索。采用多個體變因子加權學習方法,確保子代烏鴉可以同時向多個烏鴉個體學習,提高種群多樣性,避免陷入局部最優,相應數學表達為

xi,iter+1=xi,iter+ri(1,d)×fli,iter×

(λitermj,iter+(1-λiter)biter-1-xi,iter),rj≥APj,iter

(10)

λ=λmax-(iter×(λmax-λmin)/itermax)

(11)

其中ri(1,d)是區間[0,1]之間的d維隨機變量,λiter為第iter次迭代時的加權學習因子,biter-1為第iter-1代種群的最佳藏食位置,rj為烏鴉j在區間(0,1)之間的隨機數。

2.1.2 基于鄰代維度交叉的個體最優藏食位置更新方法

在位置迭代更新過程中得到的當代個體藏食位置由于受到部分變量影響,導致表現出較差適應度值無法進行更新替代,引入鄰代維度交叉方法,通過綜合歷代最優解的不同維度信息,提高最優個體藏食位置質量,增強算法尋優性能,相應的數學表達為

(12)

h=1,2,…,?Rcross×d」

(13)

3 ICSA-ELM算法實現

ICSA-ELM算法的具體流程如下,流程圖如圖3所示:

圖3 ICSA-ELM算法流程圖

步驟1:構建ELM模型,定義ICSA算法和ELM模型相關參數。隨機初始化N個初始解(烏鴉的位置),生成的初始解維數為L×(n+1),第一個維數為L×n,表示輸入權重,剩下的L維表示隱含層閾值。

步驟2:利用步驟1得到的解在訓練數據集上訓練ELM模型,計算每個解的適應度值和最佳位置,根據遞變規則構造AP值動態遞變函數,迭代更新ICSA參數。

步驟3:種群中所有烏鴉個體隨機選擇不同烏鴉跟隨,采用萊維飛行搜索方法和多個體變因子加權學習方法,在跟隨烏鴉的同時利用感知到的父代最優藏食位置生成自身藏食位置,并計算當前種群適應度值,檢查新位置可行性,獲得當前迭代最優解。

步驟4:采用鄰代維度交叉方法計算并排序解之間的維度差異,保留歷代最優維度,獲得最優個體位置。

步驟5:判斷算法是否達到最大迭代次數,如果滿足,將獲得的個體最優藏食位置作為ELM模型的輸入權重和閾值去訓練ELM模型;否則,返回步驟3繼續運行算法。

4 算法仿真與分析

4.1 算法仿真環境

為了減小隨機性帶來的影響,在每次驗證ICSA-ELM性能實驗中對所有測試進行50次,以提高算法穩健性。

種群進化最大迭代次數itermax設置為50,種群規模nPop設置為20,飛行長度fl為2,最大感知概率APmax為0.5, 加權學習因子λ遞變區間為[0.05,0.95],維度交叉比例Rcross為0.3,步長縮放因子α為0.01,常數s為1.5,隱含層神經元個數范圍設置為[5,40],步長為5。選取訓練集數據分類精度、測試集數據分類精度和標準差作為ICSA-ELM性能評估標準,評估指標均采用平均值進行計算評估。

4.2 ICSA算法性能分析

為驗證文中所提ICSA算法性能,選取基準測試函數中的F8、F10兩個測試函數進行驗證測試,并與標準CSA算法結果進行對比分析,實驗結果如圖4所示。由實驗結果可知,在相同約束條件下,在單峰測試函數尋優過程中ICSA算法具有更好的收斂速度和局部極值逃逸能力。

圖4 平均迭代對比尋優

4.3 ICSA-ELM算法性能分析

為驗證文中所提ICSA-ELM算法性能,選擇UCI機器學習數據庫中的Iris、Diabetes、Breast Cancer和Cleveland Heart四個數據集進行測試驗證。算法性能分析包括收斂性分析和分類測試結果分析。

4.3.1 收斂性分析

選取常用的優化算法(PSO,DE,CSA)對ELM進行優化,在四個數據集上計算不同隱含層數目下的ELM模型收斂時間,結果如圖5所示。由實驗結果可知,隨著隱含層神經元個數的增加,ELM網絡模型結構越復雜,計算復雜度越高,收斂時間越長。通過收斂時間對比可以發現,提出的ICSA算法與DE算法相比,在相同條件下收斂速度平均提高了5.5秒時間;與PSO優化算法相比,收斂速度平均提高了2.5秒時間;與傳統CSA算法相比,收斂速度與其相差平均為1.5秒,有時甚至可以忽略不計。實驗結果表明ICSA-ELM在進行分類操作時具有較好的收斂速度,一定程度上提升了算法效率。

圖5 收斂速度對比分析

圖6 不同數據集在不同隱含層神經元個數條件下的分類精度

4.3.2 分類測試結果分析

選取常用的優化算法(PSO、CSA、MCSA)對不同隱含層數目的ELM進行優化,在四個數據集上進行分類測試。表1、表2、表3、表4顯示了在隱含層神經元個數為20的分類測試結果。實驗結果表明,無論在訓練集上還是測試集上ICSA-ELM算法的分類精度和標準差都是最好的,具有較好的泛化性能和穩定性。ICSA-ELM算法與MCSA-ELM算法相比,分類精度平均提高了1.1%,標準差平均減小了34%;ICSA-ELM算法與CSA-ELM算法相比,分類精度平均提高了1.8%,標準差平均減小了34%;與PSO-ELM算法相比,分類精度平均提高了2.3%,標準差平均減小了57%;與ELM算法相比,分類精度平均提高了4.5%,標準差平均減小了77%。

表1 Iris數據集測試結果的比較

表2 Diabetes數據集測試結果的比較

表3 Breast Cancer數據集測試結果的比較

表4 Cleveland Heart數據集測試結果的比較

圖5顯示了不同隱含層神經元個數下的分類測試結果,實驗結果表明,隨著隱含層個數的增加,算法分類精度會有一定程度的提高,但是當增加到一定程度時,分類精度會有所降低或基本保持不變。ICSA-ELM算法與其它算法相比,分類精度波動最小,具有更好的穩定性。

5 結論

本文分析了ELM模型性能和相關缺陷,通過ICSA尋優搜索出ELM模型最佳輸入權重和閾值,解決ELM隨機生成隱含層參數帶來的欠擬合問題。ICSA算法通過在算法迭代前期引入AP值動態遞變函數平衡全局和局部搜索性能,在位置更新過程中引入萊維飛行搜索和多個體變因子加權學習避免盲目搜索,提高種群多樣性,在最優位置選擇過程中引入鄰代維度交叉方法提高藏食位置質量,實現ELM模型最佳參數選取,從而提高模型分類精度。為評估算法性能,在UCI經典分類數據集上進行實驗驗證,實驗結果表明該算法具有更好的分類效果和泛化性能。