集成算法-XGBoost

作者: 柠檬有点萌 | 来源:发表于2021-09-22 23:23 被阅读0次

Python集成学习算法
11 集成学习 - XGBoost案例 - 波士顿房价进行预测
集成学习(Ensemble learning)
集成算法-XGBoost
一文读懂机器学习大杀器XGBoost原理
GBDT进化->XGBoost & LightGBM简记
bagging算法
XGBoost算法
XGBoost算法原理小结
071 XGBoost

前面我们已经详细介绍了集成算法中的Adaboost和GBDT算法，今天我们继续来介绍一下目前最火的集成算法-XGBoost。

一、XGBoost介绍

XGBoost的全称是 eXtreme Gradient Boosting，翻译成中文就是“极端梯度提升”。它是陈天奇博士提出来的一种梯度提升算法，不同于传统的Gradient Boosting，XGBoost是一种Newton Boosting，它用二阶泰勒展开式去近似损失函数，然后通过让损失函数最小化，来求出最优的树结构以及叶子节点的值。XGBoost还在Gradient Boosting的基础上做了很多改良，例如在损失函数里增加了正则化项，训练基学习器的时候可以使用列采样，这些都能防止学习器过度拟合。

XGBoost算法流程

输入:
　　训练集 $D=\left \{ (\boldsymbol{x}_{1},y_{1}),(\boldsymbol{x}_{2},y_{2}),...,(\boldsymbol{x}_{N},y_{N}) \right \}$
　　损失函数 $l(y,f(x))$
　　弱学习器的个数 $T$
　　树复杂度超参数 $\lambda$ 和 $\gamma$
　　学习率 $\epsilon$

过程：

初始化一个常数值 $\hat{y}^{0}=\mathop{\arg\min} _{w}\sum_{i=1}^{N}l(y_{i},w)$
For $t$ = 1 to $T$
2.1 求出每个样本的一阶导(gradients)和二阶导(hessians)
$g_{it}=\left [ \frac{\partial l(y_{i},f(x_{i}))}{\partial f(x_{i})} \right ]_{f(x)=\hat{y}^{(t-1)}}$
$h_{it}=\left [ \frac{\partial ^{2} l(y_{i},f(x_{i}))}{\partial f(x_{i}) ^{2} } \right ]_{f(x)=\hat{y}^{(t-1)}}$

2.2 用 $\left \{ (x_{i},(g_{it},h_{it}))\right \}_{i=1}^{N}$ 去拟合一颗决策树 $f_{t}(x)$ ，目标是使总体损失函数最小化。

目标函数为： $Obj ^{(t)} \simeq \sum_{j=1}^{T} \left [ G_{j} w_{j} + \frac{1}{2} ( H_{j}+\lambda)w^{2}_{j} \right ]+\gamma T$ 其中 $T$ 是叶子节点的个数， $G_{j}$ 是划分到叶子节点 $j$ 的所有样本的 $g_{it}$ 和， $H_{j}$ 是划分到叶子节点 $j$ 的所有样本的 $h_{it}$ 和；

(1) 通过最小化目标函数 $Obj$ ，求得 $f_{t}(x)$ 中每个叶子节点对应的最优 $w^{*}_{j}$
$w^{*}_{j}=-\frac{G_{j}}{(H_{j}+\lambda)}$

(2) 选取最佳变量以及最佳分割点的度量标准是
$Gain= \frac{G^{2}_{L}}{H_{L}+\lambda} + \frac{G^{2}_{R}}{H_{R}+\lambda} - \frac{(G_{L}+G_{R})^{2}}{H_{L}+H_{R}+\lambda } - \gamma$

通过选取让 $Gain$ 最大的最佳分组变量以及最佳分割点来达到让损失函数最小化的目的；

2.3 更新后的模型
$\hat{y}^{(t)}=\hat{y}^{(t-1)}+\epsilon f_{t}(x)$ 其中 $\epsilon$ 是学习率，是一个超参数。

2.4 循环直到满足终止条件。

二、XGBoost的推导

我们知道，XGBoost也是一种加法模型+前向分步算法。
加法模型就是基模型的组合方式是通过相加的形式；
前向分步学习算法是用来解决加法模型优化问题的，通过循环迭代，每一步都固定前面的基模型不变，只训练当前的基模型，通过让总体目标函数最小来求得本次最优的基模型 $f(x)$ ，循环迭代，以此来达到让总体目标函数最小化的目的，这样可以简化优化的复杂度。

上面我们已经知道了每个基模型最佳分组变量以及最佳切割点的选取标准，以及叶子节点值的计算公式。下面我们来看看这些是如何得来的。

XGBoost模型可以表示为：
$\hat{y}_{i}^{(t)}=\hat{y}_{i}^{(t-1)}+f_{t}(x_{i})$

1、目标函数推导

(1) 原始目标函数

设在第 $t$ 步时，目标函数为：
$Obj ^{(t)} = \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{(t)}) + \sum_{i=1}^{t} \Omega (f_{i})$
　　　　 $= \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{(t-1)} + f_{t}(x_{i}) ) + \Omega (f_{t}) + constant$ 　　　　 $(1)$
我们的目的是找到让目标函数到达最小值的 $f_{t}$ 。

(2) 泰勒展开后的目标函数

了解AdaBoost的人就会想，为什么要用泰勒展开式去近似损失函数呢，为什么不直接通过求导损失函数来获得最佳的 $f_{t}$ 呢，因为AdaBoost的损失函数是固定的(指数损失函数)，而XGBoost的损失函数可以任意设置，损失函数多种多样，不是所有的损失函数都可以通过求导的方式来顺利的求出最佳 $f_{t}$ ，所以我们想到了用循环迭代的方式去一步步逼近最优值。这种思想和优化算法里的牛顿法思想是一致的。
通过用泰勒展开式来近似上面的目标函数，每次的基模型的训练目标都是让近似的目标函数达到最低点，循环迭代来达到让总体目标函数最小化的目的。

我们知道二阶泰勒展开式为：
$f(x+Δx) \simeq f(x) + {f}'(x) Δx +\frac{1}{2} {f}''(x)Δx^{2}$

定义： $g_{i} = \partial _{\hat{y}^{(t-1)}} l (y_{i},\hat{y}^{(t-1)} ) , 　h_{i} = \partial ^{2}_{\hat{y}^{(t-1)}} l (y_{i},\hat{y}^{(t-1)} )$
则目标函数可以近似为：
$Obj ^{(t)} \simeq \sum_{i=1}^{n} \left [ l(y_{i},\hat{y}_{i}^{(t-1)}) + g_{i}f_{t}(x_{i}) +\frac{1}{2}h_{i}f^{2}_{t}(x_{i}) \right ] +\Omega (f_{t}) + constant$
由于 $t-1$ 步的模型已经固定，所以 $l(y_{i},\hat{y}_{i}^{(t-1)})$ 是一个定值。
移除掉常数部分，目标函数变成：
$Obj ^{(t)} \simeq \sum_{i=1}^{n} \left [ g_{i}f_{t}(x_{i}) +\frac{1}{2}h_{i}f^{2}_{t}(x_{i}) \right ]+\Omega (f_{t})$ 　　　　 $(2)$

定义基模型的复杂度为：
$\Omega (f_{t})= \gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T}w^{2}_{j}$
其中 $T$ 是叶子节点的个数， $w_{j}$ 是每个叶子节点的分数

则 $f_{t}(x)=w_{q(x)}, w \in \mathbb{R}^{T} , q: \mathbb{R}^{d} \rightarrow \left \{ 1,2,...T \right \}$

代入 $(2)$ 式得：
$Obj ^{(t)} \simeq \sum_{i=1}^{n} \left [ g_{i}f_{t}(x_{i}) +\frac{1}{2}h_{i}f^{2}_{t}(x_{i}) \right ]+\Omega (f_{t})$ 　　　　
　　　　 $= \sum_{i=1}^{n} \left [ g_{i}w_{q(x_{i})} +\frac{1}{2}h_{i}w^{2}_{q(x_{i})} \right ]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T}w^{2}_{j}$
　　　　 $= \sum_{j=1}^{T} \left [ ( \sum_{i \in I_{j}}^{}g_{i})w_{j} + \frac{1}{2} ( \sum_{i \in I_{j}}^{}h_{i}+\lambda)w^{2}_{j} \right ]+\gamma T$
定义： $G_{j} = \sum_{i \in I_{j}}^{}g_{i} ,　H_{j} = \sum_{i \in I_{j}}^{}h_{i}$
损失函数变成：
$Obj ^{(t)} \simeq \sum_{j=1}^{T} \left [ G_{j} w_{j} + \frac{1}{2} ( H_{j}+\lambda)w^{2}_{j} \right ]+\gamma T$ 　　　　 $(3)$

2、基模型 $f_{t}(x)$ 的确定

有了上面(3)式的目标函数，就可以指引我们找到让目标函数最小化的树结构以及叶子节点的值。

(1) 叶子节点分数确定

首先假设当前需要训练的基模型树结构是固定的，我们先来求出让目标函数最小化的叶子节点分数。

由于树是固定的，那么T的值也固定了， $λ$ 和 $γ$ 是事先设置的超参数， $g_{i}$ 和 $h_{i}$ 是 $t-1$ 步模型中每个样本的一阶导和二阶导， $t-1$ 步模型也是固定的，所以 $g_{i}$ 和 $h_{i}$ 也是一个固定的值。所以(3)式中的未知参数只有一个 $w_{j}$ 。

那么(3)式其实可以看成是一个单变量二次函数。我们知道二次函数 $y=ax^2+bx+c$ 取得极值点的 $x=-b/2a$ ，代入到(3)式得：
最优的叶节点分数 $w^{*}_{j}=-\frac{G_{j}}{(H_{j}+\lambda)}$
最小的损失值 $Obj= - \frac{1}{2} \sum_{j=1}^{T} \frac{G^{2}_{j}}{ H_{j}+\lambda }+\gamma T$ 　　　　 $(4)$

(2) 树结构确定

当树的结构确定时，我们前面已经推导出其最优的叶节点分数以及对应的最小损失值。
现在我们不希望固定树结构，希望找到最优的树结构，但是，这里有无穷多的树结构，怎么确定树的结构呢。有2种思路：
① 暴力枚举所有可能的树结构，选择损失值最小的，但是这是一个NP难问题；
② 贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的变量以及切割点；
在实践中，我们采用贪婪的学习方式。

已知最小的损失值 $Obj= - \frac{1}{2} \sum_{j=1}^{T} \frac{G^{2}_{j}}{ H_{j}+\lambda}+\gamma T$ ，其中 $\frac{G^{2}_{j}}{H_{j}+\lambda}$ 衡量了每个叶子节点对总体损失函数的贡献，我们希望总体损失函数越小越好，所以其值越大越好。

由于我们的树是一个二叉树，因此对叶子节点进行分裂，分裂前后的增益定义为：
$Gain= \frac{G^{2}_{L}}{H_{L}+\lambda} + \frac{G^{2}_{R}}{H_{R}+\lambda} - \frac{(G_{L}+G_{R})^{2}}{H_{L}+H_{R}+\lambda } - \gamma$

我们期望 $Gain$ 的值越大越好，所以当对一个叶子结点进行分裂时，挑选能让增益最大的变量以及切割点。

(3) 如何确定最佳切割点

方法1：枚举所有特征上的所有可能拆分

图1 该方法有一个显而易见的缺点就是费时费力。

方法2：近似算法，对每个特征，只考察分位点，减少计算复杂度

图2 该方法有2种变体，一种是global方法，一种是local方法。
global方法：在学习每棵树前，提出候选切割点，并在每次分裂时使用相同的拆分建议；
local方法：在每次分裂的时候，重新提出候选切割点；

对于global方法，通常需要更多的候选点，意思就是分位点需要设置得更细一点，因为每次分裂时候选变量的切割点都固定不变。local方法在每次分裂时都会重新提出候选切割点，更适合于更深的树。我们发现local方法确实只需要较少的候选点。如果有足够多的候选变点，global方法可以和local方法一样准确。

在实际应用的时候，通常不是简单的按个数的分位数去获取候选切割点，而是需要通过二阶导加权来获取候选切割点。

Python集成学习算法
Python集成学习算法---XgBoost 转载原文在讲XGBoost之前，先讲一下GBDT，以及与Adaboo...
11 集成学习 - XGBoost案例 - 波士顿房价进行预测
08 集成学习 - XGBoost概述09 集成学习 - XGBoost公式推导10 集成学习 - XGBoost...
集成学习(Ensemble learning)
摘要：本文是理解adaboost算法与xgboost算法的前奏篇，主要介绍集成学习（Ensemble learni...
集成算法-XGBoost
前面我们已经详细介绍了集成算法中的Adaboost和GBDT算法，今天我们继续来介绍一下目前最火的集成算法-XGB...
一文读懂机器学习大杀器XGBoost原理
作者 | Ray XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在...
GBDT进化->XGBoost & LightGBM简记
很全面的阐释XGBoost：集成学习之Boosting —— XGBoost 大体来看，XGBoost 在原理方...
bagging算法
首先bagging算法是集成学习中两大类算法中的其中一个代表算法，还有另一类的经典算法是Xgboost。他们主要的...
XGBoost算法
概述 XGBoost是GBDT算法的变种，有监督集成学习算法是一种伸缩性强，便捷的并行构建模型的Gradient...
XGBoost算法原理小结
前言 XGBoost（eXtreme Gradient Boosting）全名叫极端梯度提升，XGBoost是集成...
071 XGBoost
背景谈到大杀器XGBoost，我们从集成学习开始讨论，逐步演化到XGBoost 集成学习 bagging减小方差...