XGBoost原理简述

笔记主要是参考了贪心学院在B站的公开课XGBoost的技术剖析

这篇博客也讲的十分详细：白话机器学习算法理论+实战番外篇之Xgboost，有一些上面的课程没有讲到的内容，如节点的最优切分点划分，要进行特征遍历，作者没有使用等宽或等频分桶，而是提出了等值percentiles划分算法（Weight Quantile Sketch）。

集成算法，弱分类器的概念等等就先略去了。

根据各个弱分类器之间有无依赖关系，集成算法可以分为Boosting和Bagging：

• Boosting流派：各分类器之间没有依赖关系，必须串行，比如Adaboost，GBDT，Xgboost；
• Bagging流派：各分类器之间没有依赖关系，可各自并行，比如随机森林。

为什么XGBoost这么火？

• 算法可以并行，训练效率高；

• 比起其他算法，世界效果好；

• 由于可控参数（超参数）多，可以灵活调整；

学习路径：

• 如何构造目标函数？（XGBoost的目标函数不是连续型的）
• 目标函数直接优化难，如何近似？（泰勒级数，Taylor Expansion）
• 如何把树的结果引入到目标函数？
• 仍然难优化，要不要使用贪心算法？

1.如何构造目标函数

回顾如何使用多棵树来预测：

假设已经训练了K颗树，则对于第$i$个样本的（最终）预测值为：

$$\hat{y_i} = \sum^k_{k=1}f_k(x_i), \, f_k \in \mathcal{F}$$

目标函数为：

$$Obj = \sum^n_{i=1} l(y_i,\hat{y_i}) + \sum^k_{k=1} \Omega(f_k)$$

其中前一项为损失函数，$y_i$为真实值，$\hat{y_i}$为预测值，$l(y_i,\hat{y_i})$为针对当前问题的loss；后一项为Penalty，或者称Regulation，控制模型的复杂度，防止过拟合。

现在的问题是如何给每一个树加上Penalty / Regulation。

回顾在决策树中如何定义树的复杂度：

$\sum^n_{i=1}l(y_i,\hat{y_i})$中计算了所有样本的loss，loss函数包含了不同树模型的loss，这时就可以使用叠加式的训练（Additive Training），当训练第$k$个模型（树）时，前面的第1到第$k-1$颗树是已知的。

假设现在我们要去构建第$k$颗树，

• 给定$x_i$；

• $\hat{y_i}^{(0)} = 0 \gets$ Default case ;

• $\hat{y_i}^{(1)} = f_1(x_i) = \hat{y_i}^{(0)} + f_1(x_i)$；
• $\hat{y_i}^{(2)} = f_1(x_i) + f_2(x_i) = \hat{y_i}^{(1)} + f_2(x_i)$；
• $\dots$
• $\hat{y_i}^{(k)} = f_1(x_i) + f_2(x_i) + \dots + f_k(x_i)= \sum^{k-1}_{j=1}f_j(x_i)+f_k(x_i)=\hat{y_i}^{(k-1)} + f_k(x_i)$；

其中$\hat{y_i}^{(k-1)}$表示前$k-1$颗树的预测值之和，$f_k(x_i)$表示第$k$颗树的预测值，两者之和要和真实值$y_i$越接近越好。

因为前$k-1$颗树是训练好的，则目标函数可以写成：

$$\begin{align*} Obj &= \sum^n_{i=1} l(y_i, \hat{y_i}^{(k)}) + \sum^k_{k=1}\Omega(f_k)\\ &= \sum^n_{i=1} l(y_i, \hat{y_i}^{(k-1)} + f_k(x_i)) + \sum^{k-1}_{j=1}\Omega(f_j)+\Omega(f_k) \end{align*}$$

其中$\hat{y_i}^{(k-1)}$和$\sum^{k-1}_{j=1}\Omega(f_j)$可以看作是常数，则当训练第$k$颗树时，我们要最小化：

$$minimize \quad \sum^n_{i=1} l(y_i, \hat{y_i}^{(k-1)} + f_k(x_i)) + \Omega(f_k)$$

2.使用泰勒级数优化目标函数

由上一节我们可知，构建第$k$颗树时的目标函数是 ：

$$\begin{align*} Obj &= \sum^n_{i=1} l(y_i, \hat{y_i}^{(k-1)} + f_k(x_i)) + \Omega(f_k) \end{align*}$$

回顾泰勒级数Taylor Expansion：

$$f(x+\Delta x) \approx f(x) + f'(x) \cdot \Delta x + \frac{1}{2} f^{''}(x)\cdot \Delta x^2$$

令其中的$f(x) = l(y_i, \hat{y_i}^{(k-1)} )$，$\Delta x= f_k(x_i)$，则有：

$$\begin{align*} Obj &= \sum^n_{i=1} l(y_i, \hat{y_i}^{(k-1)} + f_k(x_i)) + \Omega(f_k) \\ &= \sum^n_{i=1} \left[ l(y_i, \hat{y_i}^{(k-1)} ) +\partial_{\hat{y_i}^{(k-1)}} l(y_i, \hat{y_i}^{(k-1)} ) \cdot f_k(x_i) + \frac{1}{2}\partial^2_{\hat{y_i}^{(k-1)}} l(y_i, \hat{y_i}^{(k-1)} ) \cdot f^2_k(x_i) \right]+ \Omega(f_k) \\ &= \sum^n_{i=1} \left[ l(y_i, \hat{y_i}^{(k-1)} ) +g_i \cdot f_k(x_i) + h_i \cdot f^2_k(x_i) \right]+ \Omega(f_k) \end{align*}$$

第一项$ l(y_i, \hat{y_i}^{(k-1)} )$是已知的，那么最下化目标函数就等价于：

$$minimize \sum^n_{i=1} \left[ g_i \cdot f_k(x_i) + h_i \cdot f^2_k(x_i) \right]+ \Omega(f_k)$$

注：当训练第$k$颗树时，$\{h_i, g_i\}$是已知的。

3.在树的形状已知的情况下，求目标函数的最小值

接下来我们要把$f_k(x_i)$和$\Omega(f_k)$参数化。考虑现有如下图的一个树，那我们如何把这颗树用参数化表示出来：

定义一个权重变量，或者称leaf value，$w=(w_1, w_2, w_3) = (15, 12, 20)$；

定义一个函数$q(x)$，表示样本$x$的位置，$q(x_1) =1, q(x_2)=3, q(x_3)= 1, q(x_4) = 2, q(x_5)=3$；

则有$f_k(x_i) = w_{q(x_i)} $ ，这样就把$f_k(x_i)$参数化了，但有个问题是$w$的下标还是个函数，为此我们还需定义一个函数$I_j=\{i | q(x_i)=j\}$，表示那些样本$x_i$会落在第$j$个位置上，它按叶节点的位置把样本重新组织。$I_1=\{1,3\},I_2=\{4\}, I_3=\{2, 5\}$。

这样我们原先以样本为单位累加得到$\sum^n_{i=1} g_i \cdot f_k(x_i)=\sum^n_{i=1} g_i \cdot w_{q(x_i)}$这一项，就可以换种思路，以叶节点为单位累加，以上图为例：

$$\begin{align*} &g_1 \cdot w_{q(x_1)}+g_2 \cdot w_{q(x_2)}+g_3 \cdot w_{q(x_3)}+g_4 \cdot w_{q(x_4)}+g_5 \cdot w_{q(x_5)}\\ =&g_1 \cdot w_{q(x_1)}+g_3 \cdot w_{q(x_3)}+ \\ &g_2 \cdot w_{q(x_2)}+\\ &g_4 \cdot w_{q(x_4)}+g_5 \cdot w_{q(x_5)}\\ =& g_1 \cdot w_1+g_3 \cdot w_1+ \\ &g_2 \cdot w_2+\\ &g_4 \cdot w_3+g_5 \cdot w_3\\ =&\sum^T_{j=1}(\sum_{i\in I_j } g_i) \cdot w_j \end{align*}$$

接着考虑如何定义一颗树的复杂度，可以是树的复杂度 = 叶节点个数 + leaf value，即：

$$\Omega(f_k) = \gamma T + \frac{1}{2} \lambda \sum^T_{j=1} w_j^2$$

其中$T$是叶节点的个数，$w_j$是第$j$个叶节点的leaf value；$\gamma$和$\lambda$控制两部分的权重，是超参数。

最后将两部分结合起来，得到新的目标函数（假设树的形状已知）

$$\begin{align*} & \sum^n_{i=1} \left[ g_i \cdot f_k(x_i) + h_i \cdot f^2_k(x_i) \right]+ \Omega(f_k)\\ =& \sum^n_{i=1} \left[ g_i \cdot w_{q(x_i)} + h_i \cdot w^2_{q(x_i)} \right]+ \gamma T + \frac{1}{2} \lambda \sum^T_{j=1} w_j^2 \\ =& \sum^T_{j=1} \left[(\sum_{i\in I_j } g_i) \cdot w_j + \frac{1}{2}(\sum_{i\in I_j } h_i + \lambda) \cdot w^2_j\right] + \gamma T \end{align*}$$

令$G_j = \sum_{i\in I_j } g_i$，$H_j = \sum_{i\in I_j } h_i$，则使前一项最小的$w_j$值（回顾一元二次方程）为：

$$w_j^* = -\frac{G_j}{H_j+\lambda}$$

此时目标函数的最小值为：

$$Obj* = \frac{1}{2} \cdot \sum^T_{j=1} \frac{G_j^2}{H_j+\lambda} + \gamma T$$

那么到目前我们解决了，在树的形状已知的情况下，可以求出第$k$树的最小的目标函数值。

那接下来我们要做的是在所有可能的形状的树中，寻找出$Obj^*$最小的那颗树。

4.寻找树的形状

寻找树的形状可以用暴力算法（Brute Force Search），但这样做就效率太低了，复杂度也是节点个数的指数级的。 可行的方法是使用贪心算法去寻找。

回顾我们如何去构造一颗决策树。选择特征的依据是使不确定性变小，特征的score = 原（不确定性）- 分之后（不确定性），称为Information Gain（信息增益），每次分支的依据就是使信息增益最大化。那把这里的不确定性（Entropy）换成 $Obj$，就可以完成对有最小的$Obj^*$的树的寻找。

通过下面的例子来看一下如何寻找最好的树的形状，即寻找最好的Split。

xgboost贪心建树的思路：遍历所有特征以及所有分割点，每次算最好的那个。但这样做代价太大了，尤其是数据量很大，分割点很多的时候，计算起来非常复杂并且也无法读入内存进行计算。作者提出了一种近似分割的方式（可以理解为分割点分桶的思路），选出一些候选的分裂点，然后再遍历这些较少的分裂点来找到最佳分裂点。

进行分桶候选分裂点的一般思路是根据特征值的大小进行等宽分桶，或者进行等频分桶。这样做选择出的候选点确实少了很多，但这样划分是没什么依据的，缺乏可解释性。

作者采用了一种对loss的影响权重的等值percentiles（百分比分位数）划分算法（Weight Quantile Sketch）。考虑的是想让loss在左右子树上分布的均匀一些，而不是样本数量的均匀，因为每个样本对降低loss的贡献可能不一样，按样本均分会导致分开之后左子树和右子树loss分布不均匀，

其实这里这个损失函数还可以进一步化简的（和上面的化简不一样，上面的化简是把遍历样本转到了遍历叶子上得到基于决策树的目标函数，这里是从目标函数本身出发进行化简）：

后面的每一个分类器都是在拟合每个样本的一个残差 $\frac{g_i}{h_i}$，$h_i$可以看做计算残差时某个样本的重要性，即每个样本对降低loss的贡献程度。第一个问题说的听清楚了吧。

Xgboost引入了二阶导之后，相当于在模型降低残差的时候给各个样本根据贡献度不同加入了一个权重，这样就能更好的加速拟合和收敛。GBDT只用到了一阶导数，这样只知道梯度大的样本降低残差效果好，梯度小的样本降低残差不好，但是好与不好的程度在GBDT中无法展现。而xgboost这里就通过二阶导可以展示出来，这样模型训的时候就有数了