Xgboost算法理解

上一篇文章讲述了general GBDT的模型原理，链接：https://www.jianshu.com/p/943fcb6d651a。本文讲述Xgboost的算法原理。
最好的教材是官网的tutorial。有一点不够general的是，tutorial的Loss函数假定为均方误差。本文主要突出Xgboost改进的地方。

模型目标函数

机器学习问题的本质是数据分布的模型拟合，用数学语言表达就是目标函数的最优化问题。跟GBDT类似，Xgboost对于给定数据集进行additive trainning，学习K棵树，得到下面的预测函数：

上述预测函数是如何得到的呢？我们需要分析目标函数，如下：

其中，第一项跟GBDT中是一样的，选定某个损失函数，计算预测值与真实值的偏差，第二项为正则项，传统的GBDT并没有，也是Xgboost改进的地方。我们知道决策树的一个缺点就是易过拟合，需要剪枝操作，这里的正则项起到类似的作用。
第t次迭代，目标函数具体写作：

然后，基于前t-1次的预测值yt-1处做二阶的泰勒展开：

而GBDT的这部分则是基于前t-1次的预测值yt-1处做一阶的泰勒展开，这也是Xgboost改进的地方，泰勒二阶近似比一阶近似更接近真实的Loss Fnction，自然优化的更彻底。
接下来分析正则项的形式，如下：

为什么是这样的形式，官网的说明是：
Of course there is more than one way to define the complexity, but this specific one works well in practice.
其中，T为叶子节点的数目，w为叶子节点的value向量。
对树函数f作如下变换：

将正则项的具体形式和变换后的树函数带入目标函数，如下：

统一i，j的求和，如下：

可以看出t轮的L函数是关于w的二次函数，求极值：

回归树的学习策略

上一节明确了Xgboost每棵树的拟合目标，但是如何拟合呢？如何确定树的结构呢？
先回顾下一般的树的分裂的方法？

Xgboost的打分函数：

Xgboost的分裂规则：

还有一个问题，那每棵树的非叶子节点的最佳分割点怎么找？

解释下，近似于基于hi的直方图分割，看成一种近似的分割。我的理解跟特征的离散化很像。传统的暴力搜索十分耗时。

与GBDT的其他不同

• Shrinkage（缩减）
  xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。
• 列抽样
  这一点借鉴的是随机森林，就是对特征属性抽样。行采样是对样本的数目采样。
• 支持并行计算
  首先明确一点的是，并行的方式不是树同时训练，而是在训练每棵树时的分裂过程。排序数据是树学习最耗时的方面。 为了减少分类成本，数据存储在称为“块”的内存单元中。 每个块都有按相应特征值排序的数据列。 这种计算只需要在训练前完成一次，以后可以重复使用。块的排序可以独立完成，并可以在CPU的并行线程之间分配。 由于每列的统计数据收集是并行完成的，所以可以并行分割查找。

• 缺失值处理

  
  
  

  缺失值是实际的机器学习项目中不容忽视的问题。自带的工具包帮你解决不是好事，因为默认的处理方式不一定符合你的场景。Xgboost的处理方式是，缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那个。如果训练中没有数据缺失，预测时出现了数据缺失，默认分类到右子树。