深入解析XGBoost——算法原理篇

作者: 偲偲爸 | 来源:发表于2021-06-28 09:21 被阅读0次

XGBoost，大家都谓之比赛大杀器，凭借着效果好，速度快，支持不同基学习器和自定义损失函数等优点一路高歌猛进，根据Kaggle在2015年的统计，在29支冠军队中，有17支用的是XGBoost，其中有8支冠军队只用了XGBoost。但是（传奇的故事都有个但是），关于XGBoost的论文是在2016年才发表的，可见神器必有其非凡的经历。闲话少叙，开始正题。本文基于XGBoost作者陈天奇的文章：XGBoost: A Scalable Tree Boosting System，尝试解答XGBoost为什么具有上述神迹表现。如有不准确的地方，欢迎拍砖，欢迎讨论

首先简单地对XGBoost的个优点作出一个解释：

效果好——采用Boosting的方式更加关注降低偏差提升精度，使用 $L2$ 正则项降低模型负责度提升泛化能力

速度快——对分裂点寻找算法进行优化，在实现中采用并行、缓存、核外计算等手段优化提速

支持不同基学习器——可选择树模型的gbtree和dark，或者选择线性模型的gblinear

自定义损失函数——损失函数二阶泰勒展开，使得损失函数和目标函数解耦

XGBoost的创新贡献：

XGBoost是一个高度可扩展的梯度提升机器学习系统
提出理论上合理的加权分位数方法用于寻找最佳分裂点
在并行生成树过程中引入新的稀疏数据处理方法
在生成树实现中采用了缓存感知块结构的核外计算

XGBoost(eXtreme Gradient Boosting)是对梯度提升树的高效实现，本质上还是一个GBRT(Gradient Boosted Regression Trees)。但是作者进行了算法和工程上许多优化改进，充分利用内存和CPU潜能把速度和效率发挥到极致。

我们分算法改进和工程实现优化两个方面对XGBoost进行深入理解下。

1. 算法详解

Warning：前方将有大波公式来袭，建议屏蔽公式只看文字部分。我们将按照模型——策略——算法的模式进行抽丝剥茧仔细聊聊这个神器。坐好了，发车...

XGBoost本质上是一个GBRT。GBRT也称为GBM(Gradient Boosting Machine)或MART（Multiple Additive Regeression Trees）由Friedman在2001年提出。GBM通过在函数空间中实现梯度下降来构造前向解法的贪心加性模型。借鉴参数空间中的梯度下降的策略，沿着函数空间中负梯度方向同样会减小误差，这也是GBM中梯度的体现。

在此不对GBRT展开解释，我们着重关注作者对GBRT算法的改进。而这些改进主要体现在正则项和目标函数的重构上。

1.1 Tree Boosting模型

给定数据集 $\mathcal{D}=\left \{\left(\mathbf{x}_{i}, y_{i}\right)\right\}\left(|\mathcal{D}|=n, \mathbf{x}_{i} \in \mathbb{R}^{m}, y_{i} \in \mathbb{R}\right)$ ，一个基于 $K$ 个树构成的集成模型可以是一个加法模型：
$\hat{y}_{i}=\phi\left(\mathbf{x}_{i}\right)=\sum_{k=1}^{K} f_{k}\left(\mathbf{x}_{i}\right), \quad f_{k} \in \mathcal{F}\\$
其中， $\mathcal{F} = \{ f(\mathbf{x})=w_{q(\mathbf{x})} \}(q: \mathbb{R}^{m} \rightarrow T, w \in \mathbb{R}^{T} )$ 是由CART回归树构成的函数空间。 $q$ 表示一个树的结构，将样本数据映射到对应叶子节点上， $T$ 是树的叶子节点数。一棵树 $f_k$ 由树结构 $q$ 和叶子权重 $\omega$ 唯一确定。

对一个新的样本数据，根据树的决策规则将其映射到叶子节点上，并对各叶子节点的权重得分求和得到该样本数据的预测值。

1.2 极小化损失策略

针对如上加法模型，学习器的目标是确定加法模型中的各个树 $f_i$ ，以使得目标函数最小化，这样的树就是要构建最优树。作者为GBRT的目标函数加入了正则项 $\Omega$ ，得到XGBoost的目标函数：
$\begin{array}{l}{\mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\bbox[yellow,2pt]{\sum_{k} \Omega\left(f_{k}\right)}} \\ {\text { where } \Omega(f)=\gamma \underset{叶子数}{\underbrace{T}}+ \underset{L2正则}{\underbrace{\frac{1}{2} \lambda\|w\|^{2}}}}\end{array} \\$
其中，损失函数 $l$ 必须是可微的凸函数。正则项 $\Omega$ 可以降低模型的复杂度， $L2$ 正则项有助于平滑最终学到的权重，以避免过拟合。当然这里为什么没有选择 $L1$ 正则，作者没有提到这个问题。

这样求Tree Boosting模型就转化为一个求解最优化的问题：
$\begin{array}{l} {\underset{\phi}{\min} \mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right)} \\ \end{array}$

1.3 前向分步算法

模型最终转化为一个优化问题，而且是一个无约束的最优化问题，通常我们的办法是求导并使导数为0，这样求解。但是，这是一个复杂的基于树结构的优化问题，我们无法使用梯度下降这样的数值优化算法进行求解。且慢，我们仔细分析下，对于加法模型，学习或构建过程从上至下的，每一步只学习一个树，逐步逼近优化目标函数。这样逐步求解就可以降低优化算法的复杂度，这就是前向分步算法：
$\begin{aligned} \hat{y}_{i}^{(0)} & =f_0(x_i)=0 \\ \hat{y}_{i}^{(1)} & =f_0(x_i)+f_{1}\left(x_{i}\right)=\hat{y}_{i}^{(0)}+f_{1}\left(x_{i}\right) \\ \hat{y}_{i}^{(2)} & =f_0(x_i)+f_{1}\left(x_{i}\right)+f_{2}\left(x_{i}\right)=\hat{y}_{i}^{(1)}+f_{2}\left(x_{i}\right) \\ & \cdots \\ \underset{t轮迭代的预测}{\underbrace{\hat{y}_{i}^{(t)}}} & =\sum_{k=1}^{t} f_{k}\left(x_{i}\right)=\underset{前t-1轮的预测}{\underbrace{\hat{y}_{i}^{(t-1)}}}+\underset{第t轮训练的树}{\underbrace{f_{t}\left(x_{i}\right)}} \\ \end{aligned}\\$
在第 $t$ 轮迭代中只需要确定树 $f_t(x_i)$ 和模型输出 $\hat{y}_i^{(t)}$ 。那么什么样的树才是这轮中的最佳树呢？
于是，现在的目标变为寻找在第 $t$ 轮迭代中使模型输出在训练数据上损失最小的树，这样的树就是本轮中我们要寻找的最佳树，即：
$\begin{aligned} \arg \underset{f \in \mathcal{F}}{\min} \mathcal{L}^{(t)}(f_t) & =\arg \underset{f \in \mathcal{F}}{\min} \sum_{i} l\left(y_{i}, \color{red}{\hat{y}_{i}^{(t)}}\right)+ \color{blue}{\sum_{k} \Omega\left(f_{k}\right)} \\ & 第t轮中\hat{y}_{i}^{(t-1)}和f_k(x_i), \quad k=1, \cdots ,t-1都是常量 \\ & =\arg \underset{f \in \mathcal{F}}{\min} \sum_{i} l\left(y_{i}, \color{red}{\underset{第t-1轮的预测}{\underbrace{\hat{y}_{i}^{(t-1)}}}+f_t(x_i)}\right)+\color{blue}{\Omega\left(f_{t}\right)+\underset{前t-1轮f_k的和}{\underbrace{constant}}} \end{aligned}\\$
至此，关于求解Tree Boosting加法模型的方法已经确定了，按照前向分步算法迭代地求出每一步中的最优树 $f^*$ 就得到最终模型 $\phi {(\mathbf{x}_{i})}=\sum_{k=1}^{K} f^*_{k}(\mathbf{x}_{i})$ 。

然而，如何求解第 $t$ 轮迭代中的优化问题呢？

根据Boosting模型我们知道 $f_t$ 属于回归树构成的函数映射空间而非数值构成的参数空间，那么在求解这个优化问题时就由原来的参数空间上的梯度下降优化转变为沿着函数空间中负梯度方向优化。

作者通过对二阶泰勒展开之后的目标函数进行优化得到新的目标函数，进而使得问题得到了解决。

对任意函数 $f(x)$ 的二阶泰勒展开为：
$f(x+\Delta x) \simeq f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}\\$
目标函数的二阶的泰勒展开：
$\begin{array}{l} {\mathcal {L}^{(t)} \simeq \sum_{i=1}^{n}\left[\underset{在第t轮中是常量}{\underbrace{l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)}}+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)+\text { constant }} \\ {\text { where } g_{i}=\partial_{\hat{y}^{(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right), \quad h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)} \end{array}$
舍去常数项后得到新的目标函数：
$\begin{aligned} \tilde{\mathcal{L}}^{(t)} & =\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)\\ & = \sum_{i=1}^{n} \frac{1}{2} h_i \left [f_t(x_i)- (-\frac{g_i}{h_i})\right ]^2 + \Omega {(f_t)} + \text{constant} \end{aligned}$
终于，我们确定了新的目标函数。那么，这个新的目标函数有什么优势值得费这么大周章呢？

$\tilde{\mathcal{L}}^{(t)}$ 是关于 $f_t$ 的二次函数(凸函数)，一定存在最优解，理论上保证了收敛
实现了损失函数与目标函数的解耦，支持自定义损失函数（必须是可微的凸函数）
二阶泰勒展开应用到了牛顿法，加速了收敛速度

附上论文中Equation 7 的推导

假设节点在分裂之前的训练样本集为 $I$ ，分裂之后左子节点的训练样本集为 $I_L$ ，右子节点的训练样本集为 $I_R$ 。分裂之后的叶子节点数增加1，因此上面目标函数的第二项由 $\gamma T$ 变为 $\gamma(T+1)$ 。
$\begin{align} \mathcal {L(q_{Before})} &= - \frac{1}{2} \sum^T_{j=1} \frac{(\sum_ {i\in I_j} g_j)^2}{\sum_{i\in I_j} h_i + \lambda} + \gamma T \\ &=-\frac{1}{2} \left[ \sum^{T-1}_{j=1} \frac{(\sum _ {i\in I_j} g_j)^2}{\sum_{i\in I_j} h_i + \lambda} + \frac {(\sum _ {i\in I} g_j)^2}{\sum_{i\in I} h_i + \lambda} \right] + \underset{叶子节点数}{\underbrace{\gamma T}} \end{align}$

$\begin{align} \mathcal {L(q_{After})} &=-\frac{1}{2} \sum^{T+1}_{j=1} \frac{(\sum _ {i\in I_j} g_j)^2}{\sum_{i\in I_j} h_i + \lambda} + \gamma (T+1) \\ &=-\frac{1}{2} \left[ \sum^{T-1}_{j=1} \frac{(\sum _ {i\in I_j} g_j)^2}{\sum_{i\in I_j} h_i + \lambda} + \frac {(\sum _ {i\in I_L} g_j)^2}{\sum_{i\in I_L} h_i + \lambda} + \frac {(\sum _ {i\in I_R} g_j)^2}{\sum_{i\in I_R} h_i + \lambda} \right] + \gamma (T+1) \end{align}$

$\begin{aligned} Gain &= \mathcal L(q_{Before}) - \mathcal L(q_{After})\\ &=\frac{1}{2} \left[ \frac {(\sum _ {i\in I_L} g_j)^2}{\sum_{i\in I_L} h_i + \lambda} + \frac {(\sum _ {i\in I_R} g_j)^2}{\sum_{i\in I_R} h_i + \lambda} -\frac {(\sum _ {i\in I} g_j)^2}{\sum_{i\in I} h_i + \lambda} \right] -\gamma \end{aligned}$

gain=loss(father instances) - (loss(left branch)+loss(right branch))

深入解析XGBoost——算法原理篇

1. 算法详解

1.1 Tree Boosting模型

1.2 极小化损失策略

1.3 前向分步算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读