1、機器學習平臺匯報Jone提綱 基礎準備 CTR平臺 凸函數優化 MPI基礎 BSP Batch Learning 原理 評測 Checkerboard Incremental Learning 原理 評測 后續方向CTR平臺MPI Massage Passing Interface:是消息傳遞函數庫的標準規范，由MPI論壇開發，支持Fortran和C MPI是一種標準或規范的代表，而不是特指某一個對它的具體實現 MPI是一種消息傳遞編程模型，并成為這種編程模型的代表和事實上的標準 MPI有豐富的接口提供實時的點對點、Group對Group、點和Group進行數據交互的API 目前主流使用的有M

2、pich2和OpenMPIMPI10niiibac pnjniiijbac/010P0P0P1P2dataprocessorMPIp0p1p2p3p0p1p2p3nnmmCBA11k=m/pp0p1p2p3Layout 向量按照節點進行分割，矩陣采用row shards的方式存儲加速比不算All Reduce的開銷，加速比是Processor數目MPI支持P是進程單位，Mpich2最新版本支持同一個Node啟動多個PBSPBulk synchronous parallel: BSP was developed by Leslie Valiant during the 1980s A BSP c

3、omputation 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 th

4、is point1) No deadlock and data races2) Barrier permit novel forms of fault tolerance3) Parallel graph-processing-PregelParallel DS Local Vector Parallel Vector a0 aN-1 P0A a0 aN-1 P0 P1 P2 P3bool CreateVector(Comm,GlobalSize,LocalSize,*Vector)bool VectorSet(*Vector,double)double Dot(Vec*, Vec *)dou

5、ble VectorNorm(Vec *,NormType,double*)AXPY AYPXAClass Vector 邏輯抽象和物理存儲分開 存儲和計算都并行 通信量很少凸函數優化假設 f(x)有二階連續偏導:min( )nxRfxExample: FindMinimumPlotCosx2 - 3 y + Sinx2 + y2,x,1,y,1優化的方法： 1) 最速下降法 2) NewTon法 3) Qusai-NewTon法 4) BFGS方法 5) OWLQN所有上述方法的核心：所有上述方法的核心：f的一階導數的一階導數梯度，二階導數梯度，二階導數HessiankkkpBf -2.,x

6、 = 1.37638,y = 1.67868,Steps = 9,Function = 13,Gradient = 13凸函數優化 OWLQN或者說LBFGS不存儲Hessian矩陣，而是存儲以前迭代的梯度信息，直接計算搜索方向 S，Y中存儲前m次迭代的信息 使用two-loop recursion方法直接計算搜索方向1111kkkkkksxxyff 0()(1. ), (.1), () ()kTiiiiikTiiiikkqf xfor im dosqqqyendforpB qfor imdoy pppsendforreturn pBf x 內部向量有60個Dense Vector的向量 1億

7、的Feature的內部存儲需要48G數據 存儲：訓練數據如何存儲？ CPU：內部有大量超高緯向量的運算 Batch Learning VS Online LearningOnline 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 s

8、et of training examplescost function Batch gradient: Online gradient: 正則化Regularization實際中，Over-fit問題求解最優化的時候會加入正則化因子： 0N 1|iiLw，2 0N2iiLw， 1) L1對于取樣復雜度的關系是Log關系，也就是說L1對于無關特征的適應性較好2) L1可以訓練出很多權重為0的特征值，天然的具有特征選擇的作用3) L1和L2相比可以用更少的迭代次數達到收斂Logistic回歸模型(背景)()()()()log(Pr(|,)()min()iiiiwf wl wr wl wyxwr

9、wCwf w 1Pr(1| , )11Pr(0| , )1 Pr(1| , )1TTw xw xyx weyx wyx we Logistic Regression的訓練問題是的訓練問題是Unconstrained Optimization問題問題42240.20.40.60.81.0Instance scaleW 模型參數，線上使用X 提取的FeatureLogistic Regression訓練訓練的一般過程訓練的一般過程kkkpBf Instance加和加和 WX 計算計算MapReduce Mapper 函數計算每一個實例對目標函數以及梯度的貢獻 Reduce函數把這些貢獻匯總起來，得

10、到梯度以及目標函數值1、Single reducer2、Map和Reduce交替等待從MapReduce到MPI現狀1、性能：普通模型34個小時,右側模型35個小時，不能滿足做實驗要求，不能實現一天一更新2、擴展性：Instance從1億到6億，3小時-35個小時3、數據瓶頸：最多1000WFeature(百度有1000億Feature，2000+臺機器集群)業界Baidu放棄MapReduce，早就轉為MPI, SogouGoogle Pregel Yahoos S4復雜程度Iteration并行化效率容災MapReduce塊計算模型Summon-up形式Iteration之間獨立文件IOR

11、educe單節點問題擴展性差Framework本身支持MPI并行模型復雜競爭和死鎖可實現流計算模型(BSP)數據存放在集群內存PBL-內存POL-Cache-掃描一遍數據 無延遲數據完全并行計算并行并行化效率很高需要應用程序考慮Why faster? 數據劃分方式 Instance Shards/Feature Shards/CheckerBoard使得系統對于大規模數據不僅能算，而且能計算的很好X和W 點積的問題 W和BFGS內部迭代存儲和計算并行，通信量很小每次迭代之間不需要IO數據常駐內存 BFGS算法的優化Hessian矩陣模擬的更好，提高m帶來較快的收斂速度Scaling技術LR并行

12、化平臺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個小時

13、)效率提升50200倍“強大”:處理數據的能力強大，Olympic_train支持并行多任務(集群非獨占)，即到即用。我們的系統對Instance number和Feature number均不做限制(不管任何數據量，加機器即可以解決).當前機器規模支持40億Feature的高效訓練Olympic-架構Parallel Batch Learning(Baidu Sogou) 1、BSP Hybrid Application Model Parallel 2、Gradient & Function Evaluation 3、數據&計算并行 4、Feature Shards/Ins

14、tance Shards/Checkerboard 5、穩定 能達到最優的Empirical Loss的水平Olympic-評測 Offline-Evaluation Online-Evaluation 灰度實驗結果1.25E+081.30E+081.35E+081.40E+081.45E+08020406080100120140function valuefunction value with different iteration numerc=0.5c=1.0c=2.0c=3.00.65000.70000.75000.8000050100150200250Auc valueAuc wit

15、h different iteration numauc0.7650.770.7750.780.7850.7900.001 0.010.10.50.80.90.9511.05234AUC value with different regularization C2500000270000029000003100000330000035000003700000020406080100120140160Non-zero weight number with different iteration number0.00E+005.00E+081.00E+091.50E+092.00E+092.50E

16、+09102030405060708090100110120130140150160170180190200210220230240250260270280290300function value with different start pointinitial param = 0initial param = 3initial param = 5initial param = 10Olympic-評測PerformanceMulti-TasksScalabilityResources0200400600800100012001400160018002000olympic_train(L)m

17、apreduce_train(L)olympic_train(R)mapreduce_train(R)olympic_train(U)mapreduce_train(U)Minutesolympic train vs mapreduce train0510152025303540123456multi-tasks parallelly vs sequencelyparallelly total timesequencely total timeaverage bias0.1694915250.1785714290.1754385960.1694915250.1724137930.1694915

18、250.1685393350.2479338740.2884615380.3026481870.31813363 0.31971582123456multi-tasks thoughput rate parallelly vs sequencelysequecely thoughput rateparallely thoughput rateinstance numberfeature numbertrain time(minutes)1億億400W56億億600W101.8億億1000W10.81億億4000W371億億10000W73.655.91015211億2億4億8億16億train

19、 time with increasing instance numbertrain time(minutes)45678910111213141516, 5.8545678910111213141516, 5.1544.555.566.5024681012141618Minutesolympic train with different threads numbertotaltrain1, 6.0833332, 6.4833333, 8.34, 8.9333335, 10.76, 12.2666661, 5.3666672, 6.13, 84, 8.7166665, 10.56, 12.08

20、3333579111301234567time(minutes)one node with different processor numbertotaltrain業界 1000億次曝光的廣告展現，能否很好的訓練？ 百度1000億Feature數據，2000+機器，訓練數據30T+，時間25+小時 在超高維度的情況下，通信耗時占到總耗時60%70% 超多的Instance和超高維Feature的數據，如何做Tradeoff？CheckerBoard 1)將整個訓練數據集按橫向以instance為單位劃分到各個機器進行分布式計算 2)按縱向將超大維度的instance數據劃分成多個子段進行分布式

21、的計算Feature ShardsInstance Shards Checkerboard按instance的維度劃分行, 共N行;按feature的維度劃分列, 共M列;每個processor可以起多線程加快行數據(instance)的處理速度；L-BGFS求解過程中的S,Y,D向量與W向量分布一致不同的不同的LayoutMulti-Process +Multi-Thread25機器學習平臺OlympicLogistic 分布分布42240.20.40.60.81.0Target：Winstance shard5.7337.98362.8checkerboard c25.7333.38297

22、.82checkerboard c48.0222156.75checkerboard c826.4531.7594.65checkerboard c16100.8398.82137.13400萬4000萬4億05010015020025030035040040億億 16*3 layout：456分鐘，通信耗時只占到分鐘，通信耗時只占到20%Performance Multi-Tasks(615 tasks) Scalability Resource(CPU 70% Mem:3G5G)線上：全流量 目前累計Train 1000+次 支持實驗 50+個并行并行VectorVector并行并行Mat

23、rixMatrix存儲并行存儲并行計算并行計算并行無延遲無延遲 IOIOCheckerboard通信量單分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%性能instance shard5.7337.98362.8checkerboard c25.7333.38297.82checkerboard c48.0222156.75checkerboard c826.4531.7594.65checkerb