Xgboost - A scalable tree boosting system Chiang

XGBoost（eXtreme Gradient Boosting）其核心是对决策树（Decision Tree）的增强（Boosting）方法，属于集成学习（Ensemble Learning）。

集成算法思想

在决策树中，我们知道一个样本往左边分或者往右边分，最终到达叶子结点，这样来进行一个分类任务。其实也可以做回归任务。

看上面一个图例左边：有5个样本，现在想看下这5个人愿不愿意去玩游戏，这5个人现在都分到了叶子结点里面，对不同的叶子结点分配不同的权重项，正数代表这个人愿意去玩游戏，负数代表这个人不愿意去玩游戏。所以我们可以通过叶子结点和权值的结合，来综合的评判当前这个人到底是愿意还是不愿意去玩游戏。上面「tree1」那个小男孩它所处的叶子结点的权值是+2（可以理解为得分）。

用单个决策树好像效果一般来说不是太好，或者说可能会太绝对。通常我们会用一种集成的方法，就是一棵树效果可能不太好，用两棵树呢？

看图例右边的「tree2」，它和左边的不同在于它使用了另外的指标，出了年龄和性别，还可以考虑使用电脑频率这个划分属性。通过这两棵树共同帮我们决策当前这个人愿不愿意玩游戏，小男孩在「tree1」的权值是+2，在「tree2」的权值是+0.9， 所以小男孩最终的权值是+2.9（可以理解为得分是+2.9）。老爷爷最终的权值也是通过一样的过程得到的。

所以说，我们通常在做分类或者回归任务的时候，需要想一想一旦选择用一个分类器可能表达效果并不是很好，那么就要考虑用这样一个集成的思想。上面的图例只是举了两个分类器，其实还可以有更多更复杂的弱分类器，一起组合成一个强分类器。

XGBoost原理

1、学习目标

在讨论学习目标之前，先说一说XGBoost是如何预测输出值的。XGBoost是一个树集成模型，它使用的是K（树的总数为K）个树的每棵树对样本的预测值的和作为该样本在XGBoost系统中的预测，定义函数如下：

对于所给的数据集有n个样本，m个特征，定义为：

其中Xi表示第i个样本，yi表示第i个样本的类别标签。CART树的空间为F，如下：

其中q表示每棵树的结构映射每个样本到相应的叶节点的分数，即q表示树的模型，输入一个样本，根据模型将样本映射到叶节点输出预测的分数；Wq(x)表示树q的所有叶节点的分数组成集合；T是树q的叶节点数量。

其实，XGBoost的集成表示是什么？怎么预测？求最优解的目标是什么？看下图的说明你就能一目了然。

在XGBoost里，每棵树是一个一个往里面加的，每加一个都是希望效果能够提升，下图就是XGBoost这个集成的表示（核心）。

一开始树是0，然后往里面加树，相当于多了一个函数，再加第二棵树，相当于又多了一个函数...等等，这里需要保证加入新的函数能够提升整体对表达效果。提升表达效果的意思就是说加上新的树之后，目标函数（就是损失）的值会下降。

如果叶子结点的个数太多，那么过拟合的风险会越大，所以这里要限制叶子结点的个数，所以在原来目标函数里要加上一个惩罚项「omega(ft)」。

由于XGBoost模型中的优化参数是模型f(x)，不是一个具体的值，所以不能用传统的优化方法在欧式空间中进行优化，而是采用additive training的方式去学习模型。每一次保留原来的模型不变，加入一个新的函数f到模型中。

预测值在每一次迭代中加入一个新的函数f目的是使目标函数尽量最大地降低。 因为我们的目标是最小化L(φ)时得到模型f(x)，但是L(φ)中并没有参数f(x)，所以，我们将上图中的最后一式代入L(φ)中可得到如下式子：

对于平方误差（用于回归）来说（3）式转换成如下形式：

对于不是平方误差的情况下，一般会采用泰勒展开式来定义一个近似的目标函数，以方便我们的进一步计算。 根据如下的泰勒展开式，移除高阶无穷小项，得：

L(φ)等价于下面的式子：

由于我们的目标是求L(φ)最小化时的模型f(x)（也是变量），当移除常数项时模型的最小值变化，但是取最小值的变量不变（比如：y=x^2+C，无论C去何值，x都在0处取最小值）。所以，为了简化计算，我们移除常数项，得到如下的目标函数：

将关于树模型的迭代转换为关于树的叶子节点的迭代，得到如下过程：

此时我们的目标是求每棵树的叶节点j的分数Wj，求出Wj后，将每棵树的Wj相加，即可得到最终的预测的分数。而要想得到最优的Wj的值，即最小化我们的目标函数，所以上式对Wj求偏导，并令偏导数为0，算出此时的W*j为：

将W*j代入原式得：

上面的方程可以用作得分(score)函数来测量树结构q的质量。该得分类似于评估决策树的不纯度得分，除了它是针对更广泛的目标函数得出的。下图表示得分(score)是如何被计算的：

由上图可以看出，当我们指定一颗树的结构的时候，每棵树的得分(score)只与损失函数的一阶导数和二阶倒数相关（γ和λ是在实际应用中需要自己调参的），而该得分表示我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)。你可以认为这个就是类似吉尼系数一样更加一般的对于树结构进行打分的函数。

到这里，我们的XGBoost学习目标的原理已经介绍完毕，接下来就是如何进行节点的切分了。

分割点查找（split Finding）

为了找到特征的最优切分点，需要遍历特征所有的取值，并得到所有可能的切分点。然后带入目标函数进行计算，并将最优的目标函数值对应的切分点，作为特征的切分点。但是由于回归问题中，特征是连续的存在很多候选切分点，所以找到最优切分点需要耗费大量的时间和内存。

• 基本精确的贪心算法（Basic Exact Greedy Algorithm）

为了找到节点最好的划分，该算法的原理是在所有特征上枚举所有的可能的划分，我们称这个算法为Basic Exact Greedy Algorithm。大多数已存在的单台机器上的树提升算法库都是用这种方法实现的，例如scikit-learn，R’s gbm 以及 XGBoost的单机版本都支持这种算法。该算法要求为连续特征枚举所有可能的切分，这对计算机的要求很高，所以该算法为了有效的做到这一点，首先根据特征值排序数据并且按照顺序访问数据，以累积下面方程中结构分数的梯度统计量。

该算法如下：

• 近似算法

Basic Exact Greedy Algorithm是一个非常精确的算法，因为它枚举的所有可能的切分点。但是，当数据不能完全的加载到内存时，它可能不是特别有效地。同样的问题也出现在分布式的设置中。为了有效的支持在这两种设置中的有效的梯度提升，一个近似算法需要被使用。该算法首先根据特征分布的百分位数提出n个候选切分节点，然后，算法将位于相邻分位点之间的样本分在一个桶中，在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。注意到上面算法流程中表明有全局的近似(global)和局部(local)的近似，所谓全局就是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部就是在具体的某一次分裂节点的过程中采用近似算法。该算法如下所示：

XGBoost优缺点

• 与GBDT相比：
• GBDT以传统CART作为基分类器，而XGBoost支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；
• GBDT在优化时只用到一阶导数，XGBoost对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数。XGBoost支持自定义的损失函数，只要是能满足二阶连续可导的函数均可以作为损失函数；
• XGBoost在损失函数中引入正则化项，用于控制模型的复杂度。正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从Bias-variance tradeoff角度考虑，正则项降低了模型的方差，防止模型过拟合，这也是xgboost优于传统GBDT的一个特性；
• 当样本存在缺失值是，xgBoosting能自动学习分裂方向，即XGBoost对样本缺失值不敏感；
• XGBoost借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算，这也是xgboost异于传统gbdt的一个特性；
• XGBoost在每次迭代之后，会将叶子节点的权重乘上一个学习率（相当于XGBoost中的eta，论文中的Shrinkage），主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点；
• XGBoost工具支持并行，但并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值），XGBoost的并行是在特征粒度上的。XGBoost在训练之前，预先对数据进行了排序，然后保存为(block)结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个块结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行；
• 可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；
• XGBoost的原生语言为C/C++，这是也是它训练速度快的一个原因。
• 与LightGBM相比
• XGBoost采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低，但是不能找到最精确的数据分割点；
• XGBoost采用level-wise生成决策树策略，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行更进一步的分裂，这就带来了不必要的开销；LightGBM采用leaf-wise生长策略，每次从当前叶子中选择增益最大的叶子进行分裂，如此循环，但会生长出更深的决策树，产生过拟合，因此 LightGBM 在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合）。另一个比较巧妙的优化是 histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。

END