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

相关文章

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

机器学习(33)之局部线性嵌入(LLE)【降维】总结

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 局部线性嵌入(Locally ...

3598
来自专栏算法channel

机器学习|Adaboost算法

01 — Boosting Boosting的基本思想是将若干个弱分类器(base learner)组合起来,变成一个强分类器,它需要回答2个问题: 如何改变训...

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

收藏!机器学习与深度学习面试问题总结.....

后向传播是在求解损失函数L对参数w求导时候用到的方法,目的是通过链式法则对参数进行一层一层的求导。这里重点强调:要将参数进行随机初始化而不是全部置0,否则所有隐...

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

机器学习(6) -- SVM

本篇主要是对支持向量机(support vector machine , SVM) 总结性的文章,想详细的理解SVM的请看之前所发的支持向量机系列文章。 Co...

3255
来自专栏深度学习之tensorflow实战篇

随机森林,random forest

模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大大的减少单决策树...

2745
来自专栏新智元

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

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

33915
来自专栏机器之心

从梯度下降到拟牛顿法:详解训练神经网络的五大学习算法

选自 Neuraldesigner 作者:Alberto Quesada 机器之心编译 参与:蒋思源 在神经网络中,系统的学习过程一般是由训练算法所主导。而现如...

32110
来自专栏人工智能LeadAI

BAT机器学习面试1000题系列(第150~279题)

长文~可先收藏再看哟~ 150、在感知机中(Perceptron)的任务顺序是什么?深度学习 DL基础 易 1 随机初始化感知机的权重 2 去到数据集的下一批(...

1.2K9
来自专栏杨熹的专栏

Bagging 简述

本文结构: 基本流程 有放回抽样的好处 Bagging 特点 sklearn 中 Bagging 使用 Bagging 和 Boosting 的区别 ---- ...

2724
来自专栏小詹同学

一个AI大佬的学习笔记-- 卷积神经网络基础

这是一篇来自AI大佬关于卷积神经网络的学习笔记,转载以获得授权!在这里强势推荐一下小伙伴的公众号【AI有道】,是小詹觉得最用心的几个公众号之一!二维码见文末,要...

681

扫描关注云+社区