基于改进MapReduce模型的BP神经网络并行化研究*

李 楠，于孟渤，贾珍珍，王一惠，李昕宸，邹淑雪

（吉林大学 计算机科学与技术学院，吉林 长春 130012）

0 引 言

BP神经网络[1]是一种按误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。但是，传统BP神经网络在训练时间、逼近精度以及内存空间的利用方面都存在一定的问题。因此，并行化神经网络是发展的必然趋势。文献[2]中，“神经网络并行化提高了训练的容错度”反映出神经网络并行化可以保证良好的容错性和可靠性；文献[3]指出在并行化过程中，并行过程中隐藏层节点数目一般选择输入向量维度的2倍；文献[4]提出“并行化过程中仍旧存在训练易陷入瘫痪，训练时间较长等问题”。目前，由Google公司提出的MapReduce并行计算模型[5-7]是并行化的常用实现方式。一方面，MapReduce通过把数据集进行大规模操作，分发给网络上的每个节点来实现可靠性。另一方面，其本身为分布式系统，可高度并行处理数据，一定程度上缩短了处理时间。本文在原有MapReduce模型的Map和Reduce上分别做出改进，减少了MapReduce在神经网络并行化中不必要的消耗时间，从而提高了BP神经网络的并行化速率。

1 BP神经网络

1.1 BP神经网络的拓扑结构

BP神经网络是应用最广泛的神经网络之一。在BP神经网络中，单个样本有m个输入和n个输出，在输入层和输出层之间有一个或多个隐含层。每一个节点都与上一层的所有节点相连，称为全连接。层与层间的节点通过激励函数与权值相联系。本实验激励函数选用Sigmoid转换函数：

根据Hornik的结论[8]：如果BP神经网络的输入层与输出层选用线性转换函数，隐含层选用Sigmoid转换函数，BP网络只需具有1个隐含层就可完成对任意函数的任意逼近。一般地，增加隐含层节点数，要比增加隐含层数容易获得较小的误差，其训练效果更容易实现。因此，本训练网络设计选取1个隐含层。

1.2 BP神经网络的原理

BP神经网络分为两个过程[9]，前向传播过程和反向传播过程，如图1所示

图1 神经网络原理

前向传播过程中，输入信号经过隐含层计算后传递给输出层。若输出值与预期值的偏差e大于误差可接受范围，则进入误差反向传播过程。误差e经过隐含层向输入层传递进行误差调整，不断调整各层之间的权值，直至输出误差达到可接受范围或达到最大学习次数。

2 MapReduce模型

MapReduce模型是Google公司提出的一个编程模型[10]，用来处理大规模数据集的并行运算。Map和Reduce是它的主要思想，极大地方便了编程人员在不懂得分布式并行编程的情况下，将自己的程序运行在分布式系统上。MapReduce模型提供了并行计算框架，能够自主完成计算任务的并行处理。自动划分计算数据和计算任务，并自动分配执行任务和收集计算结果。许多底层细节全部交由系统负责，对编程人员保持透明性。

MapReduce编程模型通过一组输入键/值，经过2个库函数map函数和reduce函数，得到另一组输出键/值，工作原理如图2所示。

图2 MapReduce模型工作原理

用户自定义库函数首先将初始键/值作为用户自定义的map方法的输入，得到输出键/值，然后将具有相同key值的value放到一个集合中得到values集合。键值作为reduce的输入值，reduce将接收数据交给用户自定义的reduce函数进行处理，形成新的对，并将其作为最终输出结果。

3 BP神经网络的MapReduce并行方法

BP神经网络虽然已经是应用最广泛的神经网络之一，但其在处理海量数据时存在训练时间过长、精度不够精准等问题不可忽视。运用MapReduce模型对神经网络进行并行化，可一定程度上避免这些问题。Map和Reduce是MapReduce的主要思想。Map阶段，系统会自动将待处理数据分成多个数据块。每个数据块对应一个计算任务节点，这些任务节点并行完成数据处理。同时，MapReduce运用数据/代码互定位减少通信延迟，从而缩短神经网络运行时间。该模型可以顺序处理神经网络的训练集，并大规模分发给各个节点来保证训练结果的可靠性。

BP神经网络的MapReduce模型实现主要分为两个阶段[11]：Map阶段和Reduce阶段。在Map阶段，将原始数据集即样本数据作用到网络中，系统会自动将数据集分块成为实际的神经网络训练集，经过一系列次数的迭代得到权值矩阵；而Reduce阶段则是综合Map阶段输出的权值矩阵再次处理得到新的权值矩阵，然后根据权值来判断是否继续迭代。以下是实现的具体流程。

Map阶段[12-13]处理数据前，首先从HDFS文件系统上获得初始权值，以初始整个网络。在Map阶段中，每一个Map节点利用一条训练数据在当前网络中进行正向传播。现设节点a和节点b之间的权值为wab，节点b的阀值为m，每个节点的输出值为xb，而节点输出值是根据上一层所有节点输出值、当前节点与上一层所有节点的权值、阀值和激励函数实现的，计算公式如下：

其中S为提到的激励函数。

BP神经网络的主要目的是反复修正权值和阀值，使得误差函数值达到最小，以输出期望得到的结果。反向传播计算较正向传播过程复杂，是基于WidrowHoff学习规则，通过沿着相对误差网络权值改变量，根据梯度下降法来调整网络的权值和阀值，并经调整后输出中间键/值。Reduce阶段，在获得中间键/值后把具有相同key值的多组value值累加在一起，将一串value值输出为一个value值，完成权值矩阵的更新。根据实验条件及输出结果，判定是否重新进行迭代处理。实验中需定义一个满足Hadoop序列的WeightWritable接口类用于实验的数据传递，其中也记录经过Map训练后的所有value值。

Mapper函数伪代码如下：

输入：key，value

输出：keyWritable，WeightWritable

Mapper(key，value)

{

利用样本数据在当前网络中正向传播；

反向传播计算权值改变量；

获得当前网络权值，赋值keyWritable；

获得本次训练权值改变量，赋值WeightWritable；

Emit(keyWritable，WeightWritable)；

}

Reduce阶段以Map阶段输出的中间键/值作为输入，输出为，其中需要判断是否进行下一次迭代训练。此时，值为1需要进行迭代训练。Reduce主要是统计拥有相同key值的多个value值，最后输出平均值，即实现“归并”功能。Reduce会读取HDFS文件系统保存的上一次训练后的权值用作结果对比。若二者差值未达到足够小的水平，则需要再进行迭代处理，并用训练后的结果作为下一次迭代的输入权值。

Reducer函数伪代码如下：

输入：keyWritable，WeightWritable输出：key，value’

Reducer(keyWritable，WeightWritable)

{

while(未处理完所有WeightWritable)

{

收集Map阶段输出的WeightWritable;

}

统计计算得出本次训练权值改变量；

计算本次训练后网络权值value’；

if(|value’–value|<〥)

Emit(key，value’)；

else

进入下一次迭代计算；

}

4 改进MapReduce模型

改进后的MapReduce模型基本继承了原来MapReduce模型的Mapper函数和Reducer函数的基本功能。虽然原有的MapReduce模型在神经网络并行化过程中分布可靠，与未并行化相比减少了数据的处理时间，但是在并行处理时因频繁访问I/O消耗了一定的工作时间，某种程度上增加了实际的处理时间。在此基础上，提出了两种改进方法：一是在原来输入数据为一组样本的情况下，将输入数据改为一组样本，以减少Map的数量，从而减少资源的消耗和Map阶段处理数据的时间；二是在Reduce阶段将原来的key值替换为一个元祖tuple。该元祖包括已有key值和新加入的分组编号，使多个reduce并行工作，从而减少处理时间。改进的MapReduce模型工作原理，如图3所示。

图3 改进MapReduce模型的工作原理

4.1 Map部分

在改进后的MapReduce模型中，用户定义的Mapper函数接收数据的键/值对集合，即一组样本的而不是输入单一的。Map操作的实质是通过把输入自动分割成多个数据片而分到不同的机器上运行。实验中采取3台机器将数据分片，然后输入到各个机器进行处理。同一台机器同时间段只能允许一个Map节点进行工作。实验证明，适当的Map个数会降低数据处理时间，提高运行速率。Map节点数量过多或过少都会降低速率。

从任务执行过程来看，首先启动用户程序，每个作业执行中都会有一个主控程序，由主控程序分配Map个数和Reduce个数。被指派工作的Map节点数量要根据机器数来分配，需要保证多个Map处于同一时间片能够处理所有的样本。经过处理后，生成传给指派的Mapper函数，产生中间键/值放入缓存中。Reduce将这些作为自己的输入，使用中间key值进行归并，输出到最后的结果中。若需要继续迭代，需将处理结果作为下一轮MapReduce过程的Map阶段的输入。

4.2 Reduce部分

由MapReduce模型工作原理可知，Reduce阶段的输入有key和WeightWritable两部分。未改进的MapReduce模型中，key的类型为DoubleWritable，用来描述特定的边；而改进后模型将key替换为一个元组tuple，其类型为TupleWritable。这个元组包含Seq和key两个属性，其中Seq为IntWritable类型，用来标识分组组号，key为DoubleWritable类型，仍用来描述特定的边。每个样本训练后，每个边都对应着一个权值变化量。假设有m个样本，则未改进时每个Reduce的输入值WeightWritable都有m个值。一个Reduce要对m个数据进行处理，若m特别大，消耗的时间会较长；假设将样本数据分为k组，则每组有m/k个数据，即每个reduce的WeightWritable对应着m/k个数据，让k个reduce并行工作来完成改进前一个reduce完成的工作，从而缩短处理时间。表1为Reduce改进前与改进后的输入值情况。

表1 Reduce改进前与改进后的输入值

5 基于MapReduce改进模型的BP神经网络并行方法

根据改进的MapReduce模型，Map阶段的初始键值不再是单一键值而是一组神经网络训练集的键值，相当于将一个神经网络训练分散成多个子神经网络进行训练，其他过程基本继承原来的训练过程，从而计算输出误差，然后将生成的中间键值传递到reduce阶段。

Map函数伪代码如下：

输入：key，value

输出：tuple[seq,key]，WeightWritable

Mapper(key，value)

{

利用一组样本数据在当前网络中正向传播；

反向传播计算权值改变量；

获得当前网络权值，赋值tuple[seq,key]；

获得本次训练权值改变量，赋值WeightWritable；

计算此次训练实验误差；

Emit(tuple[seq,key]，WeightWritable)；

}

在Reduce阶段，将BP神经网络训练集在Map阶段的训练结果（tuple[seq,key]，Weight-Writable)作为输入，其中用元组tuple替代未改进前的key值，将大数据集下的同一key值对应的单一reduce工作方式改为多个reduce并行工作方式，从而减少并行处理时间。

Reduce函数伪代码如下：

输入：tuple[seq,key]，WeightWritable

输出：key，value’

Reducer(tuple[seq,key]，WeightWritable)

{

while(未处理完所有WeightWritable)

{

收集Map阶段输出的WeightWritable;

}

统计计算得出本次训练权值改变量；

计算本次训练后网络权值value’；

if(|value’–value|<〥)

Emit(key，value’)；

else

进入下一次迭代计算；

}

图4为基于BP神经网络算法改进的MapReduce并行编程模型工作流程。

图4 并行化工作流程

6 实验及结果分析

本实验采用1台物理机虚拟3台虚拟机，即1个Master和2个Slave节点，节点之间在局域网中相互连通。为了实现节点间在同一局域网上定向通信，配置使用静态地址。各节点的IP分布如表2所示（处理器型号Intel Core i5 2.7，内存6 GB）。

表2 IP地址分布表

实验利用原有的MapReduce模型和改进后的MapReduce模型分别对不同大小的数据集进行并行化处理，结果如表3所示。

表3 实验结果

如表3所示，实验中，随着数据量的增大，程序的运行时间变长，但使用改进的MapReduce模型优化效果也越明显。实验中发现，程序运行时间大多消耗在Map阶段。因此，只有数据集庞大到一定程度，Reduce阶段的模型改进效果才会更加显著。

7 结 语

本文对基于MapReduce的BP神经网络算法进行研究，完成了BP神经网络的并行化，并基于此提出了一种改进后的MapReduce模型，并将MapReduce改进模型运用到BP神经网络中，成功减少了并行处理数据的时间，提高了并行化速率。因实验条件有限，无法对过大数据集进行实验，未来将会继续对过大数据集进行试验。此外，选取合适的作业调度可以提高整个系统的计算性能，而多台机器共享MapReduce集群可以减少一定代价。因此，接下来将继续进行研究，以期使MapReduce模型更加成熟。

参考文献：

[1] 朱珍.基于神经网络集成分类器预处理的支持向量机分类算法[J].科技通报,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.模式识别与神经网络[M].北京:人民邮电出版社,2009.Ripley.B.D.Pattern Recognition and Neural Network[M].Beijing:Posts & Telecom Press,2009.

[3] 朱启敏.基于云计算平台的神经网络计算方法及其应用研究[D].广州:华南理工大学,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] 刘鹏.实战Hadoop:开启通向云计算的捷径[M].北京:电子工业出版社,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].微型电脑应用,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] 周峰,李旭伟.一种改进的MapReduce并行编程模型[J].计算机技术与信息发展,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].科技通报,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] 陈俊杰,强彦.基于模拟退火的MapReduce调度算法[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].计算机与数字工程,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.