一、Adaboost的起源

1.强可学习与弱可学习

1984年,Kearns 和 Valiant 提出的强可学习(strongly learnable)和弱可学习(weakly learnable)
• 在概率近似正确(probably approximately correct, PAC)学习的框架中,一个概念(类),如果存在一个多项式的学习算法能够学习它,并且正确率很高,称这个概念是强可学习的;
• 一个概念(类),如果存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,则称这个概念是弱可学习的。
• 1989年, Schapire 证明:
• 在PAC学习的框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习。

二、怎样实现弱学习转为强学习

例如:学习算法A在a情况下失效,学习算法B在b情况下失效,那么在a情况下可以用B算法,在b情况下可以用A算法解决。这说明通过某种合适的方式把各种算法组合起来,可以提高准确率。
为实现弱学习互补,面临两个问题:
(1)怎样获得不同的弱分类器?
(2)怎样组合弱分类器?

1.怎样获得不同的弱分类器?

◆使用不同的弱学习算法得到不同的基本学习器
◆使用相同的弱学习算法,但用不同的参数
----◆K-Means不同的K,神经网络不同的隐含层…
◆相同输入对象的不同表示凸显事物不同的特征
◆使用不同的训练集
◆装袋(Bagging)
◆提升(Boosting)

Bagging

• 也称为自举汇聚法(Bootstrap AGGregatIGN)
  • 从原始数据集选择S次后得到S个新数据集
  • 新数据集和原数据集的大小相等
  • 每个数据集都是通过在原始数据集中有放回地随机选择样本而得到的。
  • S个数据集建好之后,将某个学习算法分别作用于每个数据集就得到S个分类器。
  • 选择分类器投票结果中最多的类别作为最后的分类结果。
  • 改进的Bagging算法,如随机森林等。
    原数据集:{(x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 ), (x 4 , y 4 )} u 0 = (1, 1, 1, 1)
    采样1: {(x 2 , y 2 ), (x 2 , y 2 ), (x 3 , y 3 ), (x 4 , y 4 )} u 1 = (0, 2, 1, 1)
    采样2: {(x 1 , y 1 ), (x 1 , y 1 ), (x 1 , y 1 ), (x 4 , y 4 )} u 2 = (3, 0, 0, 1)

Bagging的弊端

• Bagging的可能弊端?
学习器是根据分布大致相同的数据学习的,它们学到的规则可能都是一样的!
• 能否控制权重u,让各个子模型学到不同的规则?
Boosting的基本思想:一个一个地训练子模型,在下一次训练的时候,当前分类错误的样本的权重增大,分类正确的样本的权重减小。那么下一次训练的时候就可以更加关注当前分类错误的样本。

2.怎样组合弱分类器?

◆多专家组合
一种并行结构,所有的弱分类器都给出各自的预测结果,通过“组合器”把这些预测结果转换为最终结果。如投票(voting)及其变种、混合专家模型
◆多级组合
一种串行结构,其中下一个分类器只在前一个分类器预测不够准(不够自信)的实例上进行训练或检测。如级联算法(cascading)

三、Adaboost的提出

• 1990 年 , Schapire 最 先 构 造 出 一 种 多 项 式 级 的 算 法 , 即 最 初 的Boosting算法;
• 1993年,Drunker和Schapire第一次将神经网络作为弱学习器,应用Boosting算法解决OCR问题;
• 1995年,Freund和Schapire提出了Adaboost (Adaptive Boosting)算法,效率和原来Boosting算法一样,但是不需要任何关于弱学习器性能的先验知识,可以非常容易地应用到实际问题中。

四、Adaboost的基本概念

• 两个问题如何解决:
  • 每一轮如何改变训练数据的权值或概率分布?
  • AdaBoost:提高那些被前一轮弱分类器错误分类样本的权值,降低那些被正确分类样本的权值
  • 如何将弱分类器组合成一个强分类器?
  • AdaBoost:加权多数表决,加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用,减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

五、Adaboost算法

Adaboost算法说明

六、示例

七、Boosting illustration