XGBoost 算法及工具

GBT 及 XGB 算法介绍
XGBoost 工具及分布式应用的探讨

GBT

GBT 其实就是多个弱分类器的集合：

`hat y_i^k = sum_(j=1)^k f_j(x_i) = hat y_i^(k-1) + f_k(x_i), quad f_j in mathcal F `¹

其中$\mathcal{F}$ 作为一个函数空间，为学到的所有函数的集合。而k 为迭代次数，也就是树的个数。

则第k 次迭代后目标函数值：

`Obj^k = sum l(y_i, hat y_i^k) +sum_(j=1)^k Omega(f_j) `

`\ \ = sum l(y_i, hat y_i^(k-1) + f_k(x_i)) + Omega(f_k) + C `

$y_i$ 和 $\hat y_i$ 为某个数据点的y 值和target 值，$l$ 为loss function 比如square loss

`Obj^k = sum (y_i-( hat y_i^(k-1) + f_k(x_i)))^2 + Omega(f_k) + C ` `\ \ = sum [2(hat y_i^(k-1) - y_i)f_k(x_i) + (f_k(x_i))^2] + Omega(f_k) + C^’ ` XGB Loss

而` sum_(j=1)^k Omega(f_j) ` 和 $\Omega(f_k)$ 为Regularization Term，用于表示树的复杂度（比如深度、节点数、L2）

一般GBT 使用梯度下降方式就是将loss function 的梯度（也就是一阶导数 ` g_(y_i) = l^1( hat y_i^k) ` 绝对值趋近于0 的方向行进，从而得到极值。但一般GBT 还没有RT。

那么GBT 中我们要最小化目标函数，那么每新的一轮迭代更新y 值后就应该更靠近极值点，假设`y_i^(k)` 相形于 `y_i^(k-1)` 更靠近极值点，则，

`y_i^(k) = y_i^(k-1) - rho g_(y_i)`

接下来找新的一棵树$T_k$，拟合使得 `sum_(i=1)^N(-g_(y_i) - T_k(x_i))^2` 最小；得到 `f_k= rho T_k ~= - rho g_(y)`

XGB Loss Function

而XGB 中，如果我们使用泰勒展开loss function，有

` l(y+ Delta y) = sum_(n=0)^( oo ) (l^((n))(y))/(n!) (Delta y)^n ~= l(y) + l^1(y) Delta y + 1/2 l^2 (y) Delta y ^2 `

在第k-1轮迭代后，设 ` Delta y = f_k(x_i) ` ，而针对 $l(y)$，一阶导数、二阶导数分别为：

`g_i = l_(hat y_i^(k-1))^1(y_i,hat y_i^(k-1))`

`h_i = l_(hat y_i^(k-1))^(2)(y_i,hat y_i^(k-1))`

那么第k 轮时候的迭代目标函数为：

` Obj^k ~= sum (l(y_i,hat y_i^(k-1))+ g_i f_k(x_i) + 1/2 h_i f_k(x_i)^2) + Omega(f_k) + C `

那么目标函数就只依赖loss function 的一阶导数、二阶导数（复杂度相形于除square loss 外的loss function 更低）。

而在第k 轮时，去掉优化时的常数项，目标函数改写为： `Obj^k ~= sum (g_i f_k(x_i) + 1/2 h_i f_k(x_i)^2) + Omega(f_k)` SL

其实我们也不难发现，这个目标函数，把square loss 的一阶、二阶导数代入后，跟square loss 的目标函数结果是一致的。

XGB Regularization Term

此项用来限制树的复杂度，比如使用叶子数量V 和 L2 进行定义：

` Omega(f_k) = gamma V + 1/2 lamda sum_(j=1)^V(w_j^2) `

对于树的学习结果，其中$w_j$ 为每个叶子节点的score 值。$\vec w$ 代表所有的叶子节点score 值的向量，设 q 函数将$x_i$ 映射到叶子节点j: $q(x_i)=j$，

叶子节点集合设为 `I_j = {i | q(x_i)=j}` 则 `f_k(x_i) = w_(q(x_i))`

将RT 及上式代入目标函数：

`Obj^k ~= sum_(i=1)^n (g_i w_(q(x_i)) + 1/2 h_i w_(q(x_i))^2) + gamma V + 1/2 lamda sum_(j=1)^V(w_j^2)`

`\ \ = sum_(j=1)^V [w_j sum_(i in I_j) g_i + 1/2 w_j^2 ( lamda +sum_(i in I_j) h_i) ] + gamma V`

再设定：

`G_j = sum_{i in I_j} g_i , H_j = sum_{i in I_j} h_i`

其实他们就分别代表：划分到某个叶子j 上的样本点的$l(y_i)$ ，对应的一阶、二阶导数值之和。

`Obj^k ~= sum_(j=1)^V [w_j G_j + 1/2 w_j^2 ( lamda + H_j) ] + gamma V`

故而，这个关于$w_j$ 的一元二次式，当

`w_j = w_j^** = -b/(2a) = - G_j / (lamda + H_j)`

`Obj_(min) = (4ac-b^2)/(4a) = gamma V - sum_(j=1)^V G_j^2/(2(lamda + H_j)) `

XGB Find Best Split

建立树结构时，就是每每通过找某个叶子节点(V 为1)的最佳分裂点。而增益：

` Gai\n = Obj^(parent) - Obj^(l\eft) - Obj^(right) `

` \ \ = - gamma - G_p^2/(2(lamda + H_p)) + G_L^2/(2(lamda + H_L)) + G_R^2/(2(lamda + H_R)) `

` \ \ = - gamma - (G_L+G_R)^2/(2(lamda + (H_L+H_R))) + G_L^2/(2(lamda + H_L)) + G_R^2/(2(lamda + H_R)) `

每次分裂，找到增益最大的分裂点。而叶子节点的Score 值就是对应的 `w_j = w_j^** = -b/(2a) = - G_j / (lamda + H_j)`

有两种方式找到最佳的树的深度：

Gain 为非正数时即刻停止分裂
一直分裂到最底端，然后自底向上剪枝剪去Gain 为非正数枝叶

XGB 优势

添加复杂度控制和后期剪枝防止过拟合；
对于loss function 具有通用性，只需求一阶二阶导数；
知道每个样本分到哪片叶子上，可提高模型表现；²
可以使用线性模型代替树模型，从而得到L1+L2 的线性或逻辑回归。³

XGB 工具

应用：

Performance:

10x GBM in sklearn&R
Can run on YARN/MPI(using Rabit) and is faster than Spark

Tasks support:

Binary classification: tree booster, linear booster
Regression: negative log likelihood
Learning to Rank: pairwise rank, lambda rank

分布式应用

XGB 直接在YARN 上使用
集成进现有Spark 机器学习工具

References

Mathjax was not loaded successfully

http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf ↩
http://quinonero.net/Publications/predicting-clicks-facebook.pdf ↩
http://www.open-open.com/lib/view/open1425527689368.html ↩

Original post: http://blog.josephjctang.com/2015-06/xgb/

GBT and XGB

June 05, 2015