崔新月，王 博，張 瑞，呂曉麗

(西北大學 數(shù)學學院, 陜西 西安 710127)

?

·數(shù)理科學·

關(guān)于增量極限學習機的逼近階估計

崔新月，王 博，張 瑞，呂曉麗

(西北大學 數(shù)學學院, 陜西 西安 710127)

增量極限學習機;貪婪算法;字典集;逼近階

近年來,人工神經(jīng)網(wǎng)絡已成功應用于自動控制、模式識別、機械工程以及生物醫(yī)學等領(lǐng)域中,其中單隱層前向神經(jīng)網(wǎng)絡(Single-Hidden layer feedforward networks,SLFNs)由于結(jié)構(gòu)簡單、學習能力強、能解決傳統(tǒng)學習算法無法解決的問題等特性,是目前為止研究最為廣泛的一類神經(jīng)網(wǎng)絡模型。雖然著名的萬有逼近定理[1-3]已經(jīng)表明,通過適當調(diào)整網(wǎng)絡中的所有參數(shù)單隱層前向神經(jīng)網(wǎng)絡能夠以任意精度逼近一個給定的連續(xù)目標函數(shù),但傳統(tǒng)的神經(jīng)網(wǎng)絡學習算法往往是基于梯度下降法而設計的,因而具有學習速度慢、容易陷入局部最小、需要人為調(diào)整網(wǎng)絡參數(shù)等不足。

極限學習機(Extreme learning machine,ELM)[4]是近年來提出的一種簡單而高效的學習算法。其基本思想是通過隨機機制來固定一個學習系統(tǒng)的隱變量將其化為線性系統(tǒng), 從而大大提高學習速度并保證泛化能力,與傳統(tǒng)的神經(jīng)網(wǎng)絡學習算法相比,極限學習機具有如下特點：①具有更快的學習速度和更強的泛化能力； ②結(jié)構(gòu)簡單,并且可以避免陷入局部最小和過度擬合等問題；③所適用的激活函數(shù)范圍較廣,既可以是連續(xù)的激活函數(shù)類,也可以是不連續(xù)的激活函數(shù)類；④不僅算法中所選取的隱節(jié)點參數(shù)之間相互獨立,而且參數(shù)選取與訓練集也是獨立的。文獻[4]中證明了當隱層激活函數(shù)無限可微且網(wǎng)絡中的輸入權(quán)重和隱層閾值服從某種連續(xù)概率分布隨機選取時, 該算法能以任意小的誤差來逼近給定的連續(xù)目標函數(shù)。

在極限學習機中,唯一需要人為調(diào)整的參數(shù)就是隱單元個數(shù)。在原始極限學習機中,隱單元個數(shù)是采用多次人工實驗比較誤差的方法確定的,但這種選取方法造成了很大的工作量,不僅很耗時而且最終確定的隱單元個數(shù)無法保證是最優(yōu)的。網(wǎng)絡結(jié)構(gòu)直接影響其泛化能力,具體地說,當隱單元個數(shù)較少時會導致訓練誤差大且泛化能力差;當隱單元過多時雖然會減小訓練誤差,但其泛化能力仍然較差。基于這一問題，文獻[5]進一步提出了網(wǎng)絡結(jié)構(gòu)增長型的極限學習機,即增量極限學習機(Incremental extreme learning machine, I-ELM)。

在增量極限學習機中,無需提前設置隱單元個數(shù),而是通過逐個添加隱單元來逼近給定的目標函數(shù)。文獻[5]中已經(jīng)證明了增量極限學習機的全局逼近能力,當可加型隱節(jié)點或RBF型隱節(jié)點的激活函數(shù)g:R→R滿足span{g(a,b,x):(a,b)∈Rd×R}在L2中稠密時,由增量極限學習機所生成的網(wǎng)絡序列可以以概率1逼近任意給定的連續(xù)目標函數(shù)。

然而，學習理論的核心問題之一是對學習算法的性能進行量化評估,已有的理論結(jié)果只是從定性角度對增量極限學習機的逼近能力進行了分析。本文將從定量角度對增量極限學習機的逼近能力進行具體分析,進而對其快速收斂的本質(zhì)給出理論保證。

1 增量極限學習機回顧

不失一般性,本文只考慮含有n個隱節(jié)點以及一個線性輸出節(jié)點的單隱層前向神經(jīng)網(wǎng)絡,其數(shù)學模型可表示為

其中g(shù)i(x)表示第i個隱節(jié)點的輸出,βi表示連接第i個隱節(jié)點與輸出節(jié)點的輸出權(quán)重。最常見的兩種隱節(jié)點類型為

1) 可加型隱節(jié)點:gi(x)=g(ai·x+bi),ai∈Rd,bi∈R。其中ai是連接輸入層與第i個隱節(jié)點的權(quán)重向量,bi是第i個隱節(jié)點的閾值。

2) RBF型隱節(jié)點:gi(x)=g(bi‖x-ai‖),ai∈Rd,bi∈R+。其中ai,bi分別表示第i個RBF型隱節(jié)點的中心和影響因子。

增量極限學習機的核心思想是通過逐個增加隱節(jié)點來確定最優(yōu)的網(wǎng)絡結(jié)構(gòu),并且在增加一個新隱節(jié)點時,已存在隱節(jié)點的輸出權(quán)重保持不變,只需計算新增隱節(jié)點與輸出層的連接權(quán)重。 其具體的網(wǎng)絡產(chǎn)生迭代公式為

fn(x)=fn-1(x)+βngn(x)。

其中fn(x)表示第n步產(chǎn)生的網(wǎng)絡,gn(x)是第n步新增隱節(jié)點的輸出,βn表示連接第n個新增隱節(jié)點與輸出層的權(quán)重,按照下式直接計算可得

limn→∞‖f-fn‖=0

以概率1成立。

引理1表明，當?shù)綌?shù)n趨于無窮大時,由增量極限學習機所產(chǎn)生的網(wǎng)絡序列以概率1無限逼近于給定的目標函數(shù)f。

2 增量極限學習機的逼近階估計

2.1 準備知識

性質(zhì)1[7]對于可加型隱節(jié)點g(a·x+b),若激活函數(shù)g:R→R不是多項式函數(shù)，則span{g(a·x+b):(a,b)∈Rd×R}在L2中稠密。

性質(zhì)2[7]對于RBF型隱節(jié)點g(b‖x-a‖),若激活函數(shù)g:R→R是有界可積的連續(xù)函數(shù),則span{g(b‖x-a‖):(a,b)∈Rd×R+}在L2中稠密。

2.2 字典集和目標函數(shù)空間的構(gòu)造

2.3 增量極限學習機的逼近階

引理2[10]若f∈A1(D*,M),則‖f‖≤M。

‖en‖=‖f-fn‖

成立。

證 明 由于f∈A1(D*),故由A1(D*)的定義可知,必存在一個M0>0，使得f∈A1(D*,M0)。

定義正項數(shù)列{bn}:

(1)

其中

則由數(shù)學歸納法可以證明

f-fn=en∈A1(D*,bn)。

接下來用數(shù)學歸納法證明上述結(jié)論。

當n=0時,由假設可知命題顯然成立,即e0=f∈A1(D*,b0)。

假設en-1∈A1(D*,bn-1)成立,則有

成立,從而由fn=fn-1+βngn可推得f-fn=f-fn-1-βngn,即

其中,Λ′=Λ∪{n},

而

成立,所以en∈A1(D*,bn)。

綜上可知,en∈A1(D*,bn)成立，于是可推得

即

(2)

成立。從而由式(1)可知

(3)

又由于{en}滿足

‖en‖2=‖en-1-βngn‖2=

(4)

于是由式(3)，(4)可推得

‖en‖2bn≤

‖en-1‖2bn-1≤

?

(5)

又由式(2)可知

(6)

故由式(4)，(6)可知

(7)

綜合(5)，(7)兩式即知

‖en‖6=

亦即

從而證得

‖en‖=‖f-fn‖

定理得證。

注1 這里AB表示存在一個常數(shù)C，使得A≤CB。

3 結(jié) 語

[1]BARRONAR.Universalapproximationboundsforsuperpositionsofasigmoidalfunction[J].IEEETransactionInformationTheory,1993(39)：930-945.

[2]HORNIKK.Approximatoncapabilitiesofmultilayerfeedforwardnetworks[J].NeuralNetworks,1991(4): 251-257.

[3]PARKJ,SANDBERGIW.Universalapproximationusingradial-basis-functionnetworks[J].NeuralCompute,1991(3): 246-257.

[4]HUANGGB,ZHUQY，SIEWCK.ExtremeLearningMachine:Theoryandapplications[J].Neurocomputing,2006, 70: 489-501.

[5]HUANGGB，LEIChen.UniversalApproximationUsingIncrementalConstructiveFeedforwardNetworksWithRandomHiddenNodes[J].IEEETransactionNeuralNetworks, 2006,17(4)：879-892.

[6]LEVIATAND，TEMLYAKOVVN.Simultaneousapproximationbygreedyalgorithms[J].AdvancedComputeMath, 2006，25：73-90.

[7]HUANGGB，CHENL.Convexincrementalextremelearningmachine[J].Neurocomputing, 2007，70：3056-3062.

[8]DEVORERA，TEMLYAKOVVN.Someremarksongreedyalgorithms[J].AdvancedComputeMath, 1996，5：173-187.

[9]BARRONR,COHENA，RONALDA.Denore.ApproximationAndLearningByGreedyAlgorithms[J].TheAnnalsofStatistics, 2008，36(1)：64-94.

[10]LIVSHITSED.RateofConvergenceofPureGreedyAlgorithms[J].Math.Notes, 2004，76(4)：497-510.

[11]KONYAGINSV，TEMLYAKOVVN.Rateofconvergenceofpuregreedyalgorithms[J].EastJApproximation, 1999，5：493-499.

(編 輯亢小玉)

The approximation order of Incremental extreme learning machine

CUI Xin-yue, WANG Bo, ZHANG Rui, Lü Xiao-li

(School of Mathematics, Northwest University, Xi′an 710069， China)

Incremental extreme learning machine; greedy algorithm; dictionary; approximation rate

2014-07-11

陜西省自然科學基金資助項目(2014JM1016)

崔新月，女，山西運城人，從事ELMs技術(shù)的算法及理論研究。

張瑞，女，陜西西安人，西北大學教授，博士生導師，從事人工神經(jīng)網(wǎng)絡及ELMs技術(shù)的研究。

O29

：ADOI：10.16152/j.cnki.xdxbzr.2015-02-001