浅析XGBOOST

前言

xgboost是一种集成学习算法，通过回归树，每一次对残差（实际值与预测值之差）进行拟合，最后把预测值相加得到最终的预测值。比如一个小男孩是10岁，我用一棵树去拟合，得到4.残差是6，第二课树拟合，得到3，这时残差是3.第三棵树继续拟合，得到2.这时我们的预测值就是4+3+2=9.和实际值10比较接近了。

tree

浅析

1）先看下前言说的相加的数学公式。

equ1

q代表每棵树的结构，通过它我们能知道每个样本在每棵树的位置。T是树的叶子数。

2）然后我们看下目标函数的形式

equ2

$\hat{y} _{i}$ 是样本i的预测值， $y_{i}$ 则是样本i的实际值。w代表每个叶子节点的分数。l( $\hat{y} _{i}$ , $y_{i}$ )代表预测值与真实值的差异。 $\Omega$ (f)作为惩罚项，主要是降低模型的复杂度，避免过拟合。惩罚主要包含两个方面， $\gamma$ T表示更少的叶子数，而||w||的平方项则希望更小的叶子节点分数。

3）我们先令 $\hat{y} _{i}$ = $\hat{y}_{i}^{t-1}$ + $f_{t}$ ( $x_{i}$ ).其中 $\hat{y}_{i}^{t-1}$ 表示前t-1颗树对样本i的预测值之和，而 $f_{t}$ ( $x_{i}$ )表示第t棵树对样本i的预测值，然后对equ2进行泰勒二阶展开。

taylor

上式便是泰勒二阶展开公式。equ2按照泰勒公式展开后如下

equ3

$g_{i}$ 为一阶导数， $h_{i}$ 为二阶导数。仔细看equ2似乎和泰勒展开表达式不太一样，可以把l( $y_{i}$ , $\hat{y} _{i} ^{t-1}$ )当成是f(x), $\Delta$ x当作是 $f_{t}$ ( $x_{i}$ ).

4)去掉常数项l( $y_{i}$ , $\hat{y}_{i}^{t-1}$ )---实际值和前t-1颗树在第t轮都是已知的。然后把 $\Omega$ 代入，得

equ4

其中j是叶子， $I_{j}$ 是叶子j上所有的样本集合。此时，我们可以求解目标函数的最小值。令上式的导数为0，我们可以解得 $w_{j}^*$ = - $\frac{\Sigma i\in I_{j} g_{i} }{\Sigma i\in I_{j} h_{i}+\lambda }$ .代入equ4得

equ5

这是目标函数的最小值。然而，需要注意的是，它依然是一个变量。因为树的结构未知。那么，能穷举么？似乎不太现实。这时我们使用贪婪算法

5）我们首先将所有样本置于一个叶子节点上，然后再对这个叶子节点进行分裂。然后不断分裂，树不断生长。然而，前面我们说过 $\Omega$ 惩罚项不希望模型太过复杂。我们可以先计算下分裂带来的目标函数下降是多少

equ6

这个式子是分裂前的目标函数减去分裂后的目标函数。当然，我们希望它是正数

6）上式的值同样是未知的。问题在于用哪个特征划分？又用哪个特征值划分？我们首先能想到的是精确算法。遍历每一个特征，遍历每一个特征值，肯定能找出最佳分裂点。这个计算量有点大。于是又有近似算法。简单说这时我们不再遍历每一个特征值，而只是计算部分特征值，从中选取最优分裂点（only among proposed splits）。如下所示

approximate

其中k代表各个特征， $s_{k1}$ , $s_{k2}$ 就是特征k上面的分割点。然后计算各个区间段的 $G_{kv}$ , $H_{kv}$ . $x_{jk}$ 便是特征k上的特征值。另外，划分分割点也有两种不同的方法，主要是根据划分的时间点。global会在初始阶段就把分割点确定好了，后面怎么分裂都是用这些分割点。而local方法会在分裂后对这些分割点进行调整，分割点不是固定的。通常global需要更多的分割点才能达到和local同样的效果。下面的图形可以说明精确算法、近似算法（global/local）的差异

split finding

eps可以看成是特征分隔区间的倒数。图中可以看出global方法如果只是把特征分成3个左右区间，准确率是不怎么高的。而local只需要3个，global提升到20个，就能媲美精确算法了。

7）如何处理缺失值。xgboost对于缺失值，要么划分到左子树，要么划分到右子树。具体划分到哪一边是从训练数据中得到的。首先我们把所有的样本分到右子树，然后从右子树不断把不缺失的样本分到左子树，计算最大的分数增加值。然后又把所有样本分到左子树，同样操作，计算最大的分数增加值。如果分到右边分数增加的更多，则默认方向就是右边。以后测试时有缺失值到达这个节点时自动分到右边。原文算法如下

direction

$I_{k}$ 是不含缺失值的集合。注意画红线的地方，先把缺失值划分到右边时，是按从小到大的顺序把非缺失值划分到左子树的。而后面是从大到小排序。这样能加快计算速度

陈天奇博士论文：https://arxiv.org/pdf/1603.02754v1.pdf 陈天奇博士PPT：https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf