李 楠,于孟渤,賈珍珍,王一惠,李昕宸,鄒淑雪
(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長(zhǎng)春 130012)
BP神經(jīng)網(wǎng)絡(luò)[1]是一種按誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò),是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。但是,傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)在訓(xùn)練時(shí)間、逼近精度以及內(nèi)存空間的利用方面都存在一定的問(wèn)題。因此,并行化神經(jīng)網(wǎng)絡(luò)是發(fā)展的必然趨勢(shì)。文獻(xiàn)[2]中,“神經(jīng)網(wǎng)絡(luò)并行化提高了訓(xùn)練的容錯(cuò)度”反映出神經(jīng)網(wǎng)絡(luò)并行化可以保證良好的容錯(cuò)性和可靠性;文獻(xiàn)[3]指出在并行化過(guò)程中,并行過(guò)程中隱藏層節(jié)點(diǎn)數(shù)目一般選擇輸入向量維度的2倍;文獻(xiàn)[4]提出“并行化過(guò)程中仍舊存在訓(xùn)練易陷入癱瘓,訓(xùn)練時(shí)間較長(zhǎng)等問(wèn)題”。目前,由Google公司提出的MapReduce并行計(jì)算模型[5-7]是并行化的常用實(shí)現(xiàn)方式。一方面,MapReduce通過(guò)把數(shù)據(jù)集進(jìn)行大規(guī)模操作,分發(fā)給網(wǎng)絡(luò)上的每個(gè)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)可靠性。另一方面,其本身為分布式系統(tǒng),可高度并行處理數(shù)據(jù),一定程度上縮短了處理時(shí)間。本文在原有MapReduce模型的Map和Reduce上分別做出改進(jìn),減少了MapReduce在神經(jīng)網(wǎng)絡(luò)并行化中不必要的消耗時(shí)間,從而提高了BP神經(jīng)網(wǎng)絡(luò)的并行化速率。
BP神經(jīng)網(wǎng)絡(luò)是應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)之一。在BP神經(jīng)網(wǎng)絡(luò)中,單個(gè)樣本有m個(gè)輸入和n個(gè)輸出,在輸入層和輸出層之間有一個(gè)或多個(gè)隱含層。每一個(gè)節(jié)點(diǎn)都與上一層的所有節(jié)點(diǎn)相連,稱(chēng)為全連接。層與層間的節(jié)點(diǎn)通過(guò)激勵(lì)函數(shù)與權(quán)值相聯(lián)系。本實(shí)驗(yàn)激勵(lì)函數(shù)選用Sigmoid轉(zhuǎn)換函數(shù):
根據(jù)Hornik的結(jié)論[8]:如果BP神經(jīng)網(wǎng)絡(luò)的輸入層與輸出層選用線(xiàn)性轉(zhuǎn)換函數(shù),隱含層選用Sigmoid轉(zhuǎn)換函數(shù),BP網(wǎng)絡(luò)只需具有1個(gè)隱含層就可完成對(duì)任意函數(shù)的任意逼近。一般地,增加隱含層節(jié)點(diǎn)數(shù),要比增加隱含層數(shù)容易獲得較小的誤差,其訓(xùn)練效果更容易實(shí)現(xiàn)。因此,本訓(xùn)練網(wǎng)絡(luò)設(shè)計(jì)選取1個(gè)隱含層。
BP神經(jīng)網(wǎng)絡(luò)分為兩個(gè)過(guò)程[9],前向傳播過(guò)程和反向傳播過(guò)程,如圖1所示
圖1 神經(jīng)網(wǎng)絡(luò)原理
前向傳播過(guò)程中,輸入信號(hào)經(jīng)過(guò)隱含層計(jì)算后傳遞給輸出層。若輸出值與預(yù)期值的偏差e大于誤差可接受范圍,則進(jìn)入誤差反向傳播過(guò)程。誤差e經(jīng)過(guò)隱含層向輸入層傳遞進(jìn)行誤差調(diào)整,不斷調(diào)整各層之間的權(quán)值,直至輸出誤差達(dá)到可接受范圍或達(dá)到最大學(xué)習(xí)次數(shù)。
MapReduce模型是Google公司提出的一個(gè)編程模型[10],用來(lái)處理大規(guī)模數(shù)據(jù)集的并行運(yùn)算。Map和Reduce是它的主要思想,極大地方便了編程人員在不懂得分布式并行編程的情況下,將自己的程序運(yùn)行在分布式系統(tǒng)上。MapReduce模型提供了并行計(jì)算框架,能夠自主完成計(jì)算任務(wù)的并行處理。自動(dòng)劃分計(jì)算數(shù)據(jù)和計(jì)算任務(wù),并自動(dòng)分配執(zhí)行任務(wù)和收集計(jì)算結(jié)果。許多底層細(xì)節(jié)全部交由系統(tǒng)負(fù)責(zé),對(duì)編程人員保持透明性。
MapReduce編程模型通過(guò)一組輸入鍵/值
圖2 MapReduce模型工作原理
用戶(hù)自定義庫(kù)函數(shù)首先將初始鍵/值
BP神經(jīng)網(wǎng)絡(luò)雖然已經(jīng)是應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)之一,但其在處理海量數(shù)據(jù)時(shí)存在訓(xùn)練時(shí)間過(guò)長(zhǎng)、精度不夠精準(zhǔn)等問(wèn)題不可忽視。運(yùn)用MapReduce模型對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行并行化,可一定程度上避免這些問(wèn)題。Map和Reduce是MapReduce的主要思想。Map階段,系統(tǒng)會(huì)自動(dòng)將待處理數(shù)據(jù)分成多個(gè)數(shù)據(jù)塊。每個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)計(jì)算任務(wù)節(jié)點(diǎn),這些任務(wù)節(jié)點(diǎn)并行完成數(shù)據(jù)處理。同時(shí),MapReduce運(yùn)用數(shù)據(jù)/代碼互定位減少通信延遲,從而縮短神經(jīng)網(wǎng)絡(luò)運(yùn)行時(shí)間。該模型可以順序處理神經(jīng)網(wǎng)絡(luò)的訓(xùn)練集,并大規(guī)模分發(fā)給各個(gè)節(jié)點(diǎn)來(lái)保證訓(xùn)練結(jié)果的可靠性。
BP神經(jīng)網(wǎng)絡(luò)的MapReduce模型實(shí)現(xiàn)主要分為兩個(gè)階段[11]:Map階段和Reduce階段。在Map階段,將原始數(shù)據(jù)集即樣本數(shù)據(jù)作用到網(wǎng)絡(luò)中,系統(tǒng)會(huì)自動(dòng)將數(shù)據(jù)集分塊成為實(shí)際的神經(jīng)網(wǎng)絡(luò)訓(xùn)練集,經(jīng)過(guò)一系列次數(shù)的迭代得到權(quán)值矩陣;而Reduce階段則是綜合Map階段輸出的權(quán)值矩陣再次處理得到新的權(quán)值矩陣,然后根據(jù)權(quán)值來(lái)判斷是否繼續(xù)迭代。以下是實(shí)現(xiàn)的具體流程。
Map階段[12-13]處理數(shù)據(jù)前,首先從HDFS文件系統(tǒng)上獲得初始權(quán)值,以初始整個(gè)網(wǎng)絡(luò)。在Map階段中,每一個(gè)Map節(jié)點(diǎn)利用一條訓(xùn)練數(shù)據(jù)在當(dāng)前網(wǎng)絡(luò)中進(jìn)行正向傳播。現(xiàn)設(shè)節(jié)點(diǎn)a和節(jié)點(diǎn)b之間的權(quán)值為wab,節(jié)點(diǎn)b的閥值為m,每個(gè)節(jié)點(diǎn)的輸出值為xb,而節(jié)點(diǎn)輸出值是根據(jù)上一層所有節(jié)點(diǎn)輸出值、當(dāng)前節(jié)點(diǎn)與上一層所有節(jié)點(diǎn)的權(quán)值、閥值和激勵(lì)函數(shù)實(shí)現(xiàn)的,計(jì)算公式如下:
其中S為提到的激勵(lì)函數(shù)。
BP神經(jīng)網(wǎng)絡(luò)的主要目的是反復(fù)修正權(quán)值和閥值,使得誤差函數(shù)值達(dá)到最小,以輸出期望得到的結(jié)果。反向傳播計(jì)算較正向傳播過(guò)程復(fù)雜,是基于WidrowHoff學(xué)習(xí)規(guī)則,通過(guò)沿著相對(duì)誤差網(wǎng)絡(luò)權(quán)值改變量,根據(jù)梯度下降法來(lái)調(diào)整網(wǎng)絡(luò)的權(quán)值和閥值,并經(jīng)調(diào)整后輸出中間鍵/值
Mapper函數(shù)偽代碼如下:
輸入:key,value
輸出:keyWritable,WeightWritable
Mapper(key,value)
{
利用樣本數(shù)據(jù)在當(dāng)前網(wǎng)絡(luò)中正向傳播;
反向傳播計(jì)算權(quán)值改變量;
獲得當(dāng)前網(wǎng)絡(luò)權(quán)值,賦值keyWritable;
獲得本次訓(xùn)練權(quán)值改變量,賦值WeightWritable;
Emit(keyWritable,WeightWritable);
}
Reduce階段以Map階段輸出的中間鍵/值
Reducer函數(shù)偽代碼如下:
輸入:keyWritable,WeightWritable輸出:key,value’
Reducer(keyWritable,WeightWritable)
{
while(未處理完所有WeightWritable)
{
收集Map階段輸出的WeightWritable;
}
統(tǒng)計(jì)計(jì)算得出本次訓(xùn)練權(quán)值改變量;
計(jì)算本次訓(xùn)練后網(wǎng)絡(luò)權(quán)值value’;
if(|value’–value|<〥)
Emit(key,value’);
else
進(jìn)入下一次迭代計(jì)算;
}
改進(jìn)后的MapReduce模型基本繼承了原來(lái)MapReduce模型的Mapper函數(shù)和Reducer函數(shù)的基本功能。雖然原有的MapReduce模型在神經(jīng)網(wǎng)絡(luò)并行化過(guò)程中分布可靠,與未并行化相比減少了數(shù)據(jù)的處理時(shí)間,但是在并行處理時(shí)因頻繁訪(fǎng)問(wèn)I/O消耗了一定的工作時(shí)間,某種程度上增加了實(shí)際的處理時(shí)間。在此基礎(chǔ)上,提出了兩種改進(jìn)方法:一是在原來(lái)輸入數(shù)據(jù)為一組樣本的情況下,將輸入數(shù)據(jù)改為一組樣本,以減少M(fèi)ap的數(shù)量,從而減少資源的消耗和Map階段處理數(shù)據(jù)的時(shí)間;二是在Reduce階段將原來(lái)的key值替換為一個(gè)元祖tuple。該元祖包括已有key值和新加入的分組編號(hào),使多個(gè)reduce并行工作,從而減少處理時(shí)間。改進(jìn)的MapReduce模型工作原理,如圖3所示。
圖3 改進(jìn)MapReduce模型的工作原理
在改進(jìn)后的MapReduce模型中,用戶(hù)定義的Mapper函數(shù)接收數(shù)據(jù)的鍵/值對(duì)集合,即一組樣本的
從任務(wù)執(zhí)行過(guò)程來(lái)看,首先啟動(dòng)用戶(hù)程序,每個(gè)作業(yè)執(zhí)行中都會(huì)有一個(gè)主控程序,由主控程序分配Map個(gè)數(shù)和Reduce個(gè)數(shù)。被指派工作的Map節(jié)點(diǎn)數(shù)量要根據(jù)機(jī)器數(shù)來(lái)分配,需要保證多個(gè)Map處于同一時(shí)間片能夠處理所有的樣本。經(jīng)過(guò)處理后,生成
由MapReduce模型工作原理可知,Reduce階段的輸入有key和WeightWritable兩部分。未改進(jìn)的MapReduce模型中,key的類(lèi)型為DoubleWritable,用來(lái)描述特定的邊;而改進(jìn)后模型將key替換為一個(gè)元組tuple,其類(lèi)型為T(mén)upleWritable。這個(gè)元組包含Seq和key兩個(gè)屬性,其中Seq為IntWritable類(lèi)型,用來(lái)標(biāo)識(shí)分組組號(hào),key為DoubleWritable類(lèi)型,仍用來(lái)描述特定的邊。每個(gè)樣本訓(xùn)練后,每個(gè)邊都對(duì)應(yīng)著一個(gè)權(quán)值變化量。假設(shè)有m個(gè)樣本,則未改進(jìn)時(shí)每個(gè)Reduce的輸入值WeightWritable都有m個(gè)值。一個(gè)Reduce要對(duì)m個(gè)數(shù)據(jù)進(jìn)行處理,若m特別大,消耗的時(shí)間會(huì)較長(zhǎng);假設(shè)將樣本數(shù)據(jù)分為k組,則每組有m/k個(gè)數(shù)據(jù),即每個(gè)reduce的WeightWritable對(duì)應(yīng)著m/k個(gè)數(shù)據(jù),讓k個(gè)reduce并行工作來(lái)完成改進(jìn)前一個(gè)reduce完成的工作,從而縮短處理時(shí)間。表1為Reduce改進(jìn)前與改進(jìn)后的輸入值情況。
表1 Reduce改進(jìn)前與改進(jìn)后的輸入值
根據(jù)改進(jìn)的MapReduce模型,Map階段的初始鍵值不再是單一鍵值而是一組神經(jīng)網(wǎng)絡(luò)訓(xùn)練集的鍵值,相當(dāng)于將一個(gè)神經(jīng)網(wǎng)絡(luò)訓(xùn)練分散成多個(gè)子神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練,其他過(guò)程基本繼承原來(lái)的訓(xùn)練過(guò)程,從而計(jì)算輸出誤差,然后將生成的中間鍵值傳遞到reduce階段。
Map函數(shù)偽代碼如下:
輸入:key,value
輸出:tuple[seq,key],WeightWritable
Mapper(key,value)
{
利用一組樣本數(shù)據(jù)在當(dāng)前網(wǎng)絡(luò)中正向傳播;
反向傳播計(jì)算權(quán)值改變量;
獲得當(dāng)前網(wǎng)絡(luò)權(quán)值,賦值tuple[seq,key];
獲得本次訓(xùn)練權(quán)值改變量,賦值WeightWritable;
計(jì)算此次訓(xùn)練實(shí)驗(yàn)誤差;
Emit(tuple[seq,key],WeightWritable);
}
在Reduce階段,將BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練集在Map階段的訓(xùn)練結(jié)果(tuple[seq,key],Weight-Writable)作為輸入,其中用元組tuple替代未改進(jìn)前的key值,將大數(shù)據(jù)集下的同一key值對(duì)應(yīng)的單一reduce工作方式改為多個(gè)reduce并行工作方式,從而減少并行處理時(shí)間。
Reduce函數(shù)偽代碼如下:
輸入:tuple[seq,key],WeightWritable
輸出:key,value’
Reducer(tuple[seq,key],WeightWritable)
{
while(未處理完所有WeightWritable)
{
收集Map階段輸出的WeightWritable;
}
統(tǒng)計(jì)計(jì)算得出本次訓(xùn)練權(quán)值改變量;
計(jì)算本次訓(xùn)練后網(wǎng)絡(luò)權(quán)值value’;
if(|value’–value|<〥)
Emit(key,value’);
else
進(jìn)入下一次迭代計(jì)算;
}
圖4為基于BP神經(jīng)網(wǎng)絡(luò)算法改進(jìn)的MapReduce并行編程模型工作流程。
圖4 并行化工作流程
本實(shí)驗(yàn)采用1臺(tái)物理機(jī)虛擬3臺(tái)虛擬機(jī),即1個(gè)Master和2個(gè)Slave節(jié)點(diǎn),節(jié)點(diǎn)之間在局域網(wǎng)中相互連通。為了實(shí)現(xiàn)節(jié)點(diǎn)間在同一局域網(wǎng)上定向通信,配置使用靜態(tài)地址。各節(jié)點(diǎn)的IP分布如表2所示(處理器型號(hào)Intel Core i5 2.7,內(nèi)存6 GB)。
表2 IP地址分布表
實(shí)驗(yàn)利用原有的MapReduce模型和改進(jìn)后的MapReduce模型分別對(duì)不同大小的數(shù)據(jù)集進(jìn)行并行化處理,結(jié)果如表3所示。
表3 實(shí)驗(yàn)結(jié)果
如表3所示,實(shí)驗(yàn)中,隨著數(shù)據(jù)量的增大,程序的運(yùn)行時(shí)間變長(zhǎng),但使用改進(jìn)的MapReduce模型優(yōu)化效果也越明顯。實(shí)驗(yàn)中發(fā)現(xiàn),程序運(yùn)行時(shí)間大多消耗在Map階段。因此,只有數(shù)據(jù)集龐大到一定程度,Reduce階段的模型改進(jìn)效果才會(huì)更加顯著。
本文對(duì)基于MapReduce的BP神經(jīng)網(wǎng)絡(luò)算法進(jìn)行研究,完成了BP神經(jīng)網(wǎng)絡(luò)的并行化,并基于此提出了一種改進(jìn)后的MapReduce模型,并將MapReduce改進(jìn)模型運(yùn)用到BP神經(jīng)網(wǎng)絡(luò)中,成功減少了并行處理數(shù)據(jù)的時(shí)間,提高了并行化速率。因?qū)嶒?yàn)條件有限,無(wú)法對(duì)過(guò)大數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),未來(lái)將會(huì)繼續(xù)對(duì)過(guò)大數(shù)據(jù)集進(jìn)行試驗(yàn)。此外,選取合適的作業(yè)調(diào)度可以提高整個(gè)系統(tǒng)的計(jì)算性能,而多臺(tái)機(jī)器共享MapReduce集群可以減少一定代價(jià)。因此,接下來(lái)將繼續(xù)進(jìn)行研究,以期使MapReduce模型更加成熟。
參考文獻(xiàn):
[1] 朱珍.基于神經(jīng)網(wǎng)絡(luò)集成分類(lèi)器預(yù)處理的支持向量機(jī)分類(lèi)算法[J].科技通報(bào),2013,29(04):26-27.ZHU Zhen.Support Vector Machine Classification Algorithm Based on Neural Network Integrated Classifier Preprocessing[J].Bulletin of Science and Technology,2013,29(04):26-27.
[2] Ripley.B.D.模式識(shí)別與神經(jīng)網(wǎng)絡(luò)[M].北京:人民郵電出版社,2009.Ripley.B.D.Pattern Recognition and Neural Network[M].Beijing:Posts & Telecom Press,2009.
[3] 朱啟敏.基于云計(jì)算平臺(tái)的神經(jīng)網(wǎng)絡(luò)計(jì)算方法及其應(yīng)用研究[D].廣州:華南理工大學(xué),2014.ZHU Qi-min.Neural Network Computing Method Based on Cloud Computing Platform and Its Application[D].Guangzhou:South China University of Technology,2014.
[4] ZHU Chen-jie,RAO Ruo-nan.The Improved BP Algorithm Based on MapReduce and Genetic Algorithm[J].CSSS,2012,28(10):9-10.
[5] Baroni M,Bernardini S.BootCaT:Bootstrapping Corpora and Terms from the Web[C].Proceedings of LREC,2004:1313-1316.
[6] Ghermawat S,Gobioff H,Leung S T.The Google File System[C].ACM SIGOPS Operating Systems Review ACM,2003:29-43.
[7] 劉鵬.實(shí)戰(zhàn)Hadoop:開(kāi)啟通向云計(jì)算的捷徑[M].北京:電子工業(yè)出版社,2011.LIU Peng.Hadoop in Action:a Shortcut to Cloud Computing[M].Beijing:Electronic Industry Press,2011.
[8] Hornik K.Multilayer Feedforward Networks are Universal Approximators[J].Neural Networks,1989,2(05):359-366.
[9] 朱晨杰,楊永麗.基于mapreduce的BP神經(jīng)網(wǎng)絡(luò)算法的研究[J].微型電腦應(yīng)用,2012,28(10):9-12.ZHU Chen-jie,YANG Yong-li.Research on BP Neural Network Algorithm Based on Mapreduce[J].Microcomputer Applications,2012,28(10):9-12.
[10] 周峰,李旭偉.一種改進(jìn)的MapReduce并行編程模型[J].計(jì)算機(jī)技術(shù)與信息發(fā)展,2009(02):65-66.ZHOU Wei,LI Xu-wei.An Improved MapReduce Parallel Programming Model[J].Computer Technology and Information Development,2009(02):65-66.
[11] 崔紅艷,曹建芳,史昊.一種基于MapReduce的并行PSO-BP神經(jīng)網(wǎng)絡(luò)算法[J].科技通報(bào),2017,33(04):110-115.CUI Hong-yan,CAO Jian-fang,SHI Hao.A Parallel PSOBP Neural Network Algorithm Based on MapReduce[J].Bulletin of Science and Technology,2017,33(04):110-115.
[12] 陳俊杰,強(qiáng)彥.基于模擬退火的MapReduce調(diào)度算法[J].計(jì)算機(jī)工程,2012,38(19):45-48.CHEN Jun-jie,QIANG Yan.MapReduce Scheduling Algorithm Based on Simulated Annealing[J].Computer Engineering,2012,38(19):45-48.
[13] 冼進(jìn),余桂城.基于云計(jì)算的作業(yè)調(diào)度算法研究[J].計(jì)算機(jī)與數(shù)字工程,2014,39(07):39-42.XIAN Jin,YU Gui-cheng.Research on Job Scheduling Algorithm Based on Cloud Computing[J].Computer &Digital Engineering,2014,39(07):39-42.