集成学习概述
定义
集成学习 是指通过将相对比较容易构建但泛化性能一般的多个学习器进行结合, 以获得比单一学习器更好的泛化性能的一种机器学习方法.
根据个体分类器是否由同一学习算法, 集成学习可以分为 同质集成 和 异质集成 两大类; 根据个体分类器的依赖关系, 可以将学习方法分为 序列化方法(串行集成) 和 并行化方法(并行集成) 两种.
提升方法
PAC 框架下, 概念类强可学习和其弱可学习等价, 但弱可学习实现更容易, 提升方法就是指将弱学习算法提升为强学习算法的方法.
AdaBoost 算法
算法AdaBoost
输入: 给定训练数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 其中 $x_i \in \mathcal{X}, y_i \in \mathcal{Y}=\{-1,+1\}, i=1,2,\cdots,N$; 弱学习算法 $\mathcal{L}$ 以及基本分类器个数 $T$;
输出: 最终分类器 $f(x)$
- 准备一个权重向量 $W_t=(w_{i,t})_{i=1}^N$, 表示第 $t$ 轮训练数据的权重分布, 初始时 $w_{i,1}=\frac{1}{N}$;
- 在第 $t$ 轮学习中, 应用算法 $\mathcal{L}$ 基于训练数据集 $D$ 和权重向量 $W_t$ 学得具有最小训练误差的基本分类器 $f_t(x)$, 即 $$f_t = \argmin_{f} \sum_{i=1}^N w_{i,t} \mathbb{I}(f(x_i) \neq y_i)$$
- 计算 $f_t(x)$ 的误差率 $$e_t = \sum_{i=1}^N w_{i,t} \mathbb{I}(f_t(x_i) \neq y_i)$$
- 计算 $f_t(x)$ 的权值 $$\alpha_t = \frac{1}{2} \ln \frac{1-e_t}{e_t}$$
- 按照投票权值更新训练数据集的权重分布 $$w_{i,t+1} = \frac{w_{i,t}}{Z_t} \exp(-\alpha_t y_i f_t(x_i))$$ 其中 $Z_t$ 是规范化因子, 使得 $w_{i,t+1}$ 成为一个概率分布.
- 经过 $T$ 轮迭代后, 得到最终分类器 $$ \begin{aligned} f(x) &= \text{sign}(G(x)) \\ G(x) &= \sum_{t=1}^T \alpha_t f_t(x) \end{aligned} $$ $G(x)$ 的符号决定了 $x$ 的类别, $|G(x)|$ 表示分类的确信度.
注意:
- $e_t$ 越小, $\alpha_t$ 越大, 表示 $f_t(x)$ 的权重越大;
- $\alpha_t$ 不仅仅平衡了 $f_t(x)$ 的权重, 还调节了样本分布的权重: $$w_{i,t+1}=\begin{cases} \frac{w_{i,t}}{Z_t} \exp(\alpha_t), & y_i=f_t(x_i) \\ \frac{w_{i,t}}{Z_t} \exp(-\alpha_t), & y_i \neq f_t(x_i) \end{cases} $$ 对于那些错误样本, 下次迭代时的权重会增大, 以便让弱分类器更关注这些样本.
- 关于为什么要这样赋值 $\alpha_t$, 由表达式可以得到 $$\exp(\alpha_t)e_t = \exp(-\alpha_t)(1-e_t)$$ 这表明分配给错误样本的权重之和与正确样本的权重之和相等.
- 计算可知 $$Z_t = \sum_{i=1}^N w_{i,t} \exp(-\alpha_t y_i f_t(x_i)) = 2 \sqrt{e_t(1-e_t)}$$
- 权值调整累计过程 $$ \begin{aligned} w_{i,t+1}&=w_{i,t} \frac{\exp(-\alpha_t y_i f_t(x_i))}{Z_t} \\ &=w_{i,1} \frac{\exp \left(-y_i \sum_{s=1}^t \alpha_s f_s(x_i)\right)}{\prod_{s=1}^t Z_s} \\ \end{aligned} $$ 取 $t=T$, 由 $w_{i,1}=\frac{1}{N}$ 可得 $$ w_{i,T} = \frac{1}{N} \frac{\exp (-y_i G(x_i))}{\prod_{s=1}^T Z_s} $$
AdaBoost 误差分析
集成分类器的训练误差为
$$ \begin{aligned} \hat{R}(f) &= \frac{1}{N} \sum_{i=1}^N \mathbb{I}(f(x_i) \neq y_i) =\frac{1}{N} \sum_{i=1}^N \mathbb{I}(y_iG(x_i) \le 0) \\ &\le \frac{1}{N} \sum_{i=1}^N \exp(-y_iG(x_i)) = \frac{1}{N} \sum_{i=1}^N \left( N \prod_{t=1}^T Z_tw_{i,T+1} \right) \\ &=\prod_{t=1}^T Z_t = \prod_{t=1}^T \left(2\sqrt{e_t(1-e_t)}\right) \le \exp\left(-2 \sum_{t=1}^T \left(\frac{1}{2}-e_t\right)^2\right)\\ \end{aligned} $$这说明 AdaBoost 的训练误差是负指数量级的. 而且不需要提前知道 $e_t$ 的值, 只需要知道 $e_t$ 的上界即可, 这也是 AdaBoost 的 Adaptive 性质所在.
加法模型
AdaBoost 可以看作是 $\{\alpha_t, f_t(x)\}$ 的加法模型, 如果我们采用指数损失函数 $\exp(-y_if(x))$, 令
$$ G_t(\alpha, f) = \frac{1}{N} \sum_{i=1}^N \exp(-y_iG(x_i) + \alpha f(x_i)) $$则可以证明第 $t$ 轮迭代得到的 $(\alpha_t,f_t)$ 是最小化 $G_t(\alpha, f)$ 的解, 过程略.
算法提升树模型
输入: 给定训练数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 其中 $x_i \in \mathcal{X}, y_i \in \mathcal{Y}=\{-1,+1\}, i=1,2,\cdots,N$; 弱学习算法(一般是分类或回归树) $\mathcal{T}$, 损失函数 $L(y,f(x))$;
输出: 最终分类器 $f(x)$
第 $m$ 个基学习器 $T(x; \Theta_m)$ 由经验风险最小化得到, 即
$$\Theta_m = \argmin_{\Theta} \sum_{i=1}^N L(y_i, f_{m-1}(x_i)+T(x_i; \Theta))$$如果是平方损失, 提升树算法实际上就是在拟合当前模型的残差.
Bagging 方法
对训练样本进行重采样, 利用不同的样本数据来学习不同的基学习器, 通过降低方差来提高集成学习器的泛化性能. Bagging (Bootstrap Aggregating) 就是一种典型的并行集成学习方法.
算法Bagging
输入: 给定训练数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 其中 $x_i \in \mathcal{X}, y_i \in \mathcal{Y}, i=1,2,\cdots,N$; 弱学习算法 $\mathcal{L}$ 以及基分类器个数 $T$;
输出: 最终分类器 $f(x)$
-
对 $t=1,2,\ldots,T$, 从$D$利用自助采样法随机抽取 $N$ 个样本得到 $D_t$. 从 $D_t$ 依学习算法 $\mathcal{L}$ 学得基分类器 $f_t(x)$.
-
返回集成分类器
$$f(x)=\argmax_{y\in\mathcal{Y}} \sum_{t=1}^T I(f_t(x)=y)$$
对样本 $x_i$ 来说，我们采用 $x_i$ 未参与训练的基学习器在 $x_i$ 上的预测的简单投票结果作为 $x_i$ 的包外预测
$$f_{\text{oob}}(x_i) = \argmax_{y \in Y} \sum_{t=1}^{T} \mathbb{I} (f_t(x_i) = y) \mathbb{I} (x_i \notin D_t)$$相应的 Bagging 算法泛化误差的包外估计 (out-of-bag estimate) 为
$$\epsilon^{\text{oob}} = \frac{1}{N} \sum_{i=1}^N \mathbb{I}(f_{\text{oob}}(x_i) \neq y_i)$$随机森林
所谓随机森林, 就是在 Bagging 方法中以决策树算法作为基学习器, 并引入随机属性选择, 即在选择划分特征时, 先从当前节点的所有 $d$ 个特征中随机选择 $k$ 个特征, 再从这 $k$ 个特征中选择最优划分特征. 随机选取的目的是为了增加基学习器之间的差异性, 使得集成学习器的泛化性能更好.
当 $k=d$ 时, 随机森林退化为 Bagging 方法, 一般取 $k=\log_2 d$.