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

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))

最后编辑于：2021.06.28 09:24:07

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,530评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,403评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,120评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,770评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,758评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,649评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,021评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,675评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,931评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,751评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,410评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,004评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,969评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,042评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,493评论 2赞 343

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

1. 算法详解

1.1 Tree Boosting模型

1.2 极小化损失策略

1.3 前向分步算法

推荐阅读更多精彩内容