無逆矩陣在線序列極限學習機*

左鵬玉，王士同

江南大學 數(shù)字媒體學院，江蘇 無錫214122

1 引言

近年來，神經(jīng)網(wǎng)絡已經(jīng)得到廣泛研究，并且成功應用到現(xiàn)實問題中[1-6]。傳統(tǒng)的單隱層前饋神經(jīng)網(wǎng)絡（single hidden-layer feedforward neural network,SLFN）中，所有的參數(shù)都需要調(diào)整，不同層的參數(shù)之間存在著依賴性，訓練效率低，學習速度慢。為此，Huang 等人提出了極限學習機（extreme learning machine,ELM），該算法無需調(diào)整任何參數(shù)，只需要隨機產(chǎn)生輸入權重及偏差，直接通過隱含層輸出矩陣的廣義逆矩陣計算得出輸出權重[7]。相比于傳統(tǒng)的SLFN，ELM 在保證了算法學習性能的基礎上，對速度有了明顯提升[8]。但由于ELM 無需調(diào)整任何參數(shù)，網(wǎng)絡結構在訓練過程中固定不變，而其中隱含層的節(jié)點數(shù)對訓練效果具有決定性影響，因此便產(chǎn)生了最優(yōu)隱含層節(jié)點數(shù)的問題。

為了解決最優(yōu)隱含層節(jié)點數(shù)的問題，Li 等人提出了無逆矩陣極限學習機（inverse-free extreme learning machine,IF-ELM）的增量學習算法，該算法通過逐步增加隱含層節(jié)點數(shù)來更新隱含層的輸出權重，通過不斷調(diào)整隱含層節(jié)點數(shù)使得訓練模型的性能達到最優(yōu)[9]。文獻[9]用大量實驗證明了在隱含層參數(shù)相同的情況下，IF-ELM 算法與經(jīng)典ELM 算法學習性能是一致的。經(jīng)典ELM 在最小二乘方法下，訓練誤差具有最優(yōu)性，這就意味著IF-ELM 的節(jié)點增加策略也具有最優(yōu)性。此算法是批量學習算法，需一次性獲得所有的訓練樣本進行學習。當收到新的數(shù)據(jù)時，批量學習方法需要將過去的數(shù)據(jù)和新的數(shù)據(jù)一起進行訓練。算法在涉及到訓練數(shù)據(jù)的迭代時，沒有進一步考慮在線學習情況下的應用，從而浪費了大量的時間。

學習是一個持續(xù)的過程，在許多實際應用中，訓練數(shù)據(jù)集并不能一次性獲得。當一些新的數(shù)據(jù)加入到訓練模型時，批量學習必須重復使用過去的數(shù)據(jù)進行學習，因此需要更多時間，效率較低。在線學習算法不同于批量學習算法，在接收到新數(shù)據(jù)時不需要重復計算已經(jīng)訓練過的數(shù)據(jù)，不僅減少了時間和空間的需求，且更好地滿足了實際應用。

Huang 等人提出了在線序列極限學習機（online sequential extreme learning machine,OS-ELM），可以逐個或多個地增添學習數(shù)據(jù)，減少了訓練數(shù)據(jù)的迭代過程，從而節(jié)省了大量的學習時間[10]。文獻[11]提出了具有遺忘系數(shù)的極限學習機（forgetting parameters extreme learning machine,FP-ELM），該算法注重當前數(shù)據(jù)，在OS-ELM 的基礎上為舊數(shù)據(jù)塊添加遺忘系數(shù)。文獻[12]提出了在線序列λ1 正則化極限學習機（online sequential λ1-regularized-ELM,OS-λ1-ELM），通過增加懲罰項的方式有效避免了過擬合問題，提高了模型的泛化能力。雖然以上這些學習算法已經(jīng)具備了在線學習的能力，但是在最初確定隱含層節(jié)點數(shù)時涉及到了逆運算，導致了大量的計算開銷。因此，如何高效求解這些在線學習算法的最佳隱含層節(jié)點數(shù)就變得十分迫切。

本文在IF-ELM 算法基礎上引入了在線學習的思想，提出無逆矩陣在線序列極限學習機（inversematrix-free online sequential extreme learning machine,IOS-ELM）算法，計算出合適的隱含層節(jié)點數(shù)后再加入新增數(shù)據(jù)，增強了算法的實時學習能力。該算法不僅可以逐步將數(shù)據(jù)加入模型訓練，還可以丟棄已經(jīng)完成訓練的數(shù)據(jù)。當新的單個或多個數(shù)據(jù)加入到訓練模型時，在線學習算法只需要學習新的數(shù)據(jù)，而無需再次學習過去已經(jīng)分析過的數(shù)據(jù)。所提的IOSELM 算法源于批量學習的IF-ELM 算法，且IF-ELM算法的性能已經(jīng)在回歸和分類問題上得到了驗證[9]。由實驗部分可知，當不斷增加訓練樣本時，本文所提的IOS-ELM 算法的學習在保證性能不變的情況下，速度明顯快于無逆矩陣極限學習機。

2 無逆矩陣極限學習機

2.1 極限學習機

ELM 是在SLFN 的基礎上提出的一種學習效率高且泛化性能好的學習方法。不同于傳統(tǒng)的神經(jīng)網(wǎng)絡求解權重的方法，ELM 只需隨機選取輸入層和隱含層的連接權重和偏差，通過隱含層輸出矩陣的偽逆運算，分析計算出隱含層和輸出層的連接權重。同時，ELM 的逼近原理表明：在一定條件下，使用任意給定輸入權重的ELM 算法，能以任意小誤差逼近任何非線性連續(xù)函數(shù)。

對于n個輸入層節(jié)點，l個隱含層節(jié)點和m個輸出層節(jié)點，ELM 的表達式如下：

其中，fj為第j個輸出節(jié)點的值，g(ai,bi,xj)是與輸入數(shù)據(jù)xj相對應的第i個隱含層節(jié)點的值。g(?)是一個激活函數(shù)，如sigmoid等。wi是輸入層到第i個隱含層節(jié)點的連接權重，bi是第i個隱含層節(jié)點的偏差值，βi是第i個隱含層節(jié)點到輸出層的連接權重。

2.2 無逆矩陣極限學習機

實際情況下，計算量與隱含層節(jié)點數(shù)成正比，訓練時間隨著隱含層節(jié)點數(shù)的增多而加長。為縮短訓練時間，實驗應盡量減少隱含層節(jié)點數(shù)。但只有在隱含層節(jié)點數(shù)接近無窮大時，ELM 才能以任意小的誤差逼近任何非線性連續(xù)函數(shù)，達到最優(yōu)精度。為了使學習效率達到較優(yōu)的狀態(tài)，需要協(xié)調(diào)以上兩個因素。在機器學習中，逐步增加隱含層節(jié)點數(shù)是使訓練達到所需精度的一種常用方法。IF-ELM 算法便使用隱含層節(jié)點數(shù)增加策略，其l+1 個隱含層節(jié)點的輸出權重可以利用l個隱含層節(jié)點的輸出權重計算得出，從而減少了計算量。

由xi和yi分別表示第i個訓練輸入和相應的第i個訓練輸出。給定訓練集{(x1,y1)…(xi,yi)…(xk,yk)}，輸入權重W和偏差b，ELM 的訓練誤差則取決于其輸出權重。對于l個隱層節(jié)點的ELM，它的輸出權重為：

其中，H=f(WlX+1 ?bl)，故：

記Y=[y1,y2,…,yk]∈Rm×k。只有當HHT是非奇異時，式（4）才能成立。此處使用了Tikhonov正則化方法來滿足這些約束條件，以避免出現(xiàn)過擬合現(xiàn)象[13-14]。其中I為單位矩陣：

對于具有l(wèi)+1 個隱含層節(jié)點的ELM，其隱含層的輸入權重Wl+1和偏差bl+1如下：

其中，Wl和bl是l個隱含層節(jié)點對應的輸入權重和偏差值，w∈Rn所取數(shù)值與Wl中的數(shù)據(jù)元素具有相同的概率分布，bl+1∈R 所取數(shù)值與bl中的數(shù)據(jù)元素具有相同的概率分布。

l+1 個隱含層節(jié)點的ELM 的輸出權重可由l個隱含層節(jié)點的輸出權重求出，為：

由式（3）和式（5）可得：

設d=f(XTw+bl+11)，式（8）可寫成以下形式：

由Schur Complement公式可得：

其中：

因此，由式（9）、式（10）可得：

假 設m=k2I+dTd-dTHT(k2I+HHT)-1Hd且m≠0，式（11）可由Sherman-Morrison 公式轉化為下式：

Dl+1的推算公式可將式（11）、式（12）、式（13）和式（14）帶入到式（15）中得到。由含有l(wèi)個隱含層節(jié)點的Dl推出Dl+1的過程如下：

由式（15）、式（17）、式（18）可以得到：

根據(jù)以上推導過程不難發(fā)現(xiàn)，通過逐步增加隱含節(jié)點數(shù)量這一方法，可將具有期望近似誤差η(η＞0)的Tikhonov正則化ELM 應用到回歸問題的求解中。

3 在線序列極限學習機

ELM 對模型更新時需要重新代入所有數(shù)據(jù)，不能很好地應用在實際場景中。針對這一問題，OSELM 應運而生。在加入新的訓練數(shù)據(jù)后，隱含層的輸出矩陣由H變?yōu)閇H h]，其中h為新增數(shù)據(jù)隱含層的輸出矩陣。由可以推出新的輸出層權重的公式，具體如下：

其中，Pk+1計算公式如下：

從OS-ELM 的推算可以得出，當H0的秩等于隱含層節(jié)點數(shù)時，OS-ELM 和ELM 在訓練誤差和泛化性能等方面表現(xiàn)相近。OS-ELM 包括初始部分和在線學習兩部分。在初始部分，訓練算法隨機給定隱含層的輸入權重和偏差，分析計算隱含層的輸出權重。其中，隱含層節(jié)點數(shù)要小于訓練樣本數(shù)。在初始化階段之后進入在線學習部分，學習算法根據(jù)需要逐步學習新增數(shù)據(jù)。

4 無逆矩陣在線序列極限學習機

4.1 算法過程

定義：期望的訓練誤差η，輸入維度為n，輸出維度為m，訓練集的初始數(shù)目為k0，增加的訓練樣本的數(shù)目為k1，初始的訓練集輸入為，訓練集輸出為。初始的ELM訓練模型有l(wèi)個隱含層節(jié)點，輸入權重為，隱含層的偏差值為，輸出權重為。

步驟1 計算出合適的隱含層節(jié)點數(shù)目：

步驟1.1 給出初始的訓練樣本集(xi,yi)，X=[x1,。

步驟1.2 給定初始的隱含層節(jié)點數(shù)目l0，期望的輸出均方誤差η。

步驟1.3 任意取值輸入權重W和偏差b。

步驟1.4 增加任意數(shù)量隱含層節(jié)點數(shù)la，則l0=l0+la，任意選定增加的隱含層節(jié)點的輸入權重w和偏差b0，更新輸入權重W和偏差b：

步驟1.5 計算d=f(XTw+b01)的值。

步驟1.6 計算D的值：

步驟1.7 更新隱含層的輸出權重β=YD。

步驟1.8 計算出增加隱含層節(jié)點后mse的值，其中mse=MSE(Y-βH),若mse小于期望值則轉至步驟2，若mse大于期望值則跳轉到步驟1.4。

步驟2 增加訓練樣本數(shù)目：

步驟2.1 假設新增加的一批訓練樣本的個數(shù)為k1，每次增加n個訓練樣本，計算出隱含層的輸出矩陣H。

步驟2.2 計算隱含層的輸出權重β(k+1)：

步驟2.3 當增加的訓練樣本個數(shù)大于k1時，則繼續(xù)步驟2.4；當增加的訓練樣本小于k1時，則跳轉到步驟2.1。

步驟2.4 輸出權重β(k+1)。

4.2 算法時間復雜度分析

此節(jié)，對IOS-ELM 算法的時間復雜度進行分析。IOS-ELM 算法時間復雜度分析分為兩部分，分別對應上述的步驟1 和步驟2。在步驟1 中，由文獻[3]可以得到，對于每i次迭代，算法的時間復雜度為ο(k0li)，其中k0為訓練樣本的個數(shù)，li為第i次迭代時隱含層的節(jié)點數(shù)。在步驟2 中，對于第i次迭代，算法的時間復雜度為ο(kil0)，其中ki表示第i次迭代時訓練樣本的個數(shù)，l0為步驟1 輸出的最終的節(jié)點數(shù)。由上述分析可以看出，所提算法的時間復雜度只與訓練樣本的數(shù)據(jù)量和其隱含層節(jié)點數(shù)有關，一般情況而言，數(shù)據(jù)集維度的增加對時間復雜度沒有影響。但在實際實驗時，維數(shù)的增加可能需要更多的隱節(jié)點。隨著新增訓練樣本數(shù)量的增加，對算法的時間復雜度會產(chǎn)生一定的影響。如果增加的樣本數(shù)遠大于原始的樣本數(shù)，則理論上會增大算法的時間復雜度。例如對于步驟1 中，對于每i次迭代，原始訓練樣本為k0，增加的樣本數(shù)為，如果，則此時的時間復雜度由ο(k0li)增加到。不過，實際中因為研究的是在線情形，這種情況并不多見。如果增加的訓練樣本數(shù)沒有原始樣本數(shù)多，則對算法的時間復雜度沒有影響。

4.3 算法總結

本文所提的IOS-ELM 算法，對于回歸問題在速度和性能都有很好表現(xiàn)。由于回歸與分類的內(nèi)在聯(lián)系，同樣的框架也可以應用于分類問題[15]。對于一個m類分類問題，屬于第i類的訓練樣本的輸出可以表示為y=ei，其中ei∈Rm，是一個第i項為1，其他項為0 的向量?？梢园凑张c回歸問題相同的步驟來訓練IOS-ELM。在預測階段，IOS-ELM 會根據(jù)測試數(shù)據(jù)生成m維的輸出向量，其中最大元素所在位置即為分類標簽。例如，若輸出向量的m個輸出元素中，第i個元素中具有最大值，則樣本被分類到第i類中。由以上可知，該算法可較好地適用于回歸和分類問題。

5 實驗分析

本章進行實驗分析，以驗證所提出的無逆矩陣在線序列極限學習機算法的有效性。為了更好評估算法的性能，實驗使用機器學習領域中具有幾個代表性的數(shù)據(jù)集進行實驗。這些數(shù)據(jù)集分別來自加利福利亞大學Irvine機器學習庫[16]和支持向量機數(shù)據(jù)庫[17]，數(shù)據(jù)集在數(shù)據(jù)量和維度上有代表性。對于回歸問題，實驗所用數(shù)據(jù)集Energy efficiency數(shù)據(jù)集[18]、Housing 數(shù)據(jù)集[19]、Parkinson數(shù)據(jù)集[20]、Airfoil self-noise數(shù)據(jù)集[21]如表1所示。在測試實驗中，對訓練數(shù)據(jù)集進行預處理，所有輸入數(shù)據(jù)和輸出數(shù)據(jù)都歸一化到[-1,1]。對于分類問題，所用數(shù)據(jù)集Diabetes 數(shù)據(jù)集[16]、Musk 數(shù)據(jù)集[22]、Feritility數(shù)據(jù)集[23]、Spambase數(shù)據(jù)集[16]、CNAE-9 數(shù)據(jù)集、Multiple Features 數(shù)據(jù)集如表2 所示。實驗結果如表3、表4 所示。

Table 1 Introduction to regression data sets表1 回歸數(shù)據(jù)集介紹

Table 2 Introduction to classification data sets表2 分類實驗數(shù)據(jù)集介紹

5.1 實驗環(huán)境

本文所有實驗均在同一環(huán)境下完成，采用在Windows 10 環(huán)境下搭建系統(tǒng)，計算機處理器配置為Intel?CoreTMi3-4150 CPU@3.5 GHz，內(nèi)存4 GB，主算法在Matlab2016b下完成。

Table 3 Experimental results on regression datasets表3 回歸數(shù)據(jù)集的實驗結果

Table 4 Experimental results on classification datasets表4 分類數(shù)據(jù)集的實驗結果

5.2 評估指標

為保證實驗結果真實準確，每個數(shù)據(jù)集對應的各個激活函數(shù)都進行20 次實驗，然后取其平均值作為最終結果。每次實驗隨機選取數(shù)據(jù)集的4/5 作為訓練集，其他的作為測試集。且每次選取訓練集的9/10 作為初始部分的樣本，剩余的1/10 作為在線學習的樣本。對于分類問題，采用常見準確率（accuracy）作為衡量指標。對于回歸問題，采用均方誤差（mse）評估所提出算法的預測性能。并計算分類實驗中準確率和回歸實驗中均方誤差的標準差來評估預測的離散程度。

5.3 實驗結果

表3 顯示了所提出的具有不同激活函數(shù)的IOSELM 算法的回歸性能，激活函數(shù)包括Sigmoid 函數(shù)、Triangular 函數(shù)、Hardlim 函數(shù)和Sine 函數(shù)。在實驗中使用Tikhonov 正則化算法來避免過擬合。實驗部分將所提IOS-ELM 在線學習算法的在線訓練時間與傳統(tǒng)的IF-ELM 批量學習算法學習時間的結果進行比較。由表3 中的結果可以得出，兩個算法在不斷增加訓練樣本之后，所提的IOS-ELM 算法在保證了與IFELM 算法相近的學習性能的情況下，學習速度有了明顯的提高，且新增的樣本數(shù)量越大，所節(jié)省的時間也越多。

表4 顯示了所提的IOS-ELM 算法與IF-ELM 算法在不同激活函數(shù)情況下的分類性能的比較。實驗所用激活函數(shù)與測試回歸性能所用激活函數(shù)相同。由表4 可以看出所提的IOS-ELM 算法與IF-ELM 算法的分類準確率相近（兩個算法的分類的測試準確率相差不超過0.5%），但所提算法在速度上確實有較大的提升。其中CNAE-9 數(shù)據(jù)集與Diabetes 數(shù)據(jù)集的數(shù)據(jù)量相差不大，但是所提IOS-ELM 算法的實驗中，CNAE-9 數(shù)據(jù)集的訓練時間是Diabetes 數(shù)據(jù)集的4 倍左右。這是因為前者數(shù)據(jù)集的維度和類別數(shù)都較大，為達到所需精度選取的隱含層節(jié)點數(shù)較多。最終，訓練時間也隨著隱含層節(jié)點數(shù)的增多而增大。

6 結束語

針對無逆矩陣極限學習機只能將所有數(shù)據(jù)一次性輸入給訓練模型這一問題，本文提出了一個快速準確的無逆矩陣在線序列極限學習機算法。該算法源于批量學習的無逆矩陣極限學習機算法，理論上在一定條件下能夠以任意小期望誤差逼近任意非線性連續(xù)函數(shù)。其首先利用初次的輸入樣本集找到合適的隱含層節(jié)點，然后可以將單個或多個樣本數(shù)據(jù)逐步進入到訓練模型當中，只要確定所期望的輸出誤差，所有隱含層參數(shù)都是任意給定。實驗結果證明，該算法與無逆矩陣極限學習機有著相同的精度和泛化能力，在速度上有很大的提升。在未來的進一步發(fā)展中可以在增加樣本數(shù)據(jù)的同時再增加或刪減隱含層節(jié)點，以達到更好的學習效果。