XGBoost详解


The impact of the system has been widely recognized in a number of machine learning and data mining challenges. Take the challenges hosted by the machine learning competition site Kaggle for example. Among the 29 challenge winning solutions published at Kaggle’s blog during 2015, 17 solutions used XGBoost. Among these solutions, eight solely used XGBoost to train the model, while most others combined XGBoost with neural nets in ensembles. For comparison, the second most popular method, deep neural nets, was used in 11 solutions.

以上是XGBoost的主要作者陈天奇在论文里对该算法有效性的说明。

本文分成三部分:

  1. 有监督学习的关键概念
  2. XGBoost算法详解
  3. 从最简单的决策树到XGBoost的过程
  4. 对XGBoost的一些思考

一、有监督学习的关键概念


二、XGBoost算法详解

在XGBoost中,我们在一个迭代的过程中,每一次迭代种一棵树,种这一棵树的目的是与之前的树合起来,使预测值在梯度方向上与准确值接近。

现在,问题1:

为了解决这个问题,我们定义一个目标函数Obj,第t次迭代的目标函数写成Obj^{(t)}

Obj^{(t)} =L(\theta)+\Omega(\theta)
(y_i是准确值,\hat{y_i}^{(t)}是本轮t给出预测值) =L(y_i,\hat{y_i}^{(t)})+\Omega(\theta)
(将\hat{y_i}^{(t)}展开) =L(y_i,\hat{y_i}^{(t-1)}+\color{red}{f_t(x)})+\Omega(\theta)

上式中\Omega是正则化项,防止模型过拟合,无论如何,Obj主要刻画的是预测值和真实值的差距。我们现在的目的就是让当前次迭代中种出来树使Obj最小。这就解决了问题1✅

问题2:

在思考XGBoost的时候一定要有这样一个概念:“树就是函数,函数就是树”。上式中的f_t(x)是我们要找的函数,通过树的形式来实现。我们知道树从最初的一个节点开始生长,是不断分叉的过程;我们的想法是,通过

  1. 改变节点上用于分叉的特征
  2. 改变特征的阈值

一遍遍尝试分叉的可能性,看看哪种树的形态可以算出最低的Obj^{(t)}

要解决问题2,我们尝试提出并解决问题3:

回到Obj^{(t)}的计算。

Obj^{(t)} =L(\theta)+\Omega(\theta)
(\hat{y_i}^{(t)}是本轮t给出预测值) =L(y_i,\hat{y_i}^{(t)})+\Omega(\theta)
(将\hat{y_i}^{(t)}展开) =L(y_i,\hat{y_i}^{(t-1)}+{f_t(x_i)})+\Omega(\theta)
(展开为n个样本的损失函数) =\Sigma_{i=1}^nl(y_i,\hat{y_i}^{(t-1)}+{f_t(x_i)})+\Omega(f_t)+\mathbf{C}

感觉有点算不下去了,不过泰勒展开在这里可以帮我们一个大忙。要是不记得泰勒展开了:

f(x+\Delta{x})\approx f(x)+f'(x)\Delta{x}+\frac12f''(x)\Delta{x}^2+\cdots

定义:

然后继续展开:

Obj^{(t)} =\Sigma_{i=1}^nl(y_i,\hat{y_i}^{(t-1)}+{f_t(x_i)})+\Omega(f_t)+\mathbf{C}
(展开) = \Sigma^n_{i=1}[l(y_i,\hat{y_i}^{(t-1)})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)+\mathbf{C}
(去掉非变量) = \Sigma^n_{i=1}[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)

定义正则项,刻画一棵树的复杂度

\Omega(f_t)=\gamma\color{red}{ T}+\color{aqua}{\frac12 \lambda \Sigma^t_{j=1}w^2_j}

T是叶子的数目,后面是一个l2 norm。继续刚才的式子:

Obj^{(t)} = \Sigma^n_{i=1}[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)
  = \Sigma^n_{i=1}[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\gamma{ T}+{\frac12 \lambda \Sigma^t_{j=1}w^2_j}

现在式子没有办法化简了,因为L(\theta)是按照n个样本来分的,而\Omega(\theta)是按照T个叶子来分的。既然同一个叶子上的样本函数值也相同,我们可以试图将n个样本转化为T个叶子。

现在一并解决问题2、3

f_t(x)=w_{q(x)},w\in\mathbf{R}^T,q:\mathbf{R}^d\mapsto\{1,2,...,T\}

w是树叶子的权重(得分),q是树的结构;q(x)将输入样本转化为所在叶子的编号。

Obj^{(t)} = \Sigma^n_{i=1}[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\gamma{ T}+{\frac12 \lambda \Sigma^t_{j=1}w^2_j}
  =\Sigma^n_{i=1}[g_iw_q(x_i)+\frac12 h_iw^2_q(x_i)]+\gamma T+\frac12 \lambda\Sigma^T_{j=1}w^2_j
  =\Sigma^T_{j=1}[(\Sigma_{i\in I_j}g_i)w_j+\frac12 (\Sigma_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T
  =\Sigma^T_{j=1}[G_j w_j+\frac12 (H_j+\lambda)w_j^2]+\gamma T
(常量标红) =\Sigma^T_{j=1}[\color{red}{G_j} w_j+\color{red}{\frac12 (H_j+\lambda)}w_j^2]+\gamma T

上式变成一个关于w_j(叶子得分)的一元二次函数。

翻开初中数学课本你就知道,一元二次函数取极值时:

对应地,想要Obj函数取到最小值:

至此,问题2、3也被解决✅

最后,就像前面所说的,通过

  1. 改变节点上用于分叉的特征
  2. 改变特征的阈值

一遍遍尝试分叉的可能性,看看哪种树的形态可以算出最低的Obj^{(t)}。如果Obj函数没法降低,那么就可以停止分叉,开始下一轮迭代了。


三、从最简单的决策树到XGBoost的过程

标📍处请重点阅读。

1.决策树

简介

决策树的特点

被攻克。


📍1.(1) 典型的决策树:ID3(迭代二叉树)

f(p)=-plog(p)

于是我们得到了ID3的训练原理:

H=q_1H(s_1)+q_2H(s_2)+\cdots+q_nH(s_n)

q_is_i的权重

有的地方介绍ID3是讲最大化信息增益,而不是最小化熵


1.(2) 传统CART决策树

CART = Classification And Regression Tree

CART与ID3的区别:

I_G(f)=\Sigma_{i=1}^mf_i(1-f_i)=\Sigma_{i=1}^m(f_i-f_i^2)=1-\Sigma_{i=1}^mf_i^2

📍📍📍1.(3) 回归树

此部分内容来自CMU的讲义 Lecture 10: Regression Trees

此处的回归树比上面的CART更接近于XGBoost中的”CART”基分类器

上图中通过两个特征将一堆车分到六个叶子上,每个叶子有自己的得分。

这里的回归树与XGBoost基分类器的区别在于


2.随机森林

Bagging(Boostrap Aggregating)

训练步骤:

  1. 如果训练集大小为N,则对于每棵树,随机且有放回地从训练集里取n个训练样本(行采样)
  2. 如果每个样本的特征维度是M,则指定一个常数m远小于M,随机从M个特征里选m个特征子集,每次树进行分裂的时候,从这m个子集中选择最优的(列采样)
  3. 每棵树都最大程度生长,不剪枝

一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。由于它们的引入,使得随机森林不容易陷入过拟合,并且具有很好得抗噪能力。

关键问题是如何选择最优的m(或者是范围),这也是随机森林唯一的一个参数

随机森林算法简单解释


📍3.Gradient Boosting 梯度提升

GB算法的步骤


4.GBDT 梯度提升决策树

别名:

在我看来,GBDT已经是80%XGBoost的样子了。整个Boosted tree的概念是建立在将Boosting中每一步加的那一个函数h(x)映射成一棵决策树T。理论上这是完全可行的,因为GBDT的基学习器–回归树–本质上就是每一个输入样本可以对应一个输出值(叶子得分),这与函数的概念完全吻合。

当谈到Boosted tree的基学习器回归树,Tianqi Chen如是说:

有人可能会问它和decision tree的关系,其实我们可以简单地把它理解为decision tree的一个扩展。从简单的类标到分数之后,我们可以做很多事情,如概率预测,排序。

GBDT中的决策树是个弱模型,深度较小一般不会超过5,叶子节点的数量也不会超过10,对于生成的每棵决策树乘上比较小的缩减系数(学习率<0.1),有些GBDT的实现加入了随机抽样(subsample 0.5<=f <=0.8)提高模型的泛化能力。通过交叉验证的方法选择最优的参数。


四、XGBoost的一些思考

XGBoost建立在GBDT的基础上


XGBoost的优化


还有一个问题:xgboost代价函数里加入正则项,是否优于cart的剪枝?

Gain=\Delta Obj = \frac12 [\color{red}{\frac{G_L^2}{H_L+\lambda}} + \color{aqua}{\frac{G_R^2}{H_R+\lambda}} - \color{blue}{\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}}] - \lambda

这个公式形式上跟ID3算法(entropy计算增益)、CART算法(GINI指数计算增益)是一致的,都是用分裂后的某种值 减去 分裂前的某种值,从而得到增益。为了限制树的生长,我们可以加入阈值,当增益大于阈值时才让节点分裂,上式中的gamma即阈值,它是正则项里叶子节点数T的系数,所以xgboost在优化目标函数的同时相当于做了预剪枝。另外,上式中还有一个系数lambda,是正则项里叶子得分的L2模平方的系数,对leaf score做了平滑,也起到了防止过拟合的作用,这个是传统GBDT里不具备的特性。

详细的比较可以参考下面这个表。

目标式 启发式
信息增益 训练损失
剪枝 根据节点数进行正则化
最大深度 函数域的限制
叶子值的平滑 叶子权重的L2正则化