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

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

?

·數(shù)理科學(xué)·

關(guān)于增量極限學(xué)習(xí)機(jī)的逼近階估計(jì)

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

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

增量極限學(xué)習(xí)機(jī);貪婪算法;字典集;逼近階

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

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

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

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

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

1 增量極限學(xué)習(xí)機(jī)回顧

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

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

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

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

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

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

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

limn→∞‖f-fn‖=0

以概率1成立。

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

2 增量極限學(xué)習(xí)機(jī)的逼近階估計(jì)

2.1 準(zhǔn)備知識(shí)

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

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

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

2.3 增量極限學(xué)習(xí)機(jī)的逼近階

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

‖en‖=‖f-fn‖

成立。

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

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

(1)

其中

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

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

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

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

假設(shè)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表示存在一個(gè)常數(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

陜西省自然科學(xué)基金資助項(xiàng)目(2014JM1016)

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

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

O29

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