Boosting原理及其应用(二)

二、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)的问题。