改进Adaboost下BP神经网络并行化训练方法

吴正江,陈如校,张霄宏

(河南理工大学 计算机科学与技术学院,河南 焦作 454003)

1 引 言

人工神经网络被广泛应用于模式识别和数据挖掘领域,例如图像信号处理[1],语音识别等.BP神经网络是目前各个领域使用的最广泛的人工神经网络之一,能够通过学习,无限接近任意曲面的边界而无需事先知道具体的数学方程[2].

早期,BP神经网络的训练都是在单机下进行.随着数据的增大,单机下的训练变得越来越耗时,可能需要几天,一周甚至无法完成模型的训练.因此,提高BP神经网络面向大规模数据集时的训练速度,具有重要的意义[3].

并行化是解决上述问题的方案之一.基本上BP神经网络的并行化有两种方式:结构并行化与数据并行化.在结构并行化时,将BP网络结构中的各个节点映射到集群中的各个节点上.这种方式的缺点是各个节点之间频繁的进行通信协调,只适用于小数据量的复杂神经网络的并行化.而在数据并行化方式下,整个数据集被切分成各个小的子数据集,由集群中的各个子节点并行处理属于自己的那部分子数据集.同时,在训练过程中存在两种对连接权值进行更新的模式:逐个更新和批更新.在逐个更新模式下,神经网络每读取一个样本进行处理之后便对网络连接权值进行更新;而在批更新模式下,在所有的数据处理一遍之后再一次性对权值进行更新.

随着近些年大数据平台Hadoop的普及,基于Hadoop平台下的BP神经网络并行化得到了很大的发展.目前大多数在Hadoop下实现的对BP神经网络并行化的研究都采用数据并行化下的批更新操作[4-10].其中[4]通过对大规模移动数据的分类,采用Adaboost算法对BP神经网络进行优化,实现了BP神经网络的并行化,[5,6]通过对[4]中提出的MBNN算法训练过程中产生过多的中间结果问题通过添加combiner函数,减少中间结果来加快网络的训练速度.[7,8]分别通过在进行经典的BP算法之前利用遗传算法,深度信念网络对BP神经网络的连接权值的初始化进行优化,加快BP神经网络的收敛速度.

然而上述均采用Hadoop来对BP神经网络进行并行化实现,由于Hadoop是基于磁盘的,因而在训练反复迭代过程中,每一次迭代都需要读取磁盘上保存上次迭代结果的信息.[7,9,10]对上述问题进行了一定程度的改善,通过在Mapper阶段根据局部数据训练得到局部收敛的BP神经网络后,在Reducer阶段再进行不同策略的整合.虽然[7,9,10]对迭代过程中读取磁盘进行了一定程度的优化,但还是避免不了多次读取磁盘,且由于BP神经网络容易陷入局部最优解的问题使得最终得到的BP神经网络结构正确率不一定达到要求.

本文提出的方法在[4]中MBNN的基础之上,对[4]方法中采用的Adaboost算法进行改进,以使Adaboost算法更好的与BP神经网络算法进行结合,同时采用同样基于MapReduce思想实现的基于内存的Spark平台进行算法实现.最后实验结果表明在保证正确率的情况下,本方法更优于[4]中提出的MBNN算法且缩短了算法训练时间.

2 神经网络算法

人工神经网络(Artificial Neural Network,ANN),是在模拟生物神经网络的基础上构建的信息处理系统,具有强大的信息存储和处理能力.至今已开发出了一系列的算法的不同分支,其中以反向传播网络,即BP神经网络模型应用最为广泛.BP算法以其良好的非线性逼近能力,泛化能力以及实用性成为了人工神经网络训练算法中应用最为广泛的算法.BP神经网络算法的基本思想是重复的使用链式法则计算出每一个网络权值对网络最后的结果误差E的影响:

(1)

这里wij表示神经元j与神经元i的连接权值,si是输出,neti是神经元i的加权和.一旦求出所有的权值的偏导数,就可以通过简单的权值下降法让误差取得最小值:

(2)

通过公式(2)不断迭代网络连接权值,最终达到终止条件,得到收敛的分类器.

3 Adaboost算法

Adaboost[11]的结构如下所示:

最后的分类器YM由多个弱分类器联合组成.相当于M个弱分类器联合决定样本属于哪个类,而且每个弱分类器的重要性αm不同.具体过程如下:

1)初始化所有样本的权重w1,i为1/N,其中N为样本总数.

2)对于1到M个弱分类器 do

a)训练弱分类器ym,使其最小化权重误差函数

(3)

其中tn为样本所属真正的类别.

b)计算出该弱分类器的重要性αm

(4)

c)更新样本的权重wm+1,i

(5)

3)得到最后的分类器

(6)

在上述Adaboost算法中,每产生一个弱分类器ym之后,对样本权值进行更新,并通过抽样的方式对样本进行抽样,得到新的样本来训练新的弱分类器ym+1.

4 基于改进Adaboost的BP神经网络算法

在上述Adaboost过程中,存在一个严重的问题:当处理的数据量变得非常大的时候,每次训练得到一个弱分类器后,得出训练下一个分类器所需要的样本变得十分的耗时困难.

本文中,将BP神经网络作为基分类器进行训练,并且采用批更新对网络连接权值进行更新.在训练得到ym分类器后,不进行抽样过程.而是通过(5)对每个样本的权重进行更新,得到每个样本都带有权值wm+1,k的一个样本集合.在对ym+1这个分类器进行训练的时候,对样本集合中的每一条数据代入上一次得到的BP神经网络中,计算出每一条记录对相应的BP神经网络连接权值更新值Δwij,通过下式算出每一条连接总的权值更新值:

(7)

通过将(7)式计算出来所有的样本加权后的BP网络连接权值的更新值对BP神经网络进行更新.

在这一过程中,由于省去了抽样的过程,大大提高了最终分类器YM的训练时间.

5 Spark

Spark*http://hadoop.apache.org.是UC Berkeley AMP lab (加州大学伯克利分校的AMP实验室)所开源的类Hadoop MapReduce的通用并行框架.Spark有Hadoop几乎所有的优点,并且在处理过程中,中间结果不是写入到磁盘上而保留在内存中,非常适合于频繁迭代算法的设计,运行原理图如图1所示.

在Spark集群运行期间,应用程序提交后,Client端初始化并构建SparkContext对象,由SparkContext与集群资源管理者master取得联系,注册程序并申请所需资源:CPU和core,即Executor.Executor接收资源管理者的命令从文件系统中读取数据形成RDD[12]并进行处理,Executor可以并行运算,运算的逻辑一样,但处理的数据不一样.在SparkContext初始化的过程中生成了DAGScheduler对象和TaskScheduler对象,DAGScheduler根据shuffledependency将应用程序分割成一个个的stage,每一个stage包含一个或者很多个task,这

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

些task之间可以进行并行执行,而所有的stage顺序运行.接着,SparkContext将应用程序的代码广播给每个Executor,同时SparkContext根据数据本地性和每个处理机的处理能力将任务分配给每个Executor,之后Executor开始执行分配给自身的任务.

6 算法并行化

Spark采用典型的master-worker并行模式,一般拥有一个master节点和多个worker节点,即计算节点.Master节点协调整个训练任务的执行,而训练的实际执行者为很多个worker节点.在运行之前训练集被切分成很多个block存储在分布式文件系统HDFS上.每个计算节点根据数据本地性读取属于自己的那部分block进行独立训练误差,具体的并行算法实现伪代码如下:

具体算法过程和流程图如下:

1)程序提交后主进程进行初始化,通过SparkContext.textFile()函数从分布式文件系统HDFS中依据Spark自身具有的数据本地性读取训练所需的数据形成RDD;

2)通过调用RDD.map(string2Tuple(_))方法将读取进来的每行记录转换成BP网络训练时需要的输入格式.其中string2Tuple方法封装了对于每一条记录的解析业务逻辑;

图2 数据并行BP算法流程图Fig.2 Data parallel BP algorithm flow chart

3)将BP网络训练连接权值wij,αt等参数以BroadCast变量的形式传递给各从进程;

4)各从进程读取传过来的BroadCast参数,并构建神经网络结构;

5)根据任务调度策略的优先顺序PROCESS_LOCAL、NODE_LOCAL、NO_PREF,RACK_LOCAL、ANY,优先根据PROCESS_LOCAL选取出RDD中对应自身的Partition进行计算,对每一条记录先根据BroadCast过来的上一次得出的正确率计算出的Δwij更新记录权值.

6)计算出各条记录通过BP神经网络后连接权值更新值并将每个连接权值与对应记录的权值进行相乘得出每条记录的对BP神经网络连接权值的加权更新量.

图3 并行计算方法示意图Fig.3 Parallel computing method

7)再将对应一个Executor的所有样本的权值更新值进行本地reduce,得出总的权值更新值并计算出对应executor对应记录的正确率和记录条数.

8)主节点将从节点上的连接权值更新值,每个executor对应的记录正确率和记录条数收集过来.

9)主节点对BP神经网络进行批更新更新并计算出则整体的正确率以及αt.

10)判断是否达到终止条件,若达到则终止训练;若没有达到,则转到3)步进行新一轮的循环.

到达终止条件后,主节点将根据Adaboost计算出的多个分类器依据(4)计算出来的权重αm进行加权集成,为了更好的理解,从数据的角度观察整个过程如图3所示:

7 实验设计与结果分析

7.1 实验环境与实验方案

7.1.1 实验环境

实验中所使用到的集群环境配置属性信息详见表1.

表1 节点信息表Table 1 Node information table

7.1.2 实验方案

对于并行算法,我们最关心的是算法的运行时间和正确率,除此之外还要考虑并行算法相对于串行算法对于计算速度的提升.

本文选取UCI里的Magic Gamma Telescope Data Set数据集作为实验数据,为了解决实验数据的数据量问题,通过原有数据经过代码生成技术在原有的数据量下生成1000万条数据,进行分类验证并行BP算法的可行性.

7.2 算法参数

输入层和输出层的神经元个数,由输入和输出向量的维数来确定.在此,根据数据集的特点可以确定出输入输出层神经元个数分别为10,2.对于隐含层数的确定,Hornik等早已证明[13]:若输入层和输出层采用线性转换函数,隐含层采用Sigmoid转换函数,具有一个隐含层的BP网络可以实现对任意函数的任意逼近.因此文中BP神经网络采取1个隐含层.同时实验结果表明选取隐藏层节点数为10时,网络模型稳定且可获得较理想结果.

实验结果分别用一台处理机和多台处理机对BP网络进行训练,统计训练的时间,正确率等,结果如表2-表5所示,其中表3,表4的迭代次数表示局部迭代次数,全局迭代次数为1:

从表2-表5可看出来总的运行时间随着处理机的个数的增加而减少,四种算法均获得了可观的加速比,证明了算法具有良好的加速性能,同时如图1所示,在相同的实验条件下,BP-Spark算法明显比[4]中提出的方法获得了更好的加速比,且同样比[9],[10]中提出的算法在达到局部收敛时获得更好的加速比.而正确率结果如图5所示,由于使用Adaboost算法进行集成的弱分类器随着迭代次数(相对于[9][10]来说为全局迭代次数)的增加,得到的弱分类器越多,最终得到的组合分类器正确率逐步提高,说明了算法的有效性,而[9],[10]中提出的算法由于局部数据逐渐减小,训练的单分类器正确率反而有所下降.最后通过在选取5台处理机的情况下对训练集的数据量逐步增大,如图6所示,由图可看出,模型的训练时间和训练集数据量基本上呈线性关系,由此表明了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

加速比与处理机个数的实验结果如图4.

8 结 语

人工神经网络对于信息处理有很强的鲁棒性和容错能力,善于联想和概括,具有自学习能力.BP网络以其良好的数据处理性能在大量的实际工程中得到了广泛的应用.但是传统的BP算法存在学习速度慢等缺点.本文分析了BP算法的局限性,改进了BP算法在并行的基础上,提升了网络的收敛速度.然而仍然存在不足,在训练BP神经网络时如何选取最合适的初始化参数,如何将多个神经网络分类器以更好的策略组合起来等.因此,需要针对这部分做进一步研究与改进.

图4 加速比与处理机个数的实验结果Fig.4 Speed ratio and the number of experimental results of the processor

图5 正确率与迭代次数的实验结果Fig.5 Eexperimental results of correct rate and iteration times

图6 处理时间与数据量关系的实验结果Fig.6 Experimental results of the relationship between processing time and data volume

正确率与处理机个数的实验结果如图5.

五台处理机下,处理时间和数据量的实验结果如图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神经网络MapReduce训练[J].计算机工程与科学,2016,38(12):2425-2433.

[13] 李军华.云计算及若干数据挖掘算法的MapReduce化研究[D].成都:电子科技大学,2010.