XGBoost

1. 背景概述

XGBoost 最初是由 Tianqi Chen 作为分布式（深度）机器学习社区（DMLC）组的一部分的一个研究项目开始的。

最初，它是作为一个终端应用程序开始的，可以使用 libsvm 配置文件进行配置。在希格斯机器学习挑战赛的获胜解决方案中使用后，它在 ML 竞赛圈中广为人知。

不久之后，构建了 Python 和 R 包，并且 XGBoost 现在具有 Java、Scala、Julia、Perl 和其他语言的包实现。这为更多的开发人员带来了该库，并促进了它在 Kaggle 社区中的普及，它已被用于大量比赛。

2. 模型算法

给定回归训练数据集：

$$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$$

其中，${\displaystyle \mathbf x_i\in \mathcal{X}\subseteq R^m}$ 表示实例的特征向量，$y\in \mathcal{Y}\subseteq R$ 。给定实例特征向量$\mathbf x$，输出所属的值 $y$ 。

假设 $T$ 步得到的集成模型为

$${\hat y}_i=f_T(\mathbf{x})=\sum_{t=1}^T h_t(\mathbf{x}),\qquad h_t\in \mathcal{F}$$

其中

$$\mathcal{F}=\{h(\mathbf{x})=w_{q(\mathbf{x})}\}(q:\mathbb{R}^m\rightarrow K,w\in \mathbb{R}^K)$$

是回归树的空间，$q$ 代表将实例映射到叶节点的树结构； $K$ 是叶节点的数量；每个 $h_t$ 都有独立的树结构 $q$ 和叶节点权重 $w$。回归树具有连续的输出值，使用 $w_i$ 代表叶节点 $i$ 的输出。一个实例的最终的预测值是该实例在不同回归树的预测值累加之和。

xgboost 定义损失函数为

$$\mathcal{L}(f)=\sum_il(\hat{y}_i, y_i)+\sum_t \Omega(h_t)$$

其中

$$\Omega(h)=\gamma K + \frac{1}{2}\lambda\|w\|^2$$

$l$ 是一个可微的图损失函数，用于衡量预测值 ${\hat y}_i$ 和目标 $y_i$ 之间的差异。$\Omega(h)$ 用来惩罚模型的复杂性，有助于平滑最终学习权重，避免过拟合。

上面的损失函数包含函数作为参数，无法使用欧几里得空间中传统的优化方法进行优化。加法模型使用前向分步算法进行优化。

使用 $\hat{y}_i^{(t)}$ 代表第 $t$ 次迭代、第 $i$ 个实例的预测值，因此添加 $h_t$ 最小化如下目标

$$\mathcal{L}(f)=\sum_il(y_i,\hat{y}_i^{(t-1)}+h_t(\mathbf{x}_i))+\sum_t \Omega(h_t)$$

对 $l$ 进行泰勒展开

$$l(y_i,\hat{y}_i^{(t-1)}+h_t(\mathbf{x}_i))\thickapprox l(y_i,\hat{y}_i^{(t-1)})+g_ih_t(\mathbf{x}_i)+\frac{1}{2}l_ih^2_t(\mathbf{x}_i)$$

其中 $g_i,l_i$ 分别为损失函数在 $\hat{y}_i^{(t-1)}$ 的一阶与二阶导数

$$g_i=\frac{\partial l(y_i,\hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}\qquad l_i=\frac{\partial l(y_i,\hat{y}_i^{(t-1)})}{\displaystyle \partial^2 \hat{y}_i^{(t-1)}}$$

第一项为常数项，同时定义 $I_i=\{i|q(\mathbf{x}_i)=j\}$ 表示叶子结点 $j$ 中的全部实例。因此，损失函数可以重新写为

$$\begin{aligned} \tilde{\mathcal{L}}^{(t)}&= \sum_i^n [g_ih_t(\mathbf{x}_i)+\frac{1}{2}l_ih^2_t(\mathbf{x}_i)] + \gamma K + \frac{1}{2}\lambda \sum_{j=1}^Kw_j^2 \\ &= \sum_{j=1}^K [(\sum_{i\in I_j}g_i)w_j + \frac{1}{2}(\sum_{i\in I_j}l_i+\lambda)w_j^2] + \gamma K \end{aligned}$$

令上式导数为 $0$，可以求得叶节点 $j$ 的最优输出值为

$$w_j^\ast=-\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}l_i+\lambda}$$

计算出最优的损失函数值

$$\tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2} \sum_{j=1}^K \frac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}l_i+\lambda}+\gamma K$$

上式用来衡量树结构 $q$ 的质量，相当于决策树中的不纯度函数。

类似于决策树的生成，不可能枚举每一种树结构，而是采用贪婪的方式生成左右子树。假设 $I_L$ 和 $I_R$ 表示分割后左右节点到的实例集，令 $I=I_L\cup I_R$，拆分后的损失减少为

$$\mathcal{L}_{split}=\frac{1}{2}\left[ \frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L}l_i+\lambda} +\frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R}l_i+\lambda}- \frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I}l_i+\lambda} \right]-\gamma$$

参考

1. XGBoost: A Scalable Tree Boosting System
2. XGBoost - wiki
3. Taylor公式（泰勒公式）通俗+本质详解 - zhihu
4. xgboost之分位点算法
5. XGBoost解读(2)—近似分割算法

---

Machine Learning

2022-07-27