本文参考整理了Coursera上由NTU的林轩田讲授的《机器学习技法》课程的第八章的内容，主要讲解了Adaptive Boosting的引入动机、如何通过加权example来获得多样的假设函数、AdaBoost的伪代码实现及其在现实生活中的应用等。文中的图片都是截取自在线课程的讲义。
欢迎到我的博客跟踪最新的内容变化。
如果有任何错误或者建议，欢迎指出，感激不尽！
--
本系列文章已发八章，前七章的地址如下：
- 一、线性SVM
- 二、SVM的对偶问题
- 三、Kernel SVM
- 四、Soft-Margin SVM
- 五、Kernel Logistic Regression
- 六、Support Vector Regression
- 七、Blending and Bagging
Motivation of Boosting
一个简单类比
想像一个小学老师教小学生如何分辨一张图片是否是一个苹果的场景，老师在网络上搜集了很多苹果的图片。
10张苹果的图片
10张非苹果的图片
你怎样描述一个苹果的特征？
- Michael:
苹果是圆形的
蓝色部分表示错误识别为苹果的例子或者没有正确识别出苹果的例子。
课堂已经获得的特征：
- 苹果是圆形的(Michael)
老师可能会把错误的例子举出来，把分类正确的例子缩小，把错误的例子放大，投入更大的关注，再寻找特征。
- Tina:
苹果是红色的
课堂已经获得的特征：
- 苹果圆圆的(Michael)
- 苹果红红的(Tina)
老师继续放大错误的，缩小正确的
老师：的确，大部分苹果是红色的，但是只靠圆形和红色来区分苹果还是有可能犯错，你有其他的建议吗？Joey?
- Joey:
苹果也可能是绿色的
课堂已经获得的特征：
- 苹果圆圆的(Michael)
- 苹果红红的(Tina)
- 苹果可能是绿色的(Joey)
老师继续放大错误的，缩小正确的
- Jessica:
苹果上面有茎
课堂已经获得的特征：
- 苹果圆圆的(Michael)
- 苹果红红的(Tina)
- 苹果可能是绿色的(Joey)
- 苹果上面有茎(Jessica)
通过不断集中于分类不太完美的例子，寻找新的特征描述，我们得到了比原来更加丰富的对苹果的认知，这就是逐步增强法(adaptive boosting)的原理所在。
Motivation
对应到我们的adaptive boosting algorithm的概念中
学生：代表一些很简单的hypotheses gt(就像垂直/水平分隔线)
班级：整个班级有很多学生，就是一个复杂的hypothesis G(就像下图中黑色的实线)，就是灰线的aggregation。
老师：一个循循善诱的学习算法，它使得学生去专注于犯过错的关键样例中。
下一节，我们将介绍逐步增强法的数学形式。
Diversity of Re-weighting
Bootstrapping as Re-weighting Process
Bagging的核心就是bootstrapping
在base algorithm中获得gt的要求可能如下
既然两笔(X1,y1)一样，不妨写成更简洁的形式
我们给每笔资料添加一个权重u
显然，两种表示方式等价。
这样，Bagging所做的就是通过bootstrapping产生这些u
base algorithm尝试最小化bootstrap-weighted error.
Weighted Base Algorithm
Bagging中u都是整数，但既然u是权重，自然可以推广到全体实数。
如何求解带有权重的Ein最小化问题呢？
SVM
比如，在SVM中，我们使用C来表示0/1错误的权重，加上权重u后
un就会跑到αn的上限位置，因此求解weighted SVM是容易的。
Logistic Regression
SGD抽样时候的概率大小不同，被抽到的概率与un成正比。
因此，把un放到algorithm中，不是特别困难。如果你学过《机器学习基石》的第8章，可能记得我们讲过class-weighted，不同类别的错误代价不同，现在不是+1或-1哪一种更重要，而是哪一个点更重要，即example-weighted是class-weighted的扩展。
因此，求解weighted base algorithm不是困难点，先想象我们已经会做这件事情了。
Re-weighting for More Diverse Hypothesis
既然，我们的base algorithm会根据u回传g，那么，我们希望g越不一样越好，怎样的u能保证这一点？
how to re-weight for more diverse hypotheses?
如果gt对于u(t+1)表现很差，那么像gt的hypotheses都不会被传回作为g(t+1)，因此g(t+1)和gt差别就很大。
表现很差如何衡量?
gt对u(t+1)的预测错误的概率，和随便猜的几率差不多，即1/2(样本平衡的状态下)。
Optimal Re-weighting
我们需要
一种可能的方法是重新放缩权重
如果第t轮错误率为εt，正确率则为1-εt。
'最优的'重新放缩方法是正确的点所对应的un乘上错误率εt，错误的点的un乘上正确率(1-εt)。
Adaptive Boosting Algorithm
Scaling Factor
定义放缩因子则
与上节的放缩效果等价。
◇t告诉了我们更多物理意义，比如如果◇t>=1，则当且仅当εt<=1/2
base algorithm应该比乱猜的效果好，则εt<=1/2，则◇t应该大于1，也就是错误的真的被放大了，正确的真的被缩小了，也就是我们之前讲的"放大错误、缩小正确"，正如刚才的类比中的老师所做的事情。
A Preliminary Algorithm
- 希望g1能对Ein最优，即un(1) = 1/N
- G(X)如何aggregate这些g呢？
- uniform g1做好了D1，但g2在D1上应该做得很糟，一人一票，也许不会做得很好
- linear,non-linear? as you wish
接下来，介绍一种在计算g中顺便将g线性融合的特殊算法。
Linear Aggregation on the Fly
α怎么计算？
- 希望好的g能多给一点票，即α大一点，而坏的g的α小一点。
- 那么什么是好的g?
好的g，Ein(u)比较小，错误率ε比较小，那么◇比较大，那么αt应该是某个单调函数(◇t)，设计该演算法的人使用了单调函数ln()。
即
如果ε=1/2，则◇t=1 ==> αt = 0 (对于坏的gt的权重为0)
如果ε=0，则◇t=∞ ==> αt = ∞ (好的g有更大的权重)
因此，adaptive boosting = 弱弱的base learning algorithm A(学生) + 最优的重新加权因子◇t(老师) + '神奇的'线性aggregation系数αt(班级)。
Adaptive Boosting (AdaBoost) Algorithm
AdaBoost：三个臭皮匠，胜过诸葛亮。
AdaBoost的理论保证
VC bound
- 第一项可以做得很小，理论已经证明 Ein(G) = 0 after T = O(log N)轮。（如果总有εt<=ε<1/2，即base algorithm比"乱猜"表现好）
- 第二项T很小、N很大，则整体也很小
则Eout(G)也很小，则实际表现很好。
从boosting的角度看待AdaBoost:
只要base algorithm A稍微比"乱猜"好一点，那么通过AdaBoost + A就可以使它变得很强(Ein = 0 && Eout 很小)。
Adaptive Boosting In Action
decision stump
一个流行的选择：决策桩
它是在某个单一的feature上的正/负向射线，有三个参数(feature i、threshold θ、direction s)。
可以通过枚举(i,θ,s)的组合，真的做到最好。
物理意义：2D平面上的垂直/水平线。
优化效率：O(d*NlogN)
decision stump如果单独用，大部分情况下太弱了，但配合AdaBoost可以变强，且允许有效率地最小化Ein(u)。
A Simple Data Set
'Teacher'-like algorithm works!
A Complicated Data Set
边界是一个类似sin的形状
AdaBoost-Stump: non-linear yet efficient
AdaBoost-Stump in Application
世界上第一个'实时'人脸识别程序
- AdaBoost-Stump作为核心模型，从24*24的小图块的162336个可能性中选择出来关键的图案，然后进行线性aggregation，即通过AdaBoost-Stump来进行特征选择。
- 修改了线性融合G，提前排除非人脸部分。
AdaBoost-Stump: efficient feature selection and aggregation。
Mind Map Summary
我们讲过了Bagging，它是Learning Uniform Aggregation；我们讲过了AdaBoost，它是Learning Linear Aggregation。在下一章，我们将介绍一种Learning Conditional Aggregation的方法，即决策树(Decision Tree)，敬请关注。
