分享

更多

   

Boosting原理及其应用

2014-10-15  why201312...
一、背景

故事:

   某男到医院就诊,医生亲切地问了一些该男的症状,最后得出结论:“医生说我怀孕了。。。”


血淋淋的故事告诉我们:

    需要一个好的诊断器:根据病人的一系列症状,得出病人患的是什么病。


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


分类问题很常见:

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.






    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章
    喜欢该文的人也喜欢 更多