林轩田机器学习技法第八讲-Adaptive Boosting

上一讲学习了如何使用blending将很多的g结合起来，从而提升模型的整体的效果，已经如何使用boosting来从一个数据集中产生多个不同的新数据集。这一讲来看一下提升算法，主要看Adaptive Boosting这个算法。

我们有一个简单的例子引入：当我们刚刚开始辨别事物的时候通常需要学习一系列的规则，比如在识别苹果时，A说苹果是圆的，反映到下面的数据集中，有些是对的，但是有些被错分了

然后讲分对的图片缩小，分错的图片放大，再去问另一个人。B说苹果除了是圆的还是红的，但是数据集中有青苹果，也有一些是红色的但不是苹果的，所以再次进行处理问另一个人

C说苹果也可能有绿的，那么蓝色部分的就被错分了，再次进行处理

然后问D说：顶部有梗的才是苹果，结果如下所示

这样经过上面几个人的认识，我们大致可以得到如下的一条辨别是否是苹果的规则

如果将其放映到图像中，每一个人的规则就是一个简单的h，即图中浅色的直线，每一条的划分效果都不是很好，而最终将所有的规则整合起来就如图中黑色的折线所示，效果很好。这里的询问人就像是一个演算法，它引导着h去关注那些关键性的数据，大多数是分错的数据

假设我们通过boosting从D中产生了一个新的数据集Dt如下所示，其中包含有两个(x1,y1)和一个(x2,y2)、(x4,y4)。如果按照最基本的做法来做，通常是如右下图黄框所示的样子，求一个最小的Ein0/1，但是这里的数据集中数据是有重复的，所以我们可以按照左下图蓝框的方法，在求和前加Ui表示每个数据的数目，再求最小的Ein。

这里的Ui就相当于权重，也可以说是惩罚项，值越大惩罚越多，反之越少。这种通过boosttrap的方式得到Ui，然后按照之前的方法最小化Ein的方法称之为booststrap-weighted error

求解的目标问题就如下所示

这种思想其实亦可以应用到在前面的算法中，比如在SVM中，我们可以在每个数据前面加上权重Ui，在经过QP方法求解，他最终会反映到αn的上界中

而在Logistic regression中，通过加入Ui表示错误点出现的次数，告知误差衡量在最小化error时更重视出错的点

在引入Ui之后，采用下面的公式得到gt和gt+1，如果gt在使用新的Ut+1是error很大，表示由Un+1计算得到gt+1和gt有很大的不同

那么如何得到上述的这种差异性呢？我们可以利用gt在使用Ut+1的时候表现很差的条件，如果在gt作用下， Ut+1中的表现近似为0.5的时候，表明gt对Ut+1的预测分类没有什么作用，就像抛硬币一样，是随机选择的。这样就能最大限度地保证会与有较大的差异性，其数学表达式如下红框所示：

那么如何解上式呢？为了后面表述方便，我们用橘色的框表示分子，即gt下犯错的点，绿色的圈表示分母，即所有的样本点，希望值为1/2。很容易想到的就是把犯错的点的数量和不犯错的点的数量调成相同的不就行了？即gt在Ut+1下犯错的数量和不犯错的数量相等。一种简单的方法就是放缩，将犯错的和没有犯错的作相应的乘积，使其相等，比如如下的方式

一般的话如果令犯错率为ε，做法是不正确的乘以1-εt，正确的乘以εt

下面定义如下的一个因子◇t，对于错误的Un乘以◇t，正确的除以◇t，它的效果和之前的ε是一样的，只是可以告诉我们更多地物理信息。如果εt≤1/2，得到◇t≥1，那么Un错误的与◇t的乘积把错误点放大了，而正确的Un与◇t的相除把正确点缩小了。这种scale up incorrect和scale down correct的做法与前面介绍的放缩是一致的，让模型更加关注出错的数据，能够保证得到不同于gt的gt+1

将◇t引入到演算法中如下所示，迭代公式发生了变化

但是上面的演算法存在两个问题：
1. U1应该是多少？
2. G(x)如何求？
相对应的给出解决的办法：
1. 初始时都是平等的，所以设置为1/N
2. 一般对所有的g(t)进行线性或是非线性的组合

如果采取上面的解决办法，对gt采取线性组合的方式，在计算g(t)的同时就能计算得到αt，是最终求得gt+1时，所有gt的线性组合的参数也就求得了。

那么如何在每次迭代的时候计算αt？我们知道αt与εt是相关的：εt 越小对应的αt应该越大，εt 越大对应的αt应该越小。又因为◇t与εt是正相关的，所以αt应该是◇t的单调函数。我们构造αt为如下黄框的形式。

例如当εt=1/2时，error很大，和掷骰子这样的随机过程没什么两样，此时对应的◇t=1、αt=0， 即gt对G没有什么贡献，权重应该设为零。而当εt=0时，没有error，表示gt预测非常准，此时对应的◇t=∞、α=∞，即gt对G贡献非常大，权重应该设为无穷大。

我们就称这种算法为Adaptive Boosting 算法，由一个基本的演算法A、权重的调整因子◇t和aggregation时的线性组合因子αt组成

完整的算法流程如下所示

理论上算法复杂度一部分是模型的复杂度，一部分是维度带来的复杂度，那满足如下的关系。对于Ein来说，如果满足εt≤ε<1/2，经过T次迭代后可以减小到零。对于第二项来说，当N很大时，也能变的很小

这种性质也正是AdaBoost算法的精髓所在。只要每次的εt≤ε<1/2，即所选择的矩g比乱猜的表现好一点点，那么经过每次迭代之后，g的表现都会比原来更好一些，模型的效果逐渐变强，最终得到Ein=0且Eout很小。

接下来看一下AdaBoost是如何使用decision stump解决实际问题的。假设二维平面上分布一些正负样本点，利用decision stump来做切割。

按照前面的算法思想，经过多次迭代，最后模型的效果就会很好，基本上没有分错的点

当数据点很多时，同样可以达到很好的效果，只是分类边界可能复杂一些。所以可以认为AdaBoost-stump这种非线性的模型对于上述的这类样本有很好的分类效果

最后总结一下，这一将主要学习了AdaBoost算法，如何通过一系列的操作，使得最后模型达到一个不错的效果

补充一些概念性的东西：

当我们拥有了不同的算法后，能否将其结合起来组成一个更强的分类器，这就是元算法的思路。AdaBoost就是其中最流行的算法，它的特点如下：
• 优点：泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整；
• 缺点：对离群点敏感
• 适用数据类型：数值型和标称性数据

强可学习：在PAC框架下，一个概念如果存在一个多项式的学习算法可以学习它，并且正确率很高，就称是强可学习的
弱可学习：在PAC框架下，一个概念如果存在一个多项式的学习算法可以学习它，但是学习的正确率仅仅比随机猜测要好一些，就称它是弱可学习的。
但是可以证明：强可学习和弱可学习在PAC框架下是等价的，即一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

Bagging：基于数据随机重抽样的分类器的构建方法，它从原始的数据集中进行S次的重抽样，每次都选取一个新的数据替换，得到的新的数据集将大小不改变，重复S次就会得到S的数据集；我们使用不同的算法作用的S个数据集上，就可以得到S个不同的分类器，我们选择分类器中投票最高的类作为我们最终的分类类别，常用的比如随机森林。

boosting：是一种将弱学习器提升为强学习器的算法，它首先根据训练数据集来学习到一个基学习器，再根据基学习器中分类错误的数据对样本进行调整，下一次训练时更加关注上次分错的数据，训练再次得到一个学习器，知道到达指定的值T，这样就得到了T个学习器，将其进行加权结合，每个权重代表在上一轮中迭代的成功度。·

算法流程：
a. 收集数据
b. 准备数据：依赖于使用的弱分类器
c. 分析数据：任意方法
d. 训练算法：花费大部分的时间，分类器在同意数据集上训练弱分类器
e. 测试算法：计算错误率
f. 使用算法

大多数的提升算法的思想都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列的弱分类器，然后将这些弱分类器结合起来，构成一个强分类器。

所以提升算法主要关注两个问题：
1. 在训练的每一轮如何改变训练数据的权值分布
2. 如何将一系列的弱学习器组合成一个强学习器

针对这两个问题，boosting中最著名的AdaBoosting的做法是：
1. 提高前一轮被弱分类器分错的数据的权值，而降低那些被正确分类的数据的权值
2. 加权多数表决的方法：加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值

在《统计学习方法》中关于AdaBoost算法（adaptive boosting）的算法描述：