自从google发表著名的GFS、MapReduce、BigTable三篇paper以后,互联网正式迎来了大数据时代。大数据的显著特点是大,哪里都大的大。本篇主要针对volume大的数据时,使用机器学习来进行数据处理过程中遇到的架构方面的问题做一个系统的梳理。
1. 背景
自从google发表著名的GFS、MapReduce、BigTable三篇paper以后,互联网正式迎来了大数据时代。大数据的显著特点是大,哪里都大的大。本篇主要针对volume大的数据时,使用机器学习来进行数据处理过程中遇到的架构方面的问题做一个系统的梳理。
有了GFS我们有能力积累海量的数据样本,比如在线广告的曝光和点击数据,天然具有正负样本的特性,累积一两个月往往就能轻松获得百亿、千亿级的训练样本。这样海量的样本如何
存储?用什么样的模型可以学习海量样本中有用的pattern?这些问题不止是工程问题,也值得每个做算法的同学去深入思考。
1.1简单模型or复杂模型
在深度学习概念提出之前,算法工程师手头能用的工具其实并不多,就LR、SVM、感知机等寥寥可数、相对固定的若干个模型和算法;那时候要解决一个实际的问题,算法工程师更多的工作主要是在特征工程方面。而特征工程本身并没有很系统化的指导理论(至少目前没有看到系统介绍特征工程的书籍),所以很多时候特征的构造技法显得光怪陆离,是否有用也取决于问题本身、数据样本、模型以及运气。
在特征工程作为算法工程师主要工作内容的时候,构造新特征的尝试往往很大部分都不能在实际工作中work。据我了解,国内几家大公司在特征构造方面的成功率在后期一般不会超过20%。也就是80%的新构造特征往往并没什么正向提升效果。如果给这种方式起一个名字的话,大概是简单模型+复杂特征;简单模型说的是算法比如LR、SVM本身并不服务,参数和表达能力基本呈现一种线性关系,易于理解。复杂特征则是指特征工程方面不断尝试使用各种奇技淫巧构造的可能有用、可能没用的特征,这部分特征的构造方式可能会有各种trick,比如窗口滑动、离散化、归一化、开方、平方、笛卡尔积、多重笛卡尔积等等;顺便提一句,因为特征工程本身并没有特别系统的理论和总结,所以初入行的同学想要构造特征就需要多读paper,特别是和自己业务场景一样或类似的场景的paper,从里面学习作者分析、理解数据的方法以及对应的构造特征的技法;久而久之,有望形成自己的知识体系。
深度学习概念提出以后,人们发现通过深度神经网络可以进行一定程度的表示学习(representation learning),例如在图像领域,通过CNN提取图像feature并在此基础上进行分类的方法,一举打破了之前算法的天花板,而且是以极大的差距打破。这给所有算法工程师带来了新的思路,既然深度学习本身有提取特征的能力,干嘛还要苦哈哈的自己去做人工特征设计呢?
深度学习虽然一定程度上缓解了特征工程的压力,但这里要强调两点:1.缓解并不等于彻底解决,除了图像这种特定领域,在个性化推荐等领域,深度学习目前还没有完全取得绝对的优势;究其原因,可能还是数据自身内在结构的问题,使得在其他领域目前还没有发现类似图像+CNN这样的完美CP。2.深度学习在缓解特征工程的同时,也带来了模型复杂、不可解释的问题。算法工程师在网络结构设计方面一样要花很多心思来提升效果。概括起来,深度学习代表的简单特征+复杂模型是解决实际问题的另一种方式。
两种模式孰优孰劣还难有定论,以点击率预测为例,在计算广告领域往往以海量特征+LR为主流,根据VC维理论,LR的表达能力和特征个数成正比,因此海量的feature也完全可以使LR拥有足够的描述能力。而在个性化推荐领域,深度学习刚刚萌芽,目前google play采用了WDL的结构[1],youtube采用了双重DNN的结构[2]。
不管是那种模式,当模型足够庞大的时候,都会出现模型参数一台机器无法存放的情况。比如百亿级feature的LR对应的权重w有好几十个G,这在很多单机上存储都是困难的,大规模神经网络则更复杂,不仅难以单机存储,而且参数和参数之间还有逻辑上的强依赖;要对超大规模的模型进行训练势必要借用分布式系统的技法,本文主要是系统总结这方面的一些思路。
1.2数据并行vs模型并行
数据并行和模型并行是理解大规模机器学习框架的基础概念,其缘起未深究,第一次看到是在姐夫(Jeff Dean)的blog里,当时匆匆一瞥,以为自己懂了。多年以后,再次开始调研这个问题的时候才想起长者的教训,年轻人啊,还是图样,图森破。如果你和我一样曾经忽略过这个概念,今天不放复习一下。
这两个概念在[3]中沐帅曾经给出了一个非常直观而经典的解释,可惜不知道什么原因,当我想引用时却发现已经被删除了。我在这里简单介绍下这个比喻:如果要修两栋楼,有一个工程队,怎么操作?第一个方案是将人分成两组,分别盖楼,改好了就装修;第二种做法是一组人盖楼,等第一栋楼盖好,另一组装修第一栋,然后第一组继续盖第二栋楼,改完以后等装修队装修第二栋楼。咋一看,第二种方法似乎并行度并不高,但第一种方案需要每个工程人员都拥有“盖楼”和“装修”两种能力,而第二个方案只需要每个人拥有其中一种能力即可。第一个方案和数据并行类似,第二个方案则道出了模型并行的精髓。
数据并行理解起来比较简单,当样本比较多的时候,为了使用所有样本来训练模型,我们不妨把数据分布到不同的机器上,然后每台机器都来对模型参数进行迭代,如下图所示
图片取材于TensorFlow的paper[4],图中ABC代表三台不同的机器,上面存储着不同的样本,模型P在各台机器上计算对应的增量,然后在参数存储的机器上进行汇总和更新,这就是数据并行。先忽略synchronous,这是同步机制相关的概念,在第三节会有专门介绍。
数据并行概念简单,而且不依赖于具体的模型,因此数据并行机制可以作为框架的一种基础功能,对所有算法都生效。与之不同的是,模型并行因为参数间存在依赖关系(其实数据并行参数更新也可能会依赖所有的参数,但区别在于往往是依赖于上一个迭代的全量参数。而模型并行往往是同一个迭代内的参数之间有强依赖关系,比如DNN网络的不同层之间的参数依照BP算法形成的先后依赖),无法类比数据并行这样直接将模型参数分片而破坏其依赖关系,所以模型并行不仅要对模型分片,同时需要调度器来控制参数间的依赖关系。而每个模型的依赖关系往往并不同,所以模型并行的调度器因模型而异,较难做到完全通用。关于这个问题,CMU的Erix Xing在[5]中有所介绍,感兴趣的可以参考。
模型并行的问题定义可以参考姐夫的[6],这篇paper也是tensorflow的前身相关的总结,其中图
解释了模型并行的物理图景,当一个超大神经网络无法存储在一台机器上时,我们可以切割网络存到不同的机器上,但是为了保持不同参数分片之间的依赖,如图中粗黑线的部分,则需要在不同的机器之间进行concurrent控制;同一个机器内部的参数依赖,即途中细黑线部分在机器内即可完成控制。
黑线部分如何有效控制呢?如下图所示
在将模型切分到不同机器以后,我们将参数和样本一起在不同机器间流转,途中ABC代表模型的不同部分的参数;假设C依赖B,B依赖A,机器1上得到A的一个迭代后,将A和必要的样本信息一起传到机器2,机器2根据A和样本对P2更新得到,以此类推;当机器2计算B的时候,机器1可以展开A的第二个迭代的计算。了解CPU流水线操作的同学一定感到熟悉,是的,模型并行是通过数据流水线来实现并行的。想想那个盖楼的第二种方案,就能理解模型并行的精髓了。
上图则是对控制模型参数依赖的调度器的一个示意图,实际框架中一般都会用DAG(有向无环图)调度技术来实现类似功能,未深入研究,以后有机会再补充说明。
理解了数据并行和模型并行对后面参数
服务器的理解至关重要,但现在让我先荡开一笔,简单介绍下并行计算框架的一些背景信息。
2. 并行算法演进
2.1 MapReduce路线
从函数式编程中的受到启发,google发布了MapReduce[7]的分布式计算方式;通过将任务切分成多个叠加的Map+Reduce任务,来完成复杂的计算任务,示意图如下
MapReduce的主要问题有两个,一是原语的语义过于低级,直接使用其来写复杂算法,开发量比较大;另一个问题是依赖于磁盘进行数据传递,性能跟不上业务需求。
为了解决MapReduce的两个问题,Matei在[8]中提出了一种新的数据结构RDD,并构建了Spark框架。Spark框架在MR语义之上封装了DAG调度器,极大降低了算法使用的门槛。较长时间内spark几乎可以说是大规模机器学习的代表,直至后来沐帅的参数服务器进一步开拓了大规模机器学习的领域以后,spark才暴露出一点点不足。如下图
从图中可以看出,spark框架以Driver为核心,任务调度和参数汇总都在driver,而driver是单机结构,所以spark的瓶颈非常明显,就在Driver这里。当模型规模大到一台机器存不下的时候,Spark就无法正常运行了。所以从今天的眼光来看,Spark只能称为一个中等规模的机器学习框架。剧透一句,公司开源的Angel通过修改Driver的底层协议将Spark扩展到了一个高一层的境界。后面还会再详细介绍这部分。
MapReduce不仅是一个框架,还是一种思想,google开创性的工作为我们找到了大数据分析的一个可行方向,时至今日,仍不过时。只是逐渐从业务层下沉到底层语义应该处于的框架下层。
本文为授权转载文章,任何人未经原授权方同意,不得复制、转载、摘编等任何方式进行使用,e-works不承担由此而产生的任何法律责任! 如有异议请及时告之,以便进行及时处理。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。