Weighted Base Algorithm
(1)基本算法引入权重
加权这类算法给每一个数据一个权重，这个权重能够看做是该数据点有几份。
在之前介绍的SVM算法中。对于一个错误扣除C的分数，而对错误加权之后。每一个数据点将扣除C·un这个多的分数，这个參数经过二次规划的计算之后，就会到α的上限中去。
对于逻辑回归来说，un能够作为样本(xn,yn)的抽样比例。
这两个样例说明将权重系数放入详细的算法中是可行的。
(2)让如果区别更大
上一节介绍Aggregation时我们知道，各种如果的区别越不一样，通过组合的机制能够得到更好的结果。
那么，我们该怎样改变u让如果g区别越大越好？
我们知道g(t)是由un(t)加权得到的。g(t+1)是由un(t+1)加权得到的。
那么，如果g(t)使用un(t+1)进行加权的结果效果非常不好，那么使用un(t+1)得到的g就会和g(t)非常不一样，那么就得到了和g(t)区别非常大的g(t+1)。
于是，我们就得到了让g(t)和g(t+1)非常不一样的方法：让g(t)在下一轮的权重之下，表现非常差。
如果g(t)的表现非常差是什么意思？就是g(t)的表现是随机的，在二元分类的情况下，其加权之后的误差被均一化之后的结果应该是1/2。
上面这个式子事实上能够表示为(犯错误的数据与对应权重的乘积) / (犯错误的数据乘以对应权重+没有出错的数据乘以其权重)。也就是说。犯错误的数据乘以对应权重的值 = 没有出错的数据乘以其权重的值。
为了达到这个目的，最优更新权重(optimal re-weighting)的方式是：把做对的数据对应的权重un(t)乘上错误的比率εt。把做错的数据对应的权重un(t)乘上正确的比率(1-εt)，这样来更新权重un(t+1)。
Adaptive Boosting Algorithm
放缩因子
上一小节中。我们讨论了最优更新权重方法，通过事先计算出来错误率εt，然后将错分数据的权重乘上(1-εt)，将正确分类数据的权重乘上εt得到新的权重。
以下。我们使用一种更加简单等价的方式来更新权重。这里的放缩因子称为◆t：
这里的◆t有更清晰的物理意义。通常情况下εt < 1/2（由于是学习之后的结果。错误率应该小于0.5），这样◆t将大于1。那么。犯错的数据将乘上大于1的数。正确数据将除以大于1的数，使得提升了犯错数据的权重(scale up incorrect)。减少做对数据的权重(scale down correct)。这样使得更加专注在犯了错的地方，来得到不一样的如果(diverse hypotheses)。
边得到g边确定系数α
这里介绍Linear Aggregation的流程大体是这种：
首先u(1)=[1/N, 1/N, … , 1/N]，通过某个算法得到g(t)。不断更新u(t)，这里还须要得到α(t)，终于通过α(t)和g(t)的线性组合的形式，得到G(x)。
如今的问题是α(t)是什么？主要的想法是，好的g应该α大一点。坏的g应该α小一点。那么，好的g。其ε小（错误率低），那么◆比較大，那么α应该是◆的单调函数的结果。
设计这个算法的人将α觉得是ln(◆)。
算法流程例如以下：
这里之所以觉得αt = ln(◆t)，处于以下的考虑：
如果εt = 1/2， 那么◆t = 1，则αt = 0，意思是随机乱猜的情况下（二元分类错误率为0.5），觉得是坏的g。则一票不给个。不使用该g
如果εt = 0。 那么◆t = ∞。则αt = ∞，意思是正确率为0的情况，给它无限多票数
上面介绍的方法称为Adaptive Boosting方法。当中有三个元素，当中包含弱算法、放缩因子和线性的组合。
能够将这个流程看做是学生在课堂上进行学习，学生看了数据资料，进行分类的选择（由于缺乏全面的认识，得到知识可能是准确的），然后老师再将数据资料进行重要性的放大和缩小（将学生犯错的数据资料拿出来给予很多其它的重视，对于做对的数据资料给予较少的关注），将这一系列的过程合起来，相当于通过不同学生的认识综合起来，得到一个更好的认知结果。
AdaBoost算法完整流程
AdaBoost理论特性
通过之前的VC Bound，来约束測试误差，当中蓝色的部分是模型的复杂度，O(dvc(H))为g的模型复杂度，而O(dvc(H))·T·logT是模型G的复杂度。
原作者证明说，能够用O(logN)次迭代能够将Ein(G)做到非常小。而且当数据量N足够多的情况下。又能够使得模型复杂度变得非常小，从而使得模型复杂度得到控制。终于预測效果Eout也会非常好。
AdaBoost的保证是让一个非常弱的算法不断变强，终于得到一个非常强是算法（Ein=0。Eout is small）。
Adaptive Boosting in Action
上面的AdaBoost仅仅须要一个非常弱的算法就能够使用。
普通情况下。能够使用决策桩(Decision Stump)，该模型相当于在某一个维度上的Perceptron模型。
转载请注明作者Jason Ding及其出处
GitCafe博客主页(http://jasonding1354.gitcafe.io/)
Github博客主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354进入我的博客主页