7.4 XGBoost

文献：XGBoost: A Scalable Tree Boosting System

7.4.1 原理

  1. 基础思想

采用boosting的思想，串行训练多个弱学习器，当前弱学习器从上一个弱学习器的残差中进行学习，最后加权综合各个弱学习器，即\(\hat y_i=\phi(x_i)=\sum_{k=1}^Kf_k(x_i)\)。

  1. 目标函数

\[ L(\phi) = \sum_{i=1}^n L(y_i, \hat y_i) + \sum_{k=1}^K \Omega(f_k) \]

\(L(\cdot)\)表示损失函数，用于度量\(y_i\)和\(\hat y_i\)之间的差异，回归任务可以为均方误差，分类任务可以为交叉熵。

\(\Omega(f_k)\)表示对第k棵树复杂度的惩罚，用于防止过拟合，定义为\(\Omega(f) = \gamma T+\frac{1}{2}\lambda ||w||^2\)，其中\(T\)为叶子节点数，\(w\)为叶子权重（即对应叶子节点的输出值），\(\gamma\)和\(\lambda\)为惩罚系数（超参数）。

  1. 计算损失函数

与梯度提升树只利用梯度信息不一样，XGBoost还利用二阶泰勒展开（利用了黑塞矩阵的信息）来更为精准地近似损失函数。

当模型训练到第t棵树时，我们需要最小化下面的损失函数

\[ \begin{aligned} L^{(t)}&=\sum_{i=1}^n L(y_i, \hat y_i^{(t)})+\Omega (f_t) \\ &=\sum_{i=1}^n L(y_i, \hat y_i^{(t-1)}+f_t(x_i))+\Omega (f_t) \\ &\approx \sum_{i=1}^n [L(y_i, \hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega (f_t) \\ & \propto \sum_{i=1}^n [g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega (f_t) \end{aligned} \]

  • 由于前t-1棵树的结构已经确定，因此\(\sum_{i=1}^{t-1}\Omega (f_i)\)也随之确定，即为常数

  • \(g_i\)和\(h_i\)分别表示损失函数的一阶导和二阶导

  • \(L(y_i, \hat y_i^{(t-1)})\)为常数

记\(I_j=\{i|q(x_i)=j\}\)，表示落在叶子节点\(j\)上的观测集合，其中\(q(\cdot)\)表示从样本到叶子节点的映射，即为树的结构。则有

\[ \begin{aligned} \tilde L^{(t)} &= \sum_{i=1}^n [g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=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 \end{aligned} \]

引入\(I_j\)的目的就是为了把\(f_t(x_i)\)转化为对应叶子节点的预测值

之后便可将\(\tilde L^{(t)}\)视作关于\(w_j\)的二次函数，故最优权重\(w_j^*\)为

\[ w_j^* = -\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i + \lambda} \]

对应的目标函数最小值为

\[ \tilde L^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^T \frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T \]

因此，可根据\(\tilde L^{(t)}(q)\)来判断当前树模型的好坏，值越小，结构越好。

  1. 树的分裂

我们没办法遍历各种树的结构，因此采用贪心算法进行分裂，记\(I_L\)和\(I_R\)分别为分裂后左右叶子节点的样本集合，则损失函数减少量为

\[ L_{split} = \frac{1}{2}[\frac{(\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j} h_i + \lambda}] - \gamma \]

注意符号，\(L_{split}\)是分裂前的损失函数值减去分裂后的损失函数值，\(L_{split}\)越大，越倾向于分裂

此处的\(\gamma\)同样用于惩罚，能够使得差值达到一定程度时才选择分裂。

  1. 收缩与列采样

除了在目标函数中增加正则项以防止过拟合，还采取收缩与列采样的技术防止过拟合。

引入收缩因子\(\eta\)用于减少每棵树的影响，即\(\eta f_t(x_i)\)，从而为后续的树留有改善空间。这里的收缩因子类似学习率。

列采样就是在训练每棵树时随机从所有特征中抽取一个子集用于训练。

  1. 缺失值处理

当某个特征中存在缺失值时，首先删掉所有缺失值对应的观测，将完整的观测按正常操作进行分裂。之后，比较把所有缺失值样本放到左子节点及右子节点的增益大小，将这些缺失值对应的观测分配到能获得更大增益的子节点，并记录分配节点作为默认方向。在测试集上的缺失值则分配到默认方向。

7.4.2 实现

python的xgboost库，示例如下。

param_dist_xgb = {
    'max_depth': stats.randint(3, 10),
    'min_child_weight': stats.randint(1, 6),
    'gamma': stats.uniform(0, 0.5),
    'subsample': stats.uniform(0.6, 0.4),
    'colsample_bytree': stats.uniform(0.6, 0.4),
    'reg_lambda': stats.uniform(0, 1.0),
    'reg_alpha': stats.uniform(0, 1.0),
    'learning_rate' : stats.uniform(0.01, 0.29),
    'n_estimators': [50,100,150,200,250,300]
}

model_xgb = xgb.XGBRegressor(objective='reg:squarederror', random_state=527)
random_search_xgb = RandomizedSearchCV(
    model_xgb, 
    param_dist_xgb, 
    n_iter=100,
    cv=5, 
    scoring='neg_mean_squared_error',
    n_jobs=-1,
    random_state=135
)
random_search_xgb.fit(X, Y)
best_score_xgb = -random_search_xgb.best_score_
print(f"最优模型的交叉验证均方误差（MSE）: {best_score_xgb:.2f}")
best_param_xgb = random_search_xgb.best_params_
print(best_param_xgb)
best_model_xgb = random_search_xgb.best_estimator_

超参数详见官方手册