文章目录
  1. 1. 学习笔记 | XGBoost
    1. 1.1. 简介
    2. 1.2. 泰勒展开
    3. 1.3. Boosting
    4. 1.4. 目标函数
    5. 1.5. 寻找最优分裂点
    6. 1.6. 算法流程
    7. 1.7. 参数说明
      1. 1.7.1. 通用参数
      2. 1.7.2. Booster 参数
        1. 1.7.2.1. 树模型
      3. 1.7.3. Dart 额外参数
      4. 1.7.4. 线性模型
      5. 1.7.5. 学习任务参数
    8. 1.8. 其他
    9. 1.9. 参考

学习笔记 | XGBoost

XGBoost 在竞赛和工业界使用都非常频繁,能有效的应用到分类、回归、排序,本文对 XGBoost 的详细算法流程进行了较为详细的整理。

简介

XGBoost 是 “Extreme Gradient Boosting” 的缩写,XGBoost 算法的步骤和 GBDT 基本相同,都是首先初始化为一个常数,GBDT 是根据一阶导数,XGBoost 是根据一阶导数 ${g_i}$ 和二阶导数 ${h_i}$,迭代生成基学习器,相加更新学习器。XGBoost 是一种 Boosting 方法,而 Boosting 方法又是集成学习的一个分支。

泰勒展开

泰勒公式是一个用函数在某点的信息描述其附近取值的公式,局部有效性。基本形式是:

一阶泰勒展开:

二阶泰勒展开:

计算机的迭代过程:

假设第 ${t}$ 次迭代的为 ${x^{(t)}}$,则第 ${t+1}$ 次迭代为:${x^{(t+1)} = x^{(t)} + \Delta x}$,则再第 ${x^{(t+1)}}$ 处进行泰勒展开,结果为:

Boosting

Boosting 是一个加法模型,从常数开始迭代,每一轮迭代增加一个函数,每次新添加的函数是基于 以往所有的学习结果的和真实值 之间的残差上学习模型。

${\hat{y_i}^{0} = 0}$

${\hat{y_i}^{1} = f_1(x_i) = \hat{y_i}^{0} + f_1(x_i)}$

${\hat{y_i}^{2} = f_1(x_i) + f_2(x_i) = \hat{y_i}^{1} + f_2(x_i)}$

${\ \ \ \ ……….}$

${\hat{y_i}^{t} = \sum_{k=1}^{t} f_k(x_i) = \hat{y_i}^{t-1} + f_t(x_i)}$

目标函数

  • Training Loss measures how well model fit on training data.
  • Regularization, measures complexity of model.

Regression Tree Ensemble

由于 ${\hat{y_i}^{t} = \hat{y_i}^{t-1} + f_t(x_i)}$。

${Obj^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y_i}^{(t)}) + \sum_{i=1}^{t} \Omega(f_i) = \sum_{i=1}^{n} l \Big(y_i,\ \hat{y_i}^{(t-1)} + f_t(x_i) + \Omega(f_t) \Big) + const}$

对于连续问题,则考虑平方损失:

寻找最优分裂点

对于一个叶子节点,如何进行分裂?

  • ${\frac{G_L^2}{H_L + \lambda}}$:The score of left child.
  • ${\frac{G_R^2}{H_R + \lambda}}$:The score of right child.
  • ${\frac{(G_L + G_R)^2}{H_L + H_R + \lambda}}$:The score of if we do not split.
  • ${- \gamma}$:The complexity cost by introducing additional leaf.

如果 ${Gain > 0}$,则该结点应该分裂,否则,不应该分裂。

算法流程

其中,关于一阶导数,二阶导数有如下定义,其中 ${i}$ 为训练集中的第 ${i}$ 个样本,${I_j}$ 为模型中第 ${j}$ 个叶子节点中的所有训练集样本。

对于一元二次函数:

因此,对于目标函数进行最小化的时候,即二次函数在对称轴时,取得最值。

对于正则化项,${w_i}$ 为第 ${i}$ 个叶节点的值。

${\Omega(f_t) = \gamma T + \frac{1}{2} \gamma \sum_{j=1}^{T} w_j^2}$

  • ${T}$:Number of leaves.
  • ${\sum_{j=1}^{T} w_j^2}$:L2 norm of leaf scores.

参数说明

括号内为 sklearn 参数。

通用参数

  • booster:基学习器类型,gbtree,gblinear 或 dart(增加了 Dropout),gbtree 和 dart 使用基于树的模型,而 gblinear 使用线性模型。
  • silent:使用 0 会打印更多信息。
  • nthread:运行时线程数。

Booster 参数

树模型

  • eta(learning_rate):更新过程中用到的收缩步长,(0, 1]。
  • gamma:在节点分裂时,只有在分裂后损失函数的值下降了,才会分裂这个节点。Gamma 指定了节点分裂所需的最小损失函数下降值。这个参数值越大,算法越保守。
  • max_depth:树的最大深度,这个值也是用来避免过拟合的。
  • min_child_weight:决定最小叶子节点样本权重和。当它的值较大时,可以避免模型学习到局部的特殊样本。但如果这个值过高,会导致欠拟合。
  • max_delta_step:这参数限制每颗树权重改变的最大步长。如果是0意味着没有约束。如果是正值那么这个算法会更保守,通常不需要设置。
  • subsample:这个参数控制对于每棵树,随机采样的比例。减小这个参数的值算法会更加保守,避免过拟合。但是这个值设置的过小,它可能会导致欠拟合。
  • colsample_bytree:用来控制每颗树随机采样的列数的占比。
  • colsample_bylevel:用来控制的每一级的每一次分裂,对列数的采样的占比。
  • lambda(reg_lambda):L2 正则化项的权重系数,越大模型越保守。
  • alpha(reg_alpha):L1 正则化项的权重系数,越大模型越保守。
  • tree_method:树生成算法,auto, exact, approx, hist, gpu_exact, gpu_hist。
  • scale_pos_weight:各类样本十分不平衡时,把这个参数设置为一个正数,可以使算法更快收敛。典型值是 sum(negative cases) / sum(positive cases)。

Dart 额外参数

  • sample_type:采样算法。
  • normalize_type:标准化算法。
  • rate_drop:前置树的丢弃率,有多少比率的树不进入下一个迭代,[0, 1]。
  • one_drop:设置为 1 的话每次至少有一棵树被丢弃。
  • skip_drop:跳过丢弃阶段的概率,[0, 1],非零的 skip_drop 比 rate_drop 和 one_drop 有更高的优先级。

线性模型

  • lambda(reg_lambda):L2 正则化项的权重系数,越大模型越保守。
  • alpha(reg_alpha):L1 正则化项的权重系数,越大模型越保守。
  • lambda_bias(reg_lambda_bias):L2 正则化项的偏置。

学习任务参数

  • objective:这个参数定义需要被最小化的损失函数。
  • base_score:初始化预测分数,全局偏置。
  • eval_metric:对于有效数据的度量方法,取值范围取决于 objective。
  • seed:随机数种子,相同的种子可以复现随机结果,用于调参。

其他

传统 GBDT 在优化时只用到一阶导数信息,XGboost 则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,XGBoost 工具支持自定义代价函数,只要函数可一阶和二阶求导。

参考

  1. github repo : xgboost
  2. github repo : xgboost-doc-zh
  3. XGBoost: A Scalable Tree Boosting System
  4. Introduction to Boosted Trees
  5. GBDT、XGBoost、LightGBM 的使用及参数调优
  6. 通俗理解kaggle比赛大杀器xgboost
  7. wepon 大神的知乎回答:机器学习算法中 GBDT 和 XGBOOST 的区别有哪些?
  8. wepon 大神的 slids
  9. Parallel Gradient Boosting Decision Trees
文章目录
  1. 1. 学习笔记 | XGBoost
    1. 1.1. 简介
    2. 1.2. 泰勒展开
    3. 1.3. Boosting
    4. 1.4. 目标函数
    5. 1.5. 寻找最优分裂点
    6. 1.6. 算法流程
    7. 1.7. 参数说明
      1. 1.7.1. 通用参数
      2. 1.7.2. Booster 参数
        1. 1.7.2.1. 树模型
      3. 1.7.3. Dart 额外参数
      4. 1.7.4. 线性模型
      5. 1.7.5. 学习任务参数
    8. 1.8. 其他
    9. 1.9. 参考