Skip to content

Latest commit

 

History

History
executable file
·
391 lines (251 loc) · 16.2 KB

README.md

File metadata and controls

executable file
·
391 lines (251 loc) · 16.2 KB
Raw

CH08 提升方法

[TOC]

前言

章节目录

  1. 提升方法AdaBoost算法
    1. 提升方法的基本思路
    2. AdaBoost算法
    3. AdaBoost的例子
  2. AdaBoost算法的训练误差分析
  3. AdaBoost算法的解释
    1. 前向分步算法
    2. 前向分布算法与AdaBoost
  4. 提升树
    1. 提升树模型
    2. 提升树算法
    3. 梯度提升

导读

  • 可能会有疑问，为什么支持向量机前置在这一章之前，可以参考本章的第一个参考文献1，Yoav Freund和Robert Schapire因此获得了2003年的哥德尔奖， 本书中关于误差率的表述与该文献是一致的， PRML中则对分类误差率进行了归一化。
  • 在训练误差分析部分有这样一句AdaBoost算法不需要知道下界$\gamma$，这正是Freund与Schapire设计AdaBoost时所考虑的。如果对这句没有sense，了解下历史。书中也讲到1988年Kearns和Valiant提出"强可学习"和"弱可学习"的概念，并提出了一个问题这两种复杂性类别是否等价。Schapire给出了答案，是等价的，并给出了算法，这是最早的Boost，但是这个算法需要知道学习器的误差界。后来AdaBoost提出，不再需要知道误差界等信息。
  • 关于AdaBoost和SVM的联系，主要在函数间隔的这个概念上文献1和本书CH02CH07中内容合并理解，本文后面在算法的解释部分会添加一个和SVM关系的对比摘要一下文献中的理解。这篇文章在介绍AdaBoost和SVM的关系的时候， 引用了三篇文献，在CH07中都有引用，是经典的SVM文献。
  • 间隔包含了分类正确性与确信度的含义。
  • 如果看过林轩田老师的课程(只需看第一课)，可能对hypothesis这个概念迷糊，没有sense。那可以翻下前面提到的这个文章，可能会对这些概念的理解有帮助。另外文章中有提到VC维，用来度量hypotheses的复杂度。
  • 另外一篇文献，推荐下RE Schapire的文章2关于间隔的理解
  • AdaBoost的两个性质：
    1. 能在学习过程中不断减少训练误差
    2. 训练误差是以指数速率下降的
  • 基函数和基本分类器不是一个概念， 在加法模型部分有提到。
  • 这章里面提到了，这样一句， 大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器， 这里改变训练数据的权值分布，可能不是很容易理解， 字面理解好像是给数据乘了系数， 实际上这个权值分布在计算分类误差率的时候才用到，通过$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$生成了对应的弱分类器的系数。另外， 这个权值分布在更新的时候， 做了归一化， 使他满足了概率分布的条件。
  • 提升树针对不同的问题， 选择不同的损失函数：指数损失（分类问题），平方损失（回归问题）， 一般损失（一般问题）， 针对一般问题， 优化方法采用梯度提升就有了GBDT。
  • 书中讲的AdaBoost是用在二分类上， 和SVM的二分类差不多， 算法8.1中有用到符号函数。公式8.4也用到了$Y={1,-1}$的性质, 和感知机部分的应用类似。
  • 在sklearn中有引用书中参考文献53，sklearn中的实现支持多分类， 引用了参考文献[^3]， 本书中引用了更早的一个实现多分类的文献4
  • 提升方法最初用来解决分类问题，这里面算法8.1描述的就是二分类的算法，
  • 本章最后介绍了提升树， 关于各种树相关的算法关系， 林轩田有页slides， 可以参考。5
  • 算法8.3用来求回归问题的提升树， 注意拟合残差这个内容的理解，可以理解例子8.2
  • 关于参考文献96， 这个文章，简要说两句， 提到了Bregman distance， 这篇文章的编辑是Bengio
  • Boosting不容易过拟合

加法模型+前向分步算法

回顾这一章其实可以划分成三个阶段：

  1. 1️⃣加法模型 + 指数损失[特例,Adaboost又进一步是特例]
  2. 2️⃣加法模型 + 平方损失[特例]
  3. 3️⃣加法模型 + 一般损失

再复习下，之前李航老师讲到的：

统计学习方法之间的不同，主要来自器模型、策略、算法的不同。确定了模型、策略、算法，统计学习的方法也就确定了。这也就是将其称为统计学习三要素的原因。

再结构化一下这三个部分，好好理解：

  • 模型：需要学习的条件概率分布或者决策函数
  • 策略：按照什么样的准则学习或选择最优的模型。统计学习的目标在于从假设空间中选取最优模型。
    • 经验风险最小化($R_{emp}$)
    • 结构风险最小化($R_{srm}$)
  • 算法：考虑用什么样的方法求解最优模型，这时统计学习问题归结为最优化问题，统计学习方法的算法称为求解最优化问题的算法。

Boosting方法是一种常用的统计学习方法，应用广泛且有效

  • 【在分类问题中】改变训练样本权重，学习多个分类器
  • 线性组合

提升方法AdaBoost算法

提升方法的基本思路

概率近似正确(PAC, Probably approximately correct)

在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。 两个问题

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

Adaboost解决方案：

  1. 提高前一轮被分错的分类样本的权值，降低被正确分类的样本的权值
  2. 加权多数表决的方法

Adaboost算法

算法8.1

  • 输入：训练数据集$T={(x_1,y_1), (x_2,y_2),...,(x_N,y_N)}, x\in \cal X\sube \R^n$, 弱学习方法
  • 输出：最终分类器$G(x)$

步骤

  1. 初始化训练数据的权值分布 $D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N},w_{1i}=\frac{1}{N})​$
  2. m = 1,2, M
    1. $G_m(x):X->{-1,+1}$
    2. 求$G_m$在训练集上的分类误差率 $e_m=\sum_{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\ne y_i)$
    3. 计算$G_m(x)$的系数，$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$，自然对数
    4. $w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))​$
    5. $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)$
  4. 最终分类器$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$■

从算法8.1的输入可以看出来，AdaBoost是个集成学习算法， 因为在他的输入中包含了弱学习算法。

注意这里面有个描述

使用具有权值分布$D_m$的训练数据集

这个怎么理解，是改变了数据么？

  • 这里不是的
  • 弱分类器的分类准则是错误率$e_m=P(G_m(x_i)\ne y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\ne y_i)$
  • 弱分类器的分类准则是错误率$e_m=\color{red}\sum_{i=1}^{N}\color{black}P(G_m(x_i)\ne y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\ne y_i)​$
  • 以上这两条再考虑下
  • 每次学习用到的数据集没有变，划分方式也没有变（比如阈值分类器中的分类点的选取方式），变是评价每个划分错误的结果。
  • 不同的权值分布上，不同样本错分对评价结果的贡献不同，分类器中分类错误的会被放大，分类正确的系数会减小，错误和正确的系数比值为$e^{2\alpha_m}=\frac{1-e_m}{e_m}$，这个比值是分类器分类正确的几率($odds$)，关于几率在CH06中有讲到，这也是为什么在1999年的时候Schapire的文章中开篇用Horse racing gambler来引入Boosting，几率就是个源自赌博的概念。
  • 书中对这点也有解释：误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，似的训练数据在基本分类器的学习中起不同的作用， 这是AdaBoost的一个特点。

AdaBoost例子

例子8.1

数据见data_8-1.txt

弱分类器选为阈值分类器，通过阈值将数据划分成两部分，标准是分类误差率最低。其实这个弱分类器就是决策树桩。

需要确定两个参数：

  1. 阈值选在哪里
  2. 划分的两部分类别指定方式

下面显示m=1，2，3时弱分类器的选择过程

m=1

不同阈值分类误差率对比

不同阈值分类误差率对比

m=2

不同阈值分类误差率对比

不同阈值分类误差率对比

m=3

不同阈值分类误差率对比

不同阈值分类误差率对比

数据显示了每一轮计算的结果

x 0 1 2 3 4 5 6 7 8 9
y 1 1 1 -1 -1 -1 1 1 1 -1
d1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
G1 1 1 1 -1 -1 -1 -1 -1 -1 -1
d2 0.07143 0.07143 0.07143 0.07143 0.07143 0.07143 0.16666 0.16666 0.16666 0.07143
f1 0.4236 0.4236 0.4236 -0.4236 -0.4236 -0.4236 -0.4236 -0.4236 -0.4236 -0.4236
sign_f1 1.0 1.0 1.0 -1.0 -1.0 -1.0 -1.0 -1.0 -1.0 -1.0
G2 1 1 1 1 1 1 1 1 1 -1
d3 0.0455 0.0455 0.0455 0.1667 0.1667 0.1667 0.1061 0.1061 0.1061 0.0455
f2 1.0732 1.0732 1.0732 0.226 0.226 0.226 0.226 0.226 0.226 -1.0732
sign_f2 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 -1.0
G3 -1 -1 -1 -1 -1 -1 1 1 1 1
d4 0.125 0.125 0.125 0.1019 0.1019 0.1019 0.0648 0.0648 0.0648 0.125
f3 0.3218 0.3218 0.3218 -0.5254 -0.5254 -0.5254 0.9774 0.9774 0.9774 -0.3218
sign_f3 1.0 1.0 1.0 -1.0 -1.0 -1.0 1.0 1.0 1.0 -1.0

准确率，误差率，分类器系数之间关系 Adaboost算法示意图 通过这个图来解释什么是加法模型

  • 同样的数据集T，配合不同的权值分布，拿到不同的基分类器G
  • 误差率的定义将权值系数分布与基分类器的结果联系在了一起
  • 权值分布D的宽度代表分类器的误差率相对大小，D1➡️D3递减
  • G的宽度代表最终模型中该分类器对应的系数大小，G1➡️G3递增
  • 在模型的最终表示中有个$\sum$

TODO：

增加不同轮次的样本权重的可视化。

AdaBoost 误差分析

这部分可以看下张潼老师的论文。其中提到这样一句， The basic idea is to minimize a convex upper bound of the classification error function I(p,y).

这样就自然的过度到了后面的AdaBoost的另外一种解释， 指数损失。

注意，张潼老师的论文里面提到了指示函数是error function。作为指示函数， 这里条件判断的是是否相等

书中的定理8.1如下描述

AdaBoost算法最终分类器的训练误差界为 $$ \frac{1}{N}\sum\limits_{i=1}\limits^N I(G(x_i)\neq y_i)\le\frac{1}{N}\sum\limits_i\exp(-y_i f(x_i))=\prod\limits_m Z_m $$ 这个的意思就是说指数损失是0-1损失的上界，然后通过递推得到了归一化系数的连乘。

定理8.2后面再看。

AdaBoost 算法的解释

加法模型， 指数损失， 前向分步， 二分类。

前向分步算法

算法8.2

输入：训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N, y_N)}, x_i \in \cal X \sube R^n, y_i\in {-1, 1}$， 损失函数$L(y, f(x))$; 基函数集合${b(x;\gamma)}$

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

步骤：

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

  2. 对$m=1,2,\dots,M$

  3. 极小化损失函数 $$ (\beta_m,\gamma_m)=\arg\min \limits_ {\beta,\gamma}\sum_{i=1}^NL(y_i, f_{m-1}(x_i)+\beta b(x_i;\gamma)) $$

  4. 更新 $$ f_m(x)=f_{m-1}(x)+\beta _mb(x;\gamma_m) $$

  5. 得到加法模型 $$ f(x)=f_M(x)=\sum_{m=1}^M\beta_m b(x;\gamma_m) $$

提升树

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。

提升树模型

以决策树为基函数的提升方法称为提升树。

决策树$T(x;\Theta_m)$

提升树模型可以表示成决策树的加法模型 $$ f_M(x)=\sum_{m=1}^MT(x;\Theta_m) $$ 上面这个公式用回归问题理解挺好理解(不等式求和)， 后面给了例子。

提升树算法

不同的问题， 主要区别在于损失函数不同：

  1. 平方误差用于回归问题
  2. 指数损失用于分类问题

算法8.3

回归问题的提升树算法

输入：训练数据集

输出：提升树$f_M(x)$

步骤：

  1. 初始化$f_0(x)=0$
  2. 对$m=1,2,\dots,M$
    1. 计算残差 $$ r_{mi}=y_i-f_{m-1}(x_i), i=1,2,\dots,N $$
    2. 拟合残差$r_{mi}$学习一个回归树，得到$T(x;\Theta_m)$
    3. 更新$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
  3. 得到回归问题提升树 $$ f(x)=f_M(x)=\sum_{m=1}^MT(x;\Theta_m) $$

5.5节中有回归树相关说明。

例子8.2

可以看代码中测试案例test_e82

梯度提升(GBDT)

算法8.4

输入： 训练数据集$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}, x_i \in \cal x \sube \R^n, y_i \in \cal y \sube \R$；损失函数$L(y,f(x))$ 输出：回归树$\hat{f}(x)$ 步骤：

  1. 初始化 $$ f_0(x)=\arg\min\limits_c\sum_{i=1}^NL(y_i, c) $$

  2. $m=1,2,\dots,M$

  3. $i=1,2,\dots,N$ $$ r_{mi}=-\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]{f(x)=f{m-1}(x)} $$

  4. 对$r_{mi}$拟合一个回归树，得到第$m$棵树的叶节点区域$R_{mj}, j=1,2,\dots,J$

  5. $j=1,2,\dots,J$ $$ c_{mj}=\arg\min_c\sum_{xi\in R_{mj}}L(y_i,f_{m-1}(x_i)+c) $$

  6. 更新 $$ f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj}) $$

  7. 得到回归树 $$ \hat{f}(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj}) $$

这个算法里面注意，关键是用损失函数的负梯度，在当前模型的值作为回归问题提升树算法中的残差近似值，拟合回归树

AdaBoost与SVM的关系

TODO: 训练数据集与测试数据集的误差率关系。

摘要文献中对AdaBoost和SVM的理解。

$|x|1=\sum{i=1}^N|x|$，向量元素绝对值的和

$|x|_\infty=\max\limits_i|x_i|$，向量所有元素绝对值中的最大值

$|x|_{-\infty}=\min\limits_i|x_i|$，向量所有元素绝对值中的最小值

向量和矩阵的范数不同，具体可以参考numpy的帮助文档7

AdaBoost这个方法， 比较迷人的地方就在于训练数据集误差率降为0之后， 依然能继续降低测试误差，看起来，似乎不会过拟合。Schapire给出的解释主要是基于间隔理论， 但是， AdaBoost的间隔和SVM的间隔是不一样的。

关于AdaBoost的间隔理论， Schapire在1998年提出之后，受到过质疑，周志华老师在这个问题上给出了解释，并说明了当间隔分布无法继续提升的时候， 过拟合终将发生。

AdaBoost与LR的关系

第一次提到AdaBoost和LR 的关系是本书参考文献[6]， 给出了Boosting和LR损失函数之间的关系， 但是里面用到的损失小二乘。

本书的参考文献[9]，从Bregman散度的角度解释AdaBoost和LR的关系。

文献[9]中有说明，LR的特征对应了AdaBoost中的弱分类器，或者是基分类器，分类器对应了hypotheses。

习题

8.2

比较SVM，AdaBoost，LR的学习策略与算法

参考

  3. [^3 ]: Multi-class AdaBoost

⬆ top

Footnotes

  1. A Short Introduction to Boosting ↩ ↩2

  2. Boosting the margin: A new explanation for the effectiveness of voting methods ↩

  3. A decision-theoretic generalization of on-line learning and an application to boosting ↩

  4. Improve boosting algorithms using confidence-rated predictions ↩

  5. Machine Learning Techniques: Lecture 11: Gradient Boosted Decision Tree ↩

  6. Logistic regression, AdaBoost and Bregman distances ↩

  7. numpy.linalg.norm ↩