AdaBoost算法

基本思想是，对于一个复杂的问题，单独用一个分类算法判断比较困难，那么我们就用一组分类器来进行综合判断，得到结果，“三个臭皮匠顶一个诸葛亮”

专业的说法，

强可学习（strongly learnable），存在一个多项式算法可以学习，并且准确率很高 
弱可学习（weakly learnable），存在一个多项式算法可以学习，但准确率略高于随机猜测

并且可以证明强可学习和弱可学习是等价的

那么发现一个弱可学习算法是很容易的，如果将弱可学习算法boosting到强可学习算法？

AdaBoost就是这样的算法，通过反复学习，得到一组弱分类器，通过组合这些弱分类器得到强分类器

问题就是如果得到一组弱分类器？

当然你可以用不同的分类算法来训练 
也可以用不同的训练集，比如bagging，对训练集进行m次随机抽样，得到m个新的训练集

AdaBoost采用的方法是，用相同的算法和训练集，但改变每个训练样本的weight，因为在求解分类器时的目标函数是，加权误差最小，所以不同的权值会得到不同的分类器参数 
具体的规则，是每轮分类后， 增大分错的样本的权值，减小分对样本的权值，所有样本权值和为1 
这样下一轮分类器求解，就会更关注上一轮分错的这样样本点，达到分而治之的目的

需要注意，可以想到，这个算法对离群值比较敏感，容易overfitting

并且每个弱分类器也有个weight，代表该分类器的误差率，最终用加权多数表决的方式来得到最终结果

具体算法，

对于 训练集

1. 初始化训练样本的权值，平均分布，每个样本的概率相同

2. 反复迭代学习得到m个弱分类器，对于第m个弱分类器，

2.1 对于训练集，以加权误差最小为目标，求出分类器，Gm

2.2 算出，该弱分类器的加权误差

2.3 算出该弱分类器的权值，log函数，可见误差越小，权值越高，即在最终强分类器中的作用越大

2.4 关键的一步，更新训练样本的权值

其中，第一个式子其实是，

指数分布，小于0，取值在(0,1)，大于0，取值大于1 
所以意思就是，当Gm(x)=y的时候，即判断正确的样本，减小权值 
判断错误的样本，增加权值 
之所以要除以Zm，是因为所有权值的和要为1，用Zm来进行规范化

3. 上面我们就得到m个弱分类器，如何组合出强分类器，

很简单的，加权多数表决 
其中sign函数，取值-1(x<0)，0，1(x>0)

本文章摘自博客园，原文发布日期： 2014-08-26