一種基于極限學習機的在線負增量算法

謝林森　任婷婷　盧誠波

1(麗水學院工程與設計學院　浙江 麗水 323000)2(浙江師范大學數理與信息工程學院　浙江 金華 321004)

?

一種基于極限學習機的在線負增量算法

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

1(麗水學院工程與設計學院浙江 麗水 323000)2(浙江師范大學數理與信息工程學院浙江 金華 321004)

在剔除影響單隱層前饋神經網絡性能的“臟數據”后，傳統的極限學習機算法需要重新訓練整個網絡，這會增加很多額外的訓練時間。針對這一問題，在傳統的極限學習機算法的基礎上，提出一種在線負增量學習算法：剔除“臟訓練樣本”后，不需要再重新訓練整個網絡，而只需在原有的基礎上，通過更新外權矩陣來完成網絡更新。算法復雜性分析和仿真實驗的結果表明所提出的算法具有更高的執行速度。

極限學習機負增量算法算法復雜性仿真實驗

0　引　言

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

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

在極限學習機的基礎上，Liang等人于2005年提出了一種在線學習的增量算法OS-ELM[10]。該算法可以在新樣本到來的時候，通過更新輸出權值矩陣來完成網絡的更新，而無需重新訓練整個網絡，具有學習速度快等優點。

在極限學習機的實際應用中，如果在訓練網絡完成后，發現一些影響網絡質量的數據：如“臟數據”、重復數據，需要對其進行剔除，從而優化網絡結構。如果直接利用極限學習機重新訓練，這會增加很多額外的訓練時間。受文獻[10]的啟發，本文提出了一種在線負增量學習算法，當剔除這些“臟數據”后，不需要再重新訓練整個網絡，而只需在原有的基礎上，通過更新外權矩陣來完成網絡的更新，從而減少運算代價，提高執行速度。本文分別從算法復雜性和仿真實驗兩方面分析驗證該負增量算法比傳統的極限學習機算法具有更好的執行速度。

1　極限學習機簡介

極限學習機是一種基于SLFNs的高效學習算法。對于SLFNs[11]，假設有N個樣本(xi,ti)，

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

則有L個隱藏結點的SLFNs可以表示為：

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

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

(1)

上述N個方程的矩陣形式可寫為：Hβ=T，其中，H是該神經網絡隱藏層結點的輸出矩陣，β為輸出權值矩陣，T為期望輸出，具體形式如下：

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

(2)

(3)

在極限學習機算法中，隱藏層的輸入權值ai和閾值bi可以隨機給定，因此只需求出輸出權值矩陣β即可完成網絡的訓練，輸出權值矩陣β可由式(4)得到：

(4)

2　在線負增量算法及其應用

(5)

在訓練網絡后，如果發現其中有N1個影響網絡性能的“臟訓練樣本”，為了提高網絡的質量，則需要剔除這N1個“臟數據”。設N1個“臟數據”的隱層結點輸出矩陣是H1，期望輸出是T1；剩余的N0個訓練樣本的隱層結點輸出矩陣是H0，期望輸出是T0，輸出權值矩陣是β(0)，則可得：

(6)

則由式(5)可得：

(7)

令：

(8)

(9)

則：

(10)

(11)

可得：

(12)

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

(13)

對應地，如果直接用傳統的極限學習機算法重新訓練剩余的N0個訓練樣本，則可得極限學習機得到的輸出權值矩陣β(0)表達式：

(14)

(15)

(16)

2.1算法時間復雜性分析

下面對本文提出的算法與傳統的極限學習機算法進行復雜性比較。

對于在線負增量算法：

則H1的計算量是：LN1n；

L3+2L2m+L2N1+LN1n

即Tnew的最大計算量：

對于極限學習機：

則H0的計算量是：LN0n；

L2m+L3+L2N0+LN0n+LN0m

即Telm的計算量：

則可得：

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

只要N0>N1+m，則Q2>Q1，即只要剔除“臟訓練數據”后的剩余訓練數據個數大于剔除樣本個數與網絡輸出維數之和(一般情況下，當訓練樣本較大時，該條件易滿足)，就可以得到Tnew計算量小于Telm的計算量，也就是相對于傳統的極限學習機算法，本文算法提高了執行速度。

2.2仿真實驗

本文通過仿真實驗結果驗證在線負增量算法的優良性能。實驗的運行環境是Matlab 2013a，CPU主頻是2.2 GHz，RAM 4.00 GB。神經網絡激勵函數是“Sigmoid”函數：g(x)=1/(1+exp(-x))，人工數據“SinC”的表達式如下：

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

表1　數據集信息

2.2.1回歸問題

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

當剔除訓練樣本時，輸入權值矩陣和閾值隨機產生，且隨機進行10次實驗并將兩種算法平均的RMSE進行統計。從表2可以看出，當剔除相同數量的樣本時，兩種算法的RMSE近似相等，且均比較小，表明當剔除訓練樣本后，兩種算法都具有較好的泛化性能。圖1給出了這兩種算法的測試時間，可見本文提出的算法比傳統的極限學習機算法所需時間少。

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

圖1　兩種算法的測試結果所需時間

2.2.2分類問題

在分類應用中，測試結果包括兩種算法求解測試樣本實際輸出的分類正確率，以及求解測試樣本實際輸出所需要的時間。實驗選用的數據集是：handwritten digits 數據集、satellite image數據集[12]和image segmentation數據集[12]，隱層結點個數分別是250、500、200，見表1所示。

當剔除訓練樣本時，輸入權值矩陣和閾值隨機產生，且隨機進行10次實驗并將兩種算法平均的分類正確率進行統計，見表3所示。從表3可以看出，當剔除相同數量的樣本時，兩種算法的分類正確率相差無幾，并且handwritten digits 數據集的分類正確率均在86%以上，satellite image數據集的分類正確率則在88%以上，而image segmentation 數據集的分類正確率高達95%以上。圖2給出了這兩種算法的測試時間，可見本文的在線負增量算法比傳統的極限學習機算法所需時間少，執行速度快。

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

圖2　兩種算法的測試結果所需時間

3　結　語

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

[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。國家自然科學基金面上項目(11171137)；浙江省自然科學基金項目(LY13A010008)。謝林森，教授，主研領域：逼近論，人工神經網絡。任婷婷，碩士。盧誠波，副教授。

TP3

A

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