大规模机器学习算法GBDT及应用 王志伟（冰逸） 2015.06.27

个人 王志伟（冰逸） 2008-2011 ：北航计算机硕士 2011-2012 ：网易有道 搜索组 2012-2014 ： 百度 网页搜索 LTR组 2014-至今 ： 阿里 推荐&投放算法小组

大纲 GBDT算法介绍 GBDT实现原理 GBDT并行实现 应用

GBDT算法介绍 一般的有监督机器学习问题 训练数据 损失函数(loss function) 目标,寻找一个F 𝑌= 𝑦 1 ,𝑦 2 …, 𝑦 𝑛 损失函数(loss function) 𝐿(𝐹(𝑋),𝑌) 目标,寻找一个F 𝐹 ∗ = 𝑎𝑟𝑔𝑚𝑖𝑛 𝐹 L(Y,F x )

损失函数 常见的回归问题 Squared error 𝐿 𝑌,𝐹(𝑋) = 𝑖=1 𝑛 (𝐹 𝑥 𝑖 − 𝑦 𝑖 ) 2 𝐿 𝑌,𝐹(𝑋) = 𝑖=1 𝑛 (𝐹 𝑥 𝑖 − 𝑦 𝑖 ) 2 absolute error 𝐿 𝑌,𝐹 𝑋 = 𝑖=1 𝑛 |𝐹 𝑥 𝑖 − 𝑦 𝑖 |

损失函数 分类问题 SVM hinge loss 𝐿 𝑌,𝐹 𝑋 = 𝑖=1 𝑛 max⁡(0,1− 𝑦 𝑖 ∗𝐹( 𝑥 𝑖 )) Logistic regression loss 𝐿 𝑌,𝐹 𝑋 = 𝑖=1 𝑛 log⁡(1+exp⁡(−2∗ 𝑦 𝑖 ∗𝐹 𝑥 𝑖 )

损失函数 排序问题 Gbrank 𝐿 𝑌,𝐹 𝑋 = 𝑖,𝑗𝜀𝑞 𝑎𝑛𝑑 𝑦 𝑖 > 𝑦 𝑗 max⁡(0,−𝐹 𝑥 𝑖 +𝐹 𝑥 𝑗 +𝜏) 2 LambdaMart 𝐿 𝑌,𝐹 𝑋 = 𝑖,𝑗𝜀𝑞, 𝑎𝑛𝑑 𝑦 𝑖 > 𝑦 𝑗 −𝑙𝑜𝑔 1 1+exp⁡(−𝐹 𝑥 𝑖 +𝐹 𝑥 𝑗 )

最优解 𝐹 ∗ 对于参数化的模型F 𝐹 𝑋;𝑃 𝐹 ∗ = 𝑎𝑟𝑔𝑚𝑖𝑛 𝐹 𝐿(𝑦,𝐹 𝑋 ) =𝑎𝑟𝑔𝑚𝑖𝑛 𝑃 𝐿(𝑌,𝐹 𝑋;𝑃 )

示例 𝑃= 𝑤 𝑇 ,𝑏 ,𝐹 𝑋;𝑃 = 𝑤 𝑇 ∗𝑋+𝑏 𝐿 𝑌,𝐹 𝑋 = 𝑖=1 𝑛 ( 𝑦 𝑖 −𝐹( 𝑥 𝑖 )) 2 𝐹 ∗ = 𝑎𝑟𝑔𝑚𝑖𝑛 𝐹 𝐿 𝑌,𝐹(𝑋) = 𝑎𝑟𝑔𝑚𝑖𝑛 𝑃 𝐿(𝑌,𝐹 𝑋;𝑃 ) = 𝑎𝑟𝑔𝑚𝑖𝑛 𝑤,𝑏 𝐿 𝑌, 𝑊 𝑇 ∗𝑋+𝑏 = 𝑎𝑟𝑔𝑚𝑖𝑛 𝑤,𝑏 𝑖=1 𝑛 ( 𝑦 𝑖 − 𝑤 𝑇 ∗ 𝑥 𝑖 −𝑏) 2

Gradient descent 参数P的求解 假设有一个初始解 𝑃 𝑚−1 ,如何寻找一个更 优解 𝑃 𝑚 𝑝 𝑚 = 𝑝 𝑚−1 +𝜌∗∆𝑝

Gradient descent 𝐿 𝑌,𝐹 𝑋;𝑃 =𝜑(𝑃) 𝐿(𝑌,𝐹 𝑋;𝑃𝑚 ) =𝜑 𝑝 𝑚 =𝜑 𝑝 𝑚−1 +𝜌∗∆𝑝 ≈𝜑 𝑝 𝑚−1 + 𝜕𝜑(𝑃) 𝜕𝑃 | 𝑃= 𝑃 𝑚−1 ∗𝜌∗∆𝑃 ∆𝑃=− 𝜕𝜑(𝑃) 𝜕𝑃 | 𝑃= 𝑃 𝑚−1 𝜑 𝑝 𝑚 <𝜑( 𝑝 𝑚−1 ) 𝑃 ∗ = 𝑖=1 𝑀 𝜌 𝑖 ∗ 𝑛𝑔 𝑚

Gradient boost 最优解 F ∗ 𝐹 ∗ = 𝑖=1 𝑀 𝑓 𝑖 (𝑋) 𝐹 ∗ = 𝑖=1 𝑀 𝑓 𝑖 (𝑋) 如果有一个初始的 𝐹 𝑚−1 (𝑋),如何找到一 个更优解 𝐹 𝑚 𝑋 𝐹 𝑚 𝑋 = 𝐹 𝑚−1 𝑋 +𝜌∗𝑓(𝑥)

Gradient boosting 𝐿 𝑌,𝐹 𝑋 =𝜑 𝐹 𝑋 𝐿 𝑌, 𝐹 𝑚 𝑋 =𝜑 𝐹 𝑚−1 𝑋 +𝜌𝑓 𝑋 ≈𝜑 𝐹 𝑚−1 𝑋 + 𝜕𝜑 𝐹 𝑋 𝜕𝐹 𝑋 | 𝐹 𝑋 = 𝐹 𝑚−1 𝑋 ∗𝜌𝑓(𝑥) 𝑓 𝑥 =− 𝜕𝜑 𝐹 𝑋 𝜕𝐹 𝑋 | 𝐹 𝑋 = 𝐹 𝑚−1 𝑋

Gradient boosting 𝑓 𝑥 =− 𝜕𝜑 𝐹 𝑋 𝜕𝐹 𝑋 | 𝐹 𝑋 = 𝐹 𝑚−1 𝑋 𝑔 𝑖 =− 𝜕𝜑(𝐹 𝑋 ) 𝜕𝐹( 𝑥 𝑖 ) | 𝐹 𝑋 = 𝐹 𝑚−1 (𝑋) =− 𝜕 𝐹 𝑥 1 ,𝐹 𝑥 2 ,…𝐹 𝑥 𝑛 𝜕𝐹 𝑥 𝑖 | 𝐹 𝑋 = 𝐹 𝑚−1 (𝑋) ？

𝜕𝐿(𝑌,𝐹 𝑋 ) 𝜕𝐹( 𝑋 𝑖 ) = 𝜕 𝑗=1 𝑛 log⁡(1+exp⁡(−2∗ 𝑦 𝑗 ∗𝐹 𝑥 𝑗 ) 𝜕𝐹( 𝑥 𝑗 ) = exp⁡(−2∗ 𝑦 𝑖 ∗𝐹 𝑥 𝑖 )∗(−2∗ 𝑦 𝑖 ) 1+exp⁡(−2∗ 𝑦 𝑖 ∗𝐹 𝑥 𝑖 ) 𝑓 𝑥 𝑖 =− 𝜕𝐿 𝑌,𝐹 𝑋 𝜕𝐹 𝑥 𝑖 | 𝐹 𝑋 = 𝐹 𝑚−1 𝑋 =− exp −2∗ 𝑦 𝑖 ∗ 𝐹 𝑚−1 𝑥 𝑖 ∗(−2∗ 𝑦 𝑖 ) 1+exp⁡(−2∗ 𝑦 𝑖 ∗ 𝐹 𝑚−1 ( 𝑥 𝑖 ))

Gradient boosting f(x) 𝑔 1 if X= 𝑥 1 𝑔 2 if X= 𝑥 2 𝑔 3 if X= 𝑥 3 …

Decision Tree L个叶子的Decision Tree记 𝑅 𝑙 𝐿 ,第l的叶子节点的值记 𝑟 𝑙 0.5 if x[1]<= 0.5 & x[2]<=1 Fea_1 <= 0.5 0.7 if x[1]<= 0.5 & x[2]>1 g(x) NO YES 0.8 if x[1]> 0.5 & x[2]<=2 Fea_2 <= 1 Fea_2 <= 2 1.0 if x[1]> 0.5 & x[2]>2 NO NO YES YES 1.0 0.5 0.7 0.8 L个叶子的Decision Tree记 𝑅 𝑙 𝐿 ,第l的叶子节点的值记 𝑟 𝑙

Decision Tree 𝑔 1 if X= 𝑥 1 𝑔 2 if X= 𝑥 2 Fit 𝑔 3 if X= 𝑥 3 f(x) … 𝑔 𝑛 if X= 𝑥 𝑛

Gradient boosting Decision Tree 输入{X,Y}, 损失函数L(Y,F(X)) 初始模型 𝐹 0 𝑋 =0 For m = 1 to M Step1:计算在每一个样本点的负梯度gi 𝑔 𝑖 =− 𝜕𝐿(𝑌,𝐹(𝑋) 𝐹( 𝑋 𝑖 ) | 𝐹 𝑥 = 𝐹 𝑚−1 (𝑋) Step2:建立一棵L叶子节点的决策树 { 𝑅 𝑙 } 𝑙=1..𝐿 ,拟合 { 𝑥 𝑖 , 𝑔 𝑖 } 𝑖=1..𝑛 ,记为 𝑔 𝑚 (𝑋) Step3: 𝐹 𝑚 𝑋 = 𝐹 𝑚−1 𝑋 +𝜌∗ 𝑔 𝑚 (𝑋) 𝐹 𝑋 = 𝐹 𝑀 (𝑋)

大纲 GBDT算法介绍 GBDT实现原理 GBDT并行实现 应用

GBDT实现原理 建立决策树拟合负梯度函数 𝑔 1 if X= 𝑥 1 𝑔 2 if X= 𝑥 2 𝑔 3 if X= 𝑥 3 f(x) Fit 𝑔 3 if X= 𝑥 3 f(x) … 𝑔 𝑛 if X= 𝑥 𝑛 g(x)

g(x)拟合f(x) 拟合指标 g(x)与f(x)的diff absolute error square error 𝑖=1 𝑛 |𝑔 𝑥 𝑖 −𝑓 𝑥 𝑖 | square error 𝑖=1 𝑛 (𝑔 𝑥 𝑖 −𝑓 𝑥 𝑖 ) 2

Greedy algorithm 𝑥 𝑖 𝜖𝑅1 (𝑟1− 𝑔 𝑖 ) 2 𝑥 𝑖 𝜖𝑅1 (𝑟1− 𝑔 𝑖 ) 2 r1 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 r2 r3 r4 r5 r6 r7 𝑥 𝑖 𝜖𝑅4 (𝑟4− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅5 (𝑟5− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅6 (𝑟6− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅7 (𝑟7− 𝑔 𝑖 ) 2

Greedy algorithm 𝑚𝑖𝑛 𝑓 𝑚𝑖𝑛 𝑣 𝑥 𝑖 𝜀𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜀𝑅3 (𝑟3− 𝑔 𝑖 ) 2 r1 𝑚𝑖𝑛 𝑓 𝑚𝑖𝑛 𝑣 𝑥 𝑖 𝜀𝑅4 (𝑟4− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜀𝑅4 (𝑟4− 𝑔 𝑖 ) 2 r2 r3 r4 r5 r6 r7 r8 r9

Min F min V x1(1,0) g1(0.5)) x2(3,1) g2(3)) x3(2,6) g3(7)) x4(6,3) r1 先计算feature 1的min V r2 r3 x1[1](1) g1(0.5)) x2[1](3) g2(3)) x3[1](2) g3(7)) x4[1](6) g4(16)) x5(5) g5(12)) 样本按feature 1的排序 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) x5(5) g5(12)) x4[1](6) g4(16))

MIN v V = 1.5 r1 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 = (𝑟2−0.5) 2 + (𝑟3−7) 2 + (𝑟3−3) 2 + (𝑟3−12) 2 + (𝑟3−16) 2 𝑟2=0.5 𝑟3= 7+3+12+16 4 =9.5 𝑒𝑟𝑟𝑜𝑟:97

MIN v V = 2.5 r1 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 = (𝑟2−0.5) 2 + (𝑟2−7) 2 + (𝑟3−3) 2 + (𝑟3−12) 2 + (𝑟3−16) 2 x1(0.5) X3(7) x2(3) X5(12) X4(16) 𝑟2= 0.5+7 2 =3.75 𝑟3= 3+12+16 3 =10.33 𝑒𝑟𝑟𝑜𝑟:109.7917

MIN v V = 4 r1 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) x5(5) 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 = (𝑟2−0.5) 2 + (𝑟2−7) 2 + (𝑟2−3) 2 + (𝑟3−12) 2 + (𝑟3−16) 2 x1(0.5) x3(7) x2(3) X5(12) X4(16) 𝑟2= 0.5+7+3 3 =3.5 𝑟3= 12+16 2 =14 𝑒𝑟𝑟𝑜𝑟:29.5

MIN v V = 5.5 r1 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 = (𝑟2−0.5) 2 + (𝑟2−7) 2 + (𝑟2−3) 2 + (𝑟2−12) 2 + (𝑟3−16) 2 x1(0.5) X3(7) X2(3) X5(12) X4(16) 𝑟2= 0.5+7+3+12 4 =5.62 𝑟3=16 𝑒𝑟𝑟𝑜𝑟:75.68

MIN v V=1.5 error :97 V=3.5 error :109.7917 V=4 error :29.5 x1[1](1) g1(0.5)) x3[1](2) g3(7)) x2[1](3) g2(3)) x5(5) g5(12)) x4[1](6) g4(16)) r2 r3 V=1.5 error :97 V=3.5 error :109.7917 V=4 error :29.5 V=5.5 error :75.68

Min V F1<=4 3.5 14

Min V 计算复杂度 N个样本，一共有n个可选的分裂点 对于一个分列V,求error n次运算 复杂度 O(N^2) ?

Min v 𝑚𝑖𝑛 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 𝑚𝑖𝑛 𝑥 𝑖 𝜖𝑅2 (𝑟2− 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 (𝑟3− 𝑔 𝑖 ) 2 =𝑚𝑖𝑛 𝑥 𝑖 𝜖𝑅2 ( 𝑎𝑣𝑒 𝑅2 − 𝑔 𝑖 ) 2 + 𝑥 𝑖 𝜖𝑅3 ( 𝑎𝑣𝑒 𝑅3 − 𝑔 𝑖 ) 2 =𝑚𝑖𝑛 𝑥 𝑖 𝜖𝑅2 𝑔 𝑖 2 − 𝑐𝑜𝑢𝑛𝑡 𝑅2 ∗ 𝑎𝑣𝑒 𝑅2 2 + 𝑥 𝑖 𝜖𝑅3 𝑔 𝑖 2 − 𝑐𝑜𝑢𝑛𝑡 𝑅3 ∗ 𝑎𝑣𝑒 𝑅3 2 =𝑚𝑖𝑛 𝑥 𝑖 𝜖𝑅1 𝑔 𝑖 2 − 𝑠𝑢𝑚 𝑅2 2 𝑐𝑜𝑢𝑛𝑡 𝑅2 − 𝑠𝑢𝑚 𝑅3 2 𝑐𝑜𝑢𝑛𝑡 𝑅3 constant =𝑚𝑖𝑛− 𝑠𝑢𝑚 𝑅2 2 𝑐𝑜𝑢𝑛𝑡 𝑅2 − 𝑠𝑢𝑚 𝑅3 2 𝑐𝑜𝑢𝑛𝑡 𝑅3 =𝑚𝑎𝑥 𝑠𝑢𝑚 𝑅2 2 𝑐𝑜𝑢𝑛𝑡 𝑅2 + 𝑠𝑢𝑚 𝑅3 2 𝑐𝑜𝑢𝑛𝑡 𝑅3

MIN v O(N) ALL_SUM=0.5+7+3+12+16=38.5 ALL_COUNT=5 x1[1](1) g1(0.5)) R2_SUM=0.5 R2_COUNT=1 R2_SUM=7.5 R2_COUNT=2 R2_SUM=10.5 R2_COUNT=3 R2_SUM=22.5 R2_COUNT=4 R3_SUM=38 R3_COUNT=4 R3_SUM=31.5 R3_COUNT=3 R3_SUM=28.5 R3_COUNT=2 R3_SUM=16 R3_COUNT=1 0.5^2/1+38^2/4=361.25 7.5^2/2+31.5^2/3=358.5 10.5^2/3+28.5^2/2=442.875 22.5^2/4+16^2/1=382.5625 O(N) V=4

Create Tree 输入 { 𝑥 𝑖 , 𝑔 𝑖 } 𝑖=1..𝑛 Step1.将所有样本放入root结点（R1），标记为可分结点 Step2.对于一个可分的结点，寻找一个最优的分裂点(fid,value),分裂结点，并将该结点标记为不可分，同时将新生成的子结点标记为可分结点。 Step3.重复step2，直至无可分结点或者叶子结点数达到域值终止。

大纲 GBDT算法介绍 GBDT实现原理 GBDT并行原理 应用

GBDT并行原理 Label Feature l Feature 2 Feature 3 Label g Work 1 Work 2

Split X1 X2 X3 X4 X5 x6 x1 x2 x3 x4 x5 x6 Fea,v R1 R1 R1 R1 R1 R1 R1 Node table Update R2 R3 R2 R3 R3 R2 R2 R3 X1 X4 X5 X2 X3 X6

Update Label Feature l Feature 2 Feature 3 Label g Node table Work 1

数据并行 Feature l Feature 2 Feature 3 Label g Node table Work 1 Work 2

Feature l Feature 2 Feature 3 图例 Label Fea Work 1 Work 2 Work 3 g Node table Work 4 Work 5 Work 6 Work 7 Work 8 Work 9

图例 Feature l Label v1 L_sum L_count R_sum R_count L_sum*L_sum/L_count+R_sum*R_sum/R_count Fea Work 1 v2 L_sum L_count R_sum R_count g L_sum*L_sum/L_count+R_sum*R_sum/R_count Node table v3 L_sum L_count R_sum R_count Work 4 L_sum*L_sum/L_count+R_sum*R_sum/R_count v4 L_sum L_count R_sum R_count L_sum*L_sum/L_count+R_sum*R_sum/R_count Work 7

Feature l v1 v2 v3 v4 图例 Local left sum Local left count Label Local right sum Local right count Fea Work 1 Local left sum Local left count g Local right sum Local right count Node table Work 4 Local left sum Local left count Local right sum Local right count Work 7 ALL_Reduce SUM global left sum global left count global right sum global right count

Feature l v1 v2 v3 v4 图例 Local left sum Local left count Label Fea Work 1 Local left sum Local left count g Node table Work 4 Local left sum Local left count Work 7 ALL_Reduce SUM global left sum global left count

split value list 样本 Split value list Split value list

通信时间 特征个数 fea_count, 数据并行度 K组， 总work数 fea_count * K Min V : Reduce local sum and weight N𝑢𝑚_𝑠𝑝𝑙𝑖𝑡𝑠∗2∗4∗ 𝑙𝑜𝑔 2 𝐾≈8𝑘𝑏∗ 𝑙𝑜𝑔 2 𝐾 Min Feature 2∗4∗ 𝑙𝑜𝑔 2 (𝑓𝑒 𝑎 𝑐𝑜𝑢𝑛𝑡 ∗𝐾) 𝑏𝑦𝑡𝑒 Node table 𝑁 8∗𝐾 byte

性能测试 数据量1亿2千万数据，特征150 单棵树叶子结点32 500棵树 数据并发度K 平均计算梯度时间 平均建树时间 总时间 加速比 1 单棵树叶子结点32 500棵树 数据并发度K 平均计算梯度时间 平均建树时间 总时间 加速比 1 15 sec 114.7 sec 18.01h 2 8 sec 60.3 sec 9.48 h 1.89 4 4 sec 32.2 sec 5.02h 3.58 8 2 sec 17.2 2.66h 6.75 16 1 sec 11.2 1.69h 10.63

大纲 GBDT算法介绍 GBDT实现原理 GBDT并行实现 应用

推荐场景 协同过滤 LR点击率预测

Ranking- pairwise optimization Click >> non click Cart & buy >> click

Multi-obojective Click & price Price high >> price low

结果 收藏夹-猜你喜欢 点击率、转化率、客单价、引导成交的全 面提升 手淘试用品推荐 点击率显著提升 已买到宝贝-猜你喜欢

集团内业务应用 共享平台、搜索、B2B、蚂蚁金服、阿里妈 妈、CDO、天猫、OS、iDST、淘宝技术 部、菜鸟、国际事业部等十几个BU的重要业 务应用

算法开放&集团外部应用 御膳房算法平台 http://pai.yushanfang.com

Q & A Thank you