AdaBoost 算法原理及推导

AdaBoost(Adaptive Boosting):自适应提升方法。

1、AdaBoost算法介绍

AdaBoost是Boosting方法中最优代表性的提升算法。该方法通过在每轮降低分对样例的权重,增加分错样例的权重,使得分类器在迭代过程中逐步改进,最终将所有分类器线性组合得到最终分类器,Boost算法框架如下图所示:

图1.1 Boost分类框架(来自PRML)

2、AdaBoost算法过程

1)初始化每个训练样例的权值,共N个训练样例。

2)共进行M轮学习,第m轮学习过程如下:

A)使用权值分布为Wm的训练样例学习得到基分类器Gm。

B)计算上一步得到的基分类器的误差率:(此公式参考PRML,其余的来自统计学习方法)

C)计算Gm前面的权重系数:

D)更新训练样例的权重系数,

E)重复A)到D)。得到一系列的权重参数am和基分类器Gm

4)将上一步得到的基分类器根据权重参数线性组合,得到最终分类器:

3、算法中的两个权重分析

1)关于基分类器权重的分析

上面计算的am表示基分类器在最终的分类器中所占的权重,am的计算根据em而得到,由于每个基分类器的分类性能要好于随机分类器,故而误差率em<0.5.(对二分类问题)

当em<0.5时,am>0且am随着em的减小而增大,所以,分类误差率越小的基分类器在最终的分类器中所占的权重越大。

注:此处的所有am之后并不为1。

2)训练样例的权重分析

根据公式可知,样例分对和分错,权重相差

倍(统计学习方法上此公式有误)。

由于am>0,故而exp(-am)<1,当样例被基本分类器正确分类时,其权重在减小,反之权重在增大。

通过增大错分样例的权重,让此样例在下一轮的分类器中被重点关注,通过这种方式,慢慢减小了分错样例数目,使得基分类器性能逐步改善。

4、训练误差分析

关于误差上界有以下不等式,此不等式说明了Adaboost的训练误差是以指数的速度下降的,

推导过程用到的公式有:

具体推导过程请看统计学习方法课本!

5、AdaBoost算法推导过程

AdaBoost算法使用加法模型,损失函数为指数函数,学习算法使用前向分步算法。

其中加法模型为:

损失函数为指数函数:

我们的目标是要最小化损失函数,通过最小化损失函数来得到模型中所需的参数。而在Adaboost算法中,每一轮都需要更新样例的权重参数,故而在每一轮的迭代中需要将损失函数极小化,然后据此得到每个样例的权重更新参数。这样在每轮的迭代过程中只需要将当前基函数在训练集上的损失函数最小即可。

现在我们需要通过极小化上面的损失函数,得到a,G。

设:

于是有:

为了方便下面推导,我们将:

这样,我们就有:

正式推导过程如下:

设:

对g(a)求导得:

,得到:

其中,在计算过程中用到的em为:

由于

,所以得到新的损失为:

最终的wmi通过规范化得到:

其中规范化因子为:

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉战队

深度学习---反向传播的具体案例

最近遇到一位小师弟,他让我给他推导一下前向传播和反向传播过程,于是我埋头在白纸上一步一步推导,最后,小师弟特别开心,在此过程中,我也更一步认识了这个知识点,感觉...

33615
来自专栏AI研习社

手把手教你如何用 TensorFlow 实现 CNN

CNN 的引入 在人工的全连接神经网络中,每相邻两层之间的每个神经元之间都是有边相连的。当输入层的特征维度变得很高时,这时全连接网络需要训练的参数就会增大很...

47012
来自专栏计算机视觉战队

经典的全连接前馈神经网络与BP

神经网络分类: ? 机器学习的四要素 ? 讨论:线性模型与广义线性模型 对于部分数据来说,其本身就是稀疏,可以通过线性模型直接优化求解,但是实际生活中大多...

3315
来自专栏石瞳禅的互联网实验室

【TensorFlow实战——笔记】第3章:TensorFlow第一步_TensorFlow实现Softmax Regression识别手写数字

MNIST(Mixed National Institute of Standards and Technology database)是一个非常简单的机器视觉...

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

梯度是如何计算的

引言 深度学习模型的训练本质上是一个优化问题,而常采用的优化算法是梯度下降法(SGD)。对于SGD算法,最重要的就是如何计算梯度。此时,估计跟多人会告诉你:采用...

2797
来自专栏机器学习算法原理与实践

梯度提升树(GBDT)原理小结

    在集成学习之Adaboost算法原理小结中,我们对Boosting家族的Adaboost算法做了总结,本文就对Boosting家族中另一个重要的算法梯度...

665
来自专栏wOw的Android小站

[深度学习]Charpter 9:卷积网络

卷积网络convolutional network,也叫做卷积神经网络convolutional neural network CNN 专门用来处理类似网格结构...

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

梯度提升树(GBDT)原理小结

地址:https://www.cnblogs.com/pinard/p/6140514.html

1152
来自专栏SIGAI学习与实践平台

反向传播算法推导-卷积神经网络

原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不能用于商业目的。

1000
来自专栏瓜大三哥

线性神经网络

自适应线性元件也是早期的神经网络模型之一,其学习算法称为LMS(Least Mean Squares)算法。Adaline网络与感知器网络非常相似,只是神经元的...

2257

扫码关注云+社区