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