对xgboost的一些理解

xgboost

• 简介
  xgboost 的全称是eXtreme Gradient Boosting，由华盛顿大学的陈天奇博士提出，在Kaggle的希格斯子信号识别竞赛中使用，因其出众的效率与较高的预测准确度而引起了广泛的关注。

• 与GBDT的区别
  GBDT算法只利用了一阶的导数信息，xgboost对损失函数做了二阶的泰勒展开，并在目标函数之外加入了正则项对整体求最优解，用以权衡目标函数的下降和模型的复杂程度，避免过拟合。所以不考虑细节方面，两者最大的不同就是目标函数的定义，接下来就着重从xgboost的目标函数定义上来进行介绍。

• xgboost的模型

xgboost对应的模型就是一堆CART树。一堆树如何做预测呢？就是将每棵树的预测值加到一起作为最终的预测值，可谓简单粗暴。

下图就是CART树和一堆CART树的示例，用来判断一个人是否会喜欢计算机游戏：

 

第二图的底部说明了如何用一堆CART树做预测，就是简单将各个树的预测分数相加。

• 目标函数
  xgboost的目标函数定义如下：

  

  其中，t表示第t轮，表示第t轮所生成的树模型，表示正则项，。接下来是xgboost的重点，我们使用二阶泰勒展开

  

  来定义一个近似的目标函数如下：

  

  因为的值由之前的过程决定，所以本轮不变，constant也不影响本轮的训练，所以将这两者其去掉，得到：

  

  现在的目标函数有一个非常明显的特点，它只依赖于每个数据点在误差函数上的一阶导数和二阶导数。接下来，我们对的定义做一下细化，将树拆分成结构部分q和叶子权重部分w：

  

  当我们给定了如上定义之后，就可以对树的复杂度进行定义了：

  

  其中，第一部分中的T为叶子的个数，第二部分为w的L2模平方。我们来看下图的示例：

  

  
  可以看到叶子的权重w就是GBDT例子中叶子结点的值，而q就是将某个样本点映射到某个叶子结点的函数。有了上边的两个式子后，继续对目标函数进行如下改写：

  

  其中，为每个叶子节点上的样本集合。现在这个目标函数包含了T个相互独立的单变量二次函数，我们定义：

  

  那么我们就得到了最终的目标函数样子：

  

  现在我们假设q已知，通过将上式对w求导并令其等于0，就可以求出令最小的w：

  

  此时目标函数 的值为：

  

  
  剩下的工作就很简单了，通过改变树的结构来找到最小的，而对应的结构就是我们所需要的结果。不过枚举所有树的结构不太可行，所以常用的是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一次具体的分割，我们可以获得的增益可以由如下公式计算：

• 问题是：树的结构近乎无限多，一个一个去测算它们的好坏程度，然后再取最好的显然是不现实的。所以，我们仍然需要采取一点策略，这就是逐步学习出最佳的树结构。这与我们将K棵树的模型分解成一棵一棵树来学习是一个道理，只不过从一棵一棵树变成了一层一层节点而已。下面我们就来看一下具体的学习过程。
  我们以上文提到过的判断一个人是否喜欢计算机游戏为例子。最简单的树结构就是一个节点的树。我们可以算出这棵单节点的树的好坏程度obj*。假设我们现在想按照年龄将这棵单节点树进行分叉，我们需要知道：
  1、按照年龄分是否有效，也就是是否减少了obj的值
  2、如果可分，那么以哪个年龄值来分。

  为了回答上面两个问题，我们可以将这一家五口人按照年龄做个排序。如下图所示：

  

  按照这个图从左至右扫描，我们就可以找出所有的切分点。对每一个确定的切分点，我们衡量切分好坏的标准如下：

  

  这个Gain实际上就是单节点的obj*减去切分后的两个节点的树obj*，Gain如果是正的，并且值越大，表示切分后obj*越小于单节点的obj*，就越值得切分。同时，我们还可以观察到，Gain的左半部分如果小于右侧的γ，则Gain就是负的，表明切分后obj反而变大了。γ在这里实际上是一个临界值，它的值越大，表示我们对切分后obj下降幅度要求越严。这个值也是可以在xgboost中设定的。

  扫描结束后，我们就可以确定是否切分，如果切分，对切分出来的两个节点，递归地调用这个切分过程，我们就能获得一个相对较好的树结构。

  注意：xgboost的切分操作和普通的决策树切分过程是不一样的。普通的决策树在切分的时候并不考虑树的复杂度，而依赖后续的剪枝操作来控制。xgboost在切分的时候就已经考虑了树的复杂度，就是那个γ参数。所以，它不需要进行单独的剪枝操作。

  
  观察xgboost的目标函数会发现如下三点：
  • 这个公式形式上跟ID3算法（采用entropy计算增益） 、CART算法（采用gini指数计算增益） 是一致的，都是用分裂后的某种值减去分裂前的某种值，从而得到增益
  • 引入分割不一定会使情况变好，因为最后有一个新叶子的惩罚项。所以这也体现了预减枝的思想，即当引入的分割所带来的增益小于一个阈值时，就剪掉这个分割
  • 上式中还有一个系数λλ，是正则项里ww的L2模平方的系数，对ww做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性

• 总结
  xgboost与传统的GBDT相比，对代价函数进行了二阶泰勒展开，同时用到了一阶与二阶导数，而GBDT在优化时只用到一阶导数的信息，个人认为类似牛顿法与梯度下降的区别。另一方面，xgboost在损失函数里加入的正则项可用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

xgboost的优化：

1. 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
2. xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍.
3. 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
4. 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。
5. xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

xgboost的优势：

1、正则化

• 标准GBM的实现没有像XGBoost这样的正则化步骤。正则化对减少过拟合也是有帮助的。 
  实际上，XGBoost以“正则化提升(regularized boosting)”技术而闻名。

2、并行处理

• XGBoost可以实现并行处理，相比GBM有了速度的飞跃，LightGBM也是微软最新推出的一个速度提升的算法。 XGBoost也支持Hadoop实现。

3、高度的灵活性

• XGBoost 允许用户定义自定义优化目标和评价标准 。

4、缺失值处理

• XGBoost内置处理缺失值的规则。用户需要提供一个和其它样本不同的值，然后把它作为一个参数传进去，以此来作为缺失值的取值。XGBoost在不同节点遇到缺失值时采用不同的处理方法，并且会学习未来遇到缺失值时的处理方法。

5、剪枝

• 当分裂时遇到一个负损失时，GBM会停止分裂。因此GBM实际上是一个贪心算法。XGBoost会一直分裂到指定的最大深度(max_depth)，然后回过头来剪枝。如果某个节点之后不再有正值，它会去除这个分裂。 
  这种做法的优点，当一个负损失（如-2）后面有个正损失（如+10）的时候，就显现出来了。GBM会在-2处停下来，因为它遇到了一个负值。但是XGBoost会继续分裂，然后发现这两个分裂综合起来会得到+8，因此会保留这两个分裂。

6、内置交叉验证

• XGBoost允许在每一轮boosting迭代中使用交叉验证。因此，可以方便地获得最优boosting迭代次数。 
  而GBM使用网格搜索，只能检测有限个值。

7、在已有的模型基础上继续

• XGBoost可以在上一轮的结果上继续训练。 
  sklearn中的GBM的实现也有这个功能，两种算法在这一点上是一致的。

 

Reference

[1]http://www.cnblogs.com/willnote/p/6801496.html

[2]https://www.jianshu.com/p/7467e616f227

[3]https://blog.csdn.net/jasonzhangoo/article/details/73061060