Boosting算法
发布时间：2016-02-18 栏目：机器学习 评论：0 Comments
Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生之前，还出现过两种比较重要的将多个分类器整合为一个分类器的方法，即boostrapping方法和bagging方法。
由于Boosting算法在解决实际问题时有一个重大的缺陷,即他们都要求事先知道弱分类算法分类正确率的下限,这在实际问题中很难做到。后来 Freund 和 Schapire提出了 AdaBoost 算法,该算法的效率与 Freund 方法的效率几乎一样,却可以非常容易地应用到实际问题中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整个训练集上维护一个分布权值向量 D( x) t ,用赋予权重的训练集通过弱分类算法产生分类假设 Ht ( x) ,即基分类器,然后计算他的错误率,用得到的错误率去更新分布权值向量 D( x) t ,对错误分类的样本分配更大的权值,正确分类的样本赋予更小的权值。每次更新后用相同的弱分类算法产生新的分类假设,这些分类假设的序列构成多分类器。对这些多分类器用加权的方法进行联合,最后得到决策结果。这种方法不要求产生的单个分类器有高的识别率,即不要求寻找识别率很高的基分类算法,只要产生的基分类器的识别率大于 0.5 ,就可作为该多分类器序列中的一员。
1. Boosting由来
Kearns & Valiant (1984)
PAC学习模型
提出问题：
1) 强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。
2) 弱学习算法：识别一组概念的正确率仅比随机猜测略好。
3) 弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。
Kearns & Valiant (1989)
证明了弱学习器和强学习器的等价问题。
Schapire (1989)
第一个提出了一个可证明的多项式时间的Boosting算法。
Schapire, etc. (1993)
第一次把Boosting算法思想用于实际应用：OCR。
Freund & Schapire (1995)
AdaBoost算法。
2. Boosting思想
基本思想：
1) 先赋予每个训练样本相同的概率。
2) 然后进行T次迭代，每次迭代后，对分类错误的样本加大权重(重采样)，使得在下一次的迭代中更加关注这些样本。
示例：
留下评论
You must be logged in to post a comment.
