机器学习技法总结（五）Adaptive Boosting, AdaBoost-Stump,决策树

上一讲主要利用不同模型计算出来的g。採用aggregation来实现更好的g。假设还没有做出来g。我们能够採用bootstrap的方法来做出一系列的“diversity”的data出来。然后训练出一系列的g。比方PLA来说，尽管模型一样，就是直线对二维平面的切割，模型都为直线，那么我们利用bootstrap来做出不同的数据，然后计算出不同的g，然后融合后就能够得到非常好的效果。或者也能够通过调整PLA的初始值来训练，得到一堆g，最后融合（parameter diversity，random initial。。。

）

以下主要讲一下一个更加强的机器学习的技法：Adaptive boosting。

以下以老师教小孩认识苹果的过程，将标识苹果的特征（形状（圆的），颜色（红的、绿的）。。

。

等等），一个同学说苹果形状是如何，还有一个同学说苹果颜色是如何，然后还有其它同学说苹果还有其它特征，就这样一次次的给苹果添加特征，然后联合起来就能让同学们都能非常好的认出苹果了（苹果的概念就非常丰富了）。

先从bootsrapping開始引入adaptive boosting，利用bootstrap来生成u，然后就比較像是Re-weighting process，用来优化Re-Weight Ein_u（h）为最小。

pic3

就是小u相应着data中数据点被抽样的次数，怎样得到g(t)与g(t+1)是有差异的呢？调整这个u(weight)来使得得到的g(t)在下一轮表现非常不好。这样g(t+1)就与g(t) diversity了。

做出u(t+1)在g(t)上的加权error大致等于掷硬币的概率0.5就好了。

在数学上仅仅须要让犯错误的u之和与没有犯错的u之和相等就能够得到0.5。处理方法：将错误的点乘以对的比率。让正确的点乘以错的比率，例如以下图所看到的：

在数学上。通过将factor规则化，scale up incorrect , scale down correct（有点类似PLA，对错误放大，然后进行调整，就像老师教学生认识苹果一样，贾同学说了苹果是圆形的，可是他在橘子上犯错了，那就放大苹果与橘子的区别，对颜色。通过颜色分别，加强对苹果认识）例如以下所看到的：

我们通过bootstrap中不同的u得到了一系列小g。那么u的更新过程就例如以下图来进行。最后将小g合并得到非常好的非常强非常丰富的G。

能够利用线性aggregation的方法来融合全部的g。得到G。

所以，这个线性的权重怎样衡量呢？我们能够用g的表现性能来进行决定alpha。算法设计的时候，用来衡量的话採用了ln()来做，当推断的概率为0.5时。就像是掷硬币一样。这样权重计算就为0，我们不选这种没用的g，当犯错误的概率为0时，计算出的权重为无穷大，这样也是合理的啊。

这样从理论上分析一下。Adaboost有何优点呢？我们知道VC bound来进行，仅仅要我们得到的小g比乱猜做的好一点。通过逐步的（AdaBoost + 演算法）。我们就能够在T=O(log(N))次的逐步演进就能够得到Ein(G)=0,同一时候依据VC bound 我们能够看出upper bound也非常小，即Eout也能保证非常小，从而实现比較好的性能。

所以。我们仅仅须要一个可以比乱猜好一点的“weak” base 学习算法A，通过adaboost就行做到最好的G。一个很好的用于adaboost的演算法—decision stump（决策树）。decision stump是利用单一的feature进行切割，二维平面上就是一条条垂直或水平的线。由于它仅仅在一个维度下进行切割。

所以，假设单独的decision stump就是一个比較弱的分类器。那么结合了adaboost呢？以下就给出几个样例