Xgboost原理及推导

Xgboost无论是工业界还是kaggle比赛效果都很好，学习过程中看了很多博客依然理解的不是很好，自己比较菜，看了陈天奇大神PPT清晰了很多，特地总结一下Xgboost，以便加深自己的理解和以后的复习，主要是对ppt的解读，也有参考其他大神的博客，非喜勿喷，如有错误欢迎指正。

Xgboost的生成过程：

• 迭代生成新的树，递归生长树，每生成新的树就是去预测上棵树的残差。
• Xgboost使用的是CART回归树，是个二叉树，使用gain来选择特征最佳分裂点分裂。
• 训练后得到的模型是多棵树，每棵树有多个叶子节点
  预测过程：样本根据特征值会在每棵树落到一个叶子节点上，最终的预测值就是每颗树对应叶子节点的分数乘树权重和。

学习过程中，有以下几个问题：
1.树怎么生长？
2.树什么时候停止生长
3.每个叶子节点分数怎么求？
4.树怎么使用损失函数来优化？
5.不同的树之间有什么区别？

模型和目标函数：（截图全部来自陈天奇Xgboost PPT）

模型和目标函数

模型是学习K颗树，每棵树去拟合上次学习的残差

Xgboost树拟合过程
最新的函数值和上一次预测值和为新的预测值
目标函数

目标函数可以改写成如上图，目标函数中目标值和上一次预测值都是已知的，要求的就是新的函数f(x)使目标函数最小

使用泰勒函数二级展开对目标函数进行展开

泰勒公式
其中gi为损失函数L(yi,y^(t-1))对y(t-1)的一阶导数，hi为损失函数L(yi,y^(t-1))对y(t-1)的二阶导数
如果损失函数为平方损失的话，两个导数值如下求得
损失函数为平方差时的一阶导和二阶导
其中L(yi,yi^(t-1))是已知的，gi也是已知，hi也是已知，未知的为新函数ft(xi)
此时我们的每棵树就是ft(xi),每棵树的叶子节点输出值就是函数的值，叶子节点数可以枚举，我们的目标就是求出叶子节点输出值，使目标最优。
抽象提取后的目标函数
这样做可以很明确知道我们的目标函数，并且工程上也很方便地在实现的时候进行损失函数的替换。
完善树的定义
用一个由叶子节点分数值组成的向量来表示一棵树，并且由一个map表来保存样本与叶子节点的映射关系，q 代表一棵树，输入一个样本会落在q的一个叶子节点上，会获得一个叶子节点编号，输入一个叶子节点编号可以在ft(x)=wq(x)中获得对于的叶节点的权重值。
定义树的复杂度
这里就是监督学习模型里面常见的正则化部分，正则化函数主要用于惩罚模型复杂度，这里使用到叶子节点数和叶子节点分数值的L2正则化项来表示模型的复杂度。
重新审视目标函数
之前的损失函数的描述是每个样本的损失值之和，这里以每个叶子节点包含的样本权重对应的损失值之和。
此时每个叶子节点权重未知，其他的参数已知。
每个叶子节点权重求解
此时只有叶子节点的权重wj未知，其他已知，便可以简单看出为关于wj的一元二次方程的最小值，由初中的抛物线知识可知ax2+bx+c=0取最小值时，x值为对称轴-b/2a；
假设树的结构固定，每个叶子节点的权重值为落在该节点的样本数对应的上一次预测损失函数的一阶导和二阶导的值。
叶子节点值计算
最终的目标函数值就是这棵树每个叶子节点上的样本对应的一阶导和二阶导对应的值计算得到。 树的生长

树的生长过程中怎么选择最佳分裂点呢？
通过对比分裂前后的目标函数值，分裂后目标值最小的分裂为最佳分裂点。

怎么高效地找到最佳分裂点

• 只需要求到分裂点左右的样本对应的一阶导和二阶导之和，然后计算增益

  
  分裂过程

• 对于样本的每个特征按照特征值进行排序

• 从左往右线性扫描找到该特征的最佳分裂点

  
  类别离散变量处理
  

  Xgboost会自动使用one-hot编码来处理类别型变量。

剪枝和正则化

回忆分裂的增益，在训练损失小于正则化系数时，增益为负。

早停

• 如果最佳分裂点有负增益，停止分裂

后剪枝

• 当树生长树到最大树深时，递归地减掉所有分裂时有负增益的叶子节点

  
  Xgboost概述

整个算法的流程如下：

• 1. 每次迭代添加一颗新树，每棵树拟合上棵树的残差
• 2.开始迭代新树之前，计算每个样本对应的损失函数一阶导和二阶导矩阵
• 3.统计目标函数增益来选择最佳分裂点，贪婪地生长树
• 4. 把新树添加到模型，会乘一个系数，防止过拟合。对残差拟合时，通常会使用步长或者学习率来控制优化，保留更大的优化空间给后续的学习。

Xgboost算法讲解完毕。

参考博客：
https://zhuanlan.zhihu.com/p/26214650
https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf