学习笔记-XGBOOST

作者: Pluto_wl | 来源:发表于2020-03-24 11:30 被阅读0次

XGBOOST是GBDT模型的升级版，同样也用到了adboosting的思想

一预备知识

XGBOOST是前向加法模型，那么有公式：
$\hat{y}^0_i=0 \tag {1.1}$
设 $f_n(x)$ 表示第n棵树的模型，那么就有
$\hat{y}^1_0=\hat{y}^0_i + f_1(x_i) \tag{1.2}$
所以第k次生成的模型为
$\hat{y}^k_i = f_0(x_i) + f_1(x_i) + ...+ f_k(x_i)=\hat{y}^{k-1}_i+f_k(x_i) \tag{1.3}$
目标函数的定义
设有 $N$ 个样本， $K$ 棵树， $f_k(x_i)$ 表示第 $k$ 棵树, $\Omega(f_k(x))$ 表示第k棵树的复杂程度，XGBOOST的损失函数定义为如下：
$obj=\sum^N_{i=1}l(y_i, \hat{y}_i)+\sum^K_{k=1} \Omega(f_k(x)) \tag{1.4}$
可以将上述目标函数拆分为两部分：

第一部分是 $\sum^N_{i=1}l(y_i, \hat{y}_i)$ ,这是普通的损失函数， $l$ 可以是均方差，也可以是其他的损失函数。
第二部分是 $\sum^K_{k=1} \Omega(f_k(x))$ ，表示训练第 $K+1$ 棵的时候，前 $K$ 棵树的复杂程度，需要将所有树的复杂度相加的原因是XGBOOST是前向加法模型，第 $K$ 个模型的结果是前 $K$ 棵树相加而得到的。
如何表示树的复杂度呢？其叶节点的个数、树的深度、和叶结点的值都可以表示复杂度。叶结点可以表示复杂度的原因是叶结点的值越小，需要的树越多，比如目标时是3，当每棵树叶结点的值是1的时候，需要三棵树；当一个树的值为2，一个树的结点为1时，那么就只需要两棵树。

训练第K棵树时
式子1.4为 $obj=\sum^N_{i=1}l(y_i, \hat{y}^{K}_i)+\sum^K_{k=1} \Omega(f_k(x))$
根据前向加法模型展开式 $1.4$
$obj= \sum^N_{i=1}l(y_i, \hat{y}^{K-1}_{i-1}+f_K(x_i)) + \sum^{K-1}_{k=1}\Omega(f_k(x)) + \Omega(f_K(x)) \tag{1.5}$
因为 $\sum^{K-1}_{k=1}\Omega(f_k(x))$ 是前 $K-1$ 棵树的复杂度，所以此部分的复杂度是已知的，将式1.5改写为下列式子：
$obj= \sum^N_{i=1}l(y_i, \hat{y}^{K-1}_{i-1}+f_K(x_i)) + \Omega(f_K(x)) \tag{1.6}$
我们的目标是最小化损失函数：
$obj= \sum^N_{i=1}l(y_i, \hat{y}^{K-1}_{i-1}+f_K(x_i)) + \Omega(f_K(x)) \tag{1.7}$

二使用泰勒级数近似目标函数

先来回忆下泰勒公式
$f(x+ \bigtriangleup x)\simeq f(x) + {f}'(x) \bigtriangleup x +\frac{1}{2}{f}''(x) \bigtriangleup x^2 \tag{2.1}$
将式1.7中的 $\hat{y}^{K-1}_i$ 当作式2.1的 $x$ , $f_K(x_i)$ 当作式2.1的 $\bigtriangleup x$ ，代入到式1.7中得：
$obj = \sum^N_{i=1} l(y_i, \hat y_i^{K-1}) + {l(y_i, \hat{y}^{K-1}_i)}'f_K(x_i) + {l}''(y,\hat y _i^{K-1})f^2_K(x_i) +\Omega(f_K(x)) \tag{2.2}$
我们发现上式中只要 $f_K(x_i)$ 是未知项， $l(y_i, \hat y_i^{K-1})$ 、 ${l(y_i, \hat{y}^{K-1}_i)}'$ 与 ${l(y_i, \hat{y}^{K-1}_i)}''$ 都是已知项，令 $g_i={l(y_i, \hat{y}^{K-1}_i)}', h_i={l(y_i, \hat{y}^{K-1}_i)}''$ ，将 ${l(y_i, \hat{y}^{K-1}_i)}$ 忽略，可将式2.2改为：
$obj = \sum^N_{i=1} g_if_K(x_i) + h_if^2_K(x_i) +\Omega(f_K(x)) \tag{2.3}$
此处需要注意下， $f_K(x)$ 就是我们得参数

三引入新的符号

为了方便之后的计算和表示，我们先引入一些符号

定义 $q_i(x)$ 表示样本 $x$ 属于哪一个叶结点
定义 $W_{q_i（x)}$ 为样本 $x$ 所属结点上的值
定义 $|I_i|_1$ 表示第i个结点上共有多少个样本

下图中表示有样本 $D=\{ (x_1,y_1), (x_2,y_2),(x_3,y_3),(x_4,y_4), (x_5,y_5)\}$ ，样本 $x_1$ 和样本 $x_3$ 决策分类值是15，样本 $x_4$ 的值是12，样本 $x_2$ 和样本 $x_5$ 的值是20。将结点从左到右排列，记为序号1，2，3所以根据上述定义，我们可以得到

$q(x_1)=1,q(x_2)=3,q(x_3)=1,q(x_4)=2,q(x_1)=3$

$W_{q_i（x)}$ 表示样本 $x$ 的预测值，那么 $f_K(x)=W_{q_i（x)}$ ,所以有下列等式
$f_K(x_1)=W_{q_{(x_1)}}=W_1=15,f_K(x_2)=W_{q_{(x_2)}}=W_3=20, f_K(x_3)=W_{q_{(x_3)}}=W_1=15,f_K(x_4)=W_{q_{(x_4)}}=W_2=12, f_K(x_5)=W_{q_{(x_5)}}=W_3=15,$

我们得知第一个结点上有两个样本，所以 $|I_1|=2$ ,第二个结点上有一个样本， $|I_2|=1$ ,结点3上有两个样本，所以 $|I_3|=2$

来自于网络

四树的复杂度

上面说过了，树的复杂度可能由深度、叶结点的个数、叶结点的值决定。我们现在来看看XGBOOST中的复杂度 $\Omega(f_k(x))$ 是如何定义的：
$\Omega(f_k(x))=\sigma T+\frac{1}{2}\lambda \sum^T_{t=1}W^2_t \tag{4.1}$
$T$ 表示有多少个叶节点， $W_t$ 表示第t个结点上的值
$\sigma$ 和 $\lambda$ 都是超参数，需要有人工设置

五

根据三和四，我们可以将式1.7改写为如下形式：
$obj =\sum^N_{i=1} [g_i W_{q_i(x)} +h_i W^2_{q(x_i)} ] + \sigma T + \frac{1}{2} \lambda W^2_{q(x_i)} \tag{5.1}$

$obj=\sum^T_{t=1}[(\sum_{j\in I_t }g_j)W_{q_{x_i}} + \frac{1}{2} (\sum_{j\in I_t}h_j)W^2_{q_{x_i}}] + \sigma T + \frac{1}{2} \lambda W^2_{q(x_i)}\tag{5.2}$
在第二部分的3小部分，我们可以知道 $g_i$ 和 $h_i$ 是已知的，所以 $\sum_{j\in I_t }g_j$ 和 $(\sum_{j\in I_t}h_j)$ 都是常数，使用 $G_t$ 表示 $\sum_{j\in I_t }g_j$ ，使用 $H_t$ 表示 $(\sum_{j\in I_t}h_j)$ ，可以下式
$obj = \sum^T_{t=1}[G_tW_{q_{x_i}} + \frac{1}{2}H_tW^2_{q_{x_i}}] + \sigma T + \frac{1}{2} \lambda W^2_{q(x_i)} \tag{5.3}$
$obj = \sum^T_{t=1}[G_tW_{q_{x_i}} + \frac{1}{2} (H_t +\lambda) W^2_{q(x_i)}]+ \sigma T\tag{5.4}$
上述式子可以看做以 $W_{q_{x_i}}$ 的二次函数，当 $W_{q_{x_i}}=- \frac{G_t}{H_t+\lambda}$ 时，obj取得最值。将 $- \frac{G_t}{H_t+\lambda}$ 代入式5.4得 $obj$ 得极值
$obj= -\sum^T_{t=1} \frac{G^2_t}{H_t+\lambda}+\sigma T \tag{5.5}$

优缺点

优点

正则化：XGBoost 在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score 的 L2 模的平方和。从 Bias-variancetradeoff 角度来讲，正则项降低了模型的 variance，使学习出来的模型更加简单，防止过拟合，这也是 XGBoost 优于传统 GBDT 的一个特性。
并行处理：我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost 在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个 block 结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
对于特征的值有缺失的样本，XGBoost 可以自动学习出它的分裂方向。

缺点

算法参数过多
只适合处理结构化数据
不适合处理超高维特征数据

参考文献

http://ihoge.cn/2018/boosting.html

学习笔记-XGBOOST

一预备知识

二使用泰勒级数近似目标函数

三引入新的符号

四树的复杂度

五

优缺点

参考文献

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

自然语言处理学习笔记

学习笔记-XGBOOST

一 预备知识

二 使用泰勒级数近似目标函数

三 引入新的符号

四 树的复杂度

五

优缺点

参考文献

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

自然语言处理学习笔记

一预备知识

二使用泰勒级数近似目标函数

三引入新的符号

四树的复杂度