当前位置:   article > 正文

Boosting原理及其应用_boosting算法应用

boosting算法应用

一、背景
故事:
   某男到医院就诊,医生亲切地问了一些该男的症状,最后得出结论:“医生说我怀孕了。。。”
血淋淋的故事告诉我们:
    需要一个好的诊断器:根据病人的一系列症状,得出病人患的是什么病。

实际上,这是一个分类问题。

分类问题很常见:
1) 博客男女
2) OCR
3) 情感分类
4) 查询意图识别
5) 排序学习
6) 等等

文本分类算法:
1) Nave Bayes
2) Decision Tree
3) KNN
4) ANN
5) SVM
6) ME
7) ...

然而,事实是残酷的。直接寻找一个强分类器很困难。

弱 + … + 弱 ≈ 强
- 古语有云:三个臭皮匠,顶个诸葛亮。
- Finding many rough rules of thumb can be a lot easier and more effective than finding a single, highly prediction rule.

启发:
    整合多个弱分类器,成为一个强大的分类器。这时候,集合分类器(Boosting, Bagging等)出现了。


二、Boosting原理
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次迭代,每次迭代后,对分类错误的样本加大权重(重采样),使得在下一次的迭代中更加关注这些样本。

示例:

3. AdaBoost算法及分析
1) Base Setting
二元分类问题
训练数据:
(x1, y1), …, (xm, ym)
where xi∈X, yi∈Y={-1, +1}
Dt(i): 样本xi 在第t次迭代的权重
D1(i)=1/m
ht(X):弱学习器Ct训练得到的判别函数
ht:X->{-1, +1}
εt:ht(X)的错误率

2) 基本思路
a) 训练一系列弱学习器h1, h2, …, hT。
b) 在训练过程中,注重那些分类错误的样本。
c) 把训练出来的一系列弱学习器组合起来,每个弱学习器ht(X)都有一个相应的权重α t:

3)AdaBoost算法
弱学习器Ct的权重αt由第t次迭代决定

训练样本的分布权重Dt (i)在每一次迭代都会更新

弱学习器Ct的选择:
    如果某次迭代的训练误差大于1/2,则抛弃,算法停止

算法在每次迭代都会更新样本的分布权重,在下一次迭代前会进行一次训练样本的重采样。

如何进行重采样?
    可根据概率分布Dt(i)来采样。“轮盘赌”算法是其中一种比较简单、高效的方法。

“轮盘赌”算法
使用一个[0~1]随机数生成器
举例:如果随机数生成器生成0.525,则恭喜你,获得“康师傅冰红茶”一瓶;若生成0.91,则能获得宝马一部。

4) AdaBoost特性分析
特性1:
    训练误差的上界,随着迭代次数的增加,会逐渐下降。

特性2:
    AdaBoost算法即使训练次数很多,也不会出现过度拟合(over fitting)的问题。


三、应用
1. 文本分类
给定某篇文档,判别其所属类别
文档可能是某些网页,也可能是短文本(query,微博等)
应用很广

AdaBoost (weak learner: NB, C4.5等)


2. 排序学习
1) 排序问题
2) 排序模型

3) 根据训练样本的形式及损失函数分类:
a) Pointwise approach
Prank
McRank
b) Pairwise approach
RankBoost
Ranking SVM
RankNet
c) Listwise approach
ListNet
ListMLE

4) RankBoost算法

参考文献
[1] Richard O. Duda, etc. Pattern Classification.
[2] Bing Liu. Web Data Mining.
[3] Tom M. Mitchell. Machine Learning.
[4] Yoav Freund, Robert E. Schapire. A short Introduction to Boosting.
[5] Dong Lehong. Survey of Boosting.
[6] Li Hang. Learning to Rank




声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/98573
推荐阅读
相关标签
  

闽ICP备14008679号