XGBoost的基本原理

损失函数

XGBoost对损失函数用二阶Taylor展开近似

Taylor公式:

在第m步的时候,令
因为跟未知量无关,所以
对于L2损失,
所以
XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。

正则项

把树拆分成结构部分q和叶子分数部分w :

结构函数q: 把输入映射到叶子的索引号

w: 给出每个索引号对应的叶子的分数(叶子节点的不纯净度度量)

T: 树中叶子节点的数目,D为特征维数

树的复杂度可以定义为
, 叶子节点的数目+叶子节点分数的L2正则

目标函数

令每个叶子节点t上的样本集合为

由
将代入得:
(分数越低越好)

建树

选择分数最小的的树结构,因为是NP问题,所以一般采用贪心算法
（1）从深度为0的树开始
（2）对于树的每个叶子节点，尝试增加一个分裂点：
令I和I分别表示加入分裂点后左右叶子结点的样本集合,

则增加分裂点后目标函数的变化为

怎么找到最优的分裂点？

1. 精确搜索算法 对每一个结点，穷举所有特征、所有可能的分裂点 ,对每个特征，通过特征值将实例进行排序 ,运用线性扫描来寻找该特征的最优分裂点 ,对于一层排序，需要时间Nlog(N)，N为样本数目,由于有D个特征，k层，所以时间复杂度为kDNlog(N). 精确搜索的性能差,需要更多的内存,对cache优化不友好.
2. 近似搜索算法 首先根据特征的统计分布（分位数）选出候选切分点；然后对于连续属性特征，根据候选切分点进行离散化；最后会从这些候选切分点中选出最优的。近似算法提出了两种版本：global variant和local variant. global variant在树初始化时就确定了候选切分点；local variant是在每次节点分裂后重新选出候选点。论文中的实验表明：在同等精度下，相对于global variant, local variant需要的候选切分点更少

3. 稀疏特征 在树的每个结点设置一个缺省方向,将稀疏特征视为缺失值 ,只访问非缺失数据 ,计算复杂度只与非缺失数据数目线性相关

   剪枝和正则

   从分裂的增益公式看
   增益有可能为负,因为新引入的叶子节点有复杂度惩罚.
   策略:

4. 出现负值提前终止 ,但被提前终止掉的分裂可能其后续的分裂会带来好处

5. 过后剪枝 将树分裂到最大深度，然后再基于上述增益计算剪枝 在实现时还有学习率，给后续轮留机会,进一步防止过拟合