读懂本文需要机器学习的基本知识,包括决策树的基本知识和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模型,通过用新的决策树拟合上一个决策树的残差形成森林,直到残差收敛。
在预测的时候,对森林中的所有树的叶子节点重的相应类别加权相加,得到最终结果,如图
其他常见的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的关注目标。
- 将$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
$$
- 将不同的样本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
$$
- 合并同类项
$$
\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
机器学习模型比深度学习模型优雅多了:-(
写的真好,希望能继续写出好的博文,加油~
写得很详细
这个叶子点权重怎么计算的啊,一直没看明白,求解答,求解答,求解答
请问怎么理解在Weighted Quantile Sketch中,把loss均分的情况呢?通过均分loss就能找到使增益最大的分裂点吗
为什么没有图呢?