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

在《统计学习方法》中第八章提升方法,包括四节,第一节介绍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 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

机器学习之特征工程-特征选择

一个基本的数据挖掘场景如下: ? 数据挖掘.jpg 从上面的数据挖掘场景可知,当数据预处理完成后,我们需要选择有意义的特征,输入机器学习的算法模型进行训练。通常...

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

机器测试题(下)

人工智能一直助力着科技发展,新兴的机器学习正推动着各领域的进步。如今,机器学习的方法已经无处不在—从手机上的语音助手到商业网站的推荐系统,机器学习正以不容忽视的...

2716
来自专栏新智元

机器学习:用初等数学解读逻辑回归

逻辑回归问题的通俗几何描述 逻辑回归处理的是分类问题。我们可以用通俗的几何语言重新表述它: 空间中有两群点,一群是圆点“〇”,一群是叉点“X”。我们希望从空间...

33915
来自专栏数据科学与人工智能

【算法】word2vec与doc2vec模型

小编邀请您,先思考: 1 word2vec算法原理是什么? 2 word2vec与doc2vec有什么差异? 3 如何做word2vec和doc2vec? 深度...

4577
来自专栏企鹅号快讯

《教育统计与SPSS应用》学习笔记(8)

第8讲 回归分析 主要内容 回归分析简介 一元线性回归分析 多元线性回归分析 第一部分 回归分析简介 一、回归分析的意义 表示变量之间的不确定性关系以...

2208
来自专栏机器学习算法与理论

《白话深度学习与Tensorflow》学习笔记(2)

1、CUDA(compute unified device architecture)可用于并行计算: GTX1060 CUDA核心数:1280 显存大小:6...

3419
来自专栏机器学习算法与Python学习

搞定机器学习面试,这些是基础

本文尽可能的不涉及到繁杂的数学公式,把面试中常问的模型核心点,用比较通俗易懂但又不是专业性的语言进行描述。希望可以帮助大家在找工作时提纲挈领的复习最核心的内容,...

1220
来自专栏人工智能

未来的人工智能将有神经元结构?谷歌 Tensorflow 系统已经实现

神经网络是Tensorflow最擅长的机器学习领域。TensorFlow拥有一套符号引擎,它使得训练复杂模型变得更简单和方便。通过这套符号引擎,我们能够实现许多...

1719
来自专栏人工智能

从损失函数的角度详解常见机器学习算法(1)

作者:章华燕 编辑:赵一帆 1、机器学习中常见的损失函数 一般来说,我们在进行机器学习任务时,使用的每一个算法都有一个目标函数,算法便是对这个目标函数进行优化,...

73513
来自专栏云时之间

随机森林再复习

这里只是准备简单谈谈基础的内容,主要参考一下别人的文章,对于随机森林与GBDT,有两个地方比较重要,首先是information gain,其次是决策树。这里特...

3017

扫码关注云+社区