layout: post title: “GBT and XGB” modified: 2015-06-05 17:20:36 +0800 tags: [GBT] categories: [机器学习] prz_url: /slides/xgb/ comments: share:
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 工具
应用：
- Kaggle Tradeshift winning solution by daxiongshu 1st
- Kaggle Malware Prediction winning solution
- Winning solution of Kaggle Higgs competition: what a single model can do
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