《统计学习方法》第八章-提升方法

在《统计学习方法》中第八章提升方法,包括四节,第一节介绍AdaBoost、第二节介绍AdaBoost的误差、第三节介绍从前向分布算法来实现AdaBoost、第四节介绍提升树。(x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\

a{1}+a{2}+b^{2}=c

第一节 提升方法AdaBoost算法

第一节首先介绍了AdaBoost的思想:是先得到一个弱分类器,然后在这个弱分类器的基础上将其提升到强分类器,具体方法是提升上一个分类器中被误分类的样本的权重,使得本次训练的分类器更加重视这些样本,最后的分类器是所有的分类器的线性组合。

它的思想可以类比为秋招季参加了很多面试:第一次面试,面试官给你打了6分,并给你建议说你知识广度够,深度不够;第二次面试前你着重对知识的深度这方面进行了准备,第二次面试面试官给你打了6.5分,并给你建议说你的表达能力有限;第三次面试,你又对表达能力进行了准备,面试官给你打了7分。三次面试完后,你总结经验,着重第三次的经验,因为第三次面试官给你打的分最高。

每一次面试,面试官给你建议就好像是算法中在该轮没有被正确分类的样本点,你开始重视这些建议就好比给这些误分类的点增加了权值,面试官给你打的分就好比是算法中该次弱分类器的权值,得分高的面试经验比得分低的面试经验更需要你重视。AdaBoost算法的思想就是这样,前一次没有正确分类的样本点在后一次会被更加重视,前一次的分类器训练结果是会影响后一次分类器结果的。$\int 3xdx$

AdaBoost先对所有划分选择出一个误分类最小的划分,得出一个分类器,分类器的权值 $$a{m}=\frac{1}{2}log(\frac{1-e{m}}{e{m}}) $$,样本的权值也发生更新 $$w{m+1,i}=\frac{w{m,i}}{Z{m}}e^{-a{m}y{i}G{m}(x{i})} $$

也就是说前一次的训练的结果会被这次的分类器产生影响。

问:AdaBoost算法每一次训练的训练误差相对于上一轮是不是一定减少?

答:首先区分训练误差和训练误差率,训练误差$$ e=\frac{1}{N}\sum{i=1}^{N}{I(G(x{i})\ne y{i})}$$ 不同于分类误差率 $$e{m}=\sum{i=1}^{N}{w{m,i}I(G{m}(x{i})\ne y_{i})}$$ ,被上一轮分类错误的样本增加了它的权值,从而使得下一轮分类器的训练重视这些被上一轮分类器误分的样本,权值更高的样本更有可能被正确分类,那么相应的分类误差率一定减小,训练误差不一定减少。

延伸:分类误差率一定一直减少,那么样本权值 $$a{m}=\frac{1}{2}log(\frac{1-e{m}}{e{m}}) $$一定一直增加,所以可以确定前一轮的分类器的权值一定小于后一轮的权值,$$ a{m}$$ 一定小于 $$a_{m+1}$$ 。

第二节 AdaBoost算法的训练误差分析

第二节介绍了AdaBoost的误差,误差要用到泰勒公式的知识,具体公式看附加知识中。我们知道训练误差率是不断减少的,那么训练误差也在学习过程中不断地减少(注意是学习过程中分类器的加法模型的训练误差一直减少,而后一个分类器的训练误差不一定比前一个分类误差的训练误差小)。训练误差是随着每加权一个弱分类器而减少的,那么我们要得出训练误差$$ e=\frac{1}{N}\sum{i=1}^{N}{I(G(x{i})\ne y{i})} $$的性质,就需要使其小于一个值(在这里是 $$\frac{1}{N}\sum{i}^{}{e^{-y{i}f(x{i})}} $$),推出后一个值的性质,就可以得出前者的性质,比如后者呈指数形式下降,前者小于后者,那么它也呈指数下降。同理,如果一个变量是一直增大的,那么要证明这个变量的性质,就要使其大于一个值,推出这个值得性质就可以得出变量的性质。

问:在第二节中AdaBoost的训练误差界的证明中得出,AdaBoost的训练误差是以指数速率下降的,和AdaBoost的损失函数是指数函数有什么联系?可不可以得出训练误差是以指数速率下降,所以选择损失函数为指数函数?

答:损失函数的意义是得出模型给出的结果和实际结果的偏离程度,AdaBoost的损失函数选择指数函数,是因为AdaBoost在第一节处理的是二分类问题,如果处理的是回归问题那么选择的是均分差损失函数,损失函数的选择只与处理的问题有关。所以训练误差的性质与损失函数的选择之间没有联系。

第三节 前向分布算法与AdaBoost

第三节介绍了前向分布算法并从前向分布算法的角度来看AdaBoost。首先介绍了前向分布算法,前向分布算法的目标是训练一个加法模型 $$f(x)=\sum{m=1}^{M}{\beta{m}b(x;\gamma{m})} $$是从前向后,每一步只学习一个基函数及其系数,而平常的分布算法是从m=1到M所有参数 $$\beta{m} , \gamma{m}$$ 的优化问题简化为逐次求解各个 $$\beta{m} , \gamma_{m} $$的优化问题,一步一个脚印肯定比一步登天更容易实现,不是吗?

AdaBoost也可以从前向分布算法的角度来看,不过要设定基函数为基本分类器,损失函数为指数损失函数。它的每一轮的分类器的训练是为了拟合残差,第一轮是为了拟合样本数据,后面都是为了拟合残差。由前向分布算法可以推导出第一节的分类器权值 $$a{m}$$ 和第m+1轮的样本权值$$a{m+1}$$。

第四节 从提升树到GBDT

第四节介绍了提升树,提升树是AdaBoost的特例,可以认为提升树是基本分类器为二类分类树,损失函数为平方损失函数的AdaBoost。分类问题的提升树改变权重,回归问题的提升树拟合残差。

前向分布算法+决策树(分类树or回归树)=提升树

因为损失函数是平方损失函数的时候,残差是好求的,而如果不是平方损失函数也不是指数损失函数的时候,残差就不可求得,这时,就要用损失函数关于当前模型f(x)的负梯度来近似代替残差。梯度提升算法就是用梯度下降法来讲弱分类器提升为强分类器的算法。

问:提升树和AdaBoost之间是什么关系?

答:AdaBoost是提升思想的算法模型,经典的AdaBoost一般用于分类问题,并没有指定基函数,或者说是基分类器,它可以从改变样本的权值的角度和前向分布算法的角度来解释。当确定基函数是回归或分类树时,结合前向分布算法就得出提升树算法。

使用梯度提升进行分类的算法叫做GBDT,进行回归时则叫做GBRT。一般的提升树是用残差来确定树的叶节点的切分,并根据残差来确定该切分下的输出值,而GBDT首先是根据负梯度来确定切分,确定切分后根据线性搜索估计叶节点区域的值,使损失函数极小化。这就好比是寻找一个全局极小值,负梯度只给定一个方向,通过线性搜索确定在该方向下走几步(该次向北,走20步。。。)线性搜索的步骤: $$c{mj}=arg min{c}\sum{x{i}\in r{mj}}^{}{L(y{i},f{m-1}(x{i})+c)} $$。所以可以认为伪残差是只给出方向的残差。

GBDT的算法流程如下:

1)初始化,初始化一个常数值,即只有一个根节点的树 $$f{0}(x)=argmin{c}\sum{i=1}^{N}{L(y{i},c)} $$

2)for m=1,2,...,M

        (a)for i=1,2,...,N,计算负梯度(伪残差):$$

r{mj}=-[\frac{\delta L(y{i},f(x{i}))}{\delta f(x{i})}]{f(x)=f{m-1}(x)} $$

(b)对伪残差拟合一个回归树,得到第m棵树的叶结点区域 ,j=1,2...,J,

       (这里的J是事先确定的,也就是把区域分成的份数,确定份数后穷举所有切分拟合残差得出损失误差最小的切分就是最佳切分,从而就可以得出第m棵树的叶结点区域)
        (c)对j=1,2,..J,计算

$$c{mj}=arg min{c}\sum{x{i}\in r{mj}}^{}{L(y{i},f{m-1}(x{i})+c)} $$

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

(3)输出回归树 $$f_{m}(x) $$

附加知识:

泰勒公式:设n是一个正整数,如果定义在一个包含a的区间上的函数f在a点处n+1次可导,那么 对于这个区间上的任意x都有:f(x)=∑n=0Nf(n)(a)n!(x−a)n+Rn(x),其中的多项式称为函数

在a处的泰勒展开式,Rn(x)是泰勒公式的余项且是(x−a)n的高阶无穷小。

—-维基百科

麦克劳伦形式的泰勒公式:

$$f(x)=f(0)+f^{'}(x)\cdot x+\frac{f^{''}(x)}{2!}\cdot x^{2}+...+\frac{f^{(n)}(x)}{n!}\cdot x^{n} $$

$$e^{-x}=1-\frac{1}{1!}\cdot x+\frac{1}{2!}\cdot x^{2}-\frac{1}{3!}\cdot x^{3}+o(x^{3}) $$

$$e^{-\frac{x}{2}}=1-\frac{1}{1!}\cdot \frac{x}{2}+\frac{1}{2!}\cdot \frac{x^{2}}{4}-\frac{1}{3!}\cdot \frac{x^{3}}{8}+o(x^{3}) $$

$$\sqrt{1-x}=1-\frac{1}{2}\cdot x-\frac{1}{2\cdot 4} \cdot x^{2} -\frac{1}{3!\cdot 8}\cdot x^{3}+o(x^{3}) $$

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

统计学习方法

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法全栈工程师

GAN系列学习(2)——前生今世

作者:刘威威 编辑:李文臣 本文是GAN系列学习--前世今生第二篇,在第一篇中主要介绍了GAN的原理部分,在此篇文章中,主要总结了常用的GAN包括...

4205
来自专栏企鹅号快讯

简析集成学习

当我们第一次接触机器学习问题的时候,面对着大量的数据和一个分类/回归的机器学习任务,我们本能地会采取这样的方式:选择一个决策树分类器或一个Lasso回归模型,将...

2169
来自专栏IT派

机器学习面试题目总结

如果你觉得好的话,不妨分享到朋友圈。 1.机器学习中特征的理解 def:特征选择和降维 特征选择:原有特征选择出子集,不改变原来的特征空间 降维:将原有的特征...

4035
来自专栏CVer

一文读懂VGG网络

网上太多关于CNN经典网络的介绍了,泛读的文章大多都从LeNet说到ResNet/DenseNet;而精读的文章质量参次不齐,而且很多介绍的并不具体。

1170
来自专栏IT派

十大机器学习算法,看完即入门

机器学习算法分为三类:有监督学习、无监督学习、增强学习。有监督学习需要标识数据(用于训练,即有正例又有负例),无监督学习不需要标识数据,增强学习介于两者之间(有...

2837
来自专栏技术与生活

机器学习之线性回归(1)

在开始理解回归分析之前,先有个二手房房价的例子,假设这里的房价只和面积,居室情况两个因素有关,那么我们就有下列的数据形式 面积 居室 房价[万] 80 2 10...

1343
来自专栏UAI人工智能

轻松读论文——层规范化技术 Layer Normalisation

1633
来自专栏专知

【重温经典】吴恩达机器学习课程学习笔记五:特征处理与多项式拟合

【导读】前一段时间,专知内容组推出了春节充电系列:李宏毅2017机器学习课程学习笔记,反响热烈,由此可见,大家对人工智能、机器学习的系列课程非常感兴趣,近期,专...

2837
来自专栏PPV课数据科学社区

【计算机视觉必读干货】图像分类、定位、检测,语义分割和实例分割方法梳理

【导读】本文作者来自南京大学计算机系机器学习与数据挖掘所(LAMDA),本文直观系统地梳理了深度学习在计算机视觉领域四大基本任务中的应用,包括图像分类、定位、检...

2738
来自专栏WD学习记录

机器学习 学习笔记(22) 深度模型中的优化

用于深度模型训练的优化算法与传统的优化算法在几个方面有所不同。机器学习通常是简接作用的,再打所述机器学习问题中,我们关注某些性能度量P,其定义于测试集上并且可能...

1613

扫码关注云+社区