一文道尽XGBOOST的前世今生

[aialgorithm]

XGBOOST 简介

XGBOOST：简单来说是集成了很多个基学习器（如Cart决策树）的模型。它是集成学习的串行方式（boosting）的一种经典实现，是广泛应用在工业、竞赛上的一大神器。

集成学习是结合一些的基学习器来改进其泛化能力和鲁棒性的方法，主流的有两种集成思想：

1. 并行方式（bagging）：独立的训练一些基学习器，然后（加权）平均它们的预测结果。如：Random Forests；
2. 串行方式（boosting）：一个接一个的(串行)训练基学习器，每一个基学习器主要用来修正前面学习器的偏差。如：AdaBoost、GBDT及XGBOOST；
   （注：此外还有stacking方法，但stacking更多被看做是融合的策略；）

一、基学习器--决策树

决策树有非线性、拟合能力强且可以通过剪枝快速调整的特性，集成学习通常选择决策树作为基学习器。
（注：XGBOOST中的基学习器可以是CART回归树-gbtree, 也可以是线性分类器-gblinear。本文着重从树模型介绍。）

决策树是一种简单的机器学习回归/分类方法，它是由(if-then)决策结构以树形组合起来，叶子节点代表最终的预测值或类别。典型的决策树模型有：ID3、C4.5和CART。
决策树算法可以概括为两个阶段：

• 树的生长：思想是自顶向下递归分治构建树，是依靠（信息增益、信息增益比、gini、平方误差）等某个指标做特征选择、划分的过程。
  

• 树的剪枝：决策树容易对数据产生过拟合，即生长出结构过于复杂的树模型。通过剪枝算法可以降低复杂度，减少过拟合的风险。
  决策树剪枝算法的根本目的是极小化损失函数（经验损失+结构损失），基本策略有”预剪枝“和”后剪枝“两种策略：
  ①预剪枝：是在决策树生成过程中，限制划分的最大深度、叶子节点数和最小样本数目等，以减少不必要的模型复杂度；
  ②后剪枝：是先从训练集生成一棵完整的决策树，然后用用验证集自底向上地对非叶结点进行考察，若将该节点对应的子树替换为叶子结点（剪枝）能带来决策树的泛化性能提升（即目标函数损失更小，常用目标函数如：loss = 模型经验损失bias+ 模型结构损失α|T|， T为节点数目, α为系数），则将该子树替换为叶子结点。

二、从Cart回归树到GBDT

CART回归树是二叉树结构的决策树，GBDT、XGBoost等梯度提升方法都使用了Cart回归树做基学习器。
树的生长是通过平方误差指标选择特征及切分点进行分裂。即遍历所有特征的的所有切分点，最小化目标函数，选择合适的树切分特征（j）及特征阈值（s）找到最优的切分特征和切分点，最终得到一棵回归树。

比如下图的树结点是基于特征（age）进行分裂的，设该特征值小于阈值（20）的样本划分为左子树，其他样本划分为右子树。

GBDT(梯度提升决策树) XGBOOST是在GBDT基础上提升了效率。说到Xgboost，都不得不先从GBDT(Gradient Boosting Decision Tree)说起，
GBDT串行学习原理简单来说分为三步：

1. 初始化，通过学习数据集拟合第一棵Cart回归树。如下图的这棵 Tree1学习去预测真实值y，最终模型预测输出y1；
2. 通过学习上一棵树的残差(残差就是预测值与真实值之间的误差，GBDT算法中的关键就是利用损失函数的负梯度作为残差的近似值）拟合下一棵Cart回归树，而后基学习器Cart树依次串行学习。如下图的这棵Tree2学习的是Tree1损失函数的负梯度数据(y-y1)；
3. 最终模型预测值就是将所有串行Cart回归树输出的预测结果相加。
   

三、XGBOOST（eXtreme Gradient Boosting）

XGBOOST 类似GBDT串行学习方式，学习到如下图tree1、tree2，预测是将tree1、tree2结果相加。

xgboost与gbdt对比主要的差异在于：

• 损失函数的加入了正则项Ω
  正则项对节点数目及叶子节点权重进行惩罚，减少模型的过拟合。损失函数如下图所示：

• 通过泰勒泰勒展开，树的生长是直接与损失函数挂钩
  xgboost使用二阶泰勒展开能够适用自定义的损失函数obj，利用泰勒展开三项做一个近似。
  

可以很清晰地看到，最终的目标函数只依赖于每个数据点在误差函数上的一阶导数gi和二阶导数hi。
对于这个目标函数obj求导等于0，可以得到一个叶子节点权重w*

代入obj得到了叶子结点取值的表达式

目标函数obj中的各部分，表示着每一个叶子节点对当前模型损失的贡献程度。融合一下，得到Gain的计算表达式，如下所示：

树的生长的过程，即是利用推导出的表达式作为分裂准则，对于所有的特征做一遍从左到右的扫描就可以枚举出所有分割取值点的梯度和GL和GR，然后用计算Gain的公式计算每个分割方案的分数并选择增益最大的分裂点，分裂结束后计算其对应的叶子结点值w*。

• 在特征粒度提升效率
  决策树的学习最耗时的一个步骤就是对特征的值进行排序以确定最佳分割点，XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构。且进行节点的分裂时，通过开多个线程实现对各特征划分点的增益的并行计算，大大提高了计算效率。

参考资料

XGBOOST 论文

XGBOOST PPT

关于作者