12. 集成学习

12.1 集成学习的种类 *

• Boosting（迭代式学习，减小 bias）

  • 串行，基学习器层层叠加

  • 训练时，对前一层分错的样本，给予更高的权重

  • 测试时，根据各层分类器的结果，加权得到最终结果

• Bagging（集体投票决策，减小 variance）

  • 并行，基学习器无强依赖

  • e.g. Random Forest

• Stacking（异质基学习器，元模型组合）

12.2 集成学习的步骤和例子 **

• 集成学习一般步骤

  • 找到误差 相互独立 的基分类器

  • 训练基分类器

  • 合并基分类器结果（voting, stacking）

• Adaboost（对正确样本降低权重，对错误样本升高权重）

  • 确定基分类器：ID3 决策树

  • 训练基分类器：初始化采样分布 $D_1(i)=1/N$

    • 按照 $D_t$ 分布，采样子集 $S_t$

    • 训练基分类器 $h_t$，计算错误率 $\epsilon_t$

    • 计算权重 $a_t=\log\frac{1-\epsilon_t}{\epsilon_t}$

    • 更新采样分布 $D_{t+1}=\begin{cases}D_t(i)&,h_t(x_i)\neq y_i \\ \frac{D_t(i)\epsilon_t}{1-\epsilon_t}&,h_t(x_i)=y_i\end{cases}$，并归一化

  • 合并基分类器：$Sign(\sum_{t=1}^T h_t(z)a_t)$

• 梯度提升决策树 GBDT（每棵树学习之前的残差）

12.3 基分类器 **

• 决策树

  • 方便将 样本权重 整合到训练过程中，不需要 过采样 调整样本权重

  • 表达能力 vs. 泛化能力，可以通过 层数 来折中

  • 样本的扰动，对决策树影响，不稳定学习器 更适合，feature_fraction 也引入随机性

• 其他模型

  • NN 也适合作为基学习器（不稳定）

  • KNN 不适合，线性分类器 / KNN 较为稳定，方差不大

12.4 Bias & Variance ***

• 定义

  • bias：通常由于对学习算法做了 错误假设，e.g. 用 一次函数 拟合 二次函数

  • variance

• 解释 Boosting, Bagging 原理

  • Bagging：降低 variance，Bootstrap Aggregating，如果相互独立，方差为 $\frac{\sigma^2}{n}$

  • Boosting：降低 bias，但不降 variance，因为基学习器之间 强相关

12.5 梯度决策提升树 GBDT **

• 基本原理

  • 思想：根据当前模型 损失函数的负梯度 来训练新加入的模型

  • GBDT（MART）中使用的决策树通常为 CART

• 梯度提升 vs. 梯度下降

  • Gradient Boosting（函数空间 F）$L=\sum_i l(y_i,F(x_i))$

    • $F=F_{t-1}-\rho_t\nabla_F L|_{F=F_{t-1}}$

  • Gradient Descent（参数空间 W）$L=\sum_i l(y_i,f_w(w_i))$

    • $w=w_{t-1}-\rho_t\nabla_w L|_{w=w_{t-1}}$

• GBDT 优点和局限

  • 优点

    • 预测 计算快，可并行计算

    • 分布稠密 的数据集上，泛化能力和表达能力都很好

    • 解释性、鲁棒性，自动发现特征间 高阶关系，不需要 预处理

  • 局限

    • 在 高维稀疏 的数据集上，不如 SVM / NN

    • 文本特征，优势不如 数值特征

    • 串行训练，只能决策树内局部并行

12.6 XGBoost 与 GBDT 的联系与区别

• XGBoost

  • GBDT 后剪枝，XGBoost 构建阶段加入正则项

  • $L_t=\sum_i l(y_i,F_{t-1}(x_i)+f_t(x_i))+\Omega(f_t)$

  • 正则项 $\Omega(f_t)=\gamma T+\frac12 \lambda \sum_{j=1}^T w_j^2$

  • 二阶泰勒展开推导出 $L_t\approx\tilde L_t=\sum_{j=1}^T[G_j w_j+\frac12(H_j+\lambda)w_j^2]=\gamma T$

  • $G_j=\sum_{i\in I_j}\nabla_{F_{t-1}} l(y_i,F_{t-1}(x_i))$

  • $H_j=\sum_{i\in I_j}\nabla^2_{F_{t-1}} l(y_i,F_{t-1(x_i)}$

  • 假设决策树结构已知，叶子节点预测值 $w_j^*=-\frac{G_j}{H_j+\lambda}$（NP-hard）

  • 预测值带入损失函数，得到差分 $Gain=\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}+\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}-\gamma$（$\gamma$ 有预剪枝效果）

• 区别和联系

  • GBDT 是机器学习算法，XGBoost 是其 工程实现

  • 使用 CART 树时，XGBoost 加入 正则项，防止过拟合，提高泛化能力

  • GBDT 使用一阶导数，XGBoost 二阶泰勒展开，同时使用 一阶二阶导数

  • GBDT 采用 CART 树，XGBoost 支持多种 基分类器，如 线性分类器

  • GBDT 使用全部数据，XGBoost 支持 数据采样（类似于 Random Forest）

  • GBDT 没有缺失值处理，XGBoost 自动学习 缺失值处理策略