吳正江,陳如校,張霄宏

(河南理工大學 計算機科學與技術學院,河南 焦作 454003)

1 引 言

人工神經(jīng)網(wǎng)絡被廣泛應用于模式識別和數(shù)據(jù)挖掘領域,例如圖像信號處理[1],語音識別等.BP神經(jīng)網(wǎng)絡是目前各個領域使用的最廣泛的人工神經(jīng)網(wǎng)絡之一,能夠通過學習,無限接近任意曲面的邊界而無需事先知道具體的數(shù)學方程[2].

早期,BP神經(jīng)網(wǎng)絡的訓練都是在單機下進行.隨著數(shù)據(jù)的增大,單機下的訓練變得越來越耗時,可能需要幾天,一周甚至無法完成模型的訓練.因此,提高BP神經(jīng)網(wǎng)絡面向大規(guī)模數(shù)據(jù)集時的訓練速度,具有重要的意義[3].

并行化是解決上述問題的方案之一.基本上BP神經(jīng)網(wǎng)絡的并行化有兩種方式:結構并行化與數(shù)據(jù)并行化.在結構并行化時,將BP網(wǎng)絡結構中的各個節(jié)點映射到集群中的各個節(jié)點上.這種方式的缺點是各個節(jié)點之間頻繁的進行通信協(xié)調(diào),只適用于小數(shù)據(jù)量的復雜神經(jīng)網(wǎng)絡的并行化.而在數(shù)據(jù)并行化方式下,整個數(shù)據(jù)集被切分成各個小的子數(shù)據(jù)集,由集群中的各個子節(jié)點并行處理屬于自己的那部分子數(shù)據(jù)集.同時,在訓練過程中存在兩種對連接權值進行更新的模式:逐個更新和批更新.在逐個更新模式下,神經(jīng)網(wǎng)絡每讀取一個樣本進行處理之后便對網(wǎng)絡連接權值進行更新;而在批更新模式下,在所有的數(shù)據(jù)處理一遍之后再一次性對權值進行更新.

隨著近些年大數(shù)據(jù)平臺Hadoop的普及,基于Hadoop平臺下的BP神經(jīng)網(wǎng)絡并行化得到了很大的發(fā)展.目前大多數(shù)在Hadoop下實現(xiàn)的對BP神經(jīng)網(wǎng)絡并行化的研究都采用數(shù)據(jù)并行化下的批更新操作[4-10].其中[4]通過對大規(guī)模移動數(shù)據(jù)的分類,采用Adaboost算法對BP神經(jīng)網(wǎng)絡進行優(yōu)化,實現(xiàn)了BP神經(jīng)網(wǎng)絡的并行化,[5,6]通過對[4]中提出的MBNN算法訓練過程中產(chǎn)生過多的中間結果問題通過添加combiner函數(shù),減少中間結果來加快網(wǎng)絡的訓練速度.[7,8]分別通過在進行經(jīng)典的BP算法之前利用遺傳算法,深度信念網(wǎng)絡對BP神經(jīng)網(wǎng)絡的連接權值的初始化進行優(yōu)化,加快BP神經(jīng)網(wǎng)絡的收斂速度.

然而上述均采用Hadoop來對BP神經(jīng)網(wǎng)絡進行并行化實現(xiàn),由于Hadoop是基于磁盤的,因而在訓練反復迭代過程中,每一次迭代都需要讀取磁盤上保存上次迭代結果的信息.[7,9,10]對上述問題進行了一定程度的改善,通過在Mapper階段根據(jù)局部數(shù)據(jù)訓練得到局部收斂的BP神經(jīng)網(wǎng)絡后,在Reducer階段再進行不同策略的整合.雖然[7,9,10]對迭代過程中讀取磁盤進行了一定程度的優(yōu)化,但還是避免不了多次讀取磁盤,且由于BP神經(jīng)網(wǎng)絡容易陷入局部最優(yōu)解的問題使得最終得到的BP神經(jīng)網(wǎng)絡結構正確率不一定達到要求.

本文提出的方法在[4]中MBNN的基礎之上,對[4]方法中采用的Adaboost算法進行改進,以使Adaboost算法更好的與BP神經(jīng)網(wǎng)絡算法進行結合,同時采用同樣基于MapReduce思想實現(xiàn)的基于內(nèi)存的Spark平臺進行算法實現(xiàn).最后實驗結果表明在保證正確率的情況下,本方法更優(yōu)于[4]中提出的MBNN算法且縮短了算法訓練時間.

2 神經(jīng)網(wǎng)絡算法

人工神經(jīng)網(wǎng)絡(Artificial Neural Network,ANN),是在模擬生物神經(jīng)網(wǎng)絡的基礎上構建的信息處理系統(tǒng),具有強大的信息存儲和處理能力.至今已開發(fā)出了一系列的算法的不同分支,其中以反向傳播網(wǎng)絡,即BP神經(jīng)網(wǎng)絡模型應用最為廣泛.BP算法以其良好的非線性逼近能力,泛化能力以及實用性成為了人工神經(jīng)網(wǎng)絡訓練算法中應用最為廣泛的算法.BP神經(jīng)網(wǎng)絡算法的基本思想是重復的使用鏈式法則計算出每一個網(wǎng)絡權值對網(wǎng)絡最后的結果誤差E的影響:

(1)

這里wij表示神經(jīng)元j與神經(jīng)元i的連接權值,si是輸出,neti是神經(jīng)元i的加權和.一旦求出所有的權值的偏導數(shù),就可以通過簡單的權值下降法讓誤差取得最小值:

(2)

通過公式(2)不斷迭代網(wǎng)絡連接權值,最終達到終止條件,得到收斂的分類器.

3 Adaboost算法

Adaboost[11]的結構如下所示:

最后的分類器YM由多個弱分類器聯(lián)合組成.相當于M個弱分類器聯(lián)合決定樣本屬于哪個類,而且每個弱分類器的重要性αm不同.具體過程如下:

1)初始化所有樣本的權重w1,i為1/N,其中N為樣本總數(shù).

2)對于1到M個弱分類器 do

a)訓練弱分類器ym,使其最小化權重誤差函數(shù)

(3)

其中tn為樣本所屬真正的類別.

b)計算出該弱分類器的重要性αm

(4)

c)更新樣本的權重wm+1,i

(5)

3)得到最后的分類器

(6)

在上述Adaboost算法中,每產(chǎn)生一個弱分類器ym之后,對樣本權值進行更新,并通過抽樣的方式對樣本進行抽樣,得到新的樣本來訓練新的弱分類器ym+1.

4 基于改進Adaboost的BP神經(jīng)網(wǎng)絡算法

在上述Adaboost過程中,存在一個嚴重的問題:當處理的數(shù)據(jù)量變得非常大的時候,每次訓練得到一個弱分類器后,得出訓練下一個分類器所需要的樣本變得十分的耗時困難.

本文中,將BP神經(jīng)網(wǎng)絡作為基分類器進行訓練,并且采用批更新對網(wǎng)絡連接權值進行更新.在訓練得到y(tǒng)m分類器后,不進行抽樣過程.而是通過(5)對每個樣本的權重進行更新,得到每個樣本都帶有權值wm+1,k的一個樣本集合.在對ym+1這個分類器進行訓練的時候,對樣本集合中的每一條數(shù)據(jù)代入上一次得到的BP神經(jīng)網(wǎng)絡中,計算出每一條記錄對相應的BP神經(jīng)網(wǎng)絡連接權值更新值Δwij,通過下式算出每一條連接總的權值更新值:

(7)

通過將(7)式計算出來所有的樣本加權后的BP網(wǎng)絡連接權值的更新值對BP神經(jīng)網(wǎng)絡進行更新.

在這一過程中,由于省去了抽樣的過程,大大提高了最終分類器YM的訓練時間.

5 Spark

Spark*http://hadoop.apache.org.是UC Berkeley AMP lab (加州大學伯克利分校的AMP實驗室)所開源的類Hadoop MapReduce的通用并行框架.Spark有Hadoop幾乎所有的優(yōu)點,并且在處理過程中,中間結果不是寫入到磁盤上而保留在內(nèi)存中,非常適合于頻繁迭代算法的設計,運行原理圖如圖1所示.

在Spark集群運行期間,應用程序提交后,Client端初始化并構建SparkContext對象,由SparkContext與集群資源管理者master取得聯(lián)系,注冊程序并申請所需資源:CPU和core,即Executor.Executor接收資源管理者的命令從文件系統(tǒng)中讀取數(shù)據(jù)形成RDD[12]并進行處理,Executor可以并行運算,運算的邏輯一樣,但處理的數(shù)據(jù)不一樣.在SparkContext初始化的過程中生成了DAGScheduler對象和TaskScheduler對象,DAGScheduler根據(jù)shuffledependency將應用程序分割成一個個的stage,每一個stage包含一個或者很多個task,這

圖1 Spark工作原理Fig.1 Spark works

些task之間可以進行并行執(zhí)行,而所有的stage順序運行.接著,SparkContext將應用程序的代碼廣播給每個Executor,同時SparkContext根據(jù)數(shù)據(jù)本地性和每個處理機的處理能力將任務分配給每個Executor,之后Executor開始執(zhí)行分配給自身的任務.

6 算法并行化

Spark采用典型的master-worker并行模式,一般擁有一個master節(jié)點和多個worker節(jié)點,即計算節(jié)點.Master節(jié)點協(xié)調(diào)整個訓練任務的執(zhí)行,而訓練的實際執(zhí)行者為很多個worker節(jié)點.在運行之前訓練集被切分成很多個block存儲在分布式文件系統(tǒng)HDFS上.每個計算節(jié)點根據(jù)數(shù)據(jù)本地性讀取屬于自己的那部分block進行獨立訓練誤差,具體的并行算法實現(xiàn)偽代碼如下:

具體算法過程和流程圖如下:

1)程序提交后主進程進行初始化,通過SparkContext.textFile()函數(shù)從分布式文件系統(tǒng)HDFS中依據(jù)Spark自身具有的數(shù)據(jù)本地性讀取訓練所需的數(shù)據(jù)形成RDD;

2)通過調(diào)用RDD.map(string2Tuple(_))方法將讀取進來的每行記錄轉(zhuǎn)換成BP網(wǎng)絡訓練時需要的輸入格式.其中string2Tuple方法封裝了對于每一條記錄的解析業(yè)務邏輯;

圖2 數(shù)據(jù)并行BP算法流程圖Fig.2 Data parallel BP algorithm flow chart

3)將BP網(wǎng)絡訓練連接權值wij,αt等參數(shù)以BroadCast變量的形式傳遞給各從進程;

4)各從進程讀取傳過來的BroadCast參數(shù),并構建神經(jīng)網(wǎng)絡結構;

5)根據(jù)任務調(diào)度策略的優(yōu)先順序PROCESS_LOCAL、NODE_LOCAL、NO_PREF,RACK_LOCAL、ANY,優(yōu)先根據(jù)PROCESS_LOCAL選取出RDD中對應自身的Partition進行計算,對每一條記錄先根據(jù)BroadCast過來的上一次得出的正確率計算出的Δwij更新記錄權值.

6)計算出各條記錄通過BP神經(jīng)網(wǎng)絡后連接權值更新值并將每個連接權值與對應記錄的權值進行相乘得出每條記錄的對BP神經(jīng)網(wǎng)絡連接權值的加權更新量.

圖3 并行計算方法示意圖Fig.3 Parallel computing method

7)再將對應一個Executor的所有樣本的權值更新值進行本地reduce,得出總的權值更新值并計算出對應executor對應記錄的正確率和記錄條數(shù).

8)主節(jié)點將從節(jié)點上的連接權值更新值,每個executor對應的記錄正確率和記錄條數(shù)收集過來.

9)主節(jié)點對BP神經(jīng)網(wǎng)絡進行批更新更新并計算出則整體的正確率以及αt.

10)判斷是否達到終止條件,若達到則終止訓練;若沒有達到,則轉(zhuǎn)到3)步進行新一輪的循環(huán).

到達終止條件后,主節(jié)點將根據(jù)Adaboost計算出的多個分類器依據(jù)(4)計算出來的權重αm進行加權集成,為了更好的理解,從數(shù)據(jù)的角度觀察整個過程如圖3所示:

7 實驗設計與結果分析

7.1 實驗環(huán)境與實驗方案

7.1.1 實驗環(huán)境

實驗中所使用到的集群環(huán)境配置屬性信息詳見表1.

表1 節(jié)點信息表Table 1 Node information table

7.1.2 實驗方案

對于并行算法,我們最關心的是算法的運行時間和正確率,除此之外還要考慮并行算法相對于串行算法對于計算速度的提升.

本文選取UCI里的Magic Gamma Telescope Data Set數(shù)據(jù)集作為實驗數(shù)據(jù),為了解決實驗數(shù)據(jù)的數(shù)據(jù)量問題,通過原有數(shù)據(jù)經(jīng)過代碼生成技術在原有的數(shù)據(jù)量下生成1000萬條數(shù)據(jù),進行分類驗證并行BP算法的可行性.

7.2 算法參數(shù)

輸入層和輸出層的神經(jīng)元個數(shù),由輸入和輸出向量的維數(shù)來確定.在此,根據(jù)數(shù)據(jù)集的特點可以確定出輸入輸出層神經(jīng)元個數(shù)分別為10,2.對于隱含層數(shù)的確定,Hornik等早已證明[13]:若輸入層和輸出層采用線性轉(zhuǎn)換函數(shù),隱含層采用Sigmoid轉(zhuǎn)換函數(shù),具有一個隱含層的BP網(wǎng)絡可以實現(xiàn)對任意函數(shù)的任意逼近.因此文中BP神經(jīng)網(wǎng)絡采取1個隱含層.同時實驗結果表明選取隱藏層節(jié)點數(shù)為10時,網(wǎng)絡模型穩(wěn)定且可獲得較理想結果.

實驗結果分別用一臺處理機和多臺處理機對BP網(wǎng)絡進行訓練,統(tǒng)計訓練的時間,正確率等,結果如表2-表5所示,其中表3,表4的迭代次數(shù)表示局部迭代次數(shù),全局迭代次數(shù)為1:

從表2-表5可看出來總的運行時間隨著處理機的個數(shù)的增加而減少,四種算法均獲得了可觀的加速比,證明了算法具有良好的加速性能,同時如圖1所示,在相同的實驗條件下,BP-Spark算法明顯比[4]中提出的方法獲得了更好的加速比,且同樣比[9],[10]中提出的算法在達到局部收斂時獲得更好的加速比.而正確率結果如圖5所示,由于使用Adaboost算法進行集成的弱分類器隨著迭代次數(shù)(相對于[9][10]來說為全局迭代次數(shù))的增加,得到的弱分類器越多,最終得到的組合分類器正確率逐步提高,說明了算法的有效性,而[9],[10]中提出的算法由于局部數(shù)據(jù)逐漸減小,訓練的單分類器正確率反而有所下降.最后通過在選取5臺處理機的情況下對訓練集的數(shù)據(jù)量逐步增大,如圖6所示,由圖可看出,模型的訓練時間和訓練集數(shù)據(jù)量基本上呈線性關系,由此表明了BP-Spark算法的良好的可伸縮性.

表2 本文提出的方法串行與并行的實驗結果Table 2 Experimental results of a method proposed in this paper of serial and parallel mode

表3 [4]中提出的方法并行的實驗結果Table 3 [4] proposed in parallel with the experimental results

表4 [10]中提出的方法并行的實驗結果Table 4 [10] proposed in parallel with the experimental results

表5 [9]中提出的方法并行的實驗結果Table 5 [9] proposed in parallel with the experimental results

加速比與處理機個數(shù)的實驗結果如圖4.

8 結 語

人工神經(jīng)網(wǎng)絡對于信息處理有很強的魯棒性和容錯能力,善于聯(lián)想和概括,具有自學習能力.BP網(wǎng)絡以其良好的數(shù)據(jù)處理性能在大量的實際工程中得到了廣泛的應用.但是傳統(tǒng)的BP算法存在學習速度慢等缺點.本文分析了BP算法的局限性,改進了BP算法在并行的基礎上,提升了網(wǎng)絡的收斂速度.然而仍然存在不足,在訓練BP神經(jīng)網(wǎng)絡時如何選取最合適的初始化參數(shù),如何將多個神經(jīng)網(wǎng)絡分類器以更好的策略組合起來等.因此,需要針對這部分做進一步研究與改進.

圖4 加速比與處理機個數(shù)的實驗結果Fig.4 Speed ratio and the number of experimental results of the processor

圖5 正確率與迭代次數(shù)的實驗結果Fig.5 Eexperimental results of correct rate and iteration times

圖6 處理時間與數(shù)據(jù)量關系的實驗結果Fig.6 Experimental results of the relationship between processing time and data volume

正確率與處理機個數(shù)的實驗結果如圖5.

五臺處理機下,處理時間和數(shù)據(jù)量的實驗結果如圖6.

：

[1] Vesel,Karel,Burget L,et al.Parallel training of neural networks for speech recognition[C].International Conference on Text,Speech and Dialogue.Springer-Verlag,2010:439-446.

[2] Hecht-Nielsen.Theory of the backpropagation neural network[C].International Joint Conference on Neural Networks.IEEE Xplore,1989:593-605.

[3] Gu R,Shen F,Huang Y.A parallel computing platform for training large scale neural networks[C].IEEE International Conference on Big Data,IEEE,2013:376-384.

[4] Liu Z,Li H Y,Miao G.MapReduce-based backpropagation neural network over large scale mobile data[C].International Conference on Natural Computation,ICNC 2010,Yantai,Shandong,China,10-12 August.DBLP,2010:1726-1730.

[5] Cui J M,Ye Y X.Data Mining with BP neural network algorithm based MapReduce[J].Applied Mechanics & Materials,2013,380-384:2915-2919.

[6] Zhang H J,Xiao N F.Parallel implementation of multilayered neural networks based on Map-Reduce on cloud computing clusters[J].Soft Computing,2016,20(4):1471-1483.

[7] Zhu C,Ruonan R.The improved BP algorithm based on MapReduce and genetic algorithm[C].International Conference on Computer Science & Service System,IEEE,2012:1567-1570.

[8] Sun K,Wei X,Jia G,et al.Large-scale artificial neural network:MapReduce-based deep learning[J].Computer Science,2015，(1):1-9.

[9] Chen Wang-hu,Yu Mao-yi,Ma Sheng-jun,et al.The BP neural network MapReduce training based on the evolution of local convergence rights[J].Computer Engineering and Applications,2016,38(12):2425-2433.

[10] Zhou B,Wang W,Zhang X.Training backpropagation neural network in MapReduce[C].CCIT14,2014.

[11] Schapire R E,Freund Y,Barlett P,et al.Boosting the margin:a new explanation for the effectiveness of voting methods[C].Fourteenth International Conference on Machine Learning,Morgan Kaufmann Publishers Inc.,1997:322-330.

[12] Zaharia M,Chowdhury M,Das T,et al.Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing[C].Usenix Conference on Networked Systems Design and Implementation,USENIX Association,2012:2-2.

[13] Li Jun-hua.Computation and some numerical descaling algorithm MapReduceization study[D].Chengdu:University of Electronic Science and Technology of China,2010.

附中文參考文獻：

[9] 陳旺虎,俞茂義,馬生俊,等.基于局部收斂權陣進化的BP神經(jīng)網(wǎng)絡MapReduce訓練[J].計算機工程與科學,2016,38(12):2425-2433.

[13] 李軍華.云計算及若干數(shù)據(jù)挖掘算法的MapReduce化研究[D].成都:電子科技大學,2010.