机器学习技法-lecture8：Adaptive Boosting

Adaptive Boosting

lecture7中我们主要介绍了blending和bagging,当hypothesis已知时可以我们可以uniformly/linearly/nonl-linearly地组合已知的有差异的hypothesis；反之可以通过又放回采样产生不同的资料进而得到有差异的hypothesis，然后接着往下进行。本节课我们将讨论一个新的演算法—adaptive boosting。

Motivation of Boosting

首先我们先看一个小学生的苹果辨识问题，类似监督学习的过程，老师一共提供了20张水果的图片，其中10张是是苹果10张非苹果，然后分别让4个学生观察给出辨识的可能规则，先后有4个同学根据前一个同学犯错的例子总结了4个规则：可能是圆的，可能是红的也可能是绿的，还可能是带柄的。

在整个问题中，小学生提出的规则对应的就是那些简单的hypothesis g,最终结合多个g我们总结得到了复杂的G，而老师扮演的角色就是引导学生将更多的关注点放在一些关键的犯错的例子上，然后我们的目的就是揭示这个演算法背后的数学本质。

Diversity by Re-weighting

我们回顾下在bagging里面做的事情，中间的主要过程是bootsrap,实例化一下我们原始有资料集D，通过bootstrap过程产生资料集D’，然后计算新资料集上的0/1损失，实际上我们可以通过引入参数u使其转化为计算D上的error的问题，也就是说bagging所做的事情就是产生u,然后透过基础的algorithm最小化资料集D上的weighted Ein进而得到不同的g的过程。

接下来我们需要思考的是如何将u加入我们的演算法的问题，我们来看两个例子，在SVM中，实际上最终的u对整个问题的改变只是放缩了α的上界；在logistic regression中，当选用SGD方法时，我们只需要将u作为抽样的比例即可实现；由此可见将u加入基础的演算法是不难做到的，接下来先假设我们可以实现这个过程进入下一步的讨论。

接下来我们的思考是怎么通过bagging的过程得到不同的hypothesis以便于后面的aggregation过程，我们的思路是这样的，我们先通过一个u1任取一个g1,然后我们将g1上加入另一个weigh u',如果g' “表现很差”则不回传g1或者与g1相似的hypothesis都不会被选择作为g',由此保证了g'与g的差异性。

然后需要明确的“表现很差”如何度量？我们通过计算某个u的犯错的期望，如果期望与丢硬币的效果(1/2)差不多则表现很差。

通过一些数学上的推导，我们知道只需要将犯错误的点的权重和与没犯错误的权重和相等，就可以达到另某个hypothesis表现很差的目的，于是可以在数学处理上做到optimal re-weighting的过程。

Adaptive Boosting Algorithm

我们将得到不同的hypothesis的过程总结一下：首先我们计算某个g的错误率εt,然后我们定义一个scaling factor:(1-εt)/εt的平方根，然后对错误的点和非错误的点进行缩放，在这个条件下scaling factor有一定的物理意义，一般情况下εt是小于等于0.5，于是scaling factor大于1，相应缩放的意义就是放大错误点的权重和降低正确点的权重，而这也就是最开始例子中老师扮演的角色，通过放大错误的点的权重从而达到产生不同hypothesis的目的。

于是我们可以得到演算法的基本流程如上图，需要完善的问题主要有两个：1、首先是g1的怎么取的问题，一般情况下我们取每个点权重为1/N；2、怎么合并为最后的G的问题，显然uniform形式是不可取的，于是我们思考的方向是linear/non-linear形式，接下来我们将介绍一个可以边得到g边确定α的演算法。

接下来我们的主要问题是在得到一个g之后怎么计算相应的α，我们的原则是犯错误越小的g应当获得更多的投票权即更大的α，于是我们很自然地与前面定义的关于εt的参数scaling factor联系起来，通过取其对数来得到相应的α，对具体的α值分析可以知道它是合理的。于是我们完善了整个演算法，我们将其称为Adaptive Boosting,这个演算法的三元素是：1、students:那些看起来比较弱的g;2、teacher：不断修正的scaling factor;3、class:确定α后的aggregation过程，然后我们可以整理得到完整的AdaBoost演算法流程如下：

本节课我们主要介绍AdaBoost演算法，首先我们引入小学生苹果辨识案例，然后我们结合bagging引出了weighted based algorithm，接着我们实现了通过产生不同的weight产生不同的g,更进一步我们定义了scaling factor，联系得到了α，最终整体上完成了AdaBoost算法的推导。