Boosting原理及其应用_kearns和valiant(1989)提出的强学习与弱学习等价性原理

一、背景

故事：

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

血淋淋的故事告诉我们：

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

 

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

 

分类问题很常见：

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

 

示例：

仔细观察c1 c2 c3  最后一幅图是有前面图的 划分线拼凑而成

 

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.

 

原文： http://blog.chinaunix.net/uid-8695538-id-3130689.html