概述¶
提升方法是一种重要的统计学习方法，通过将多个弱分类器组合成一个强分类器来提高分类性能。本文将详细介绍AdaBoost算法和提升树模型。
一、AdaBoost算法¶
1.1 基本概念¶
强学习与弱学习
- 在概率近似正确(PAC)学习的框架中
- 弱学习算法：准确率比随机猜测略好
- Schapire证明：强学习和弱学习是等价的
AdaBoost核心思想
通过迭代学习一个基分类器，每次迭代中，提高那些被前一个分类器错误分类的样本的权重，构造一系列基本分类器（弱分类器），并将这些基本分类器组合，构成一个强分类器。
1.2 AdaBoost算法步骤¶
输入：训练数据集 $T = \{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}$，其中 $x_i \in \mathcal{X} \subseteq \mathbb{R}^n$，$y_i \in \mathcal{Y} = \{-1, +1\}$
输出：最终分类器 $G(x)$
算法流程：
-
初始化训练数据的权值分布
$$D_1 = (w_{11}, w_{12}, ..., w_{1N}), \quad w_{1i} = \frac{1}{N}, \quad i = 1, 2, ..., N$$ -
对于 $m = 1, 2, ..., M$
- 使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器：
$$G_m(x): \mathcal{X} \rightarrow \{-1, +1\}$$
-
计算 $G_m(x)$ 在训练数据集上的分类误差率：
$$e_m = \sum_{i=1}^{N} w_{mi} I(G_m(x_i) \neq y_i)$$ -
计算 $G_m(x)$ 的系数：
$$\alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m}$$
（这里对数是自然对数） -
更新训练数据集的权值分布：
$$D_{m+1} = (w_{m+1,1}, w_{m+1,2}, ..., w_{m+1,N})$$
$$w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(x_i)), \quad i = 1, 2, ..., N$$
其中 $Z_m$ 是规范化因子：
$$Z_m = \sum_{i=1}^{N} w_{mi} \exp(-\alpha_m y_i G_m(x_i))$$
- 构建基本分类器的线性组合
$$f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$$
得到最终分类器：
$$G(x) = \text{sign}(f(x)) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)$$
1.3 AdaBoost的训练误差分析¶
定理：AdaBoost算法最终分类器的训练误差界为：
$$\frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^{N} \exp(-y_i f(x_i)) = \prod_{m=1}^{M} Z_m$$
二类分类问题AdaBoost的训练误差界：
$$\prod_{m=1}^{M} Z_m = \prod_{m=1}^{M} [2\sqrt{e_m(1-e_m)}] = \prod_{m=1}^{M} \sqrt{(1-4\gamma_m^2)} \leq \exp\left(-2\sum_{m=1}^{M} \gamma_m^2\right)$$
其中 $\gamma_m = \frac{1}{2} - e_m$
推论：如果存在 $\gamma > 0$，对所有 $m$ 有 $\gamma_m \geq \gamma$，则：
$$\frac{1}{N} \sum_{i=1}^{N} I(G(x_i) \neq y_i) \leq \exp(-2M\gamma^2)$$
这表明在此条件下AdaBoost的训练误差是以指数速率下降的。
二、提升树（Boosting Tree）¶
2.1 提升树模型¶
提升树是以分类树或回归树为基本分类器的提升方法，是统计学习中一类重要的方法。
提升树模型：
$$f_M(x) = \sum_{m=1}^{M} T(x; \Theta_m)$$
其中 $T(x; \Theta_m)$ 表示决策树，$\Theta_m$ 为决策树的参数，$M$ 为树的个数。
2.2 提升树算法¶
前向分步算法：
- 初始化 $f_0(x) = 0$
- 对于 $m = 1, 2, ..., M$
- 极小化损失函数：
$$\hat{\Theta}_m = \arg\min_{\Theta_m} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m))$$
- 更新模型：
$$f_m(x) = f_{m-1}(x) + T(x; \hat{\Theta}_m)$$
2.3 回归问题的提升树¶
当损失函数为平方损失时：
$$L(y, f(x)) = (y - f(x))^2$$
第 $m$ 步的模型：
$$f_m(x) = f_{m-1}(x) + T(x; \Theta_m)$$
损失函数：
$$L(y, f_m(x)) = [y - f_{m-1}(x) - T(x; \Theta_m)]^2 = [r - T(x; \Theta_m)]^2$$
其中 $r = y - f_{m-1}(x)$ 是当前模型拟合数据的残差。
结论：回归问题的提升树算法只需要简单地拟合当前模型的残差。
三、梯度提升树（Gradient Boosting Tree）¶
3.1 梯度提升算法¶
当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。
梯度提升算法：
-
初始化
$$f_0(x) = \arg\min_{\gamma} \sum_{i=1}^{N} L(y_i, \gamma)$$ -
对于 $m = 1, 2, ..., M$
- 对 $i = 1, 2, ..., N$ 计算：
$$r_{mi} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)}$$
- 拟合残差学习一个回归树，得到叶结点区域 $R_{mj}, j = 1, 2, ..., J_m$
- 对 $j = 1, 2, ..., J_m$，计算：
$$\gamma_{mj} = \arg\min_{\gamma} \sum_{x_i \in R_{mj}} L(y_i, f_{m-1}(x_i) + \gamma)$$
- 更新：
$$f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{mj} I(x \in R_{mj})$$ -
得到回归树
$$\hat{f}(x) = f_M(x) = \sum_{m=1}^{M} \sum_{j=1}^{J_m} \gamma_{mj} I(x \in R_{mj})$$
3.2 梯度提升树的特点¶
- 优点：能够处理各种类型的损失函数，具有很好的预测性能
- 灵活性：可以通过调整学习率、树的深度等参数控制模型复杂度
- 广泛应用：适用于回归、分类等多种机器学习任务
总结¶
提升方法通过组合多个弱学习器来构建强学习器，其中：
- AdaBoost 通过调整样本权重来关注难以分类的样本
- 提升树 通过拟合残差来逐步改进模型
- 梯度提升树 利用梯度信息来处理一般损失函数
这些方法在统计学习和机器学习中都有广泛应用，并在许多实际问题中取得了优异的效果。
注：本文使用Qwen转换自本人的统计学习方法笔记。
