GBT and XGB

Reading time ~12 minutes

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 `1

其中$\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

还有logistic loss: $l(y_i,\hat y_i) = y_i \ln(1 + e^{-\hat y_i}) + (1-y_i) \ln(1+e^{\hat y_i})$

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

C 为常数,代表k 轮之前的树的复杂度之和; 因为k 轮迭代之前的Regulation Term,在第k 轮迭代时为常数了。 第k 轮时,就 $f_k$ 是一个变量,也就是需要来学习并最小化目标函数的。 而此目标函数,复杂度就依赖于loss function 的复杂度。

一般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)`

其中$\rho$ 为步长。通过square loss 这个二元凸函数`z=l(y)=(y-f)^2`看。离中轴线(极值点,也是一阶导数为0 的地方)越远的y值,梯度越大,那么就应该更快地靠近极值点;离极值点越近的y 值,梯度越小,也就应该更慢的靠近极值点,以防越过极值点。那么上面式子,y 值靠近极值点的步伐(`- 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)`

而进一步的看,因为有`-ab>= -(a+b)^2 /2 `

则`l(y_i^(k)) = l(y_i^(k-1)) - Delta y_i g_(y_i) = l(y_i^(k-1) + f_k(x_i)) >= l(y_i^(k-1)) - (Delta y_i + g_(y_i))^2/2` 那么loss function 收敛的时候,`Delta y + g_(y_i)\ = 0`,即 ` Delta y_i = f_k(x_i) = - g_(y_i)` 这样梯度下降方式就更加直观了。

其他GBT 知识可参见:

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 具有通用性,只需求一阶二阶导数;
  • 知道每个样本分到哪片叶子上,可提高模型表现;2
  • 可以使用线性模型代替树模型,从而得到L1+L2 的线性或逻辑回归。3

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

  1. http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf 

  2. http://quinonero.net/Publications/predicting-clicks-facebook.pdf 

  3. http://www.open-open.com/lib/view/open1425527689368.html 

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

2016 記

2015 年做的和沒做的,也大體記錄在了[這裏]({% post_url 2016-01-01-annual-review-and-planning %})。匆匆一年已逝,幾多慨嘆,幾多欣喜。後面列列過去已經做的,以及相對的未來一年的TODO list。主要也是從工作上的個人提升,以及生活上的...… Continue reading

《神经网络》课程笔记

Published on November 06, 2016

搜索广告机制设计

Published on November 02, 2016