手推记录-XGboost

xgboost 是集成学习boosting的一种，它的基础分类器是CART，即分类回归树。
下图就是CART树和一堆CART树的示例，用来判断一个人是否会喜欢计算机游戏：

用多棵CART树做预测时，就是将各个树的预测分数相加。

\hat{y_{i}} = \sum_{k = 1}^{K} f_{k} (x_{i}), f_{k} \subseteq K

其中 $K$ 表示有K棵CART树， $f_{k}$ 函数是第 $k$ 棵树得到的分数。

定义目标函数为

o b j = \sum_{i = 1}^{n} l (y_{i}, \hat{y_{i}}) + \sum_{k = 1}^{K} Ω (f_{k})

目标函数包括第一部分的损失函数和第二部分的正则项。
xgboost在训练时，先优化第一棵树，之后第二棵，第三棵……直到优化完K棵树，真个过程如下图所示：

在第t步时，添加了一棵最优的CART树 $f_{t}$ ，这棵最优的CART树 $f_{t}$ 就是在现有的t-1棵树的基础上，使得目标函数最小的那棵CART树，

\begin{aligned} o b j^{(t)} & = \sum_{i = 1}^{n} l (y_{i}, {\hat{y_{i}}}^{(t)}) + \sum_{k = 1}^{K} Ω (f_{k}) \\ = \sum_{i = 1}^{n} l (y_{i}, {\hat{y_{i}}}^{(t - 1)} + f_{t} (x_{i})) + Ω (f_{t}) + c o n s t a n t \end{aligned}

这里的 $Ω (f_{t})$ 是第t步时，当前的CART树的正则项，而 $c o n s t a n t$ 就是前t-1棵树的正则项了。
将损失函数进行泰勒二阶展开，

o b j^{(t)} = \sum_{i = 1}^{n} [l (y_{i}, {\hat{y_{i}}}^{(t - 1)}) + g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t}) + c o n s t a n t

其中

g_{i} = \frac{\partial l (y_{i}, {\hat{y}}_{i}^{(t - 1)})}{\partial {\hat{y}}_{i}^{(t - 1)}} ， h_{i} = \frac{\partial^{2} l (y_{i}, {\hat{y}}_{i}^{(t - 1)})}{\partial {\hat{y}}_{i}^{(t - 1)}}

再去掉常数项，

o b j^{(t)} \approx \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t})

再看正则项，首先看CART树的另一个定义，

这里的 $w$ 函数是CART树打分的函数， $q$ 函数是将x定位到哪个叶子节点的函数。
xgboost就使用了如下的正则化项，

Ω (f_{t}) = γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2}

将其带入到目标函数，

\begin{aligned} o b j^{(t)} & \approx \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t}) \\ = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \\ = \sum_{j = 1}^{T} [\sum_{i \in I_{j}} g_{i} + \frac{1}{2} (\sum_{i \in I_{j}} h i + λ) w_{j}^{2}] + γ T \\ = \sum_{j = 1}^{T} [G_{j} + \frac{1}{2} (H_{j} + λ) w_{j}^{2}] + γ T \end{aligned}

其中将 $\sum_{i \in I_{j}} g_{i}$ 简化为 $G_{j}$ ，将 $\sum_{i \in I_{j}} h_{i}$ 简化为 $H_{j}$ 。

对于第t棵CART树的某一个确定的结构（可用 $q (x)$ 表示），所有的 $G_{j}$ 和 $H_{j}$ 都是确定的。而且上式中各个叶子节点的值 $w_{j}$ 之间是互相独立的。上式其实就是一个简单的二次式，我们很容易求出各个叶子节点的最佳值以及此时目标函数的值。

对 $w_{j}^{*}$ 的一个直观的解释是，假设分到 j 这个叶子节点上的样本只有一个，那么

w_{j}^{*} = (\frac{1}{h_{j} + λ}) * (- g_{j})

这个式子告诉我们， $w_{j}^{*}$ 的最优值就是负的梯度乘以一个系数，这个系数类似于随机梯度下降中的学习率。 $h_{j}$ 越大，这个系数越小，也就是学习率越小。 $h_{j}$ 越大代表在该点附近梯度变化非常剧烈，此时，我们在使用反向梯度更新时步子就要小，也就是权重系数要小。

$o b j^{*}$ 则是衡量了第t棵树结构的好坏。与叶子节点的值可是无关的。 $o b j^{*}$ 只和 $G_{j}$ 和 $H_{j}$ 和 $T$ 有关，而它们又只和树的结构 $(q (x))$ 有关。

有了评判CART树的标准，我们就可以构造出最优的第t棵树，怎么构造？树的结构有很多，不能每个结构都计算一次 $o b j^{*}$ 来确定哪个结构做最好。这里就采用逐步学习出最佳的树结构。当样本输入时，先找一个特定的特征j,然后在找该特定的值c，当特征j的值小于c时分到左节点，大于c分到右节点。
问题是怎么决定j和c，xgboost采用的是遍历。

我们以上文提到过的判断一个人是否喜欢计算机游戏为例子。最简单的树结构就是一个节点的树。我们可以算出这棵单节点的树的好坏程度obj*。解设我们先按年龄分，先将这一家五口人按照年龄做个排序

从左至右扫描，找出所有可能的切分点。当切分点确定时，用下列式子作为切分点好坏的标准。

这里的 $G a i n$ 其实是切分前后的差值。如果是正的，而且值越大说明 $o b j^{*}$ 下降得越多，如果是负数，也就是说，左边的这一项小于 $γ$ 项，说明切分后 $o b j^{*}$ 反而变大了。其实 $γ$ 是可以自己设定的阈值，也就说这个值越大，对切分点的要求就越严格。

递归地调用这个切分过程，就能获得一个相对较好的树结构。得到了最优的树结构，也就能找到最优的叶子节点，这样就完成了找出第t棵树的目的。之后再进行第t+1棵树，直到K棵树完成。

相关推荐