一種適用于物聯(lián)網(wǎng)的在線GP-ELM算法

張 杰,沈蘇彬

(南京郵電大學(xué) 計算機學(xué)院,南京 210046)

0 概述

自從極限學(xué)習(xí)機(Extreme Learning Machine,ELM)被提出以來,由于其具有泛化能力強、訓(xùn)練時間短的優(yōu)點,受到了許多學(xué)者的關(guān)注。文獻[1]證明了ELM的一致逼近性并將ELM直接應(yīng)用于回歸與多分類問題[2]。為處理非平衡數(shù)據(jù)的學(xué)習(xí)問題,文獻[3]通過引入類別權(quán)值,提出了加權(quán)極限學(xué)習(xí)機(W-ELM)。文獻[4]提出的在線序列極限學(xué)習(xí)機(OS-ELM),將ELM延伸至在線學(xué)習(xí)問題,拓寬其實際應(yīng)用范圍。目前,ELM在語音識別[5]、電力系統(tǒng)[6]等領(lǐng)域已得到初步應(yīng)用。

作為一種新興技術(shù),ELM在回歸和分類應(yīng)用中表現(xiàn)出良好的性能,具有較高的運行速度和較好的通用性,但為探索ELM在現(xiàn)實問題中的普遍適用性,需要確定用于解決特定任務(wù)的最合適的網(wǎng)絡(luò)架構(gòu)。ELM與批量學(xué)習(xí)方案[7]以及在線順序?qū)W習(xí)方案[8]是以固定網(wǎng)絡(luò)規(guī)模開發(fā)的,搜索這種固定網(wǎng)絡(luò)大小的常用方法是通過反復(fù)實驗。該方法簡單明了,但計算成本高,不能保證所選擇的網(wǎng)絡(luò)規(guī)模接近最優(yōu)。文獻[9]提出增量ELM(I-ELM)算法,其中隱藏節(jié)點被逐一隨機添加,并且當(dāng)添加新的隱藏節(jié)點時,現(xiàn)有隱藏節(jié)點的輸出權(quán)重被凍結(jié),證明了I-ELM的通用逼近能力。凸面I-ELM(CI-ELM)[10]采用另一種源于巴倫凸優(yōu)化概念的增量方法。當(dāng)添加新的隱藏節(jié)點時,這種方法允許適當(dāng)?shù)卣{(diào)整現(xiàn)有隱藏節(jié)點的輸出權(quán)重。在這種情況下,CI-ELM可以實現(xiàn)比I-ELM更快的收斂速度,同時保留I-ELM的簡單性。在I-ELM和CI-ELM的學(xué)習(xí)過程中,一些新添加的隱藏節(jié)點僅在網(wǎng)絡(luò)的最終輸出中起很小的作用,因此可能增加網(wǎng)絡(luò)復(fù)雜性。為避免上述問題并獲得更緊湊的網(wǎng)絡(luò)架構(gòu),文獻[11]提出增強型I-ELM(EI-ELM)算法。在EI-ELM的每個學(xué)習(xí)步驟中,隨機生成若干隱藏節(jié)點,并且僅將導(dǎo)致最大殘余誤差減少的節(jié)點添加到現(xiàn)有網(wǎng)絡(luò)。此外,EI-ELM還將I-ELM擴展到通用SLFN。文獻[12]在SAP-ELM 算法的基礎(chǔ)上,結(jié)合L2正則化因子和奇異值分解 (SVD),提出一種改進 的SAP-ELM (ImSAP-ELM)算法以提高預(yù)測精度和數(shù)值穩(wěn)定性。文獻[13]對靈敏度進行修正,提出更符合實際需求的神經(jīng)網(wǎng)絡(luò)剪枝算法IS-ELM。

文獻[14]提供一種誤差最小化ELM(EM-ELM)方法。該方法允許逐個或逐組添加隨機隱藏節(jié)點(具有不同的大小)。此外,EM-ELM在網(wǎng)絡(luò)增長期間遞增地更新輸出權(quán)重,降低了計算復(fù)雜度。然而,在所有上述建設(shè)性ELM的實現(xiàn)中,隱藏節(jié)點的數(shù)量隨著學(xué)習(xí)進度和最終數(shù)量單調(diào)增加,隱藏節(jié)點的數(shù)量相當(dāng)于學(xué)習(xí)步驟。如果需要進行許多迭代步驟,最終將獲得大量隱藏節(jié)點,而一些隱藏節(jié)點可能在網(wǎng)絡(luò)輸出中起很小的作用。文獻[15]基于和聲搜索算法優(yōu)化極限學(xué)習(xí)機的方法,結(jié)合了和聲搜索算法和極限學(xué)習(xí)機兩者的優(yōu)勢,利用和聲搜索算法調(diào)整極限學(xué)習(xí)機的輸入權(quán)值和隱含層閾值,避免了隨機設(shè)定無效節(jié)點而導(dǎo)致預(yù)測效果不穩(wěn)定、泛化能力較差等問題。文獻[16]提出了一種新的隱含層節(jié)點的選擇算法SHN-ELM。通過對隱含層節(jié)點的選擇,提高了ELM 算法的穩(wěn)定性和分類準(zhǔn)確率。文獻[17]提出了以粒子群優(yōu)化算法搜索ELM隱藏層最佳神經(jīng)元個數(shù),用極限學(xué)習(xí)機模型的測試準(zhǔn)確率作為粒子群優(yōu)化算法適應(yīng)值。文獻[18]提出了一種P-ELM算法,通過統(tǒng)計方法去除不相關(guān)或相關(guān)性較低的隱藏節(jié)點,系統(tǒng)地確定學(xué)習(xí)過程中隱藏節(jié)點的數(shù)量,但是這樣的方法卻無法自動地完成。文獻[19]設(shè)計了一種基于 EFAST 的隱藏層節(jié)點剪枝算法(FOS-ELM),利用傅里葉敏感度測試方法對 OS-ELM 的隱藏節(jié)點進行分析,能適用于剪枝后的網(wǎng)絡(luò)參數(shù)調(diào)整算法。文獻[20]針對隱藏節(jié)點數(shù)量影響ELM泛化性能的問題,提出一種SRM-ELM算法。SRM-ELM在結(jié)構(gòu)風(fēng)險最小化原則下,建立隱藏節(jié)點數(shù)與泛化能力的關(guān)系函數(shù),利用PSO簡單高效的全局搜索能力,優(yōu)化ELM的隱藏節(jié)點數(shù),避免了傳統(tǒng)方法反復(fù)進行調(diào)節(jié)實驗的繁瑣。但是上述算法耗時比較長,不適用于物聯(lián)網(wǎng)的特性。為此,本文提出一種適合物聯(lián)網(wǎng)的在線GP-ELM算法。該算法能夠在添加多個節(jié)點的同時進行剪枝、刪減節(jié)點,以提高ELM的準(zhǔn)確性。

1 極限學(xué)習(xí)機及其相關(guān)理論

1.1 極限學(xué)習(xí)機

在ELM中,只需要預(yù)先確定隱藏神經(jīng)元的數(shù)量,而隱藏神經(jīng)元的參數(shù)(如RBF節(jié)點的中心和影響因子或附加節(jié)點的偏差和輸入權(quán)重)是隨機分配的。因此,給出如下ELM預(yù)測公式:

(1)

其中,β=[β1,β2,…,βk]是連接隱藏層和輸出層的輸出權(quán)重的向量,H(X)=[H1(X),H2(X),…,Hk(X)]是隱藏層相對于樣本X的輸出。 根據(jù)Bartlett理論,對于訓(xùn)練誤差較小的神經(jīng)網(wǎng)絡(luò),權(quán)重范數(shù)越小,網(wǎng)絡(luò)的泛化性能越可能更好,因此,將訓(xùn)練誤差與輸出權(quán)重的范數(shù)最小化:

(2)

其中,H是隱藏層的輸出矩陣:

(3)

并且:

(4)

將最小范數(shù)最小二乘法用于經(jīng)典ELM的原始實現(xiàn)中,即:

β=H?T

(5)

其中,H?是H的Moore-Penrose廣義逆,即偽逆。

如果使用標(biāo)準(zhǔn)優(yōu)化方法,則基于約束優(yōu)化的ELM可以寫成:

受限于:

ξ=T-Hβ

(6)

根據(jù)KKT條件,可以通過以下雙重優(yōu)化來解決:

(7)

其中,αi∈α=[α1,α2,…,αN]對應(yīng)于訓(xùn)練樣本的拉格朗日乘數(shù)。KKT最佳條件如下:

(8)

(9)

(10)

根據(jù)訓(xùn)練集的大小可以實現(xiàn)不同的解決方案:

1)訓(xùn)練樣本數(shù)量很大的情況

如果訓(xùn)練數(shù)據(jù)N的數(shù)量非常大,如比特征空間L的維數(shù)大得多,即N> >L,則以下解決方案是優(yōu)選的。

(11)

在這種情況下,ELM的輸出函數(shù)為:

(12)

2)訓(xùn)練樣本數(shù)量少的情況

在這種情況下,通過將式(8)、式(9)代入式(10),可以等效地將式(11)、式(12)寫為:

(13)

由式(4)～式(8),有:

(14)

ELM的輸出方程為:

(15)

1.2 EM-ELM算法

EM-ELM是一種簡單而有效的算法,可以逐個或逐組地隨機添加隱藏節(jié)點。在網(wǎng)絡(luò)增長期間,基于誤差最小化方法遞增地更新輸出權(quán)重。

(16)

可以等效地以矩陣形式表示:

Hβ=T

(17)

其中:

(18)

(19)

其中,H?是H的Moore-Penrose廣義逆,即偽逆。

(20)

(21)

(22)

其中:

(23)

然后計算β2:

(24)

同樣,輸出權(quán)重可以逐步更新為:

(25)

1.3 在線序列學(xué)習(xí)機

訓(xùn)練數(shù)據(jù)可以在實際應(yīng)用中逐塊或逐個(塊的特殊情況)到達。在線序列學(xué)習(xí)機(OS-ELM)算法針對在線學(xué)習(xí)案例,并在短時間內(nèi)不斷更新輸出權(quán)重。

當(dāng)新的采樣數(shù)據(jù)到來時,ELM的數(shù)學(xué)模型應(yīng)該被修改為:

(26)

其中,δH和δT是新生成的隱藏層輸出矩陣,使用當(dāng)前學(xué)習(xí)參數(shù)和由新獲得的觀測值組成的輸出矩陣,β′是修改后的輸出權(quán)重矩陣。OS-ELM算法分為兩個階段,即初始化階段和順序階段。初始化階段與普通ELM算法相同,而輸出權(quán)重矩陣β將通過迭代方式在順序階段中更新。

OS-ELM算法步驟如下:

2)計算初始隱藏層輸出矩陣H0:

4)設(shè)置k= 0,其中k是表示呈現(xiàn)給網(wǎng)絡(luò)的數(shù)據(jù)塊數(shù)量的索引。

步驟2(序列階段) 給出第(k+ 1)個新觀察結(jié)果:

其中,nk表示k塊中新獲得的觀察的數(shù)量。顯然,可以得到N0=n0。

1)計算部分隱藏層輸出矩陣hk+1:

hk+1=

2)計算輸出權(quán)重矩陣βk+1:

設(shè)置k=k+ 1,然后返回序列學(xué)習(xí)階段。

2 GP-ELM算法

2.1 算法描述

最早的ELM應(yīng)用是預(yù)先設(shè)定好隱藏層節(jié)點的個數(shù),存在準(zhǔn)確率不穩(wěn)定等不足。該類算法主要有2種:1)逐漸增加一個或者多個節(jié)點,這種算法將節(jié)點添加之后,隱藏層的參數(shù)即固定,這樣一些不必要的節(jié)點或者貢獻很小的節(jié)點會增加計算量;2)先設(shè)定一個較大的值作為隱藏層節(jié)點的個數(shù),根據(jù)第一次訓(xùn)練節(jié)點的權(quán)值刪減一些節(jié)點,然后再訓(xùn)練,這種算法必定要設(shè)置一個非常大的值,這對不同的數(shù)據(jù)的適應(yīng)性就非常低,因為一些數(shù)據(jù)只需要較少的節(jié)點,而有些則需要較多的節(jié)點。

本文算法是在EM-ELM[12]算法模型的基礎(chǔ)上,固定每輪增加節(jié)點的個數(shù),增加了每輪對整體節(jié)點進行剪枝的過程,能夠保證節(jié)點的質(zhì)量。本文算法結(jié)合上文兩類算法的優(yōu)點,既能動態(tài)地根據(jù)數(shù)據(jù)來生成隱藏節(jié)點,又能剔除那些沒有起到作用的節(jié)點,先生成固定數(shù)值節(jié)點,在這些節(jié)點加入之后進行一次訓(xùn)練,根據(jù)權(quán)值矩陣β來計算每個節(jié)點的貢獻值:

1)如果β是一維的,則直接將這一列換算成比例。

2)如果β是n維的,則先將每一列換算成比例,然后將每一行取平均值。

根據(jù)計算出的貢獻值來選擇刪去哪些節(jié)點,然后返回到增加節(jié)點的步驟,如此循環(huán),直到達到一定的標(biāo)準(zhǔn)停止循環(huán)。

由于物聯(lián)網(wǎng)下的數(shù)據(jù)是不斷產(chǎn)生的,因此在線訓(xùn)練數(shù)據(jù)更新參數(shù)又是非常有必要的,所以本文算法在確定隱藏層結(jié)構(gòu)后,會根據(jù)新來的數(shù)據(jù)更新參數(shù)。

2.2 算法步驟

本文算法步驟如下:

步驟1初始化階段:

2)計算隱藏層的輸出矩陣:

3)計算最優(yōu)的輸出權(quán)重:

β=H?T

其中,H?為H的廣義逆,T為目標(biāo)矩陣。于是,得到初始函數(shù)Ψ1以及相關(guān)的誤差E1:

步驟2隱藏節(jié)點上升并且刪減(最大隱藏節(jié)點數(shù)Lmax,需求的錯誤率ε):

1)生成M個隱藏節(jié)點參數(shù)并將其加入到當(dāng)前模型,然后根據(jù)迭代式計算:

2)計算出輸出權(quán)重,生成模型Ψn(x)=βnGn(x),計算其誤差En,如果Lnε,置n=n+1,進入步驟3;否則Ψn(x)為當(dāng)前標(biāo)準(zhǔn)模型。

3)根據(jù)計算出的β計算每個節(jié)點的貢獻值:

(1)如果β是一維的,則直接將這一列換算成比例。

(2)如果β是n維的,則先將每一列換算成比例,然后將每一行取平均值。

4)刪除那些幾乎不起作用的節(jié)點(兩種方案):

(1)節(jié)點貢獻值低于某一個值會被刪除。

(2)對貢獻值進行排序,貢獻值最小的m個節(jié)點會被刪除。

5)轉(zhuǎn)到步驟1。

步驟3在線學(xué)習(xí)階段:

設(shè)置r= 0,其中k是表示呈現(xiàn)給網(wǎng)絡(luò)的數(shù)據(jù)塊的數(shù)量的索引,給出第(r+ 1)個新觀察結(jié)果:

其中,nr表示r塊中新獲得的觀察的數(shù)量。顯然,可以得到N0=n0。

1)計算部分隱藏層輸出矩陣hr+1:

2)計算輸出權(quán)重矩陣βk+1:

3)如果還有數(shù)據(jù)進入,則設(shè)置r=r+1,然后返回序列學(xué)習(xí)階段,否則程序結(jié)束。

2.3 收斂性證明

定理1給定一個SLFN,令H1作為有L0個隱藏節(jié)點的SLFN隱藏層輸出矩陣,如果L1-L0個節(jié)點被加入當(dāng)前模型,新的隱藏層輸出矩陣為H2,于是有:

證明:根據(jù)前文的推理,增加σL0=L1-L0可以得到H2=[H1σH1],其中:

σH1=

由上面的證明可以看出,本文算法可以使得誤差值達到指定小的值,即算法是收斂的,能夠迭代終止。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

本文實驗的實驗平臺為 Intel i7-6700 3.4 GHz,16 GB 內(nèi)存和 1 TB硬盤的PC,實驗在 Windows 10 系統(tǒng)上用 Matlab 2016(b)實現(xiàn)。本文實驗采用了實際應(yīng)用的公開的數(shù)據(jù)集Image Segment(圖片分割)、Satellite Image(衛(wèi)星圖片分類)和DNA,如表1所示。

表1 實驗所用數(shù)據(jù)集

3.2 實驗結(jié)果對比

本文實驗將提出的算法GP-ELM與ELM以及各種衍生版本OS-ELM、EI-ELM、D-ELM、EM-ELM進行了對比(本文所有實驗結(jié)果都是重復(fù)實驗10次后的均值)。

3.2.1 各個數(shù)據(jù)ELM網(wǎng)絡(luò)結(jié)構(gòu)的確定

對每個數(shù)據(jù)集逐漸增加隱藏節(jié)點的個數(shù),如圖1所示。

圖1 準(zhǔn)確度隨節(jié)點數(shù)增長過程

從圖1可以看出,隨著隱藏節(jié)點個數(shù)的增長,訓(xùn)練準(zhǔn)確度和測試準(zhǔn)確度都在逐步上升,測試準(zhǔn)確度在500隱藏節(jié)點時達到了平穩(wěn)狀態(tài),并且在550左右開始下降,因此,對于數(shù)據(jù)集Satellite Image,ELM的最優(yōu)隱藏節(jié)點個數(shù)在550左右。對于其他兩組數(shù)據(jù)集進行同樣的實驗得到了相應(yīng)的節(jié)點個數(shù)。

3.2.2 與ELM、OS-ELM算法的對比

將本文算法與ELM、OS-ELM算法進行實驗對比,結(jié)果如表2所示。從表2可以看出,本文算法在增加較少訓(xùn)練時間的代價下,首先完成了隱藏節(jié)點個數(shù)自動生成的任務(wù),并且在準(zhǔn)確度上有了一定的提升,同時需要更少的隱藏節(jié)點來完成。這是因為本文提出的算法在每次增加節(jié)點之后,對一些不重要的對結(jié)果影響特別小的那些隱藏節(jié)點都進行刪除,這樣,留下來的節(jié)點都是提取了非常重要的特征,對最后的結(jié)果有著很大的影響,所以本文提出的算法能用比較少的節(jié)點得到比較高的準(zhǔn)確度。

表2 GP-ELM與ELM、OS-ELM算法性能對比

3.2.3 與EI-ELM、D-ELM、EM-ELM算法的對比

本文算法與EI-ELM、D-ELM、EM-ELM算法的性能對比如表3所示。從表3可以看出,本文算法具有更高的準(zhǔn)確度,這是因為刪去不重要的節(jié)點,使得本文算法生成的節(jié)點數(shù)量基本是最少的。另外,DP-ELM在訓(xùn)練時間上相比其他算法要少,這是由于本文的算法并不是一個一個地增加節(jié)點,而是一塊一塊地增加,這樣大幅節(jié)省了訓(xùn)練時間,同時,本文算法通過對原有的節(jié)點進行刪除修剪,這樣更有效地對ELM的結(jié)構(gòu)進行組裝,提高所選節(jié)點的質(zhì)量,在得到較高準(zhǔn)確度的同時節(jié)省了隨機搜索而進行的大量迭代時間,保證了更少的節(jié)點。

表3 GP-ELM與EI-ELM、D-ELM、EM-ELM 算法性能對比

通過觀察圖2所示的迭代次數(shù)與被加入的隱藏節(jié)點個數(shù)的對比,可以發(fā)現(xiàn)GP-ELM是每次增加多個節(jié)點然后進行修剪,所以會很快地并以較少的節(jié)點完成迭代,可以看出本文算法具有較大的優(yōu)勢。

圖2 節(jié)點個數(shù)隨迭代次數(shù)變化過程

4 結(jié)束語

為適應(yīng)機器學(xué)習(xí)算法準(zhǔn)確、快速以及自適應(yīng)產(chǎn)生參數(shù)的需求,本文通過研究ELM網(wǎng)絡(luò)結(jié)構(gòu)的確定方法,結(jié)合EM-ELM算法節(jié)點增加的方式和廣義逆的迭代公式,引入節(jié)點的修剪刪除的階段,實現(xiàn)達到根據(jù)數(shù)據(jù)本身自動地確定ELM網(wǎng)絡(luò)結(jié)構(gòu)的能力,并且在確定的過程中不斷地刪除貢獻較低的節(jié)點,以保持網(wǎng)絡(luò)的大小,提高ELM的準(zhǔn)確性。實驗結(jié)果表明,與EM-ELM、D-ELM和EI-ELM算法相比,DP-ELM算法能夠保證泛化能力,在準(zhǔn)確率、訓(xùn)練時間、模型大小等方面都有著很好的表現(xiàn),滿足物聯(lián)網(wǎng)下邊緣設(shè)備對機器學(xué)習(xí)產(chǎn)生的應(yīng)用需求。下一步將把該算法拓展到真實的物聯(lián)網(wǎng)場景下進行應(yīng)用,以測試實際的效果與適用范圍。