XGBoost all in one

发表于   |   分类于   |   阅读次数 2657

读懂本文需要机器学习的基本知识，包括决策树的基本知识和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，陈天齐的slides，XGBoost的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_value和max_gain_value

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

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

计算score_before
对每一个特征：
    以该特征的值 sort 所有样本
    score_left，score_right = 0, 0
    for i from 1 to n
        把第i个样本划分到左边        
        更新score_left的G和H, GL += gj, HL += hj
        更新score_right的G和H, GR -= gj, HR -= hj
        计算score_left score_right, 计算差值
        维护一个max_gain_split_value和max_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
    2017-03-20 11:15:02

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

  • zzxx reply
    2017-04-17 16:24:43

    写得很详细

  • 王栎汉 reply
    2017-09-10 00:02:02

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

  • 376609914 reply
    2018-03-11 17:12:41

    请问怎么理解在Weighted Quantile Sketch中，把loss均分的情况呢？通过均分loss就能找到使增益最大的分裂点吗