提升方法

《统计学习方法》笔记 第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) 初始化训练数据的权值分布

\[D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N}), \ w_{1i}=\frac{1}{N},\ i=1,2,\cdots,N\]

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

  • 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本分类器
\[G_m(x):\mathcal{X}\rightarrow\{-1,+1\}\]
  • 计算 $G_m(x)$ 在训练数据集上的分类误差率
\[e_m=\sum_{i=1}^N P(G_m(x_i) \neq y_i)=\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},\cdots,w_{m+1,i},\cdots,w_{m+1,N}), \\ w_{m+1,i}=\frac{w_{mi}\ }{Z_m}\exp(-\alpha_m y_i G_m(x_i)),\ i=1,2,\cdots,N\]

这里 $Z_m$ 是规范化因子

\[Z_m=\sum_{i=1}^N w_{mi}\exp(-\alpha_m y_i G_m(x_i))\]

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

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

\[f(x)=\sum_{m=1}^M \alpha_mG_m(x)\]

得到最终分类器

\[G(x)=\text{sign}(f(x)) \\ = \text{sign}\bigg(\sum_{m=1}^M\alpha_mG_m(x)\bigg)\]

8.1.3 AdaBoost 的例子

8.2 AdaBoost 算法的训练误差分析

AdaBoost 的训练误差界

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

\[\frac{1}{N}\sum_{i=1}^N I(G(x_i)\neq y_i) \leq\frac{1}{N}\sum_i\exp(-y_i f(x_i)) = \prod_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\bigg( -2 \sum_{m=1}^M \gamma_m^2 \bigg)\]

这里 $\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 的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。

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)=\arg\underset{\beta,\gamma}{\min}\sum_{i=1}^N L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma))\]

得到参数 $\beta_m,\gamma_m$

  • 更新
\[f_m(x)=f_{m-1}(x)+\beta_m b(x;\gamma_m)\]

(3) 得到加法模型

\[f(x)=f_M(x)=\sum_{m=1}^M\beta_m b(x;\gamma_m)\]

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

8.3.2 前向分步算法与 AdaBoost

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

8.4 提升树

8.4.1 提升树模型

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

\[f_M(x)=\sum_{m=1}^M T(x;\Theta_m)\]

其中,$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}=y_i-f_{m-1}(x_i),\ i=1,2,\cdots,N\]
  • 拟合残差 $r_{mi}$ 学习一个回归树,得到 $T(x;\Theta_m)$。

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

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

\[f_M(x)=\sum_{m=1}^M T(x;\Theta_m)\]

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) 初始化

\[f_0(x)=\arg\underset{c}{\min}\sum_{i=1}^N L(y_i,c)\]

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

  • 对 $i=1,2,\cdots,N$ 计算
\[r_{mi}=-\bigg[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}\]
  • 对 $r_{mi}$ 拟合一个回归树,得到第 $m$ 棵树的叶结点区域 $R_{mj}, \ j=1,2,\cdots,J$。

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

\[c_{mj}=\arg\underset{c}{\min}\sum_{x_i\in R_{mj}\ } L(y_i,f_{m-1}(x_i)+c)\]
  • 更新 $f_m(x)=f_{m-1}(x)+\displaystyle\sum_{j=1}^J c_{mj}I(x\in R_{mj})$

(3) 得到回归树

\[\hat{f}(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^J c_{mj}I(x\in R_{mj})\]

第8章完结


如果对您有帮助,欢迎赞助一杯咖啡!