集成学习

集成学习（Ensemble Learning）通过组合多个"弱学习器"来构建一个更强大的模型。其核心思想是"三个臭皮匠，顶个诸葛亮"。

集成学习原理

为什么集成有效？

偏差-方差分解是理解集成有效性的关键。对于单个模型的泛化误差：

\[ \text{Error} = \text{Bias}^2 + \text{Variance} + \text{Irreducible Noise} \]

• Bagging（如 Random Forest）主要降低方差：通过平均多个高方差模型的预测来减少波动
• Boosting（如 AdaBoost、XGBoost）主要降低偏差：逐步关注难分类样本，修正前序模型的错误

集成有效的条件（Condorcet 陪审团定理的推广）：

• 基学习器的准确率需要大于 50%（好于随机猜测）
• 基学习器之间需要具有多样性（即它们的错误不完全相关）

假设有 \(T\) 个独立的基学习器，每个的错误率为 \(\epsilon < 0.5\)，则集成后通过多数投票的错误率为：

\[ \epsilon_{\text{ensemble}} = \sum_{k=\lceil T/2 \rceil}^{T} \binom{T}{k} \epsilon^k (1-\epsilon)^{T-k} \]

当 \(T \to \infty\) 时，\(\epsilon_{\text{ensemble}} \to 0\)。

---

Bagging

Bootstrap 采样

Bagging（Bootstrap Aggregating）的核心是 Bootstrap 采样：

1. 从原始数据集（\(n\) 个样本）中有放回地随机采样 \(n\) 个样本，形成一个新的训练集
2. 重复 \(T\) 次，得到 \(T\) 个不同的训练集
3. 在每个训练集上训练一个基学习器
4. 预测时取多数投票（分类）或平均值（回归）

每次 Bootstrap 采样中，约有 \(1 - (1-1/n)^n \approx 63.2\%\) 的样本被选中，剩余约 36.8% 为袋外样本（OOB）。

Random Forest

Random Forest 在 Bagging 的基础上引入了特征子空间随机化：

• 在每个节点分裂时，随机选择 \(m\) 个特征（而非全部 \(d\) 个特征）
• 对分类任务，推荐 \(m = \lfloor\sqrt{d}\rfloor\)；对回归任务，推荐 \(m = \lfloor d/3 \rfloor\)

OOB 误差估计：

对于每个样本 \(\mathbf{x}_i\)，用所有未包含它的树进行预测，得到 OOB 预测。OOB 误差是所有样本 OOB 预测的平均误差，可以作为泛化误差的无偏估计，无需额外的验证集。

Random Forest 的优势：

• 不容易过拟合（增加树的数量不会导致过拟合）
• 能处理高维数据
• 提供特征重要度排序
• 支持并行训练
• 对缺失值和异常值有一定鲁棒性

特征重要度：

• 基于不纯度的重要度（MDI）：计算每个特征在所有树中分裂带来的不纯度下降总和
• 基于排列的重要度（MDA）：随机打乱某个特征后，观察 OOB 误差的增加量

---

Boosting

AdaBoost

AdaBoost（Adaptive Boosting）通过迭代地调整样本权重，使后续学习器更关注前序学习器错分的样本。

算法步骤：

1. 初始化样本权重 \(w_i^{(1)} = \frac{1}{n}\)
2. 对于 \(t = 1, 2, \dots, T\)： - 用权重分布 \(\mathbf{w}^{(t)}\) 训练基学习器 \(h_t\) - 计算加权错误率：

\[ \epsilon_t = \sum_{i=1}^{n} w_i^{(t)} \cdot \mathbb{1}[h_t(\mathbf{x}_i) \neq y_i] \]

- 计算学习器权重：

\[ \alpha_t = \frac{1}{2} \ln\frac{1-\epsilon_t}{\epsilon_t} \]

- 更新样本权重：

\[ w_i^{(t+1)} = \frac{w_i^{(t)} \exp(-\alpha_t y_i h_t(\mathbf{x}_i))}{Z_t} \]

其中 \(Z_t\) 为归一化因子。

1. 最终预测：\(H(\mathbf{x}) = \text{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(\mathbf{x})\right)\)

AdaBoost 可以被证明是在指数损失函数下的加法模型的前向分步算法。

---

Gradient Boosting

Gradient Boosting 的核心思想是每一步拟合前序模型残差的负梯度方向。

通用框架：

给定损失函数 \(L(y, F(\mathbf{x}))\)，初始化 \(F_0(\mathbf{x}) = \arg\min_c \sum_i L(y_i, c)\)。

对于 \(t = 1, 2, \dots, T\)：

1. 计算负梯度（伪残差）：

\[ r_{it} = -\frac{\partial L(y_i, F(\mathbf{x}_i))}{\partial F(\mathbf{x}_i)}\bigg|_{F=F_{t-1}} \]

1. 用基学习器 \(h_t\) 拟合伪残差 \(\{(\mathbf{x}_i, r_{it})\}\)
2. 确定步长 \(\eta_t\)（可通过线搜索）
3. 更新模型：\(F_t(\mathbf{x}) = F_{t-1}(\mathbf{x}) + \eta_t h_t(\mathbf{x})\)

当 \(L\) 为平方损失时，\(r_{it} = y_i - F_{t-1}(\mathbf{x}_i)\) 就是真正的残差。

---

XGBoost

XGBoost（eXtreme Gradient Boosting）是 Gradient Boosting 的高效工程实现，引入了多项关键改进。

正则化目标函数

\[ \mathcal{L} = \sum_{i=1}^{n} L(y_i, \hat{y}_i) + \sum_{t=1}^{T} \Omega(f_t) \]

其中正则化项：

\[ \Omega(f) = \gamma \cdot T_{\text{leaves}} + \frac{1}{2}\lambda \sum_{j=1}^{T_{\text{leaves}}} w_j^2 \]

\(T_{\text{leaves}}\) 为叶子节点数，\(w_j\) 为叶子节点的权重，\(\gamma\) 控制树的复杂度，\(\lambda\) 为 L2 正则化系数。

二阶泰勒展开

对目标函数在 \(F_{t-1}\) 处做二阶泰勒展开：

\[ \mathcal{L}^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(\mathbf{x}_i) + \frac{1}{2} h_i f_t^2(\mathbf{x}_i) \right] + \Omega(f_t) \]

其中 \(g_i = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}\)，\(h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}\)。

最优叶子权重和增益：

\[ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}, \quad \text{Gain} = \frac{1}{2}\left[\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} g_i)^2}{\sum_{i \in I} h_i + \lambda}\right] - \gamma \]

近似分裂算法

对于大数据集，XGBoost 使用加权分位数草图（Weighted Quantile Sketch）来近似寻找最佳分裂点，避免枚举所有可能的分裂值。

稀疏感知

XGBoost 原生支持稀疏数据，为每个节点学习一个默认方向，当特征值缺失时将样本分到默认方向。

工程优化

• 列块（Column Block）：数据按列排序存储，加速分裂点搜索
• 缓存感知：利用 CPU 缓存优化内存访问
• 核外计算：支持数据不完全放入内存时的计算

---

LightGBM

LightGBM 由微软提出，针对大数据场景进行了极致优化。

GOSS（Gradient-based One-Side Sampling）

保留所有梯度大的样本（信息量大），对梯度小的样本随机采样：

• 按梯度绝对值排序
• 保留前 \(a\%\) 大梯度样本
• 从剩余样本中随机采样 \(b\%\)
• 对采样的小梯度样本放大权重 \(\frac{1-a}{b}\) 以维持原始分布

EFB（Exclusive Feature Bundling）

将互斥特征（很少同时非零的特征）捆绑在一起，减少特征数量。这在稀疏高维数据中非常有效。

Leaf-wise 生长策略

与 XGBoost 的 level-wise 策略不同，LightGBM 采用 leaf-wise 策略：每次选择增益最大的叶子节点进行分裂。

• 优点：相同叶子数下，leaf-wise 通常能获得更低的损失
• 风险：容易过拟合，需要用 max_depth 限制深度

---

CatBoost

CatBoost 由 Yandex 提出，专门针对类别特征和预测偏移问题进行了优化。

Ordered Boosting

传统 Boosting 在训练过程中存在预测偏移（prediction shift）：用于计算残差的模型和用于训练的数据有重叠。

CatBoost 的 Ordered Boosting：

1. 对数据进行随机排列
2. 对于第 \(i\) 个样本，只用前 \(i-1\) 个样本训练的模型来计算其残差
3. 这确保了残差的无偏性

类别特征处理

CatBoost 使用 Ordered Target Encoding：

\[ \hat{x}_i^k = \frac{\sum_{j < i, x_j^k = x_i^k} y_j + a \cdot p}{\sum_{j < i, x_j^k = x_i^k} 1 + a} \]

其中 \(p\) 为目标变量的先验均值，\(a\) 为平滑参数。使用随机排列来避免目标泄露。

对称树

CatBoost 默认使用对称决策树（Oblivious Trees）：同一层的所有节点使用相同的分裂条件。这使得预测速度极快，并且有正则化效果。

---

Stacking

Stacking（堆叠泛化）使用一个元学习器（Meta-learner）来组合多个基学习器的预测。

基本流程

1. 第一层：训练 \(M\) 个不同的基学习器 \(h_1, h_2, \dots, h_M\)
2. 使用基学习器对数据进行预测，生成新的特征矩阵
3. 第二层：用元学习器（如逻辑回归、线性回归）学习如何组合基学习器的预测

交叉验证 Stacking

为避免过拟合，通常使用 \(K\) 折交叉验证来生成第一层的预测：

1. 将数据划分为 \(K\) 折
2. 对于每一折，用其他 \(K-1\) 折训练基学习器，对当前折进行预测
3. 拼接所有折的预测结果作为元学习器的训练数据

元学习器的选择： 通常选择简单的模型（如线性回归、逻辑回归），因为第一层已经足够复杂。如果元学习器也很复杂，容易过拟合。

---

XGBoost vs LightGBM vs CatBoost 对比

维度	XGBoost	LightGBM	CatBoost
分裂策略	Level-wise	Leaf-wise	Symmetric tree
类别特征	需手动编码	原生支持（按分裂值分组）	原生支持（Ordered TS）
缺失值处理	学习默认方向	学习默认方向	多种模式
训练速度	中等	最快	较慢（ordered boosting 开销）
预测速度	中等	中等	最快（对称树）
GPU 支持	支持	支持	支持
过拟合控制	正则化 + 剪枝	max_depth + 正则化	Ordered boosting + 对称树
大数据表现	好	最好（GOSS + EFB）	好
小数据表现	好	易过拟合	最好（ordered boosting）
适用场景	通用	大数据、高维稀疏	类别特征多、小数据集

选择建议

• 数据量大、特征多（尤其是稀疏特征）：优先考虑 LightGBM
• 类别特征多：优先考虑 CatBoost
• 需要精细调参、社区资源丰富：XGBoost 是经典选择
• 竞赛和实际项目：通常同时训练三者，最终做 Stacking 或选最优

---

集成学习方法总览

方法	核心思想	降低偏差/方差	基学习器要求	是否可并行
Bagging	Bootstrap + 投票/平均	降低方差	高方差模型（如深度决策树）	是
Random Forest	Bagging + 特征随机化	降低方差	决策树	是
AdaBoost	样本加权	降低偏差	弱学习器（如决策树桩）	否
Gradient Boosting	拟合残差	降低偏差	浅决策树	否
XGBoost	正则化 + 二阶梯度	降低偏差	CART	树内并行
LightGBM	GOSS + EFB	降低偏差	CART	树内并行
CatBoost	Ordered Boosting	降低偏差	对称树	树内并行
Stacking	元学习器组合	两者兼顾	异质模型	第一层可并行

---

评论