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 条评论
登录 后参与评论

相关文章

来自专栏机器之心

ECCV 2018 | 微软亚洲研究院与北京大学共同提出用于物体检测的可学习区域特征提取模块

作者:Jiayuan Gu、Han Hu、Liwei Wang、Yichen Wei、Jifeng Dai

772
来自专栏专知

什么是MAP? 理解目标检测模型中的性能评估

【导读】近日,机器学习工程师Tarang Shah发布一篇文章,探讨了机器学习中模型的度量指标的相关问题。本文首先介绍了机器学习中两个比较直观和常用的度量指标:...

5455
来自专栏人工智能

机器学习集成算法——袋装法和随机森林

随机森林是最流行、最强大的机器学习算法之一。它是机器学习集成算法中的一种,可称之为自助集成(Bootstrap Aggregation)或袋装法(Bagging...

4366
来自专栏AI科技评论

零示例学习中的映射域迁移 (projection domain shift) 问题

AI 科技评论按:本文由上海交通大学副教授牛力为 AI 科技评论提供的独家稿件,未经许可不得转载。

2123
来自专栏CVer

ECCV 2018 | 目标检测的可学习区域特征

本文经机器之心(微信公众号:almosthuman2014)授权转载,禁止二次转载

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

干货 | 卷积神经网络入门这一篇就够了

【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 先明确一点就是,Deep Learning是全部深度学习算法...

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

反向传播算法推导-全连接神经网络

反向传播算法是人工神经网络训练时采用的一种通用方法,在现代深度学习中得到了大规模的应用。全连接神经网络(多层感知器模型,MLP),卷积神经网络(CNN),循环神...

1801
来自专栏红色石头的机器学习之路

Coursera吴恩达《神经网络与深度学习》课程笔记(2)-- 神经网络基础之逻辑回归

上节课我们主要对深度学习(Deep Learning)的概念做了简要的概述。我们先从房价预测的例子出发,建立了标准的神经网络(Neural Network)模型...

2720
来自专栏算法channel

神经网络精炼入门总结:出现缘由,多层感知机模型,前向传播,反向传播,避免局部最小

在本文中,我将初步介绍神经网络有关的概念和推导,本文是后续深度学习的入门,仅对神经网络做初步理解,后续文章中会继续进行学习。

1140
来自专栏专知

深入广义线性模型:分类和回归

【导读】本文来自AI科学家Semih Akbayrak的一篇博文,文章主要讨论了广义的线性模型,包括:监督学习中的分类和回归两类问题。虽然关于该类问题的介绍文章...

5146

扫码关注云+社区

领取腾讯云代金券