一種高效二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

曾曉勤 , 周建新 , 鄭　星 , 鐘水明

(1.河海大學(xué) 計(jì)算機(jī)及信息工程學(xué)院 智能科學(xué)與技術(shù)研究所，211100 南京；2.南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院， 210044 南京)

?

一種高效二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

曾曉勤1, 周建新1, 鄭星1, 鐘水明2

(1.河海大學(xué) 計(jì)算機(jī)及信息工程學(xué)院 智能科學(xué)與技術(shù)研究所，211100 南京；2.南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院， 210044 南京)

摘要:為解決二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)(BFNN)缺乏高效實(shí)用學(xué)習(xí)算法的問(wèn)題，提出一種新的融合自適應(yīng)調(diào)節(jié)結(jié)構(gòu)和權(quán)值的BFNN學(xué)習(xí)算法. 該算法借鑒并改進(jìn)了極限學(xué)習(xí)機(jī)(ELM)方法，可以高效地訓(xùn)練單隱層的BFNN來(lái)解決分類問(wèn)題. 為了滿足網(wǎng)絡(luò)的訓(xùn)練精度，算法可以自動(dòng)增加隱層神經(jīng)元個(gè)數(shù)和調(diào)節(jié)網(wǎng)絡(luò)隱層及輸出層神經(jīng)元權(quán)值；同時(shí)為了提高網(wǎng)絡(luò)的泛化精度，算法通過(guò)建立二進(jìn)神經(jīng)元敏感性作為度量隱層神經(jīng)元重要性的尺度，自動(dòng)地裁剪重要性小的神經(jīng)元，并對(duì)裁剪損失的信息進(jìn)行補(bǔ)償. 實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法在處理離散分類問(wèn)題時(shí)的可行性和有效性.

關(guān)鍵詞:二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)； 學(xué)習(xí)算法； 敏感性； 結(jié)構(gòu)裁剪； 分類

二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)(BFNN)是一種離散的前饋多層網(wǎng)絡(luò)，網(wǎng)絡(luò)中神經(jīng)元的激活函數(shù)通常是硬極限函數(shù)或?qū)ΨQ硬極限函數(shù). 理論上，離散問(wèn)題可作為連續(xù)問(wèn)題的特例來(lái)處理，但是對(duì)于那些本質(zhì)上是離散且連續(xù)技術(shù)不直接適用的應(yīng)用領(lǐng)域，如邏輯運(yùn)算、信號(hào)處理、分類與聚類、模式識(shí)別等，BFNN比連續(xù)神經(jīng)網(wǎng)絡(luò)有明顯的優(yōu)勢(shì)[1]. 但是由于激活函數(shù)的離散性質(zhì)使得BFNN無(wú)法使用成熟的BP算法來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行訓(xùn)練[2-3]，迄今為止尚沒(méi)有高效的學(xué)習(xí)算法. 文獻(xiàn)[4-5]針對(duì)BFNN提出了MRII算法，但MRII算法會(huì)使網(wǎng)絡(luò)學(xué)習(xí)陷入局部震蕩，成功率不高，并且在訓(xùn)練集樣本個(gè)數(shù)較多的情況下，MRII算法的收斂速度也不理想. 文獻(xiàn)[6]針對(duì)BFNN從幾何角度提出了一些幾何構(gòu)造算法，這類算法具有自動(dòng)確定網(wǎng)絡(luò)結(jié)構(gòu)的長(zhǎng)處，但是隨意性大，不能有效控制結(jié)構(gòu)規(guī)模. 文獻(xiàn)[1]在MRII算法的基礎(chǔ)上，利用BFNN網(wǎng)絡(luò)的敏感性技術(shù)，對(duì)BFNN網(wǎng)絡(luò)的訓(xùn)練算法進(jìn)行了進(jìn)一步的研究和改進(jìn)，但也存在著網(wǎng)絡(luò)訓(xùn)練的時(shí)間復(fù)雜度過(guò)高等問(wèn)題. 文獻(xiàn)[7-8]針對(duì)單隱層連續(xù)前饋神經(jīng)網(wǎng)絡(luò)提出了極限學(xué)習(xí)機(jī)ELM及其快速學(xué)習(xí)算法. ELM學(xué)習(xí)算法通過(guò)增加隱層神經(jīng)元并隨機(jī)選取權(quán)值和偏置, 以及采用最小二乘法求得輸出層神經(jīng)元權(quán)值，來(lái)使網(wǎng)絡(luò)達(dá)到訓(xùn)練精度要求. 只要隱層神經(jīng)元數(shù)目足夠多，單隱層的前饋神經(jīng)網(wǎng)絡(luò)可以逼近任意的連續(xù)函數(shù)[9]，因此ELM將網(wǎng)絡(luò)結(jié)構(gòu)限制為單隱層，既不失一般性，又省去了對(duì)網(wǎng)絡(luò)隱層數(shù)目的考慮. 因?yàn)镋LM隱層神經(jīng)元權(quán)參數(shù)隨機(jī)給定，需要調(diào)節(jié)的只是隱層神經(jīng)元個(gè)數(shù)和輸出層神經(jīng)元權(quán)參數(shù)，所以ELM學(xué)習(xí)算法效率較BP算法要高. 但是，也正因?yàn)镋LM學(xué)習(xí)算法在增加隱層神經(jīng)元個(gè)數(shù)的同時(shí)，僅隨機(jī)給定權(quán)參數(shù)值，并沒(méi)有進(jìn)行自適應(yīng)調(diào)節(jié)，所以會(huì)導(dǎo)致訓(xùn)練所得的初始網(wǎng)絡(luò)結(jié)構(gòu)較大，而且沒(méi)有充分利用新增神經(jīng)元的潛能，影響后繼對(duì)網(wǎng)絡(luò)裁剪的效率.

本文針對(duì)單隱層二進(jìn)前饋神經(jīng)網(wǎng)絡(luò)，提出一種類似ELM學(xué)習(xí)算法但又不盡相同的高效學(xué)習(xí)算法. 該算法不僅調(diào)節(jié)輸出層神經(jīng)元的權(quán)值，同時(shí)也會(huì)調(diào)節(jié)隱層神經(jīng)元權(quán)參數(shù)，它的合理性從理論上可解釋為：隱層通過(guò)增加神經(jīng)元個(gè)數(shù)將網(wǎng)絡(luò)輸入向高維空間映射，使得隱層輸出更容易線性可分，從而方便輸出層的分類，并且在增加隱層神經(jīng)元個(gè)數(shù)的同時(shí)，對(duì)隱層神經(jīng)元權(quán)參數(shù)進(jìn)行適當(dāng)調(diào)節(jié)，使得訓(xùn)練所得的網(wǎng)絡(luò)結(jié)構(gòu)不至于過(guò)大，從而提高裁剪的效率.

本文學(xué)習(xí)算法具有以下創(chuàng)新：1)能使網(wǎng)絡(luò)在較小的結(jié)構(gòu)內(nèi)快速滿足學(xué)習(xí)精度要求；2)提出利用神經(jīng)元輸出對(duì)其輸入擾動(dòng)的敏感性打造重要性尺度，來(lái)度量網(wǎng)絡(luò)隱層中神經(jīng)元的重要性，指導(dǎo)裁剪網(wǎng)絡(luò)隱層中起作用小的神經(jīng)元；3)提出利用輸出層神經(jīng)元偏置以及適當(dāng)?shù)脑賹W(xué)習(xí)對(duì)裁剪后網(wǎng)絡(luò)信息丟失進(jìn)行補(bǔ)償.

1BFNN模型及符號(hào)約定

BFNN是一種離散型的前饋多層神經(jīng)網(wǎng)絡(luò)，由多個(gè)離散二進(jìn)神經(jīng)元(BN)按一定層次結(jié)構(gòu)組成，用以建立輸入與輸出之間的映射.

BN是BFNN的基本構(gòu)造元素，構(gòu)成網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，也是BFNN最簡(jiǎn)單的形式. 結(jié)構(gòu)上，BN一般由輸入、連接權(quán)、偏置、激活函數(shù)以及輸出等幾部分組成. 一個(gè)BN的工作原理是把輸入分量與對(duì)應(yīng)權(quán)分量乘積的和，再加上一個(gè)偏置產(chǎn)生一個(gè)模擬量，然后送入激活函數(shù)得到一個(gè)數(shù)字輸出. 在本文中，輸入向量表示為X=(x1,x2,…,xn)T∈{-1,1}n，與之相關(guān)聯(lián)的權(quán)記為W=(w1,w2,…,wn)T∈Rn，w0∈R表示偏置. 就功能而言，BN實(shí)現(xiàn)了一種從輸入空間到輸出空間的邏輯映射關(guān)系，即f:{-1,1}n→{-1,1}，可表示如下：

BFNN由多個(gè)BN神經(jīng)元按一定的規(guī)則連接而成. 在BFNN中，BN分層組織，每層由若干個(gè)具有相同輸入的BN組成，相鄰兩層上的BN彼此互相連接，同層和非相鄰層上的BN彼此沒(méi)有連接. 各層神經(jīng)元的輸出構(gòu)成該層的輸出，前層輸出作為相鄰后繼層每個(gè)神經(jīng)元的輸入，第一層神經(jīng)元的輸入是網(wǎng)絡(luò)輸入，最后一層的輸出是網(wǎng)絡(luò)輸出. 為表達(dá)方便，用記號(hào)n0-n1-n2來(lái)表示單隱層BFNN，其中，n0代表輸入層并指出輸入維數(shù)，n1代表隱層并指出隱層神經(jīng)元個(gè)數(shù)，n2代表輸出層并指出輸出層神經(jīng)元個(gè)數(shù). 此外，用Xn×1∈Rn表示整個(gè)網(wǎng)絡(luò)的輸入，Ym×1∈{-1,1}m表示網(wǎng)絡(luò)的輸出.

從功能上來(lái)看，BFNN通過(guò)學(xué)習(xí)機(jī)制調(diào)整自身網(wǎng)絡(luò)參數(shù)(包括BN的權(quán)值和偏置以及網(wǎng)絡(luò)結(jié)構(gòu))來(lái)實(shí)現(xiàn)給定訓(xùn)練樣本數(shù)據(jù)中所蘊(yùn)含的輸入輸出之間的映射關(guān)系.

2關(guān)鍵技術(shù)

2.1調(diào)權(quán)學(xué)習(xí)算法

2.1.1調(diào)權(quán)規(guī)則

在錯(cuò)誤更正這類調(diào)權(quán)算法中，有許多權(quán)值更新規(guī)則，如Mays’，LMS以及感知機(jī)規(guī)則等. 在本學(xué)習(xí)算法中，為了使當(dāng)前樣本的學(xué)習(xí)對(duì)權(quán)值調(diào)整的幅度盡可能小，從而減小對(duì)已有網(wǎng)絡(luò)的破壞，采用感知機(jī)學(xué)習(xí)規(guī)則[10]進(jìn)行調(diào)權(quán). 以單個(gè)BN為例，規(guī)則可表示為

式中：Wnew和Wold是調(diào)整后和調(diào)整前的權(quán)，γ為學(xué)習(xí)速率，t為理想輸出，a為實(shí)際輸出，X為輸入樣本. 該數(shù)學(xué)式的表示為：對(duì)應(yīng)當(dāng)前輸入樣本，當(dāng)實(shí)際輸出與理想輸出不一致時(shí)，權(quán)需要向當(dāng)前輸入樣本的方向做適當(dāng)調(diào)整. 顯然，這樣的學(xué)習(xí)過(guò)程是一個(gè)循環(huán)迭代的過(guò)程，直至完成對(duì)當(dāng)前樣本的學(xué)習(xí)為止.

2.1.2簡(jiǎn)化的MRII學(xué)習(xí)算法

在文獻(xiàn)[4]給出的MRII算法中，根據(jù)最小擾動(dòng)原則，提出了以每個(gè)BN的加權(quán)和的絕對(duì)值為衡量標(biāo)準(zhǔn)的置信度概念，通過(guò)不斷迭代翻轉(zhuǎn)置信度最小的神經(jīng)元來(lái)找到分類效果最理想的網(wǎng)絡(luò)權(quán)值. 事實(shí)上，由于置信度并不能精確地反映BN的學(xué)習(xí)對(duì)整個(gè)網(wǎng)絡(luò)的影響，因此MRII算法會(huì)使網(wǎng)絡(luò)學(xué)習(xí)陷入局部震蕩，導(dǎo)致成功率不高. 在本學(xué)習(xí)算法中，并不需要一個(gè)精確衡量BN的學(xué)習(xí)對(duì)于網(wǎng)絡(luò)影響程度的度量，因?yàn)樵诮o定結(jié)構(gòu)，如果網(wǎng)絡(luò)無(wú)法收斂，算法會(huì)自動(dòng)增加隱層神經(jīng)元個(gè)數(shù)，將網(wǎng)絡(luò)輸入向高維空間映射，使得隱層輸出更容易線性可分，從而方便輸出層的分類. 因此，本算法仍采用置信度作為隱層調(diào)權(quán)的依據(jù)，但是只針對(duì)單個(gè)樣本進(jìn)行學(xué)習(xí)，具體學(xué)習(xí)算法如下：

1)將樣本送入網(wǎng)絡(luò)進(jìn)行計(jì)算.

2)如果網(wǎng)絡(luò)對(duì)當(dāng)前樣本的輸出正確，直接退出.

3)在隱層執(zhí)行以下步驟：

①計(jì)算隱層神經(jīng)元置信度.

②根據(jù)置信度從小到大的順序，對(duì)隱層神經(jīng)元進(jìn)行排序.

③對(duì)排序后的神經(jīng)元依次做翻轉(zhuǎn)的嘗試. 如果這次嘗試使得樣本理想輸出與網(wǎng)絡(luò)輸出一致，則接受這次翻轉(zhuǎn)，同時(shí)退出；如果這次嘗試可以降低網(wǎng)絡(luò)的輸出錯(cuò)誤，則同樣接受這次翻轉(zhuǎn)嘗試，轉(zhuǎn)去執(zhí)行步驟②；如果這次嘗試，并沒(méi)有降低網(wǎng)絡(luò)的輸出錯(cuò)誤，則拒絕這次嘗試，然后對(duì)置信度次小的下一個(gè)神經(jīng)元進(jìn)行翻轉(zhuǎn)嘗試.

4)對(duì)輸出層神經(jīng)元進(jìn)行調(diào)權(quán)，使網(wǎng)絡(luò)輸出與樣本理想輸出完全一致，完成網(wǎng)絡(luò)對(duì)該樣本的學(xué)習(xí).

不難看出，以上樣本學(xué)習(xí)算法的思想在于，網(wǎng)絡(luò)首先通過(guò)調(diào)節(jié)隱層神經(jīng)元權(quán)參數(shù)，以減少網(wǎng)絡(luò)輸出錯(cuò)誤，如果在隱層無(wú)法將網(wǎng)絡(luò)輸出錯(cuò)誤減少到零，則對(duì)輸出層神經(jīng)元調(diào)權(quán)直接完成對(duì)單個(gè)樣本的學(xué)習(xí).

2.2由輸入擾動(dòng)引起的BN敏感性及其計(jì)算

本節(jié)所定義的敏感性度量，期望它能用來(lái)反映由BN輸入擾動(dòng)導(dǎo)致的輸出擾動(dòng)程度. 因此，此處的敏感性定義為在所有輸入模式點(diǎn)中由輸入擾動(dòng)導(dǎo)致BN輸出值發(fā)生變化的概率，表達(dá)式為

式中：Ninp是所有輸入模式點(diǎn)的個(gè)數(shù)，Npert是對(duì)每個(gè)輸入模式點(diǎn)進(jìn)行擾動(dòng)的次數(shù)，Nvar是所有模式點(diǎn)經(jīng)不同擾動(dòng)后輸出發(fā)生變化的次數(shù)總和.ES()是將S視為統(tǒng)計(jì)變量求得的數(shù)學(xué)期望. 如此定義的敏感性是神經(jīng)元權(quán)W和偏置w0的函數(shù)，反映了BN輸入的變化對(duì)輸出變化的影響. 由于不同的BN有不同的權(quán)和偏置值，因此敏感性可作為一個(gè)相對(duì)尺度來(lái)度量同一層中不同神經(jīng)元對(duì)下一層輸入的影響程度. 顯然，敏感性小的神經(jīng)元對(duì)下一層輸入的影響相對(duì)要小.

1)Nvar初始化為0.

2)循環(huán)：對(duì)X的各種可能取值計(jì)算σ1=XTW+w0.

循環(huán)：對(duì)ΔX使得當(dāng)前X只有一個(gè)分量發(fā)生變化的各種可能進(jìn)行以下統(tǒng)計(jì).

循環(huán)：對(duì)X發(fā)生變化的分量以步長(zhǎng)h在區(qū)間[-a,a]的各種可能擾動(dòng)計(jì)算σ2=ΔXTW.

如果σ1<0且σ2≥-σ1，Nvar=Nvar+1；如果σ1≥0且σ2<-σ1，Nvar=Nvar+1.

3)計(jì)算得出Nvar結(jié)果.

4)計(jì)算敏感性的結(jié)果為

2.3BN重要性尺度

前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)仍是一個(gè)值得深入研究的問(wèn)題，研究已得出結(jié)論是，網(wǎng)絡(luò)結(jié)構(gòu)在能滿足訓(xùn)練精度前提下應(yīng)盡可能的小，這樣既可減少開(kāi)銷又可獲得較好的泛化性能. 裁減網(wǎng)絡(luò)結(jié)構(gòu)是獲得小結(jié)構(gòu)網(wǎng)絡(luò)的一條途徑，文獻(xiàn)[11-12]綜述了早前這方面的研究情況，近年提出的ELM方法中也可見(jiàn)到對(duì)隱層節(jié)點(diǎn)裁減的討論[13]. 問(wèn)題關(guān)鍵是如何建立一個(gè)能有效度量節(jié)點(diǎn)重要性的尺度，據(jù)此來(lái)定位網(wǎng)絡(luò)隱層中重要性小的神經(jīng)元，使得裁剪后丟失的信息盡可能的少. 前面定義的BN敏感性反映了輸入變化對(duì)輸出的影響，當(dāng)敏感性值很小時(shí)，意味輸出近乎一個(gè)常量，在網(wǎng)絡(luò)起的作用一定相對(duì)較小. 注意到隱層BN敏感性只可能反映對(duì)輸出層的輸入影響，而輸出層的輸出由其輸入和權(quán)值共同決定，所以敏感性還不能完全控制對(duì)輸出層輸出的影響，因?yàn)楸M管隱層BN敏感性相對(duì)較小，乘上一個(gè)較大的輸出層權(quán)值將可能放大輸出層的輸入變化. 因此，需要將敏感性和輸出層權(quán)值一起考慮，來(lái)建立對(duì)隱層BN重要性的度量. 此處將BN重要性定義為BN本身的敏感性與其連接到輸出層所有權(quán)值絕對(duì)值和的乘積，表達(dá)式如下：

2.4信息丟失的補(bǔ)償

BN的重要性尺度可用來(lái)幫助裁剪隱層上的節(jié)點(diǎn). 然而，訓(xùn)練好的BFNN網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都會(huì)包含有用的信息，裁掉一個(gè)節(jié)點(diǎn)必然會(huì)引起網(wǎng)絡(luò)信息或多或少的丟失，導(dǎo)致性能變差. 為了彌補(bǔ)信息的丟失，可有以下方法對(duì)裁剪隱層節(jié)點(diǎn)后的網(wǎng)絡(luò)進(jìn)行補(bǔ)償：

2)對(duì)調(diào)整后的網(wǎng)絡(luò)，用訓(xùn)練樣本數(shù)據(jù)再對(duì)網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)挠?xùn)練.

3學(xué)習(xí)算法

給出一個(gè)完整只考慮單隱層BFNN的學(xué)習(xí)算法. 鑒于輸入維數(shù)和輸出層BN個(gè)數(shù)通?？筛鶕?jù)應(yīng)用需求確定，本算法最終給出一個(gè)隱層結(jié)構(gòu)盡可能小以及確定權(quán)值的BFNN. 在學(xué)習(xí)算法中，一次迭代是指訓(xùn)練樣本集中的所有樣本均輸入網(wǎng)絡(luò)完成一次學(xué)習(xí). 以下是算法的具體步驟：

1)用預(yù)先給定的結(jié)構(gòu)和隨機(jī)的權(quán)值和偏置來(lái)初始化BFNN網(wǎng)絡(luò).

2)在訓(xùn)練樣本集中隨機(jī)挑選一個(gè)樣本，使用2.1.2給出的樣本學(xué)習(xí)算法送入網(wǎng)絡(luò)進(jìn)行訓(xùn)練，直到樣本集中的所有樣本均完成一次學(xué)習(xí)(升結(jié)構(gòu)階段的一次迭代).

3)如果在給定的迭代次數(shù)內(nèi)訓(xùn)練的BFNN網(wǎng)絡(luò)能夠達(dá)到要求的訓(xùn)練精度，則停止訓(xùn)練，執(zhí)行步驟4)開(kāi)始裁剪；否則增加一個(gè)隱層節(jié)點(diǎn)(權(quán)值和偏置隨機(jī)給出)，然后執(zhí)行步驟2).

4)備份當(dāng)前BFNN網(wǎng)絡(luò)，包括它的結(jié)構(gòu)以及各BN權(quán)值和偏置，并計(jì)算隱層所有節(jié)點(diǎn)的敏感性和重要性，試圖裁掉BN重要性最小的節(jié)點(diǎn).

5)根據(jù)被裁剪掉的BN，對(duì)輸出層BN的偏置進(jìn)行補(bǔ)償.

6)在訓(xùn)練樣本集中隨機(jī)挑選一個(gè)樣本，使用2.1.2給出的樣本學(xué)習(xí)算法送入網(wǎng)絡(luò)進(jìn)行再訓(xùn)練，直到樣本集中的所有樣本均完成一次學(xué)習(xí)(裁剪階段的一次迭代).

7)如果在給定的迭代次數(shù)內(nèi)訓(xùn)練的BFNN網(wǎng)絡(luò)能夠達(dá)到要求的訓(xùn)練精度，則停止訓(xùn)練，執(zhí)行步驟4)繼續(xù)裁剪；否則將BFNN網(wǎng)絡(luò)恢復(fù)至之前由步驟4)所備份的結(jié)構(gòu)，并給出該網(wǎng)絡(luò)最終的權(quán)和偏置值.

4實(shí)驗(yàn)驗(yàn)證

用若干實(shí)驗(yàn)來(lái)驗(yàn)證上述BFNN學(xué)習(xí)算法的有效性. 在這些實(shí)驗(yàn)中，需要驗(yàn)證以下幾點(diǎn)：

1)上述學(xué)習(xí)算法可以高效將BFNN網(wǎng)絡(luò)訓(xùn)練到理想的精度，并且得到一個(gè)較小的網(wǎng)絡(luò)結(jié)構(gòu).

2)裁剪后的網(wǎng)絡(luò)在泛化性能上要優(yōu)于原來(lái)的網(wǎng)絡(luò).

實(shí)驗(yàn)以Microsoft Visual C++ 2013為平臺(tái)進(jìn)行，選擇了三類具有代表性的問(wèn)題：一是奇偶校驗(yàn)問(wèn)題；二是針對(duì)UCI數(shù)據(jù)庫(kù)中Iris數(shù)據(jù)集的分類問(wèn)題；三是針對(duì)UCI數(shù)據(jù)庫(kù)中Monk數(shù)據(jù)集的分類問(wèn)題. 為了使網(wǎng)絡(luò)快速收斂到給定訓(xùn)練精度，實(shí)驗(yàn)中均指定樣本集在某一網(wǎng)絡(luò)結(jié)構(gòu)上只進(jìn)行一次迭代，如果經(jīng)過(guò)該次迭代，無(wú)法達(dá)到給定訓(xùn)練精度，則直接增加隱層節(jié)點(diǎn)數(shù)，接著繼續(xù)進(jìn)行下一次迭代訓(xùn)練，如此循環(huán)往復(fù)，直至達(dá)到訓(xùn)練精度，之后進(jìn)行裁剪. 對(duì)于裁剪，設(shè)定在某一網(wǎng)絡(luò)結(jié)構(gòu)上進(jìn)行迭代的最大次數(shù)為200次，如果經(jīng)過(guò)200次的迭代訓(xùn)練，網(wǎng)絡(luò)仍然無(wú)法達(dá)到給定訓(xùn)練精度，則裁剪完畢，給出網(wǎng)絡(luò)最終的權(quán)參數(shù).

4.1算法高效性驗(yàn)證

4.1.1奇偶校驗(yàn)分類實(shí)驗(yàn)

奇偶校驗(yàn)是較難的線性不可分的二分類問(wèn)題，它的每一個(gè)輸入樣本點(diǎn)都位于一個(gè)m維超立方的頂點(diǎn). 實(shí)驗(yàn)分別對(duì)2維、5維以及7維奇偶校驗(yàn)各做了10次，要求每次實(shí)驗(yàn)均達(dá)到100%的訓(xùn)練精度. 使用記號(hào)m-n-l來(lái)表示m維輸入，隱層含有n個(gè)節(jié)點(diǎn)以及輸出層含有l(wèi)個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)初始結(jié)構(gòu).

表1～3分別記錄了對(duì)2維、5維以及7維奇偶校驗(yàn)問(wèn)題的實(shí)驗(yàn)結(jié)果，表明算法可以用較少迭代達(dá)到100%訓(xùn)練精度，并同時(shí)將網(wǎng)絡(luò)裁剪到一個(gè)較小的結(jié)構(gòu).

表1針對(duì)2維奇偶校驗(yàn)本文算法實(shí)驗(yàn)結(jié)果(網(wǎng)絡(luò)初始結(jié)構(gòu)2-2-1)

實(shí)驗(yàn)序號(hào)升結(jié)構(gòu)階段未經(jīng)裁剪的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)裁剪階段經(jīng)裁剪后的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)總迭代次數(shù)165338232213343325432224554211156432367542378543489322131065249

表2針對(duì)5維奇偶校驗(yàn)本文算法實(shí)驗(yàn)結(jié)果(網(wǎng)絡(luò)初始結(jié)構(gòu)5-5-1)

實(shí)驗(yàn)序號(hào)升結(jié)構(gòu)階段未經(jīng)裁剪的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)裁剪階段經(jīng)裁剪后的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)總迭代次數(shù)11410547572171352639325216598041285111951612522523761286189197715115233482420526469252152312521021175145162

表3針對(duì)7維奇偶校驗(yàn)本文算法實(shí)驗(yàn)結(jié)果(網(wǎng)絡(luò)初始結(jié)構(gòu)7-7-1)

實(shí)驗(yàn)序號(hào)升結(jié)構(gòu)階段未經(jīng)裁剪的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)裁剪階段經(jīng)裁剪后的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)總迭代次數(shù)1504412941382453913150189382767213289474681411918754539823127066256918123775650896146865599287346979731327634910655912125184

4.1.2Iris數(shù)據(jù)集分類實(shí)驗(yàn)

UCI數(shù)據(jù)庫(kù)中的Iris數(shù)據(jù)集[13]為三分類問(wèn)題，共含150個(gè)樣本，4維輸入. 實(shí)驗(yàn)中用4-2-2結(jié)構(gòu)作為網(wǎng)絡(luò)初始結(jié)構(gòu)，進(jìn)行10組實(shí)驗(yàn)，當(dāng)網(wǎng)絡(luò)訓(xùn)練到98%以上的精度后，開(kāi)始裁剪，并保證裁剪后的精度仍然為98%以上. 實(shí)驗(yàn)結(jié)果如表4所示，表明算法可以保證在達(dá)到給定精度的情況下，同時(shí)將網(wǎng)絡(luò)裁剪到一個(gè)較小的結(jié)構(gòu).

表4針對(duì)Iris數(shù)據(jù)集本文算法實(shí)驗(yàn)結(jié)果(網(wǎng)絡(luò)初始結(jié)構(gòu)4-2-2)

實(shí)驗(yàn)序號(hào)升結(jié)構(gòu)階段未經(jīng)裁剪的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)裁剪階段經(jīng)裁剪后的隱層節(jié)點(diǎn)數(shù)迭代次數(shù)總迭代次數(shù)1151444458222212134155329282117145420193114133514132708362423389112776234408171621511679292821511791027262121147

4.1.3本文算法與MRII算法對(duì)比

為了驗(yàn)證本文算法的高效性，對(duì)傳統(tǒng)的MRII學(xué)習(xí)算法與本文算法做了完整的對(duì)比實(shí)驗(yàn). 對(duì)固定網(wǎng)絡(luò)初始結(jié)構(gòu)的BFNN隨機(jī)給定初始權(quán)值與偏置，分別使用本文算法與MRII算法各做10組實(shí)驗(yàn)，記錄下網(wǎng)絡(luò)收斂次數(shù)以及收斂所需的迭代次數(shù)均值. 由于MRII不具備調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)的能力，因此其網(wǎng)絡(luò)初始結(jié)構(gòu)即為最終結(jié)構(gòu)；而本文算法會(huì)在網(wǎng)絡(luò)初始結(jié)構(gòu)的基礎(chǔ)上增加隱層節(jié)點(diǎn)個(gè)數(shù)，達(dá)到所需精度后進(jìn)行裁剪，如果經(jīng)裁剪后的網(wǎng)絡(luò)隱層節(jié)點(diǎn)個(gè)數(shù)不大于網(wǎng)絡(luò)初始結(jié)構(gòu)，則視為收斂，并且記錄網(wǎng)絡(luò)裁剪到初始結(jié)構(gòu)隱層節(jié)點(diǎn)數(shù)時(shí)所需的迭代次數(shù). 表5分別記錄了本文算法與MRII算法對(duì)于2維、5維、7維奇偶校驗(yàn)以及Iris數(shù)據(jù)集的分類實(shí)驗(yàn)對(duì)比結(jié)果. 其中，奇偶校驗(yàn)實(shí)驗(yàn)的最大迭代次數(shù)為1 000次，所需達(dá)到的訓(xùn)練精度為100%，Iris數(shù)據(jù)集分類實(shí)驗(yàn)的最大迭代次數(shù)為500次，所需達(dá)到的訓(xùn)練精度為98%. 如果達(dá)到最大迭代次數(shù)，網(wǎng)絡(luò)仍然無(wú)法訓(xùn)練到給定精度，則視為不收斂.

表5　本文算法與MRII算法實(shí)驗(yàn)對(duì)比結(jié)果

從結(jié)果對(duì)比中不難看出，對(duì)于同一網(wǎng)絡(luò)結(jié)構(gòu)，多數(shù)情況下本文算法相比MRII收斂率更高，并且可以用更少迭代達(dá)到給定訓(xùn)練精度. MRII算法的實(shí)驗(yàn)結(jié)果好壞特別依賴于初始權(quán)值的給定，如果初始權(quán)值給的不好，那么MRII算法極易陷入局部震蕩，從而需要較多的迭代次數(shù)來(lái)進(jìn)行網(wǎng)絡(luò)的訓(xùn)練，甚至很可能無(wú)法收斂，這一點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)較小的時(shí)表現(xiàn)更為明顯. 而本文算法分為升結(jié)構(gòu)與裁剪結(jié)構(gòu)兩個(gè)階段，在升結(jié)構(gòu)階段為了將BFNN訓(xùn)練至給定精度，算法使BFNN從一個(gè)小結(jié)構(gòu)網(wǎng)絡(luò)通過(guò)逐漸增加隱層神經(jīng)元個(gè)數(shù)升至一個(gè)大結(jié)構(gòu)網(wǎng)絡(luò)，因此算法收斂速度與成功率對(duì)于初始網(wǎng)絡(luò)給定的權(quán)值依賴較小并且一定可以收斂. 例如，在Iris分類實(shí)驗(yàn)中，可以明顯看出MRII算法的實(shí)驗(yàn)結(jié)果好壞依賴于初始權(quán)值給定的好壞，如果初始權(quán)值給定的好，那么以較少的迭代次數(shù)就可使網(wǎng)絡(luò)收斂，但是如果初始權(quán)值給的不好，那么很可能無(wú)法收斂. 從表5可以看出，多數(shù)情況下MRII算法在Iris數(shù)據(jù)集上達(dá)到最大迭代次數(shù)后仍然無(wú)法收斂，而本文算法基本穩(wěn)定在100次左右迭代即可收斂.

4.2算法泛化性能驗(yàn)證

使用UCI標(biāo)準(zhǔn)樣本庫(kù)中的Monk分類問(wèn)題中的一個(gè)數(shù)據(jù)集Monk1來(lái)進(jìn)行實(shí)驗(yàn)驗(yàn)證. Monk1問(wèn)題為兩分類問(wèn)題，共含124個(gè)樣本，6維輸入. 實(shí)驗(yàn)中網(wǎng)絡(luò)的初始結(jié)構(gòu)為6-2-1，當(dāng)網(wǎng)絡(luò)訓(xùn)練精度達(dá)到100%后，開(kāi)始裁剪，經(jīng)過(guò)裁剪和補(bǔ)償后，仍然保證精度為100%. 使用Monk1問(wèn)題來(lái)驗(yàn)證裁剪對(duì)網(wǎng)絡(luò)泛化率的影響. 在每一次實(shí)驗(yàn)中，將Monk1樣本集隨機(jī)劃分成60%的訓(xùn)練樣本集與40%的測(cè)試集. 將訓(xùn)練樣本集訓(xùn)練到100%的精度后，分別統(tǒng)計(jì)未經(jīng)裁剪與經(jīng)過(guò)裁剪后網(wǎng)絡(luò)對(duì)于測(cè)試集的泛化率. 同之前的奇偶校驗(yàn)與Iris實(shí)驗(yàn)一樣，為了快速收斂到所需精度，算法在升結(jié)構(gòu)階段在某一網(wǎng)絡(luò)結(jié)構(gòu)只進(jìn)行1次迭代，如果達(dá)不到訓(xùn)練精度，直接升隱層節(jié)點(diǎn)，因此在裁剪前通常會(huì)獲得較大的網(wǎng)絡(luò)結(jié)構(gòu). 但可以通過(guò)在裁剪階段進(jìn)行較多次數(shù)的迭代學(xué)習(xí)，來(lái)減小網(wǎng)絡(luò)規(guī)模. 實(shí)驗(yàn)結(jié)果如表6所示，多數(shù)經(jīng)過(guò)裁剪后的較小結(jié)構(gòu)網(wǎng)絡(luò)比起未經(jīng)裁剪的網(wǎng)絡(luò)有著更好的泛化率.

表6　Monk實(shí)驗(yàn)(網(wǎng)絡(luò)初始結(jié)構(gòu)6-2-1)

5結(jié)論

本文給出一種帶結(jié)構(gòu)調(diào)整的高效單隱層BFNN學(xué)習(xí)算法，解決了長(zhǎng)期以來(lái)BFNN沒(méi)有高效學(xué)習(xí)算法的難題. 該算法能自適應(yīng)調(diào)節(jié)隱層結(jié)構(gòu)并同時(shí)對(duì)隱層以及輸出層神經(jīng)元的權(quán)參數(shù)進(jìn)行調(diào)整，在滿足給定訓(xùn)練精度的前提下通過(guò)打造BN重要性尺度盡可能地裁剪隱層BN，使網(wǎng)絡(luò)具有較小的結(jié)構(gòu). 通過(guò)處理難度大的奇偶校驗(yàn)問(wèn)題以及UCI數(shù)據(jù)集里的真實(shí)問(wèn)題，驗(yàn)證了算法的可行性和有效性.

參考文獻(xiàn)

[1] ZHONG Shuiming, ZENG Xiaoqin, LIU Huiyi, et al. Approximate computation of Madaline sensitivity based on discrete stochastic technique [J]. Science China: Information Science, 2010,53(12): 2399-2414.

[2] RUMELHART D E, HINTON G E, WILLIAMS R J. Learning representations by back propagation errors [J]. Nature, 1986,323(9): 533-536.

[3] RUMELHART D E, MCCLELLAND J L. Parallel distributed processing: explorations in the microstructure of cognition [M]. Cambridge: MIT Press, 1986.

[4] WINTER R, WIDROW B.Madaline rule II: a training algorithm for neural networks[C] // IEEE International Conference on Neural Networks. San Diega: IEEE Publishrs,1988: 401-408.

[5] WINTER R.Madaline rule II: a new method for training networks for BNs [D]. Stanford: Standford University, 1989.

[6] 張軍英，許進(jìn). 二進(jìn)前向人工神經(jīng)網(wǎng)絡(luò)理論與應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2001: 157-168.

[7] HUANG G B, ZHU Q, SIEW C K. Extreme learning machine: a new learning scheme of feedforward neural networks[C]//Proceedings of the IEEE International Joint Conference on Neural Networks.[s. n.]:IEEE,2004:985-990.

[8] HUANG G B, ZHU Q, SIEW C K. Extreme learning machine: theory and applications[J]. Neurocomputing，2006，70(1/2/3)：489-501.

[9] HORNIK K, STINCHCOMBEA M, WHITE H. Miltilayer feedforward networks are universal approximators[J]. Neural Networks，1989，2(5)：359-366.

[10]MARTIN T H, HOWARD B D, MARK H B. Neural Network Design[M].Beijing: China Machine Press, 2002: 24-27.

[11]REED R. Pruning algorithms—a survey[J]. IEEE Transactions on Neural Networks, 1993,4(5):740-747.

[12]ENGELBRECHT A P. A new pruning heuristic based on variance analysis of sensitivity information[J].IEEE Transactions on Neural Networks,2001,12(6):1386-1398.

[13]MICHE Y, SORJAMAA A, BAS P, et al. OP-ELM: optimally pruned extreme learning machine [J]. IEEE Trans on Neural Networks, 2010, 21(1): 158-162.

(編輯王小唯苗秀芝)

An efficient learning algorithm for binary feedforward neural networks

ZENG Xiaoqin1, ZHOU Jianxin1, ZHENG Xing1, ZHONG Shuiming2

(1. Institute of Intelligence Science and Technology, Computer and Information College, Hohai University, 211100 Nanjing, China;2. School of Computer and Software, Nanjing University of Information Science and Technology, 210044 Nanjing, China)

Abstract:Focusing on the lack of efficient and practical learning algorithm for Binary Feedforward Neural Networks (BFNN), a novel learning algorithm by fusing the self-adaptations of both architecture and weight for training BFNN is proposed. Based on improving the methodology of Extreme Learning Machines (ELM), the algorithm can effectively train BFNNs with single hidden layer for solving classification problems. In order to satisfy training accuracy, the algorithm can automatically increase hidden neurons and adjust the neuron’s weights with the Perceptron Learning Rule. As to improve generalization accuracy, the algorithm can automatically, by establishing binary neuron’s sensitivity as a tool for measuring the relevance of each hidden neuron, prune the least relevant hidden neuron with some compensation for information losing due to the pruning. Experiment results verified the feasibility and effectiveness of the proposed algorithm.

Keywords:binary feedforward neural network; learning algorithm; sensitivity; architecture pruning; classification

中圖分類號(hào):TP183

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):0367-6234(2016)05-0148-07

通信作者:周建新， zhoujx0219@163.com.

作者簡(jiǎn)介:曾曉勤(1957—)，男，教授，博士生導(dǎo)師.

基金項(xiàng)目:國(guó)家自然科學(xué)基金項(xiàng)目(60971088).

收稿日期:2015-05-08.

doi：10.11918/j.issn.0367-6234.2016.05.024