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

2、pich2和OpenMPIMPI10niiibac pnjniiijbac/010P0P0P1P2dataprocessorMPIp0p1p2p3p0p1p2p3nnmmCBA11k=m/pp0p1p2p3Layout 向量按照節(jié)點進行分割，矩陣采用row shards的方式存儲加速比不算All Reduce的開銷，加速比是Processor數(shù)目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 邏輯抽象和物理存儲分開 存儲和計算都并行 通信量很少凸函數(shù)優(yōu)化假設(shè) f(x)有二階連續(xù)偏導(dǎo):min( )nxRfxExample: FindMinimumPlotCosx2 - 3 y + Sinx2 + y2,x,1,y,1優(yōu)化的方法： 1) 最速下降法 2) NewTon法 3) Qusai-NewTon法 4) BFGS方法 5) OWLQN所有上述方法的核心：所有上述方法的核心：f的一階導(dǎo)數(shù)的一階導(dǎo)數(shù)梯度，二階導(dǎo)數(shù)梯度，二階導(dǎo)數(shù)HessiankkkpBf -2.,x

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

7、的Feature的內(nèi)部存儲需要48G數(shù)據(jù) 存儲：訓練數(shù)據(jù)如何存儲？ CPU：內(nèi)部有大量超高緯向量的運算 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問題求解最優(yōu)化的時候會加入正則化因子： 0N 1|iiLw，2 0N2iiLw， 1) L1對于取樣復(fù)雜度的關(guān)系是Log關(guān)系，也就是說L1對于無關(guān)特征的適應(yīng)性較好2) L1可以訓練出很多權(quán)重為0的特征值，天然的具有特征選擇的作用3) L1和L2相比可以用更少的迭代次數(shù)達到收斂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 模型參數(shù)，線上使用X 提取的FeatureLogistic Regression訓練訓練的一般過程訓練的一般過程kkkpBf Instance加和加和 WX 計算計算MapReduce Mapper 函數(shù)計算每一個實例對目標函數(shù)以及梯度的貢獻 Reduce函數(shù)把這些貢獻匯總起來，得

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

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

12、化平臺Olympic：更快(捷) 更高(效) 更強(大)“快捷”:使用方便，單機版Uni-processor和并行版Multi-processor程序是同一個二進制的Binary，有或者沒有MPI環(huán)境均可以使用，SVN checkout即可以使用，接口簡單。在MPI的環(huán)境中，只要配好MPI環(huán)境即可立刻啟動并行版Olympic_train“高效”:訓練速度高效，目前訓練 線上的CTR模型只需要5分鐘(MapReduce版本需要3個小時)，加入右側(cè)數(shù)據(jù)的CTR模型需要10分鐘(MapReduce版本需要35個小時)，User-Model模型需要11.2分鐘(MapReduce版本需要19.5個小時

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

14、tance Shards/Checkerboard 5、穩(wěn)定 能達到最優(yōu)的Empirical Loss的水平Olympic-評測 Offline-Evaluation Online-Evaluation 灰度實驗結(jié)果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 time average bias0.1694915250.1785714290.1754385960.1694915250.1724137930.169491

18、5250.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億trai

19、n 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.0

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

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

22、3.38297.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

23、并行并行MatrixMatrix存儲并行存儲并行計算并行計算并行無延遲無延遲 IOIOCheckerboard通信量單分1列，每個processor都需要拉取剩下的(N-1)*Dim/N那部分數(shù)據(jù)單份1行，每個processor都可以計算自己那部分的W*X,因此計算過程中不需要拉取任何W數(shù)據(jù)(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.65checker