Boosting

训练集中一共有$n$个点,我们可以为里面的每一个点赋上一个权重$W_i$,表示这个点的重要程度.通过依次训练模型的过程,我们对点的权重进行修正,如果分类正确了,权重降低,如果分类错了,则权重提高,初始的时候,权重都是一样的。

可以想象得到,程序越往后执行,训练出的模型就越会在意那些容易分错(权重高)的点。当全部的程序执行完后,会得到M个模型,通过加权或投票的方式组合成一个最终的模型$Y_M(x)$。


Re-Weighting

前面提到过,模型做Aggregation的时候,我们希望模型间的差异越大越好。比如在Bagging里面我们通过Bootstrapping生成不同的训练集来训练出不同的模型,当我们模型对训练集比较敏感时,将会得到比较好的结果。

现在我们希望通过加权的方式来改变样本的分布,从而训练出不同的模型,那么如何加权可以使得模型之间的差异更大呢?

如果上一轮训练出来的模型在这一轮的加权方式下表现的很糟糕,猜对的概率就像扔硬币一样,那么这一轮训练出的模型将会和上一轮有很大的区别。


具体怎么做呢?


更好的做法,


总结一下,


AdaBoost

现在我们可以得到初步的算法流程,


但同时我们会面临一个问题,训练出的模型如何做Aggregation呢?每个模型都重点针对上一次分错的点,之前分对的点实际上关注度就会下降,这会使得我们单个的模型在训练集上表现得并不好($E_{in}$),所以我们无法通过线性的方式进行融合。


算法流程

这就是AdaBoost的雏形了。


理论保证

理论保证,为什么多个弱分类器通过Boosting可以获得一个强分类器。