集成学习之XGBoost——算法优化
前言之前总结过梯度提升树GBDT，提到了XGBoost (eXtreme Gradient Boosting)、LightGBM(Light Gradient Boosting Machine)等“大杀器”。这一篇先来讲讲XGBoost。
XGBoost是陈天奇等人2016年提出并开发的一个开源机器学习项目，高效地实现了GBDT算法，同时加入了很多独有的思路和方法。
算法的优化：在算法的弱学习器选择上，GBDT只支持决策树，XGBoost还可以直接很多其他的弱学习器。在算法的损失函数上，除了本身的损失，XGBoost还加上了正则化部分（L1、L2）。在算法的优化方式上，GBDT的损失函数只对误差函数做负梯度（一阶泰勒）展开，而XGBoost对误差函数做二阶泰勒展开。本篇将重点放在算法的优化和改进上。
<hr/>XGBoost损失函数
首先，XGBoost在损失函数中加入了两个正则化项： \gamma J + \frac{\lambda}2 \sum_{j=1}^J \omega^2_{tj} . 其中前一项衡量决策树的子节点个数， J 等于叶子节点的个数；后一项衡量各个叶子节点取值大小。
L_t=\sum_{i=1}^m L(y_i,f_{t1}(x_i)+T_t(x_i))+\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj}
另外，GBDT中求损失函数的负梯度，相当于对损失函数作一阶泰勒展开。XGBoost对损失函数作二阶泰勒展开：
\begin{eqnarray} L_t &=& \sum_{i=1}^m L(y_i,f_{t1}(x_i)+T_t(x_i))+\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj} \\ &\approx& \sum_{i=1}^m L(y_i,f_{t1}(x_i)) + g_{ti}T_t(x_i)+\frac{1}2 h_{ti}T_t^2(x_i)+\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj} \end{eqnarray}
其中 g_{ti}=\frac{L(y_i,f_{t1}(x_i)}{f_{t1}(x_i)} , h_{ti}=\frac{^2 L(y_i,f_{t1}(x_i)}{f^2_{t1}(x_i)} 分别为损失函数对 f_{t-1} 的一阶和二阶导数。
损失函数里面 L(y_i,f_{t1}(x_i)) 是常数，可以去掉；同时由于每个决策树的第 j 个叶子节点的取值最终会是同一个值 \omega_{tj} ，因此损失函数可以继续化简：
\begin{eqnarray} L_t &\approx& g_{ti}T_t(x_i)+\frac{1}2 h_{ti}T_t^2(x_i) +\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj} \\ &=& \sum_{j=1}^J (\sum_{x_i \in R_{tj}} g_{ti}\omega_{tj} +\frac{1}2 \sum_{x_i \in R_{tj}}h_{ti}\omega^2_{tj})+\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj} \\ &=& \sum_{j=1}^J (G_{tj} \omega_{tj} +\frac{1}2 H_{tj} \omega^2_{tj})+\gamma J + \frac{\lambda}2 \sum_{j=1}^J w^2_{tj}\end{eqnarray}
其中 G_{tj}=\sum_{x_i\in R_{tj}} g_{ti}, H_{tj}=\sum_{x_i\in R_{tj}} h_{ti}
最终损失函数的形式变成：
L_t = \sum_{j=1}^J +\gamma J
<hr/>损失函数的优化
假设决策树的结构已经确定，即 J 个叶子节点的区域划分已经确定，那么 J 、 G_{tj} 、 H_{tj} 是定值。我们该如何选择每个叶子节点的取值 \omega_{tj} ，使得损失函数最小？从上面的公式看出，这实际上是一个简单的一元二次方程的优化问题，只需要取 \omega_{tj}^{\star}=\frac{G_{tj}} {H_{tj}+\lambda} . 此时损失函数最小，等于 L_t=\frac{1}2 \sum_{j=1}^J \frac{G^2_{tj}} {H_{tj}+\lambda}+\gamma J
剩下的问题是，如何选择特征和相应的特征值进行分裂，使损失函数 L_t 最小？
在GBDT里面，我们直接拟合CART回归树，所以树节点分裂使用的是均方误差。XGBoost使用贪心法，即每次分裂都期望最小化我们的损失函数的误差。具体来说：
我们的目标是最大化上图中的Gain，其中 G_L,H_L, G_R,H_L 分别为当前节点左右子树的一阶、二阶导数。背后的逻辑是，在每次左右子树分裂时，我们都尽可能地最大化损失函数的“损失”。
我们已经确定好了分裂左右子树的特征，接下来的问题是，对于该特征，如何选择最好的特征值进行分裂？
XGBoost选择对该特征的所有取值进行线性扫描，每个取值对应一种分裂方式，也就对应一个Gain，选择使得Gain最大的那个特征值。
总之，在分裂子树和选择叶子节点的取值时，普通CART回归树用方差作为评价度量；
GBDT构建CART回归树时，用方差作为评价度量；只在选择叶子节点的取值时，根据损失函数选择最优的取值。
而XGBoost用的是已选定的损失函数作为度量。
除了评价度量不同，三者的分裂子树思路是一样的。<hr/>XGBoost算法流程
输入是训练集样本 I=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\} ，最大迭代次数 T , 损失函数 L ，正则化系数 \lambda, \gamma
输出是强学习器 f(x)
对迭代轮数 t=1,2,...T 有：
1）对于第 i 个样本 (i=1,2,..m) 计算 g_{ti}=\frac{L(y_i,f_{t1}(x_i)}{f_{t1}(x_i)} ， h_{ti}=\frac{^2 L(y_i,f_{t1}(x_i)}{f^2_{t1}(x_i)}
2）基于当前节点尝试分裂决策树，默认分数score=0， G 和 H 分别为当前节点的一阶、二阶导数之和。
对特征序号 k=1,2...K ：
a) G_L=0,H_L=0
b.i) 将样本按特征 k 的特征值从小到大排列，依次取出第 j 个特征值对应的样本，计算当前样本放入左子树后左右子树的一阶、二阶导数和：
G_L=G_L+g_{ti}, G_R=GG_L \\ H_L=H_L+h_{ti},H_R=HH_L
b.ii) 尝试更新最大的分数：
score=max(score,\frac{1}2 [\frac{G^2_L}{H_L+\lambda}+\frac{G^2_R}{H_R+\lambda}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]\gamma)
3) 基于最大score对应的划分特征和特征值分裂子树。
4) 如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的 w_{tj} , 得到弱学习器 T_t ，更新强学习器 f_t(x) = f_{t-1}(x) + \epsilon T_t(x) ，其中 \epsilon为步长，常取值为0.1，接着进入下一轮弱学习器迭代。如果最大score不是0，则转到第2)步继续尝试分裂决策树。
Remarks
2)b) 中对于每个特征，将样本按照特征值从小到大排列，依次将样本放入左子树，只需在梯度特征 G_L 累加上 g_{ti}即可。原文中把这种遍历全部特征以及对应的全部特征值的方法叫做Exact Greedy Algorithm.
It is computationally demanding to enumerate all the possible splits for continuous features. In order to do so efficiently, the algorithm must first sort the data according to feature values and visit the data in sorted order to accumulate the gradient statistics for the structure score.<hr/>小结
除了算法上的改进，XGBoost还在算法运行效率上做了优化（如特征粒度的并行计算、缓存优化等），并且通过对特征的缺失值的处理，使得算法整体上更为健壮。
XGBoost是Kaggle比赛中经常见到的算法，它将GBDT的优化走向了一个极致。后来微软出了LightGBM，在内存占用和运行速度上又做了不少优化，但是从算法本身来说，优化点则并没有XGBoost多。
何时使用XGBoost，何时使用LightGBM呢？可以优先选择XGBoost。但如果使用XGBoost遇到内存占用或者运行速度问题，那么可以尝试LightGBM陈天奇不仅提出了XGBoost算法，还开发了XGBoost库，不仅支持Python，还支持R, Java等语言。使用方法可以参考XGBoost类库使用小结 - 刘建平Pinard - 博客园或者官方文档 gboost docs
<hr/>References
XGBoost算法原理小结 - 刘建平Pinard - 博客园
XGBoost: A Scalable Tree Boosting System
陈天奇的PPT
XGBoost类库使用小结 - 刘建平Pinard - 博客园
页:
[1]