XGBoost all in one


读懂本文需要机器学习的基本知识,包括决策树的基本知识和ensemble tree的基本知识,如果不关注传统GBDT和XGBoost的区别,GBDT的知识不是必须的。

loss function和object function向来纠缠不清,本文倾向于loss func == obj func,倾向于一个loss func/obj func的组成为training loss + regularization。

XGBoost是截止目前为止相当棒的Tree ensemble模型,是工业界和kaggle、天池这样的data science必备的一个模型/工具。

XGBoost是一个工具,也是一个gradient boosted tree的模型,无论公式还是实现,和传统GBDT都有一些区别。
关于XGB最权威的资料,参考XGBoost的Github陈天齐的slidesXGBoost的paper

Boosted Tree

Boosted Tree,是一类拟合残差的tree ensemble模型,通过用新的决策树拟合上一个决策树的残差形成森林,直到残差收敛。
在预测的时候,对森林中的所有树的叶子节点重的相应类别加权相加,得到最终结果,如图
boosted tree

其他常见的tree ensemble模型还有random forests, GBM等。

两座大山

在Boosted Tree的学习过程中,主要关注“两座大山”,

  • 其一是找到最好的树的结构
  • 其二是找到最好的叶子权重

这两者是Boosted Tree的学习核心。我们来看XGBoost如何进行这两者的学习,以及它与传统GBDT有什么区别。

XGBoost的推导

目标函数

一般机器学习的目标函数

一般地,我们对机器学习的模型,都有如下(1)所示的Object function:
$$
\begin{equation}
Obj(\Theta) = L(\Theta) + \Omega(\Theta)
\end{equation}
$$

其中,$L(\Theta) = \sum_{i=1}^{n}{L(y_i, \hat{y_i})} $是training loss,度量了预测值和真实值之间的误差,是目标函数的主要构成, $\Omega(\Theta)$是正则项,当做loss加入object function,是为了控制模型的复杂程度,是目标函数的次要构成。
其中,training loss标识了模型误差的度量,尽量减小training loss会使模型更精确;正则项则把模型参数的大小纳入模型的考量范围,模型参数越多/越大/取值越悬殊,则模型越复杂,越可能出现过拟合的情况。因此把正则加入目标函数中,以此来惩罚模型的复杂度。

常见的training loss有:

  • square loss: $ l(y_i, \hat{y_i}) = \left (\hat{y_i}-y_i \right )^2$
  • 0/1 loss: $ l(y_i, \hat{y_i}) = 1 \iff \hat{y_i} \neq y_i$
  • cross entropy loss: $l(y_i, \hat{y_i}) = -({\hat{y_i} \log(y_i) + (1-\hat{y_i}) \log (1-y_i)})$
  • ...

正则项则通常选用:

  • l1 正则 $ \Omega(\Theta) = \sum_{i=1}^{n}\Vert w\Vert $
  • l2 正则 $ \Omega(\Theta) = \sum_{i=1}^{n}\Vert w\Vert^2 $
  • ...

等等。f

注意: training loss的选取和正则项的选择,因具体问题而异。

XGBoost的正则项选择

对于一个Tree ensemble模型,模型的复杂度当然不仅仅包括参数大小,也包括树的结构:树越多,每棵树越深,叶子节点越多,则模型越复杂,越容易陷入过拟合的窘境。
传统Tree ensemble会通过剪枝的策略,对不那么重要的树枝来进行剪枝来达到削减模型复杂程度,降低过拟合风险的目的。
XGBoost则选择直接把叶子节点的个数写进正则项中,如式(2)所示:
$$
\begin{equation}
\omega(\theta) = \gamma T + \frac{1}{2}\Vert{\mathit{w}}\Vert^2
\end{equation}
$$
即,以$\gamma$的系数惩罚森林的总叶子数量$T$,同时对叶子权重$w$进行l2正则。
当然了,l2正则项也是可以有参数$\lambda$的,XGBoost的正则项最终如下式所示:
$$
\begin{equation}
\omega(\theta) = \gamma T + \lambda\frac{1}{2}\Vert{\mathit{w}}\Vert^2
\end{equation}
$$
其中$\gamma$和$\lambda$就是XGBoost的两个超参数了。

为方便起见,后文可能同时使用$\Omega(\Theta)$和$ \gamma T + \Vert{w}\Vert^2/{2}$的写法。

此时,模型的representation和obj function表示为:
model预测$y_i$的representation为所有decision tree的结果加和:
$$
\begin{equation}
\hat{y_i} = \phi(x_i) = \sum_{k=1}^{K}f_{k}(x_i), f_k \in \mathcal{F}
\end{equation}
$$
其中$\mathcal{F}$为所有regression tree function的空间,$f_k(x_i)$是decision tree的函数表示。
loss function/obj function为:
$$
\begin{equation}
\mathcal{L}(\phi) = \sum_{i}l(\hat{y_i}, y_i) + \sum_{k}\Omega(f_k) \quad where \quad \Omega(f) = \gamma T + \frac{1}{2} \Vert w\Vert^2
\end{equation}
$$

XGBoost的object function

考虑第t轮训练,即构造第t棵树时的情况,我们有如下的loss function形式:
$$
\begin{equation}
\mathcal{L}^{t} =\sum_{i=1}^{n} l(yi, \hat{y_i}^{(t-1)} + f_t(x_i)) + \Omega(f_t)
\end{equation}
$$
即,对$x_i$的预测值为第t棵树的预测值加上前t-1棵树的预测值的和。
也可理解为,第t棵树的以前t-1棵树的残差为label值,training loss为第t棵树的估计值$\hat{y_i} = f_t(x_i)$与残差的loss,正则项为第t棵树的正则项$\Omega(f_t)$.

注意,对于第t棵树而言,前t-1棵树的预测值$\hat{y_i}^{t-1}$,与前t棵树的残差$l(y_i, \hat{y_i}^{t-1})$,都是与第t棵树无关的常量

training loss符合泰勒公式的形式$f(x + \Delta x)$, 因此,我们尝试对training loss进行二阶泰勒公式展开。

泰勒公式的二阶展开形式如下:
$ f(x+\Delta x) \approxeq f(x) + f'(x)\Delta x + \frac{1}{2} f''(x) \Delta x^2 $

为简化形式,我们将原函数的一阶导数和二阶导数分别定义为$g_i$和$h_i$。
$$
\begin{equation}
g_i = \frac{\partial l(y_i, \hat{y_i}^{t-1})}{\partial \hat{y_i}^{t-1}}
\end{equation}
$$
$$
\begin{equation}
h_i = \frac{\partial^2 l(y_i, \hat{y_i}^{t-1})}{\partial^2 \hat{y_i}^{t-1}}
\end{equation}
$$
则有:
$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{n}[l(y_i, \hat{y}^{t-1}) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)
$$

我们移除常数项$l(y_i, \hat{y}^{t-1})$,则得到一个更加简单的obj function:

$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{n}[ g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)
$$
至此,obj fucntion的形式已经非常漂亮,是一个典型的二次函数。可是问题在于,loss是sample wise的,而正则项则关注tree structure,两者尚不能统一,仍然不能直接得到一个直观的结果。
我们希望的obj function的形式是易于计算的,所以下一步我们要将training loss从sample-wise转化成tree-structure-wise,试图让obj function仅关注一个东西,然后或许能变得更加简单易于计算。

从sample-wise loss到 tree-structure-wise loss

对于boosted tree森林中的一颗决策树T而言,每一个样本都和T中的某个叶子一一对应,形成映射关系,因此,我们可以定义函数:
$$
j = q(x_i)
$$
即,样本$x_i$对应的叶子节点为$j$。
形象地说,对于下面的一棵树,

样本与叶子(可能)有多对一的关系,即可以定义样本下标集合$I_j$:
$$
I_j = \{i \vert q(x_i) = j\}
$$
即,$I_j$为所有对应到叶子$j$ 的样本的index的集合。
在boosted tree中,每一个叶子$j$都有权重$w_j$,树T对样本$x_i$在第$t$轮的估计值就等于该样本在这棵树上的叶子对应的权重。即:
$$
f_t(x_i) = w_{q(x_i)}
$$
到这里,我们就可以顺利地将样本group by叶子,实现统一obj function的关注目标。

  1. 将$f_t(x)$替换成$w_{q(x)}$,并展开正则项:

$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{n}[ g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t) \
= \sum_{i=1}^{n}[ g_iw_{q(x_i)} + \frac{1}{2}h_iw^2_{q(x_i)}] + \gamma T + \lambda \frac{1}{2}\Vert{\mathit{w}}\Vert^2
$$

  1. 将不同的样本group by leaf

$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{T}[ (\sum_{i\in I_j}g_i)w_j + \frac{1}{2}(\sum_{i\in I_j}h_i)w_j^2] + \gamma T + \lambda \frac{1}{2}\Vert{\mathit{w}}\Vert^2
$$

  1. 合并同类项

$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{T}[ (\sum_{i\in I_j}g_i)w_j + \frac{1}{2}(\sum_{i\in I_j}h_i + \lambda)w_j^2] + \gamma T
$$

此时,我们得到了最理想的Object function的形式。这个形式的Object function有多理想呢?

  • 它只关注tree structure相关信息,没有其他杂质
  • 它的形式依然是一个简单的二次函数的形式,其极值是直接可求得的,换句话说,对于每一棵树,其最佳参数可以在O(1)的时间内求出数值解。这使得XGBoost相对于传统GBDT的求解速度大大提升

简单求解一下这个二次函数的极值,我们有,在给定的tree structure下,最佳的参数取值$ w_j^* $ 和此时的loss:
$$
w_j^* = - \frac{G_j}{H_j + \lambda}
$$

$$
Obj = -\frac{1}{2} \sum^T_{j=1} \frac{G_j^2}{H_j + \lambda} + \gamma T
$$

到此,参数和树的结构两座大山已经解决了一座“参数”。

Tree structure

对于树的结构,一直没有比较优雅的办法来做这件事情,XGBoost也是,sklearn或者MLlib的传统GBDT实现也是,都是在速度和精确度之间做trade of。XGB的做法在几乎不丢失loss的情况下达到了速度数倍的提升。

计算最佳tree structure的指标

Score/Gain

不同的决策树算法有不同的度量(information gain, gini, etc.),用来评价新划分对模型的loss有多少影响。
因为XGBoost已经有了一个需要minimize的object function,XGBoost的score/gain的度量方式就可以简单选取新划分的loss和划分之前的loss的差值,如果新划分让loss变小,换言之,划分前的loss比划分后的loss大,那么就说明划分是有用的。
$$
Gain = loss_{old} - (loss_{newleft} + loss_{newright}) \quad \quad split \ is\ good\ if\ Gain>0\ or\ Gain>threshold
$$

所以Gain的表达式为:
$$
Gain = \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} - \gamma
$$
式中的$\gamma$是因为一次split后,原树的一个叶子节点分裂成两个新的叶子节点,叶子节点数量T增加了1,其权重为$\gamma$。

Finding best split

有了score/gain 函数之后,要寻找到最佳的分裂点,即找到最佳tree structure。现有的boosted tree基本基于贪心的思想,即“每次仅考虑对当前层次/树效果最好的结点作为分裂节点”。传统的GBDT和XGBoost都是在贪心思想的基础上做文章。

一种暴力算法

在贪心的思想下,最简单的方法当然是遍历:

计算score_before
对每一个训练样本的每一个特征:
    以该样本的该特征作为split feature,以该特征值作为split value,计算全部样本的score_left, score_right,计算差值
    维护一个max_gain_split_valuemax_gain_value

这个算法是可行的,不过,时间复杂度稍大(单层就有$O(mn^2)$, m是特征数量,n是样本数量)。

考虑到在每一次split loss的计算中,每个样本对loss的贡献是不变的,我们可以对样本按照feature value做一次pre sort。然后逐个做split value。

计算score_before
对每一个特征:
    以该特征的值 sort 所有样本
    score_leftscore_right = 0, 0
    for i from 1 to n
        把第i个样本划分到左边        
        更新score_leftGH, GL += gj, HL += hj
        更新score_rightGH, GR -= gj, HR -= hj
        计算score_left score_right, 计算差值
        维护一个max_gain_split_valuemax_gain_value                 

时间复杂度降低到$O(mnlgn)$,然而这种方法仍然每次要遍历全部样本,和样本规模相关,样本数量巨大的时候计算量仍然非常大。

Weighted Quantile Sketch

XGBoost则采取了一种trade off,近似地找到best split,就是标题的一种weighted quantile sketch算法。
既然样本数量太大,我们可不可以按比例来选择,从n个样本中抽取k个样本来进行计算,取k个样本中的最优值作为split value,这样就大大减少了运算数量。这就是k分位点选取的思想,即quantile sketch。
要如何抽取k个样本?10000个样本取10个的话,每1000个样本计算一次split value看似可行,其实是不可以的,我们要均分的是loss,而不是样本的数量,而每个样本对loss的贡献可能是不一样的,按样本均分会导致loss分布不均匀,取到的分位点会有偏差
回忆loss function的早期形式:
$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{n}[l(y_i, \hat{y}^{t-1}) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)
$$

对其变形得到:
$$
\mathcal{L}^{t} \approxeq \sum_{i=1}^{n}\frac{1}{2} h_i(f_t(x_i) + \frac{g_i}{h_i})^2 + \Omega(f_t) + constant
$$

这个形式的loss说明了, $x_i$的loss也可以看做是以$-g_i/h_i$作为label的均方误差,乘以大小为$h_i$的权重,换句话说,$x_i$对loss的贡献权重为$h_i$
那么,对loss取k分位点,即是$D_k = \{(x_i, h_i)\}$的序列按权重$h_i$取k分位点即可。
流程如下:

有一点是,这个k分位点的选取是近似的,不能像遍历一样保证取到的split value是最佳的split value。不过经过试验,k取到3的时候,算法性能就已经相差无几了,见下图:

值得注意的是,XGBoost还提出,如果嫌每一层取k分位点慢,可以在第一棵树的时候构建一个全局的k分位点,也能得到类似的性能,不过global quantile sketch的k值选取,要比local quantile sketch 精细一些,实验中发现,全局k分位点取20和局部k分位点取3,得到了近似的效果。

总结

至此,XGBoost的模型部分基本介绍完毕, XGBoost对传统GBDT的改进(算法层面)主要是以下两点:

  • 二阶泰勒展开
  • 更高效的finding best split(近似)

这两点是使得XGB拥有令人惊叹效率的核心所在。思路本身也令人惊叹。

TODO

(本文章,但是好累啊,不想写了)

  • sparse feature的处理
  • 缺失值的处理

(新文章,也好累啊,不想写了)

  • 介绍XGBoost的参数和它们在模型中的位置和作用
  • 调参经验

Reference

[1] XGBoost: A Scalable Tree Boosting System
[2] Overview of tree algorithms from decision tree to xgboost
[3] Introduction to Boosted Trees - Washington
[4] dmlc/xgboost

机器学习模型比深度学习模型优雅多了:-(

Comments
Write a Comment
  • zhuchen reply

    写的真好,希望能继续写出好的博文,加油~

  • zzxx reply

    写得很详细

  • 王栎汉 reply

    这个叶子点权重怎么计算的啊,一直没看明白,求解答,求解答,求解答