提升方法

《统计学习方法》笔记 第8章

Posted by Cheereus on February 12, 2020

第8章 提升方法

提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。

8.1 提升方法 AdaBoost 算法

8.1.1 提升方法的基本思路

在概率近似正确(probably approximately correct, PAC)学习的框架中,一个概念(一个类),如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么就称这个概念是强可学习的(strongly learnable);一个概念,如果存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,那么就称这个概念是弱可学习的。

非常有趣的是,后来证明强可学习与弱可学习是等价的,也就是说,在 PAC 学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。

8.1.2 AdaBoost 算法

输入:训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in\mathcal{X} \subseteq \mathcal{R}^n,y \in\mathcal{Y} \subseteq \{+1,-1\},i=1,2,\cdots,N$;弱学习算法;

输出: 最终分类器 $G(x)$。

(1) 初始化训练数据的权值分布

(2) 对 $m=1,2,\cdots,M$

  • 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本分类器
  • 计算 $G_m(x)$ 在训练数据集上的分类误差率
  • 计算 $G_m(x)$ 的系数

这里的对数是自然对数

  • 更新训练数据集的权值分布

这里 $Z_m$ 是规范化因子

它使 $D_{m+1}$ 成为一个概率分布。

(3) 构建基本分类器的线性组合

得到最终分类器

8.1.3 AdaBoost 的例子

8.2 AdaBoost 算法的训练误差分析

AdaBoost 的训练误差界

AdaBoost 算法最终分类器的训练误差界为

二分类问题 AdaBoost 的训练误差界

这里 $\gamma_m=\frac{1}{2}-e_m$

推论:如果存在 $\gamma>0$,对所有 $m$ 有 $\gamma_m \geq\gamma$,则

这表明在此条件下 AdaBoost 的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。

8.3 AdaBoost 算法的解释

前向分步算法

输入:训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,损失函数 $L(y,f(x))$;基函数集 $\{b(x;\gamma)\}$

输出:加法模型 $f(x)$。

(1) 初始化 $f_0(x)=0$;

(2) 对 $m=1,2,\cdots,M$

  • 极小化损失函数

得到参数 $\beta_m,\gamma_m$

  • 更新

(3) 得到加法模型

这样,前向分步算法将同时求解从 $m=1$ 到 $M$ 所有参数 $\beta_m,\gamma_m$ 的优化问题简化为逐次求解各个 $\beta_m,\gamma_m$ 的优化问题。

8.3.2 前向分步算法与 AdaBoost

Adaboost 算法是前向分步加法算法的特例。这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。

8.4 提升树

8.4.1 提升树模型

提升树模型可以表示为决策树的加法模型:

其中,$T(x;\Theta_m)$ 表示决策树,$\Theta_m$ 为决策树的参数,$M$ 为决策树的个数。

8.4.2 提升树算法

输入:训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}, $x_i \in\mathcal{X} \subseteq \mathcal{R}^n,y \in\mathcal{Y}\subseteq R$

输出:提升树 $f_M(x)$。

(1) 初始化 $f_0(x)=0$。

(2) 对 $m=1,2,\cdots,M$。

  • 计算残差:
  • 拟合残差 $r_{mi}$ 学习一个回归树,得到 $T(x;\Theta_m)$。

  • 更新 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$.

(3) 得到回归问题提升树

8.4.3 梯度提升

输入:训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}, x_i \in\mathcal{X} \subseteq \mathcal{R}^n,y \in\mathcal{Y}\subseteq R$;损失函数 $L(y,f(x))$;

输出:回归树 $\hat{f}(x)$

(1) 初始化

(2) 对 $m=1,2,\cdots,M$

  • 对 $i=1,2,\cdots,N$ 计算
  • 对 $r_{mi}$ 拟合一个回归树,得到第 $m$ 棵树的叶结点区域 $R_{mj}, \ j=1,2,\cdots,J$。

  • 对 $j=1,2,\cdots,J$,计算

  • 更新 $f_m(x)=f_{m-1}(x)+\displaystyle\sum_{j=1}^J c_{mj}I(x\in R_{mj})$

(3) 得到回归树

第8章完结