自然语言处理学习笔记

学习笔记-XGBOOST

2020-03-24  本文已影响0人  Pluto_wl

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

一 预备知识

  1. 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}

  2. 目标函数的定义
    设有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}
    可以将上述目标函数拆分为两部分：

  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}

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

  1. 先来回忆下泰勒公式
    f(x+ \bigtriangleup x)\simeq f(x) + {f}'(x) \bigtriangleup x +\frac{1}{2}{f}''(x) \bigtriangleup x^2 \tag{2.1}
  2. 将式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}
  3. 我们发现上式中只要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)就是我们得参数

三 引入新的符号

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

下图中表示有样本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}

优缺点

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

参考文献

  1. http://ihoge.cn/2018/boosting.html
上一篇 下一篇

猜你喜欢

热点阅读