XGBoost简介

作者: Jaydu | 来源:发表于2019-02-21 16:37 被阅读1次

XGBoost

Extreme Gradient Boosting(XGBoost)是由华盛顿大学（University of Washington）的陈天奇作为 Distributed (Deep) Machine Learning Community (DMLC) 组员所开发的一个研究项目。在陈天奇与队友一起赢得了Higgs Machine Learning Challenge后，许多的数据科学竞赛队伍使用XGBoost并获得了冠军，促进了该工具在数据科学应用中的广泛使用。

目标函数

在有监督学习中，我们的目标函数可以分解为训练损失和正则化项：
$obj(\theta)=L(\theta)+\Omega(\theta)$
如果对每个样本，训练损失函数为 $l(y,\hat{y})$ ，则 $L(\theta)=\sum\limits_{i=1}^n l(y_i,\hat{y}_i)$
对树模型而言， $\hat{y}=f(x)=w_{q(x)},\ w\in R^T,\ q:\mathbb{R}^d\rightarrow\{1,2,\cdots,T\}$ ，其中 $w_i$ 是第 $i$ 个叶子结点上的socre，每个样本点 $x$ 会落在某一个叶子节点 $q(x)$ 上， $T$ 是叶子数。在XGBoost中，树的复杂度描述为：
$\Omega(f)=\gamma T+\frac{1}{2}\lambda \sum\limits_{i=1}^Tw_i^2$
当然还可以加上其他正则项，如L1正则（对应正则化系数 $\alpha$ ）等。

Boosting

Boosting的过程，是拟合一个加性模型。假设我们已经训练了 $t-1$ 步，对应的模型为 $\hat{y}^{(t-1)}(x)=\sum\limits_{k=1}^{t-1}f_k(x)$
第 $t$ 步，我们的目标是找到 $f_t(x)$ ，以最小化目标函数：
$\begin{align} \min\limits_{f_k}\quad &obj^{(t)}=\sum\limits_{i=1}^n l(y_i,\hat{y}_i^{(t)})+\Omega(f_t)\\ where\quad & \hat{y}_i^{(t)} = \sum\limits_{k=1}^{t}f_k(x_i)\\ \end{align}$

将样本损失函数在 $y'=\hat{y}^{(t-1)}$ 处做二阶泰勒展开,
$l(y,y')=l(y,\hat{y}^{(t-1)})+\dfrac{\partial l(y,y')}{\partial y'}\Bigg|_{y'=\hat{y}^{(t-1)}}f_t(x)+\frac{1}{2}\dfrac{\partial^2 l(y,y')}{\partial y'\partial y'}\Bigg|_{y'=\hat{y}^{(t-1)}}f_t^2(x)+O(f_t^2(x))$
对应地，将每个样本代入可得：
$obj^{(t)}=\sum\limits_{i=1}^n \left[l(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t)$
其中
$\begin{align} g_i&=\dfrac{\partial l(y_i,y')}{\partial y'}\Bigg|_{y'=\hat{y}_i^{(t-1)}} \\ h_i&=\dfrac{\partial^2 l(y_i,y')}{\partial y'\partial y'}\Bigg|_{y'=\hat{y}_i^{(t-1)}}\\ \end{align}$
而 $\sum\limits_{i=1}^n l(y_i,\hat{y}_i^{(t-1)})$ 是与 $f_t(x)$ 无关的，因此，我们的目标函数可以简化为：
$obj^{(t)}\approx\sum\limits_{i=1}^n \left[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t)$

第 $t$ 棵树的目标函数是理论目标函数最优值与前 $t-1$ 棵树预测的目标函数值的残差，即以目标函数的负梯度来作为第 $t$ 棵树的学习目标。

树的分裂准则

我们可以将目标函数重写为
$\begin{align} obj^{(t)}&\approx \sum\limits_{i=1}^n[ g_i w_{q(x_i)}+ \frac{1}{2}h_i w^2_{q(x_i)}]+\gamma T+ \frac{1}{2}\lambda \sum\limits_{j=1}^Tw_j^2\\ &= \sum\limits_{j=1}^T\left[\left(\sum\limits_{i\in I_j}g_i\right)w_j+ \frac{1}{2}\left(\sum\limits_{i\in I_j}h_i+\lambda\right)w_j^2\right]+\gamma T\\ &\triangleq \sum\limits_{j=1}^T\left[G_jw_j+ \frac{1}{2}\left(H_j+\lambda\right)w_j^2\right]+\gamma T\\ \end{align}$
其中 $I_j=\{i | q(x_i) = j\}$ 。因此，
$\begin{align} w_j^*&=-\frac{G_j}{H_j+\lambda}\\ obj^*&=-\frac{1}{2} \sum\limits_{j=1}^T \dfrac{G^2}{H_j+\lambda}+\gamma T \end{align}$
因此后者可以用来衡量树结构的好坏，用来决定树的分裂。这里我们定义结点分裂的增益为
$\begin{align} Gain&=\frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right]-\gamma \end{align}$

特性

支持线性分类器、DART（Dropouts meet Multiple Additive Regression Trees）以及Tweedie Regression；支持分类、回归、排序任务；
二阶导信息。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
正则化项。xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
缩减（Shrinkage）。相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
对缺失值的处理。xgboost把缺失值当做稀疏矩阵来对待，本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。
支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点，大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中计算Gain按最大值找出最佳的分割点。
特征重要性。XGBoost在训练的过程中给出各个特征的评分，Gain、Cover、Frequency，从而表明每个特征对模型训练的重要性。

常见问题

XGBoost在什么地方做的剪枝，怎么做的？
答：XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
XGBoost如何分布式？特征分布式和数据分布式？各有什么存在的问题？
答：XGBoost在训练之前，预先对数据按列进行排序，然后保存block结构。（1）特征分布式/特征间并行：由于将数据按列存储，可以同时访问所有列，那么可以对所有属性同时执行split finding算法，从而并行化split finding（切分点寻找）；（2）数据分布式/特征内并行：可以用多个block(Multiple blocks)分别存储不同的样本集，多个block可以并行计算。
问题：（1）不能从本质上减少计算量；（2）通讯代价高。

XGBoost简介

XGBoost

目标函数

Boosting

树的分裂准则

特性

常见问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法小白菜