XGBoost原理简介

1. 背景

今天听了贪心学院主办，李文哲老师主讲的《XGBoost的技术剖析》直播，让我对XGB的原理有了一些了解。于是我想写一篇笔记整理一下听课的内容。

老师讲得挺通俗易懂的，不过由于XGB本身具有一定的复杂性，要看懂这篇笔记需要有如下的背景知识：

1. 决策树的原理
2. 泰勒级数
3. 损失函数
4. 惩罚函数

如果对这些概念不太了解，推荐阅读复旦大学邱锡鹏老师的开源书《神经网络与深度学习》还有人民邮电出版社的《机器学习实战》，泰勒级数可以参考高数课本和网络资料。

2. Boosting

从 XGBoost 这个名字就能看出来，这个模型使用了 Boosting 的方法，那么我们就来先了解一下 Boosting 它是个啥玩意儿。

$\text{Figure 1. Bagging vs Boosting}$Figure 1. Bagging vs Boosting

老师的PPT中对比了 Bagging 和 Boosting 两种常用的集成学习方法。

• Bagging：利用多个过拟合的弱学习器来获得更好的效果。典型的算法有随机森林。

• Boosting：利用多个欠拟合的弱学习器来获得更好的效果。典型的算法有GBDT/GBRT，Adaboost，XGBoost和LightGBM。

Boosting 本身在不同算法中的具体应用也不完全相同，而从 XGBoost ¹的论文 中我们能够了解到，它主要借鉴了 GBDT 的 Boosting 方法

为了加深对 Boosting 的了解，我把 GBDT ² 的论文也找出来看了一下。

2.1. 建立映射

首先，我们通过公式 $\left(1\right)$(1)建立从 $x$x 到 $y$y 的映射。

$\begin{array}{cc}\widehat{y}=F(x;{\{{\beta }_m,a_m\}}_1^M)=\sum _{m=1}^M{\beta }_{m}h(x;a_m)& \text{(1)}\end{array}$y ​=F(x;{βm​,am​}1M​)=m=1∑M​βm​h(x;am​)(1)

这里的 $x$x 和 $a_m$am​ 用粗体显示，表示它们都是向量， $\widehat{y}$y ​ 表示模型的预测值。

公式 $\left(1\right)$(1)中的 $h(x;a_m)$h(x;am​) 表示一个个弱分类器， $a_m$am​ 是弱分类器的参数， ${\beta }_m$βm​ 是其权重， ${\{{\beta }_m,a_m\}}_1^M${βm​,am​}1M​ 是 $a_m$am​ 和 ${\beta }_m$βm​ 的 $M$M 个组合。 $M$M表示弱分类器的数量。

公式 $\left(1\right)$(1)表示 GBDT 是通过对多个弱分类器结果进行线性加权求和从而求出最终结果的。

2.2. 计算参数

建立了 $x$x 到 $y$y 的映射之后，我们就需要考虑如何去计算函数中的参数。

(βm​,am​)=argβ,amin​i=1∑N​L(yi​,Fm−1​(xi​)+βh(xi​;a))(2)

公式 $\left(2\right)$(2) 中， argβ,amin​ 表示使其右边的表达式最小的 $(\beta ,a)$(β,a) 组合， $L(y_i,\widehat{y_i})$L(yi​,yi​^​) 为损失函数。

公式 $\left(2\right)$(2) 说明参数 $({\beta }_m,a_m)$(βm​,am​)是通过使得损失函数最小化计算出来的，具体如何计算就取决于我们使用什么具体的损失函数和优化器了。

同时， 我们还可以推出公式 $\left(3\right)$(3)。

$\begin{array}{cc}{F}_m\left(x\right)=F_{m-1}\left(x\right)+{\beta }_{m}h(x;a_m)& \text{(3)}\end{array}$Fm​(x)=Fm−1​(x)+βm​h(x;am​)(3)

公式 $\left(3\right)$(3) 中 $F_m\left(x\right)$Fm​(x) 是训练完 $m$m 个弱分类器以后，模型的输出结果。

公式 $\left(3\right)$(3) 说明 GBDT 在训练每第 $m$m 个弱分类器时，我们需要先将前 $m-1$m−1 个弱分类器的预测结果求和，从而获得一个新的预测结果，在此基础上对第 $m$m 个弱分类器进行训练和预测。即新的弱分类器是在已有模型的残差上进行训练的。

可理解为如下公式。

$\begin{array}{cc}{\beta }_{m}h(x;a_m)\to (y_i-\sum _{k=1}^{m-1}{\beta }_{k}h(x;a_k))& \text{(4)}\end{array}$βm​h(x;am​)→(yi​−k=1∑m−1​βk​h(x;ak​))(4)

即第 $m$m 个弱分类器的训练目标是输出趋近于 $y_i$yi​ 和 前 $m-1$m−1 个弱分类器的结果之和的差值。

再结合老师PPT中的例子，应该就能够很好地理解 Boosting 的作用。

$\text{Figure 2. Boost Tree}$Figure 2. Boost Tree

$\text{Figure 3. Model Predict}$Figure 3. Model Predict

3. XGBoost的目标函数

了解了 Boosting 之后，我们就可以开始学习 XGBoost 了，首先从它的目标函数开始分析。

$\text{Figure 4. Object Function}$Figure 4. Object Function

我们一般使用树模型来作为弱分类器，假设有 $K$K 颗树，对第 $i$i 个输入，它们的预测值为 ${\widehat{y}}_i$y ​i​。

$\begin{array}{cc}{\widehat{y}}_i=\sum _{k=1}^K{f}_k\left(x_i\right),f_k\in F& \text{(5)}\end{array}$y ​i​=k=1∑K​fk​(xi​),  fk​∈F(5)

公式 $\left(5\right)$(5) 中 $f_k\left(x_i\right)$fk​(xi​) 表示第 $k$k 颗树对第 $i$i 个输入向量的预测输出。

而 XGBoost 的目标函数由损失函数和惩罚函数组成，这一点大多数机器学习模型都差不多。通过最小化损失函数来提高预测精度，引入惩罚函数来控制模型复杂度，防止过拟合。

$\begin{array}{cc}Obj=\sum _{i=1}^{n}l(y_i,{\widehat{y}}_i)+\sum _{k=1}^K\Omega \left(f_k\right)& \text{(6)}\end{array}$Obj=i=1∑n​l(yi​,y ​i​)+k=1∑K​Ω(fk​)(6)

公式 $\left(6\right)$(6) 中的 $n$n 表示输入数据的总数目，我们的优化目标就是最小化目标函数。

$\begin{array}{cc}\min Obj& \text{(7)}\end{array}$minObj(7)

4. 化简目标函数

有了目标函数以后，我们还没有好的办法直接对它进行求解，还需要进行化简。图5是老师的PPT。

$\text{Figure 5. Additive Traning}$Figure 5. Additive Traning

图5的左半部分主要在解释Additive Traning，和我们在 Boosting 部分提到的类似。我们主要关注右半部分的化简过程。

通过将 ${\widehat{y}}_i$y ​i​ 展开，去除常数项，可以将目标函数化简为

Obj​=i=1∑n​l(yi​,y ​i(k)​)+k=1∑K​Ω(fk​)=i=1∑n​l(yi​,y ​i(k−1)​+fk​(xi​))+Ω(fk​)​​(8)

此处利用了公式 $\left(5\right)$(5) 将 ${\widehat{y}}_i^{\left(k\right)}$y ​i(k)​ 中前 $k-1$k−1 项分离了出来。因为前 $k-1$k−1 项已经在各自的训练过程中优化过了，在这里可以视为常数项，所以我们将惩罚函数中的前 $k-1$k−1 项去除，仅考虑要优化的 $f_k$fk​ 部分。

5. 使用泰勒级数近似目标函数

尽管我们对目标函数进行了化简，但直接对目标函数进行求解，运算的复杂度会非常高，所以我们选择对目标函数进行二级泰勒展开，提高模型的训练速度。

$\text{Figure 6. Taylor Expansion}$Figure 6. Taylor Expansion

根据公式 $\left(9\right)$(9) 中的二级泰勒展开式。

$\begin{array}{cc}f(x+\Delta x)\approx f\left(x\right)+f^{\prime }\left(x\right)\cdot \Delta x+\frac{1}{2}{f}^{\prime \prime }\left(x\right)\cdot \Delta x^2& \text{(9)}\end{array}$f(x+Δx)≈f(x)+f′(x)⋅Δx+21​f′′(x)⋅Δx2(9)

对目标函数进行展开：

Obj​=i=1∑n​l(yi​,y ​i(k−1)​+fk​(xi​))+Ω(fk​)=i=1∑n​[l(yi​,y^​(k−1))+gi​fk​(xi​)+21​hi​fk2​(xi​)]+Ω(fk​)​​(10)

其中 $g_i={\partial }_{\widehat{y}(k-1)}l(y_i,{\widehat{y}}^{(k-1)})$gi​=∂y^​(k−1)​l(yi​,y^​(k−1)) 且 $h_i={\partial }_{\widehat{y}(k-1)}^{2}l(y_i,{\widehat{y}}^{(k-1)})$hi​=∂y^​(k−1)2​l(yi​,y^​(k−1))， 对应二级泰勒展开式中的一阶导数和二阶导数，由于它们都是基于前 $k-1$k−1 个模型的，所以在训练第 $k$k 个模型时也是已知的，可以视为常数项。

公式 $\left(10\right)$(10) 中， $l(y_i,{\widehat{y}}^{(k-1)})$l(yi​,y^​(k−1)) 也可视为常数项，并且这一项没有和变量 $f_k\left(x_i\right)$fk​(xi​)相乘，所以我们可以将展开后的目标函数再次进行化简，结果为：

$\begin{array}{cc}Obj=\sum _{i=1}^n[g_i{f}_k\left(x_i\right)+\frac{1}{2}{h}_i{f}_k^2\left(x_i\right)]+\Omega \left(f_k\right)& \text{(11)}\end{array}$Obj=i=1∑n​[gi​fk​(xi​)+21​hi​fk2​(xi​)]+Ω(fk​)(11)

6. 模型参数化

在公式 $\left(5\right)$(5) 中 ，我们提到 $f_k\left(x_i\right)$fk​(xi​) 表示第 $k$k 颗树对第 $i$i 个输入向量的预测输出。那么我们又应该如何在公式中将 $f_k\left(x_i\right)$fk​(xi​) 展开，从而进行训练和调优，最终达到优化模型的目的呢。这里我们就需要将模型参数化，将问题转化为参数优化的问题。

那么我们这一节要解决的子问题就是，如何用参数的形式来表示一颗决策树，或者说，如何将决策树的模型参数化。

我们参考周志华老师《机器学习》 ³ 书中的一个例子。

$\text{Figure 7. Decision Tree}$Figure 7. Decision Tree

设 ${\widehat{y}}_i=1$y ​i​=1表示模型预测第 $i$i 个瓜为好瓜， ${\widehat{y}}_i=0$y ​i​=0表示模型预测第 $i$i 个瓜为坏瓜。叶子节点标签后的数字为叶子节点的标号。

设 $I_j=\left\{i\mid q\right(x_i)=j\}$Ij​={i∣q(xi​)=j} 为被分到第 $j$j 个叶子节点中的 $x_i$xi​ 的序号集合。 $q\left(x_i\right)$q(xi​) 为输入 $x_i$xi​到叶子节点序号的映射。

设 $w_j=\alpha \left(j\right)$wj​=α(j) 为第 $j$j 个叶子节点的 $\widehat{y}$y ​ 值。取样例数据进行说明：

$\text{Table 1. Sample Data}$Table 1. Sample Data

则

fk​(x1​)=α(q(x1​))=α(2)=1=w2​fk​(x2​)=α(q(x2​))=α(1)=0=w1​fk​(x3​)=α(q(x3​))=α(3)=0=w3​​​

根据上面的定义，我们继续对目标函数进行化简。

首先展开惩罚函数:

$\begin{array}{cc}\Omega \left(f\right)=\gamma T+\frac{1}{2}\lambda \parallel w{\parallel }^2& \text{(12)}\end{array}$Ω(f)=γT+21​λ∥w∥2(12)

Obj​=i=1∑n​[gi​fk​(xi​)+21​hi​fk2​(xi​)]+γT+21​λj=1∑T​wj2​​(13)

公式 $\left(12\right)$(12) 中 $\gamma$γ 为树的深度， $T$T 为叶子节点个数， $\lambda$λ 为惩罚项系数。 $\parallel w{\parallel }^2$∥w∥2 为L2正则化项。公式 $\left(13\right)$(13) 为将惩罚函数带入后的目标函数。

下面将 $f_k\left(x_i\right)$fk​(xi​) 从对每一项输入数据的输出求和，转为对每一个叶子节点的输出求和。

$\begin{array}{cc}Obj=\sum _{j=1}^T[\left(\sum _{i\in I_j}{g}_i\right)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T& \text{(14)}\end{array}$Obj=j=1∑T​⎣⎡​⎝⎛​i∈Ij​∑​gi​⎠⎞​wj​+21​⎝⎛​i∈Ij​∑​hi​+λ⎠⎞​wj2​⎦⎤​+γT(14)

公式 $\left(14\right)$(14) 中 $I_j=\left\{i\mid q\right(x_i)=j\}$Ij​={i∣q(xi​)=j} 是被分到第 $j$j 个叶子节点中的 $x_i$xi​ 的序号集合。

7. 寻找最佳分裂点

我们假设树的结构 $q\left(x_i\right)$q(xi​) 是确定的，即公式 $\left(13\right)$(13) 中， $\gamma$γ 和 $T$T 两个参数是确定的， $I_j$Ij​ 也是确定的，剩下的自变量就只有 $w_j^2$wj2​，我们就得到了一个一元二次方程。

要使这个一元二次方程最小，我们就需要找到它的极值点。

首先考虑二次项系数的正负性。 $\lambda$λ 是惩罚项系数，是非负的，而
$h_i={\partial }_{\widehat{y}(k-1)}^{2}l(y_i,{\widehat{y}}^{(k-1)})$hi​=∂y^​(k−1)2​l(yi​,y^​(k−1))，是损失函数的二阶导数。

我们参考《神经网络与深度学习》 ⁴ 中给出的常用损失函数。

$\text{Figure 8. Loss Function}$Figure 8. Loss Function

XGBoost 常用的是平方损失，它的二阶导函数恒为正数。所以目标函数二次项系数也恒为正。

所以我们根据一元二次方程的性质，求解目标函数的最小值。

$\begin{array}{cc}{w}_j^{\ast }=-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda }& \text{(15)}\end{array}$wj∗​=−∑i∈Ij​​hi​+λ∑i∈Ij​​gi​​(15)

带入公式 $\left(14\right)$(14) 可求得

$\begin{array}{cc}Obj\left(q\right)=-\frac{1}{2}\sum _{j=1}^T\frac{{\left(\sum _{i\in I_j}{g}_i\right)}^2}{\sum _{i\in I_j}{h}_i+\lambda }+\gamma T& \text{(16)}\end{array}$Obj(q)=−21​j=1∑T​∑i∈Ij​​hi​+λ(∑i∈Ij​​gi​)2​+γT(16)

公式 $\left(16\right)$(16) 中 $q$q 为某一确定的树结构。 $Obj\left(q\right)$Obj(q) 可以作为评分函数，用来计算树结构的得分。类似于决策树模型中的信息熵(Information Entropy)。

由于遍历所有的树结构是一个 $NP$NP 问题，所以 XGBoost 采用了贪心算法来求得树结构的局部最优解。

假设 $I_L$IL​ 和 $I_R$IR​ 是分割后的左节点和右节点的 $x_i$xi​ 的序号集合， $I=I_L\bigcup I_R$I=IL​⋃IR​，那么每次分裂后 $Obj\left(q\right)$Obj(q) 的减少值为：

$\begin{array}{cc}{L}_{split}=\frac{1}{2}[\frac{{\left(\sum _{i\in I_L}{g}_i\right)}^2}{\sum _{i\in I_L}{h}_i+\lambda }+\frac{{\left(\sum _{i\in I_R}{g}_i\right)}^2}{\sum _{i\in I_R}{h}_i+\lambda }-\frac{{\left(\sum _{i\in I}{g}_i\right)}^2}{\sum _{i\in I}{h}_i+\lambda }]-\gamma & \text{(17)}\end{array}$Lsplit​=21​[∑i∈IL​​hi​+λ(∑i∈IL​​gi​)2​+∑i∈IR​​hi​+λ(∑i∈IR​​gi​)2​−∑i∈I​hi​+λ(∑i∈I​gi​)2​]−γ(17)