《统计学习方法》读书笔记提升方法部分

1. 提升方法的基本思路

首先介绍两个概念:强可学习弱可学习

强可学习就是,存在一个多项式的学习算法可以进行学习,并且正确率很高;弱可学习就是,学习的正确率仅比随机猜测略好。

一般来说,得到一个弱可学习的算法要比得到一个强可学习的算法要简单的多。那么,我们能否通过若弱可学习算法来得到强可学习算法?(这个研究问题就是我们说的提升方法)

对于 提升方法来说,我们需要解决两个问题:

  • 在每一轮如何改变训练数据的权值或概率分布
  • 如何将弱分类器组合成一个强分类器

对于问题一,AdaBoost 的做法是, 提高那些被前一轮分类器错误分类样本的权值。也就是希望之后的分类器更加关注之前出错的样本。

对于问题二,AdaBoost 采取 加权多数表决的方法,加大分类误差率小的弱分类器的权值。


2. 前向分步算法

假设模型为 $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$。$G_m(x)$ 为基函数

前向分步算法的思路是:因为学习的是加法模型,如果可以从前往后,每一步只学习一个基函数及其系数,逐步逼近目标函数。就可以简化优化的复杂度。

image-20210521101454835

将 $f(x)=f_{m-1}(x_i)+\alpha G(x_i)$ 带入损失函数 $loss=exp[-y_if(x)]$ 得到:

$Loss=arg\ min_{\alpha,G} \sum_{i=1}^N exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))]$

image-20210521102137486

得到 $G$ 的最优解因为 $G_m^*=arg\ min_a \sum_i \overline{w_{m_i}}[y_i\neq G(x_i)]$

接下来求 $\alpha$ 的最优解:

image-20210521104609015

至此我们得到了参数 $G$ 和 $\alpha$

更新 $f_m(x)=f_{m-1}(x)+\alpha G(x)$

得到加法模型 $f(x)=f_M(x)=\sum_{i=1}^M\alpha_mG(x)$

算法(前向分步算法)

输入:训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$,其中 $x_i \in R^n,y_i \in {-1,+1}$;

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

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

  2. 对 $m=1,2,…,M$

    • 极小化损失函数:$Loss=arg\ min_{\alpha,G} \sum_{i=1}^N exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))]$

      解得参数 $G$ 和 $\alpha$

    • 更新 $f_m(x)=f_{m-1}(x)+\alpha G(x)$

  3. 得到加法模型 $f(x)=f_M(x)=\sum_{i=1}^M\alpha_mG(x)$

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


3. AdaBoost 算法

AdaBoost 算法是一个非常具有代表性的提升方法。从训练数据中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成一个强分类器。

算法(AdaBoost)

输入:训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$,其中 $x_i \in R^n,y_i \in {-1,+1}$;弱学习算法

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

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

    $D_1=(w_{11},…,w_{1i},…,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,…,N$

  2. 对 $m=1,2,…,M$ (不同分类器)

    • 使用权值分布 $D_m$ 的训练数据集学习,得到基本分类器 $G_m(x):\chi \rightarrow {-1,+1}$

    • 计算 $G_m(x)$ 在训练数据集上的分类误差率 $e_m=\sum_{i=1}^NP(G_m(x_i)\neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)$

      (将分类错误的样本对应的权值求和)

    • 计算 $G_m(x)$ 的系数 $\alpha_m=\frac{1}{2}ln\frac{1-e_m}{e_m}$(表达式符合 $e_m$ 越小,$\alpha_m$ 越大,源自前向分步算法的 $\alpha$)

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

      $D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N})$

      $w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)),\ i=1,2,…,N$

      此处 $Z_m$ 为规范化因子,$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$

  3. 构建基本分类器的线性结合 $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$($\alpha_m$ 为权重(可信程度))

得到最终分类器 $G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$

简单来说,先初始化每一个训练数据的权值($w_{1i}=\frac{1}{N}$),然后依次使用不同的分类器进行学习,根据每次学习的误差率计算下一轮各分类器的系数 $\alpha_m$。并通过 $G_m(x)$ 更新每一个训练数据的权值 $w_{m,i}$ 。

3.1 前向分步算法和 AdaBoost 算法的关系

其实,我们可以由前向分步算法推导出 AdaBoost 算法(AdaBoost 算法是前向分步算法的一个特例,当基函数为基本分类器时、损失函数为指数函数时,加法模型等价于 AdaBoost 分类器)

  • 首先我们发现前向分步算法和 AdaBoost 的最终分类器都为 $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$

  • 当前向分步算法的损失函数为指数损失函数 $L(y,f(x))=exp[-yf(x)]$ 时,我们求出损失函数

    image-20210521162917660
  • 然后求出使损失达到最小的 $\alpha_m^*$ 和 $G_m^*(x)$ 就是 AdaBoost 算法中的 $\alpha_m$ 和 $G_m(x)$

    image-20210521165013640

    对于 $\alpha_m$ 的求解,详见第二章(将 $G_m^*(x)$ 带入求解的优化问题,得到 $\alpha_m^*$ 的表达式并对 $\alpha_m^*$ 求导,令导数为 0 求解出 $\alpha_m$) 可得 $\alpha_m^*=\frac{1}{2}ln\frac{1-e_m}{e_m}$ 和 AdaBoost 算法中的 $\alpha_m$ 完全一致

  • 每一轮的样本权值 $\overline{w_{m_i}}$ 等价

    由 $f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)$ 和 $\overline{w_{m,i}}=exp[-y_if_{m-1}(x_i)]$ 可得:

    $\overline{w_{m+1,i}}=\overline{w_{m,i}}exp[-y_i\alpha_mG_m(x)]$ 这和 AdaBoost 算法中的样本权值仅相差规范化因子,因而等价。


4. AdaBoost 算法训练误差分析

我们希望证明 AdaBoost 算法训练误差具有上界,以证明算法的可靠性

定理(AdaBoost 的训练误差界)AdaBoost 算法最终分类器的训练误差界为 $\frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i)\leq \frac{1}{N}\sum_iexp(-y_if(x_i))=\prod_mZ_m$

这一定理说明,可以在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小,从而使训练误差下降得最快。

先证明左侧的不等号:

  • 当 $G(x) \neq y_i$ 时,$y_if(x_i)<0$,因而 $exp(-y_if(x_i))\geq1$

    因此左侧不等号成立

然后证明右侧等号:

image-20210521143133526

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

定理(二分类问题 AdaBoost 的训练误差界)

$\prod_{m=1}^MZ_m=\prod_{m=1}^M[2\sqrt{e_m(1-e_m)}]=\prod_{m=1}^M\sqrt{(1-4\gamma_m^2)}\leq exp(-2\sum_{i=1}^M\gamma_m^2)$

此处,$\gamma_m=\frac{1}{2}-e_m$

先证明左侧的两个等号:

image-20210521150345484

再证明右侧的不等号:

image-20210521151531058

5. 提升树

提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。

其中,以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型:$f_M(x)=\sum_{m=1}^MT(x;\Theta_m)$,其中 $T(x;\Theta_m)$ 表示决策树,$\Theta_m$ 为决策树的参数,$M$ 为树的个数。

5.1 提升树算法

image-20210521095626658

5.2 梯度提升算法

提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数是平方损失函数或指数损失函数时,每一步的优化时很简单的。但对一般损失函数而言,我们一般使用梯度提升算法。

这是利用最速下降方法的近似方法,其关键是将损失函数的负梯度作为残差的近似值

image-20210521095442469

6. 总结

我们学习了如何将多个弱可学习模型组合为一个强可学习模型(提升方法)

提升方法中一个最具代表性的就是 AdaBoost 算法:$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$

通过迭代,每次学习一个基本分类器。在迭代中提高前一轮被错误分类数据的权值;提高分类误差小的基本分类器在结果所占的权值。

AdaBoost 的训练误差存在上界$\frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i)\leq \frac{1}{N}\sum_iexp(-y_if(x_i))=\prod_mZ_m$

表明可以在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小,从而使训练误差下降得最快。

AdaBoost 算法其实是前向分步算法的一个实现。在这个方法里,模型是加法模型,损失函数是指数损失函数,算法是前向分步算法。可以通过第三章的推导得到两者的最终分类模型、每一轮样本权重、分类器和各分类器权重一致/等价。

提升树是以决策树为基函数的提升方法。因为树的线性组合可以很好的拟合数据,即使数据中的输入与输出之间的关系很复杂,因此提升树是一个高功能的学习方法。包括:

  • 使用平方误差损失函数的回归问题(见 5.1)
  • 使用指数损失函数的分类问题
  • 使用一般损失函数的一般决策问题(梯度提升算法,见 5.2)