一種基于極限學(xué)習(xí)機(jī)的在線負(fù)增量算法

謝林森　任婷婷　盧誠波

1(麗水學(xué)院工程與設(shè)計(jì)學(xué)院　浙江 麗水 323000)2(浙江師范大學(xué)數(shù)理與信息工程學(xué)院　浙江 金華 321004)

?

一種基于極限學(xué)習(xí)機(jī)的在線負(fù)增量算法

謝林森1任婷婷2盧誠波1

1(麗水學(xué)院工程與設(shè)計(jì)學(xué)院浙江 麗水 323000)2(浙江師范大學(xué)數(shù)理與信息工程學(xué)院浙江 金華 321004)

在剔除影響單隱層前饋神經(jīng)網(wǎng)絡(luò)性能的“臟數(shù)據(jù)”后，傳統(tǒng)的極限學(xué)習(xí)機(jī)算法需要重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，這會(huì)增加很多額外的訓(xùn)練時(shí)間。針對(duì)這一問題，在傳統(tǒng)的極限學(xué)習(xí)機(jī)算法的基礎(chǔ)上，提出一種在線負(fù)增量學(xué)習(xí)算法：剔除“臟訓(xùn)練樣本”后，不需要再重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，而只需在原有的基礎(chǔ)上，通過更新外權(quán)矩陣來完成網(wǎng)絡(luò)更新。算法復(fù)雜性分析和仿真實(shí)驗(yàn)的結(jié)果表明所提出的算法具有更高的執(zhí)行速度。

極限學(xué)習(xí)機(jī)負(fù)增量算法算法復(fù)雜性仿真實(shí)驗(yàn)

0　引　言

人工神經(jīng)網(wǎng)絡(luò)是生物神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)模型，簡(jiǎn)稱神經(jīng)網(wǎng)絡(luò)。而前饋神經(jīng)網(wǎng)絡(luò)是神經(jīng)網(wǎng)絡(luò)中一種典型的分層結(jié)構(gòu)，其中單隱層前饋神經(jīng)網(wǎng)絡(luò)SLFNs(single hidden layer feedforward networks)因其算法簡(jiǎn)單、容易實(shí)現(xiàn)，且具有強(qiáng)大的非線性辨識(shí)能力而受到特別的重視[1]。SLFNs最常用的學(xué)習(xí)方法是BP算法[2]和支持向量機(jī)SVM算法[3]，BP算法在應(yīng)用過程中需要對(duì)權(quán)重、偏差等大量參數(shù)進(jìn)行設(shè)置，并且存在訓(xùn)練速度慢、易陷入局部極值、過擬合等問題，支持向量機(jī)盡管較BP神經(jīng)網(wǎng)絡(luò)運(yùn)算時(shí)間短、精度高，但是其同樣需要進(jìn)行多參數(shù)的選擇，如核函數(shù)、懲罰系數(shù)、誤差控制等。

近年來，Huang為SLFNs提出了一種稱為極限學(xué)習(xí)機(jī)ELM的學(xué)習(xí)方法[4-8]：設(shè)置合適的隱藏層結(jié)點(diǎn)數(shù)，為輸入權(quán)值和隱藏層偏差進(jìn)行隨機(jī)賦值，然后通過最小二乘法得到輸出層權(quán)值。整個(gè)過程一次完成，無需迭代，極限學(xué)習(xí)機(jī)在保證網(wǎng)絡(luò)具有良好泛化性能的同時(shí)，極大地提高了學(xué)習(xí)速度，同時(shí)避免了由于梯度下降算法產(chǎn)生的問題，如局部極小、過擬合、學(xué)習(xí)時(shí)間長、需要大量的參數(shù)設(shè)置等[2,9]。

在極限學(xué)習(xí)機(jī)的基礎(chǔ)上，Liang等人于2005年提出了一種在線學(xué)習(xí)的增量算法OS-ELM[10]。該算法可以在新樣本到來的時(shí)候，通過更新輸出權(quán)值矩陣來完成網(wǎng)絡(luò)的更新，而無需重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，具有學(xué)習(xí)速度快等優(yōu)點(diǎn)。

在極限學(xué)習(xí)機(jī)的實(shí)際應(yīng)用中，如果在訓(xùn)練網(wǎng)絡(luò)完成后，發(fā)現(xiàn)一些影響網(wǎng)絡(luò)質(zhì)量的數(shù)據(jù)：如“臟數(shù)據(jù)”、重復(fù)數(shù)據(jù)，需要對(duì)其進(jìn)行剔除，從而優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。如果直接利用極限學(xué)習(xí)機(jī)重新訓(xùn)練，這會(huì)增加很多額外的訓(xùn)練時(shí)間。受文獻(xiàn)[10]的啟發(fā)，本文提出了一種在線負(fù)增量學(xué)習(xí)算法，當(dāng)剔除這些“臟數(shù)據(jù)”后，不需要再重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，而只需在原有的基礎(chǔ)上，通過更新外權(quán)矩陣來完成網(wǎng)絡(luò)的更新，從而減少運(yùn)算代價(jià)，提高執(zhí)行速度。本文分別從算法復(fù)雜性和仿真實(shí)驗(yàn)兩方面分析驗(yàn)證該負(fù)增量算法比傳統(tǒng)的極限學(xué)習(xí)機(jī)算法具有更好的執(zhí)行速度。

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

極限學(xué)習(xí)機(jī)是一種基于SLFNs的高效學(xué)習(xí)算法。對(duì)于SLFNs[11]，假設(shè)有N個(gè)樣本(xi,ti)，

xi=[xi1,xi2,…,xin]T∈Rn，ti=[ti1,ti2,…,tim]T∈Rm

則有L個(gè)隱藏結(jié)點(diǎn)的SLFNs可以表示為：

其中ai=[ai1,ai2,…,ain]T是連接第i個(gè)隱藏層結(jié)點(diǎn)的輸入權(quán)值；bi是第i個(gè)隱藏層結(jié)點(diǎn)的偏差；βi=[βi1,βi2,…,βim]T是連接第i個(gè)隱藏層結(jié)點(diǎn)的輸出權(quán)值；ai·xj表示ai和xj的內(nèi)積，激勵(lì)函數(shù)g(x)可以是任意有界的非常量連續(xù)函數(shù)。

如果g(x)無限可導(dǎo)，理論上SLFNs能以一個(gè)極小的誤差逼近N個(gè)訓(xùn)練樣本[5]，且對(duì)于任意給定的ai和bi，有：

(1)

上述N個(gè)方程的矩陣形式可寫為：Hβ=T，其中，H是該神經(jīng)網(wǎng)絡(luò)隱藏層結(jié)點(diǎn)的輸出矩陣，β為輸出權(quán)值矩陣，T為期望輸出，具體形式如下：

H(a1,…,aL,b1,…,bL,x1,…,xN)

(2)

(3)

在極限學(xué)習(xí)機(jī)算法中，隱藏層的輸入權(quán)值ai和閾值bi可以隨機(jī)給定，因此只需求出輸出權(quán)值矩陣β即可完成網(wǎng)絡(luò)的訓(xùn)練，輸出權(quán)值矩陣β可由式(4)得到：

(4)

2　在線負(fù)增量算法及其應(yīng)用

(5)

在訓(xùn)練網(wǎng)絡(luò)后，如果發(fā)現(xiàn)其中有N1個(gè)影響網(wǎng)絡(luò)性能的“臟訓(xùn)練樣本”，為了提高網(wǎng)絡(luò)的質(zhì)量，則需要剔除這N1個(gè)“臟數(shù)據(jù)”。設(shè)N1個(gè)“臟數(shù)據(jù)”的隱層結(jié)點(diǎn)輸出矩陣是H1，期望輸出是T1；剩余的N0個(gè)訓(xùn)練樣本的隱層結(jié)點(diǎn)輸出矩陣是H0，期望輸出是T0，輸出權(quán)值矩陣是β(0)，則可得：

(6)

則由式(5)可得：

(7)

令：

(8)

(9)

則：

(10)

(11)

可得：

(12)

由式(5)、式(12)可得剔除“臟數(shù)據(jù)”樣本后，由文中提出的在線負(fù)增量算法得到的輸出權(quán)值矩陣β(0)表達(dá)式：

(13)

對(duì)應(yīng)地，如果直接用傳統(tǒng)的極限學(xué)習(xí)機(jī)算法重新訓(xùn)練剩余的N0個(gè)訓(xùn)練樣本，則可得極限學(xué)習(xí)機(jī)得到的輸出權(quán)值矩陣β(0)表達(dá)式：

(14)

(15)

(16)

2.1算法時(shí)間復(fù)雜性分析

下面對(duì)本文提出的算法與傳統(tǒng)的極限學(xué)習(xí)機(jī)算法進(jìn)行復(fù)雜性比較。

對(duì)于在線負(fù)增量算法：

則H1的計(jì)算量是：LN1n；

L3+2L2m+L2N1+LN1n

即Tnew的最大計(jì)算量：

對(duì)于極限學(xué)習(xí)機(jī)：

則H0的計(jì)算量是：LN0n；

L2m+L3+L2N0+LN0n+LN0m

即Telm的計(jì)算量：

則可得：

Q2-Q1=L2(N0-N1-m)+Ln(N0-N1)+LN0m

只要N0>N1+m，則Q2>Q1，即只要剔除“臟訓(xùn)練數(shù)據(jù)”后的剩余訓(xùn)練數(shù)據(jù)個(gè)數(shù)大于剔除樣本個(gè)數(shù)與網(wǎng)絡(luò)輸出維數(shù)之和(一般情況下，當(dāng)訓(xùn)練樣本較大時(shí)，該條件易滿足)，就可以得到Tnew計(jì)算量小于Telm的計(jì)算量，也就是相對(duì)于傳統(tǒng)的極限學(xué)習(xí)機(jī)算法，本文算法提高了執(zhí)行速度。

2.2仿真實(shí)驗(yàn)

本文通過仿真實(shí)驗(yàn)結(jié)果驗(yàn)證在線負(fù)增量算法的優(yōu)良性能。實(shí)驗(yàn)的運(yùn)行環(huán)境是Matlab 2013a，CPU主頻是2.2 GHz，RAM 4.00 GB。神經(jīng)網(wǎng)絡(luò)激勵(lì)函數(shù)是“Sigmoid”函數(shù)：g(x)=1/(1+exp(-x))，人工數(shù)據(jù)“SinC”的表達(dá)式如下：

在回歸的實(shí)驗(yàn)中，用的數(shù)據(jù)集是：人工數(shù)據(jù)“SinC”，UCI數(shù)據(jù)庫中的abalone數(shù)據(jù)集[12]和wine quality數(shù)據(jù)集[13]；實(shí)驗(yàn)數(shù)據(jù)的輸入歸一化到[-1,1]，實(shí)驗(yàn)數(shù)據(jù)的輸出歸一化到[0,1]。在分類的實(shí)驗(yàn)中，用的數(shù)據(jù)集是：handwritten digits 數(shù)據(jù)集、satellite image數(shù)據(jù)集[12]和image segmentation數(shù)據(jù)集[12]；實(shí)驗(yàn)數(shù)據(jù)的輸入歸一化到[-1,1]，數(shù)據(jù)集具體信息見表1所示。

表1　數(shù)據(jù)集信息

2.2.1回歸問題

在回歸問題的應(yīng)用中，測(cè)試結(jié)果包括本文算法和極限學(xué)習(xí)機(jī)求解測(cè)試樣本的實(shí)際輸出與期望輸出的均方根誤差RMSE(root-mean-square error)，以及兩種算法求解測(cè)試樣本實(shí)際輸出所需的時(shí)間。在實(shí)驗(yàn)中，采用的數(shù)據(jù)集是：人工數(shù)據(jù)“SinC”、abalone數(shù)據(jù)集[12]和wine quality數(shù)據(jù)集[13]，隱層結(jié)點(diǎn)個(gè)數(shù)均是200，見表1所示，其中人工數(shù)據(jù)“SinC”是在區(qū)間(-10,10)內(nèi)隨機(jī)產(chǎn)生5000個(gè)訓(xùn)練樣本和2000個(gè)測(cè)試樣本。

當(dāng)剔除訓(xùn)練樣本時(shí)，輸入權(quán)值矩陣和閾值隨機(jī)產(chǎn)生，且隨機(jī)進(jìn)行10次實(shí)驗(yàn)并將兩種算法平均的RMSE進(jìn)行統(tǒng)計(jì)。從表2可以看出，當(dāng)剔除相同數(shù)量的樣本時(shí)，兩種算法的RMSE近似相等，且均比較小，表明當(dāng)剔除訓(xùn)練樣本后，兩種算法都具有較好的泛化性能。圖1給出了這兩種算法的測(cè)試時(shí)間，可見本文提出的算法比傳統(tǒng)的極限學(xué)習(xí)機(jī)算法所需時(shí)間少。

表2　兩種算法的測(cè)試結(jié)果的均方差(RMSE)

圖1　兩種算法的測(cè)試結(jié)果所需時(shí)間

2.2.2分類問題

在分類應(yīng)用中，測(cè)試結(jié)果包括兩種算法求解測(cè)試樣本實(shí)際輸出的分類正確率，以及求解測(cè)試樣本實(shí)際輸出所需要的時(shí)間。實(shí)驗(yàn)選用的數(shù)據(jù)集是：handwritten digits 數(shù)據(jù)集、satellite image數(shù)據(jù)集[12]和image segmentation數(shù)據(jù)集[12]，隱層結(jié)點(diǎn)個(gè)數(shù)分別是250、500、200，見表1所示。

當(dāng)剔除訓(xùn)練樣本時(shí)，輸入權(quán)值矩陣和閾值隨機(jī)產(chǎn)生，且隨機(jī)進(jìn)行10次實(shí)驗(yàn)并將兩種算法平均的分類正確率進(jìn)行統(tǒng)計(jì)，見表3所示。從表3可以看出，當(dāng)剔除相同數(shù)量的樣本時(shí)，兩種算法的分類正確率相差無幾，并且handwritten digits 數(shù)據(jù)集的分類正確率均在86%以上，satellite image數(shù)據(jù)集的分類正確率則在88%以上，而image segmentation 數(shù)據(jù)集的分類正確率高達(dá)95%以上。圖2給出了這兩種算法的測(cè)試時(shí)間，可見本文的在線負(fù)增量算法比傳統(tǒng)的極限學(xué)習(xí)機(jī)算法所需時(shí)間少，執(zhí)行速度快。

表3　兩種算法的測(cè)試樣本分類正確率(%)

圖2　兩種算法的測(cè)試結(jié)果所需時(shí)間

3　結(jié)　語

在極限學(xué)習(xí)機(jī)訓(xùn)練單隱層前饋神經(jīng)網(wǎng)絡(luò)模型的實(shí)際應(yīng)用中，剔除影響網(wǎng)絡(luò)性能的“臟數(shù)據(jù)”后，傳統(tǒng)的極限學(xué)習(xí)機(jī)算法需要重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，這會(huì)增加很多額外的訓(xùn)練時(shí)間。本文提出了一種在線負(fù)增量學(xué)習(xí)算法，在剔除“臟數(shù)據(jù)”后，不需要再重新訓(xùn)練整個(gè)網(wǎng)絡(luò)，而只需在原有的基礎(chǔ)上，通過更新輸出矩陣來完成網(wǎng)絡(luò)的更新。在計(jì)算測(cè)試結(jié)果之后，無需重新計(jì)算，剔除后的測(cè)試結(jié)果只需在原測(cè)試結(jié)果的基礎(chǔ)上進(jìn)行更新，從而減少運(yùn)算代價(jià)，提高執(zhí)行速度。通過仿真實(shí)驗(yàn)從分類和回歸的應(yīng)用兩方面驗(yàn)證了文中算法的速度優(yōu)勢(shì)。本文只進(jìn)行了算法的時(shí)間復(fù)雜性分析，在以后的工作中進(jìn)一步研究空間復(fù)雜度。除此之外，對(duì)于影響網(wǎng)絡(luò)性能的“臟數(shù)據(jù)”，文中研究了剔除這些數(shù)據(jù)后，不需要重新訓(xùn)練整個(gè)網(wǎng)絡(luò)的在線負(fù)增量算法。如果用一些優(yōu)良數(shù)據(jù)替換這些“臟數(shù)據(jù)”，并且利用不需要重新訓(xùn)練整個(gè)網(wǎng)絡(luò)的在線學(xué)習(xí)方法，是否可以得到更好的泛化性能，且具有較好的執(zhí)行速度，這是未來工作中另一個(gè)可以研究的方向。

[1] Sanger T D.Optimal unsupervised learning in a single-layer linear feedforward neural network[J].Neural networks,1989,2(6):459-473.

[2] Chauvin Y,Rumelhart D E.Backpropagation: theory,architectures,and applications[M].Psychology Press,1995.

[3] Cortes C,Vapnik V.Support vector networks[J].Machine Learning,1995,20(3):273-295.

[4] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:a new learning scheme of feedforward neural networks[J].Neural Networks,2004,2:985-990.

[5] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:theory and applications[J].Neurocomputing,2006,70(1-3):489-501.

[6] Huang G B,Zhou H,Ding X,et al.Extreme learning machine for regression and multiclass classification[J].Systems,Man,and Cybernetics,Part B:Cybernetics,IEEE Transactions on,2012,42(2):513-529.

[7] Peng D,Zhu Q.Extreme learning machine-based functional link network[C]//Intelligent Control and Automation (WCICA),2014 11th World Congress on.IEEE,2014:5785-5790.

[8] Huang G B.An insight into extreme learning machines:random neurons,random features and kernels[J].Cognitive Computation,2014,6(3):376-390.

[9] Haykin S S.Neural networks and learning machines[M].Upper Saddle River:Pearson Education,2009.

[10] Liang N Y,Huang G B,Saratchandran P,et al.A fast and accurate online sequential learning algorithm for feedforward networks[J].Neural Network,IEEE Transaction on,2006,17(6):1411-1423.

[11] Huang G B.Extreme learning machine:learning without iterative tuning[D/OL].School of Electrical and Electronic Engineering,Nanyang Technological University,Singapore,2010.http://www.extreme-learning-machines.org/.

[12] Lichman M.UCI Machine Learning Repository[D/OL].Irvine,CA:University of California,School of Information and Computer Science,2013.http://archive.ics.uci.edu/ml.

[13] Cortez P,Cerdeira A,Almeida F,et al.Modeling wine preferences by data mining from physicochemical properties[J].Decision Support Systems,2009,47(4):547-553.

AN ONLINE NEGATIVE INCREMENTAL ALGORITHM BASED ON EXTREME LEARNING MACHINE

Xie Linsen1Ren Tingting2Lu Chengbo1

1(School of Engineering and Design,Lishui University,Lishui 323000,Zhejiang,China)2(SchoolofMathematicsPhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,Zhejiang,China)

After weeding out the dirty data that affecting the performance of single hidden layer feedforward network, traditional extreme learning machine has the need to train the entire networks. However, this will increase a lot of extra training time. In light of this issue, the paper proposes an online negative incremental algorithm based on traditional extreme learning machine algorithm:after the “dirty training sample” being eliminated, there has no need to train the whole networks once again, but only need to accomplish the network update by updating output weights matrix on the basis of original. The complexity analysis of the algorithm and the result of simulation experiment show that the proposed algorithm has higher execution speed.

Extreme learning machineNegative incremental algorithmAlgorithm’s complexitySimulation experiment

2015-05-07。國家自然科學(xué)基金面上項(xiàng)目(11171137)；浙江省自然科學(xué)基金項(xiàng)目(LY13A010008)。謝林森，教授，主研領(lǐng)域：逼近論，人工神經(jīng)網(wǎng)絡(luò)。任婷婷，碩士。盧誠波，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.09.063