一、Boosting算法的发展历史
Boosting算法是一种把若干个分类器整合为一个分类器的方法,在boosting算法产生之前,还出现过两种比较重要的将多个分类器整合为一个分类器的方法,即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。
1)bootstrapping方法的主要过程
主要步骤:
i)重复地从一个样本集合D中采样n个样本
ii)针对每次采样的子样本集,进行统计学习,获得假设Hi
iii)将若干个假设进行组合,形成最终的假设Hfinal
iv)将最终的假设用于具体的分类任务
2)bagging方法的主要过程
主要思路:
i)训练分类器
从整体样本集合中,抽样n* < N个样本 针对抽样的集合训练分类器Ci
ii)分类器进行投票,最终的结果是分类器投票的优胜结果
但是,上述这两种方法,都只是将分类器进行简单的组合,实际上,并没有发挥出分类器组合的威力来。直到1989年,Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖(Godel price)。
Schapire还提出了一种早期的boosting算法,其主要过程如下:
i)从样本整体集合D中,不放回的随机抽样n1 < n 个样本,得到集合 D1
训练弱分类器C1
ii)从样本整体集合D中,抽取 n2 < n 个样本,其中合并进一半被 C1 分类错误的样本。得到样本集合D2
训练弱分类器C2
iii)抽取D样本集合中,C1 和 C2 分类不一致样本,组成D3
训练弱分类器C3
iv)用三个分类器做投票,得到最后分类结果
到了1995年,Freund and schapire提出了现在的adaboost算法,其主要框架可以描述为:
i)循环迭代多次
更新样本分布
寻找当前分布下的最优弱分类器
计算弱分类器误差率
ii)聚合多次训练的弱分类器
在下图中可以看到完整的adaboost算法:
图1.1 adaboost算法过程
现在,boost算法有了很大的发展,出现了很多的其他boost算法,例如:logitboost算法,gentleboost算法等等。在这次报告中,我们将着重介绍adaboost算法的过程和特性。
二、Adaboost算法及分析
从图1.1中,我们可以看到adaboost的一个详细的算法过程。Adaboost是一种比较有特点的算法,可以总结如下:
1)每次迭代改变的是样本的分布,而不是重复采样(re weight)
2)样本分布的改变取决于样本是否被正确分类
总是分类正确的样本权值低
总是分类错误的样本权值高(通常是边界附近的样本)
3)最终的结果是弱分类器的加权组合
权值表示该弱分类器的性能
简单来说,Adaboost有很多优点:
1)adaboost是一种有很高精度的分类器
2)可以使用各种方法构建子分类器,adaboost算法提供的是框架
3)当使用简单分类器时,计算出的结果是可以理解的。而且弱分类器构造极其简单
4)简单,不用做特征筛选
5)不用担心overfitting!
总之:adaboost是简单,有效。
下面我们举一个简单的例子来看看adaboost的实现过程:
图中,“+”和“-”分别表示两种类别,在这个过程中,我们使用水平或者垂直的直线作为分类器,来进行分类。
第一步:
根据分类的正确率,得到一个新的样本分布D2,一个子分类器h1
其中划圈的样本表示被分错的。在右边的途中,比较大的“+”表示对该样本做了加权。
第二步:
根据分类的正确率,得到一个新的样本分布D3,一个子分类器h2
第三步:
得到一个子分类器h3
整合所有子分类器:
因此可以得到整合的结果,从结果中看,及时简单的分类器,组合起来也能获得很好的分类效果,在例子中所有的。
Adaboost算法的某些特性是非常好的,在我们的报告中,主要介绍adaboost的两个特性。一是训练的错误率上界,随着迭代次数的增加,会逐渐下降;二是adaboost算法即使训练次数很多,也不会出现过拟合的问题。
下面主要通过证明过程和图表来描述这两个特性:
1)错误率上界下降的特性
从而可以看出,随着迭代次数的增加,实际上错误率上界在下降。
2)不会出现过拟合现象
通常,过拟合现象指的是下图描述的这种现象,即随着模型训练误差的下降,实际上,模型的泛化误差(测试误差)在上升。横轴表示迭代的次数,纵轴表示训练误差的值。
而实际上,并没有观察到adaboost算法出现这样的情况,即当训练误差小到一定程度以后,继续训练,返回误差仍然不会增加。
对这种现象的解释,要借助margin的概念,其中margin表示如下:
通过引入margin的概念,我们可以观察到下图所出现的现象:
从图上左边的子图可以看到,随着训练次数的增加,test的误差率并没有升高,同时对应着右边的子图可以看到,随着训练次数的增加,margin一直在增加。这就是说,在训练误差下降到一定程度以后,更多的训练,会增加分类器的分类margin,这个过程也能够防止测试误差的上升。
三、多分类adaboost
在日常任务中,我们通常需要去解决多分类的问题。而前面的介绍中,adaboost算法只能适用于二分类的情况。因此,在这一小节中,我们着重介绍如何将adaboost算法调整到适合处理多分类任务的方法。
目前有三种比较常用的将二分类adaboost方法。
1、adaboost M1方法
主要思路: adaboost组合的若干个弱分类器本身就是多分类的分类器。
在训练的时候,样本权重空间的计算方法,仍然为:
在解码的时候,选择一个最有可能的分类
2、adaboost MH方法
主要思路: 组合的弱分类器仍然是二分类的分类器,将分类label和分类样例组合,生成N个样本,在这个新的样本空间上训练分类器。
可以用下图来表示其原理:
3、对多分类输出进行二进制编码
主要思路:对N个label进行二进制编码,例如用m位二进制数表示一个label。然后训练m个二分类分类器,在解码时生成m位的二进制数。从而对应到一个label上。
四、总结
最后,我们可以总结下adaboost算法的一些实际可以使用的场景:
1)用于二分类或多分类的应用场景
2)用于做分类任务的baseline
无脑化,简单,不会overfitting,不用调分类器
3)用于特征选择(feature selection)
4)Boosting框架用于对badcase的修正
只需要增加新的分类器,不需要变动原有分类器
由于adaboost算法是一种实现简单,应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器,同时具有分类错误率上界随着训练增加而稳定下降,不会过拟合等的性质,应该说是一种很适合于在各种分类场景下应用的算法。
相关推荐
### Boosting算法详解 #### 引言:提升预测精度的艺术 在机器学习领域,Boosting是一种广为人知且被广泛应用的算法,它旨在通过结合多个弱分类器来创建一个强分类器,从而显著提高预测准确性。这篇论文由Yoav ...
**Boosting算法详解** Boosting算法是一种集成学习方法,它通过组合多个弱学习器来创建一个强学习器。这个概念最初源于20世纪90年代的统计和机器学习领域,其核心思想是“集体智慧优于个体”,即通过一系列简单的、...
boosting 算法
"集成学习Boosting算法综述" Boosting 算法是机器学习领域中的一种重要算法家族,属于集成学习的范畴。Boosting 算法的主要思想是将多个弱分类器组合成一个强分类器,从而提高分类的准确性。该算法的提出有助于...
**Boosting算法简介** Boosting是一种集成学习方法,它的核心思想是通过组合多个弱分类器形成一个强分类器。在Adaboost(Adaptive Boosting)算法中,这个概念得到了充分的体现。Adaboost是由Freund和Schapire于...
Boosting 算法综述 Boosting 算法是一种常用的集成学习方法,它通过组合多个弱学习器来提高预测精度和稳定性。以下是 Boosting 算法的主要知识点: 1. 基本理论:Boosting 算法的基本思想是通过多个弱学习器的组合...
集成学习:Boosting算法综述 集成学习是机器学习领域中的一种重要方法,它通过组合多个基础模型来提高预测准确性和泛化能力。Boosting算法是集成学习中的一种经典算法,它通过对弱分类器的组合来生成强分类器以提高...
### 集成学习:Boosting算法综述 #### 1. 引言 随着机器学习领域的迅速发展,如何从有限的观测数据中构建出精确的预测模型成为了研究的热点。Boosting算法作为一种有效的集成学习方法,近年来在学术界和工业界受到...
Boosting算法是一种集成学习策略,其目标是提升弱分类器的性能,将其转化为强学习算法。在机器学习中,弱学习算法是指那些只有稍微优于随机猜测的分类器,其错误率略低于0.5。而强学习算法则具有较高的识别准确率,...
内容概要:本文详细介绍了集成学习的基本概念及其两大类方法——Bagging和Boosting,重点讨论了Boosting算法的具体实现和技术细节。文中分别阐述了Adaboost、XGBoost、Gradient Boosting Tree等几种典型Boosting算法...
Adaboost是Boosting算法的一个重要实例,由Yoav Freund和Robert Schapire共同提出。Adaboost的工作流程如下: 1. 初始化所有训练样本的权重相等。 2. 对于每个迭代t(从1到T),使用当前权重分布训练弱学习算法,...
### Boosting算法详解 #### 一、Boosting算法概述 Boosting算法作为一种强大的集成学习方法,在机器学习领域占据着极其重要的地位。它通过构建多个弱分类器并将它们以一定的方式组合起来,形成一个强分类器。...
### Boosting算法学习知识点 #### 一、Boosting算法概述 **Boosting**是一种机器学习技术,主要用于提高预测模型的准确性。它通过结合多个弱学习器(即性能略好于随机猜测的学习算法)来构建一个强学习器。...
### Boosting算法简介 Boosting是一种非常重要的机器学习方法,主要应用于分类和回归问题中,其核心思想是将多个弱分类器(弱学习器)组合起来形成一个强分类器(强学习器)。Boosting方法在实际应用中表现出了优异...
Boosting是一种集成学习方法,它通过组合多个弱分类器形成一个强分类器。在这个场景中,我们关注的是AdaBoost.M1算法,这是...通过阅读和理解这些文件,你可以深入学习和掌握如何在实际项目中应用Boosting算法。
在Boosting算法 中,我们将分类任务划分成多个子分类器,每个子分类器专注于一些难分类的样 本,然后组合这些子分类器形成一个强的分类器。
解密人工智能:KNN K-均值 降维算法 梯度Boosting算法 AdaBoosting算法.md
针对该问题,结合KFDA(kernel Fisher discriminant analysis)能有效提取样本非线性特征的特性和集成学习中Boosting算法的思想,提出了KFDA-Boosting算法。为了验证该算法对不平衡数据分类的有效性和优越性,以G-...