大规模逻辑回归并行化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013-1-7,#,机器学习平台汇报,Iniyosaliu(),1,提纲,基础准备,CTR,平台,凸函数优化,MPI,基础,BSP,Batch Learning,原理,评测,Checkerboard,Incremental Learning,原理,评测,后续方向,2,CTR,平台,3,MPI,M,assage,P,assing,I,nterface:,是消息传递函数库的标准规范，由,MPI,论坛开发，支持,Fortran,和,C,MPI,是一种标准或规范的代表，而不是特指某一个对它的具体实现,MPI,是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准,MPI,有丰富的接口提供实时的点对点、,Group,对,Group,、点和,Group,进行数据交互的,API,目前主流使用的有,Mpich2,和,OpenMPI,4,MPI,P0,P0,P1,P2,data,processor,5,MPI,p0,p1,p2,p3,p0,p1,p2,p3,k=m/p,p0,p1,p2,p3,Layout,向量按照节点进行分割，矩阵采用,row shards,的方式存储,加速比,不算,All Reduce,的开销，加速比是,Processor,数目,MPI,支持,P,是进程单位，,Mpich2,最新版本支持同一个,Node,启动多个,P,6,BSP,Bulk synchronous parallel,:,BSP was developed by,Leslie Valiant,during the 1980s,A BSP computation proceeds in a series of global,supersteps,. A superstep consists of three ordered stages:,1),Concurrent computation,: local data, independent,asynchronously,2),Communication,: At this stage, the processes exchange data between themselves.,3),Barrier synchronization,: When a process reaches this point,1) No deadlock and data races,2) Barrier permit novel forms of fault tolerance,3) Parallel graph-processing-Pregel,7,Parallel DS,Local Vector,Parallel Vector,P0,A,P0,P1,P2,P3,bool,CreateVector(Comm,GlobalSize,LocalSize,*Vector),bool VectorSet(*Vector,double),double Dot(Vec*, Vec *),double VectorNorm(Vec *,NormType,double*),AXPY AYPX,A,Class Vector,逻辑抽象和物理存储分开 存储和计算都并行,通信量很少,8,凸函数优化,假设,f(x),有二阶连续偏导,:,Example: FindMinimumPlotCosx2 - 3 y + Sinx2 + y2,x,1,y,1,优化的方法：,1),最速下降法,2) NewTon,法,3) Qusai-NewTon,法,4) BFGS,方法,5) OWLQN,所有上述方法的核心：,f,的一阶导数,梯度，二阶导数,Hessian,-2.,x = 1.37638,y = 1.67868,Steps = 9,Function = 13,Gradient = 13,9,凸函数优化,OWLQN,或者说,LBFGS,不存储,Hessian,矩阵，而是存储以前迭代的梯度信息，直接计算搜索方向,S,，,Y,中存储前,m,次迭代的信息,使用,two-loop recursion,方法直,接计算搜索方向,内部向量有,60,个,Dense Vector,的向量,1,亿的,Feature,的内部存储需要,48G,数据,存储：训练数据如何存储？,CPU,：内部有大量超高纬向量的运算,10,Batch Learning VS Online Learning,Online algorithms,operate by repetitively drawing a fresh random example,and adjusting,the parameters on the basis of this single example only.,Batch algorithms,completely,optimizing the cost function,defined on,a set of training examples,cost function,Batch gradient:,Online gradient,:,11,正则化,Regularization,实际中，,Over-fit,问题求解最优化的时候会加入正则化因子：,L1,对于取样复杂度的关系是,Log,关系，也就是说,L1,对于无关特征的适应性较好,L1,可以训练出很多权重为,0,的特征值，天然的具有特征选择的作用,L1,和,L2,相比可以用更少的迭代次数达到收敛,12,Logistic,回归模型,(,背景,),Logistic Regression,的训练问题是,Unconstrained Optimization,问题,Instance scale,W,模型参数，线上使用,X,提取的,Feature,13,Logistic Regression,训练,训练的一般过程,Instance,加和,WX,计算,14,MapReduce,Mapper,函数,计算每一个实例对目标函数以及梯度的贡献,Reduce,函数,把这些贡献汇总起来，得到梯度以及目标函数值,1,、,Single reducer,2,、,Map,和,Reduce,交替等待,15,从,MapReduce,到,MPI,现状,1,、性能：普通模型,34,个小时,右侧模型,35,个小时，不能满足做实验要求，不能实现一天一更新,2,、扩展性：,Instance,从,1,亿到,6,亿，,3,小时,-35,个小时,3,、数据瓶颈：最多,1000WFeature(,百度有,1000,亿,Feature,，,2000+,台机器集群,),业界,Baidu,放弃,MapReduce,，早就转为,MPI, Sogou,Google Pregel Yahoos S4,16,Why faster?,数据划分方式,Instance Shards/Feature Shards/CheckerBoard,使得系统对于大规模数据不仅能算，而且能计算的很好,X,和,W,点积的问题,W,和,BFGS,内部迭代,存储和计算并行，通信量很小,每次迭代之间不需要,IO,数据常驻内存,BFGS,算法的优化,Hessian,矩阵模拟的更好，提高,m,带来较快的收敛速度,Scaling,技术,17,LR,并行化平台,Olympic,：,更,快,(,捷,),更高,(,效,),更强,(,大,),“,快捷,”:,使用方便，,单机版,Uni-processor,和并行版,Multi-processor,程序是同一个二进制的,Binary,，有或者没有,MPI,环境均可以使用，,SVN checkout,即可以使用，接口简单。在,MPI,的环境中，只要配好,MPI,环境即可立刻启动并行版,Olympic_train,“,高效,”:,训练速度高效,，目前训练 线上的,CTR,模型只需要,5,分钟,(,MapReduce,版本需要,3,个小时,),，加入右侧数据的,CTR,模型需要,10,分钟,(,MapReduce,版本需要,35,个小时,),，,User-Model,模型需要,11.2,分钟,(MapReduce,版本需要,19.5,个小时,),效率提升,50200,倍,“,强大,”:,处理数据的能力强大,，,Olympic_train,支持并行多任务,(,集群非独占,),，即到即用。我们的系统对,Instance number,和,Feature number,均不做限制,(,不管任何数据量，加机器即可以解决,).,当前机器规模支持,40,亿,Feature,的高效训练,18,Olympic-,架构,Parallel Batch Learning(Baidu Sogou),1,、,BSP Hybrid Application Model Parallel,2,、,Gradient & Function Evaluation,3,、数据,&,计算并行,4,、,Feature Shards/Instance Shards/Checkerboard,5,、稳定 能达到最优的,Empirical Loss,的水平,19,Olympic-,评测,Offline-Evaluation,Online-Evaluation,灰度实验结果,20,Olympic-,评测,Performance,Multi-Tasks,Scalability,Resources,instance number,feature number,train time(minutes),1,亿,400W,5,6,亿,600W,10,1.8,亿,1000W,10.8,1,亿,4000W,37,1,亿,10000W,73.6,21,业界,1000,亿次曝光的广告展现，能否很好的训练？,百度,1000,亿,Feature,数据，,2000+,机器，训练数据,30T+,，时间,25+,小时,在超高维度的情况下，通信耗时占到总耗时,60%70%,超多的,Instance,和超高维,Feature,的数据，如何做,Tradeoff,？,22,CheckerBoard,1),将整个训练数据集按横向以,instance,为单位划分到各个机器进行分布式计算,2),按纵向将超大维度的,instance,数据划分成多个子段进行分布式的计算,Feature Shards,Instance Shards,Checkerboard,23,按,instance,的维度划分行,共,N,行,;,按,feature,的维度划分列,共,M,列,;,每个,processor,可以,起,多线程加快行数据,(instance),的处理速度；,L-BGFS,求解过程中的,S,Y,D,向量与,W,向量分布一致,不同的,Layout,Multi-Process,+,Multi-Thread,24,25,机器学习平台,Olympic,Logistic,分布,Target,：,W,40,亿,16*3 layout,：,456,分钟，通信耗时只占到,20%,Performance Multi-Tasks(615 tasks) Scalability Resource(CPU 70% Mem:3G5G),线上：全流量 目前累计,Train 1000+,次,支持实验,50+,个,并行,Vector,并行,Matrix,存储并行,计算并行,无延迟,IO,25,Checkerboard,通信量,单分,1,列，每,个,processor,都需要拉取剩下,的,(N-1)*Dim/N,那部分数据,单,份,1,行，每个,processor,都可以计算自己那部分的,W*X,因此计算过程中不需要拉取任何,W,数据,(,Online Learning),分,N,行,M,列，由于,W,的分片是从相同列拉取的，故,每个,processor,通信量为,Dim/M-Dim/(N*M)=(N-1)*Dim/(N*M),其等于单列通信量的,1/M,我们的通信耗时,20%,Baidu,的通信耗时,60%70%,26,性能,40,亿维度的,featur,e,instance shard,无法计算,checkerboard c2,无法计算,checkerboard c4,无法计算,checkerboard c8,能计算,时间较长,checkerboard c16,456.77,分钟,27,内存,28,Incremental Learning,29,Incremental Learning,Parallel Online Learning,1,、,One Pass,高效收敛快,2,、参数敏感 不容易达到最优,Empirical Loss,3,、不稳定 不易于监控,(,百度现状,),4,、接受信号就可以输出,model,5,、自动分时进行训练,6,、机器成本显著降低,7,、可做完美容灾,30,训练任务自动化与容灾设计,日志数据下载,-,模型训练,- AUC,计算,-,模型文件上传，所有步骤都实现了全自动化；维护一份训练程序，使用不同的配置文件起不同的任务；,对于训练集群的容灾，同样的实现了全自动化：,完美容灾：后续接入,Tborg + XFS,，心跳上报到,Master,，,CheckPoints,31,谢谢,32,