Adaboost详解（转）
我的图书馆
Adaboost详解（转）
提到AdaBoost的人脸识别，不得不提的几篇大牛的文章可以看看，但是大牛的文章一般都是只有主要的算法框架，没有详细的说明。大牛论文推荐：1. Robust Real-time Object Detection, Paul Viola, Michael Jones2. Rapid Object Detection using a Boosted Cascade of Simple Features, 作者同上。还有一篇北大的本科生的毕业论文也不错：基于 AdaBoost 算法的人脸检测，赵楠。另外，关于我写的AdaBoost的人脸识别程序的下载地址：1. C++版本：说明：需要自己配置opencv2.3.1, 自己配置分类器。在程序运行前会捕捉10帧用户图像，计算人脸平均面积，这个过程不会有显示，但是程序没有出问题，稍等一会就会出现摄像头信息。&2. C#版本：说明：使用了emgucv2.3.0的库，需要自己重新添加引用动态链接库文件。两个版本的程序都能正确运行，没有任何问题。特别说明：一般进行人脸检测以后，会对检测到的人脸特征进行提取，处理等操作。常用的操作就是人脸特征点定位，嘴角、眼睛、下吧等特征点的定位，这个技术比较成熟的算法是ASM(主动形状模型)，关于ASM的详细介绍请见：1. Adaboost方法的引入1.1 Boosting方法的提出和发展&&&&&&& 在了解Adaboost方法之前，先了解一下Boosting方法。&&&&&&& 回答一个是与否的问题，随机猜测可以获得50%的正确率。如果一种方法能获得比随机猜测稍微高一点的正确率，则就可以称该得到这个方法的过程为弱学习；如果一个方法可以显著提高猜测的正确率，则称获取该方法的过程为强学习。1994年，Kearns和Valiant证明，在Valiant的PAC（Probably ApproximatelyCorrect）模型中，只要数据足够多，就可以将弱学习算法通过集成的方式提高到任意精度。实际上，1990年，SChapire就首先构造出一种多项式级的算法，将弱学习算法提升为强学习算法，就是最初的Boosting算法。Boosting意思为提升、加强，现在一般指将弱学习提升为强学习的一类算法。1993年，Drucker和Schapire首次以神经网络作为弱学习器，利用Boosting算法解决实际问题。前面指出，将弱学习算法通过集成的方式提高到任意精度，是Kearns和Valiant在1994年才证明的，虽然Boosting方法在1990年已经提出，但它的真正成熟，也是在1994年之后才开始的。1995年，Freund提出了一种效率更高的Boosting算法。1.2 AdaBoost算法的提出&&&&&&& 1995年，Freund和Schapire提出了Adaboost算法，是对Boosting算法的一大提升。Adaboost是Boosting家族的代表算法之一，全称为Adaptive Boosting。Adaptively，即适应地，该方法根据弱学习的结果反馈适应地调整假设的错误率，所以Adaboost不需要预先知道假设的错误率下限。也正因为如此，它不需要任何关于弱学习器性能的先验知识，而且和Boosting算法具有同样的效率，所以在提出之后得到了广泛的应用。首先，Adaboost是一种基于级联分类模型的分类器。级联分类模型可以用下图表示：级联分类器介绍：级联分类器就是将多个强分类器连接在一起进行操作。每一个强分类器都由若干个弱分类器加权组成，例如，有些强分类器可能包含10个弱分类器，有些则包含20个弱分类器，一般情况下一个级联用的强分类器包含20个左右的弱分类器，然后在将10个强分类器级联起来，就构成了一个级联强分类器，这个级联强分类器中总共包括200若分类器。因为每一个强分类器对负样本的判别准确度非常高，所以一旦发现检测到的目标位负样本，就不在继续调用下面的强分类器，减少了很多的检测时间。因为一幅图像中待检测的区域很多都是负样本，这样由级联分类器在分类器的初期就抛弃了很多负样本的复杂检测，所以级联分类器的速度是非常快的；只有正样本才会送到下一个强分类器进行再次检验，这样就保证了最后输出的正样本的伪正(false positive)的可能性非常低。&也有一些情况下不适用级联分类器，就简单的使用一个强分类器的情况，这种情况下一般强分类器都包含200个左右的弱分类器可以达到最佳效果。不过级联分类器的效果和单独的一个强分类器差不多，但是速度上却有很大的提升。级联结构分类器由多个弱分类器组成，每一级都比前一级复杂。每个分类器可以让几乎所有的正例通过，同时滤除大部分负例。这样每一级的待检测正例就比前一级少，排除了大量的非检测目标，可大大提高检测速度。其次，Adaboost是一种迭代算法。初始时，所有训练样本的权重都被设为相等，在此样本分布下训练出一个弱分类器。在第（& =1,2,3, …T，T为迭代次数）次迭代中，样本的权重由第& -1次迭代的结果而定。在每次迭代的最后，都有一个调整权重的过程，被分类错误的样本将得到更高的权重。这样分错的样本就被突出出来，得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到新的弱分类器。经过T次循环，得到T个弱分类器，把这T个弱分类器按照一定的权重叠加起来，就得到最终的强分类器。2. 矩形特征2.1 Haar特征\矩形特征AdaBoost算法的实现，采用的是输入图像的矩形特征，也叫Haar特征。下面简要介绍矩形特征的特点。影响Adaboost检测训练算法速度很重要的两方面是特征的选取和特征值的计算。脸部的一些特征可以由矩形特征简单地描绘。用图2示范：上图中两个矩形特征，表示出人脸的某些特征。比如中间一幅表示眼睛区域的颜色比脸颊区域的颜色深，右边一幅表示鼻梁两侧比鼻梁的颜色要深。同样，其他目标，如眼睛等，也可以用一些矩形特征来表示。使用特征比单纯地使用像素点具有很大的优越性，并且速度更快。在给定有限的数据情况下，基于特征的检测能够编码特定区域的状态，而且基于特征的系统比基于象素的系统要快得多。矩形特征对一些简单的图形结构，比如边缘、线段，比较敏感，但是其只能描述特定走向（水平、垂直、对角）的结构，因此比较粗略。如上图，脸部一些特征能够由矩形特征简单地描绘，例如，通常，眼睛要比脸颊颜色更深；鼻梁两侧要比鼻梁颜色要深；嘴巴要比周围颜色更深。对于一个 24×24 检测器，其内的矩形特征数量超过160,000 个，必须通过特定算法甄选合适的矩形特征，并将其组合成强分类器才能检测人脸。常用的矩形特征有三种：两矩形特征、三矩形特征、四矩形特征，如图：由图表可以看出，两矩形特征反映的是边缘特征，三矩形特征反映的是线性特征、四矩形特征反映的是特定方向特征。特征模板的特征值定义为：白色矩形像素和减去黑色矩形像素和。接下来，要解决两个问题，1：求出每个待检测子窗口中的特征个数。2：求出每个特征的特征值。子窗口中的特征个数即为特征矩形的个数。训练时，将每一个特征在训练图像子窗口中进行滑动计算，获取各个位置的各类矩形特征。在子窗口中位于不同位置的同一类型矩形特征，属于不同的特征。可以证明，在确定了特征的形式之后，矩形特征的数量只与子窗口的大小有关[11]。在24×24的检测窗口中，矩形特征的数量约为160,000个。特征模板可以在子窗口内以“任意”尺寸“任意”放置，每一种形态称为一个特征。找出子窗口所有特征，是进行弱分类训练的基础。2.2子窗口内的条件矩形，矩形特征个数的计算如图所示的一个m*m大小的子窗口，可以计算在这么大的子窗口内存在多少个矩形特征。以 m×m 像素分辨率的检测器为例，其内部存在的满足特定条件的所有矩形的总数可以这样计算：对于 m×m 子窗口，我们只需要确定了矩形左上顶点A(x1,y1)和右下顶点B(x2,63) ，即可以确定一个矩形；如果这个矩形还必须满足下面两个条件（称为(s, t)条件，满足(s, t)条件的矩形称为条件矩形）：1) x 方向边长必须能被自然数s 整除（能均等分成s 段）；2) y 方向边长必须能被自然数t 整除（能均等分成t 段）；则 ， 这个矩形的最小尺寸为s×t 或t×s， 最大尺寸为[m/s]·s×[m/t]·t 或[m/t]·t×[m/s]·s；其中[ ]为取整运算符。2.3条件矩形的数量我们通过下面两步就可以定位一个满足条件的矩形：由上分析可知，在m×m 子窗口中，满足(s, t)条件的所有矩形的数量为：实际上，(s, t)条件描述了矩形特征的特征，下面列出了不同矩形特征对应的(s, t)条件：下面以 24×24 子窗口为例，具体计算其特征总数量：下面列出了，在不同子窗口大小内，特征的总数量：3. 积分图3.1 积分图的概念在获取了矩形特征后，要计算矩形特征的值。Viola等人提出了利用积分图求特征值的方法。积分图的概念可用图3表示：坐标A(x,y)的积分图是其左上角的所有像素之和（图中的阴影部分）。定义为：&&&&其中ii(x,y)表示积分图，i(x,y)表示原始图像，对于彩色图像，是此点的颜色值；对于灰度图像，是其灰度值，范围为0~255。在上图中，A(x,y)表示点(x,y)的积分图；s(x,y)表示点(x,y)的y方向的所有原始图像之和。积分图也可以用公式（2）和公式（3）得出：3.2 利用积分图计算特征值3.3 计算特征值由上一节已经知道，一个区域的像素值，可以由该区域的端点的积分图来计算。由前面特征模板的特征值的定义可以推出，矩形特征的特征值可以由特征端点的积分图计算出来。以“两矩形特征”中的第二个特征为例，如下图，使用积分图计算其特征值：1. 弱分类器在确定了训练子窗口中的矩形特征数量和特征值后，需要对每一个特征f ，训练一个弱分类器h(x,f,p,O) 。在CSDN里编辑公式太困难了，所以这里和公式有关的都用截图了。特别说明：在前期准备训练样本的时候，需要将样本归一化和灰度化到20*20的大小，这样每个样本的都是灰度图像并且样本的大小一致，保证了每一个Haar特征（描述的是特征的位置）都在每一个样本中出现。2. 训练强分类器在训练强分类器中，T表示的是强分类器中包含的弱分类器的个数。当然，如果是采用级联分类器，这里的强分类器中的弱分类器的个数可能会比较少，多个强分类器在级联起来。在c(2)步骤中，“每个特征f”指的是在20*20大小的训练样本中所有的可能出现的矩形特征，大概要有80,000中，所有的这些都要进行计算。也就是要计算80,000个左右的弱分类器，在选择性能好的分类器。训练强分类器的步骤如图：3. 再次介绍弱分类器以及为什么可以使用Haar特征进行分类对于本算法中的矩形特征来说，弱分类器的特征值f(x)就是矩形特征的特征值。由于在训练的时候，选择的训练样本集的尺寸等于检测子窗口的尺寸，检测子窗口的尺寸决定了矩形特征的数量，所以训练样本集中的每个样本的特征相同且数量相同，而且一个特征对一个样本有一个固定的特征值。对于理想的像素值随机分布的图像来说，同一个矩形特征对不同图像的特征值的平均值应该趋于一个定值k。这个情况，也应该发生在非人脸样本上，但是由于非人脸样本不一定是像素随机的图像，因此上述判断会有一个较大的偏差。对每一个特征，计算其对所有的一类样本(人脸或者非人脸)的特征值的平均值，最后得到所有特征对所有一类样本的平均值分布。下图显示了20×20 子窗口里面的全部78,460 个矩形特征对全部2,706个人脸样本和4,381 个非人脸样本6的特征值平均数的分布图。由分布看出，特征的绝大部分的特征值平均值都是分布在0 前后的范围内。出乎意料的是，人脸样本与非人脸样本的分布曲线差别并不大，不过注意到特征值大于或者小于某个值后，分布曲线出现了一致性差别，这说明了绝大部分特征对于识别人脸和非人脸的能力是很微小的，但是存在一些特征及相应的阈值，可以有效地区分人脸样本与非人脸样本。为了更好地说明问题，我们从78,460 个矩形特征中随机抽取了两个特征A和B，这两个特征遍历了2,706 个人脸样本和4,381 个非人脸样本，计算了每张图像对应的特征值，最后将特征值进行了从小到大的排序，并按照这个新的顺序表绘制了分布图如下所示：可以看出，矩形特征A在人脸样本和非人脸样本中的特征值的分布很相似，所以区分人脸和非人脸的能力很差。下面看矩形特征B在人脸样本和非人脸样本中特征值的分布：可以看出，矩形特征B的特征值分布，尤其是0点的位置，在人脸样本和非人脸样本中差别比较大，所以可以更好的实现对人脸分类。由上述的分析，阈值q 的含义就清晰可见了。而方向指示符p 用以改变不等号的方向。一个弱学习器（一个特征）的要求仅仅是：它能够以稍低于50%的错误率来区分人脸和非人脸图像，因此上面提到只能在某个概率范围内准确地进行区分就已经完全足够。按照这个要求，可以把所有错误率低于50%的矩形特征都找到（适当地选择阈值，对于固定的训练集，几乎所有的矩形特征都可以满足上述要求）。每轮训练，将选取当轮中的最佳弱分类器（在算法中，迭代T 次即是选择T 个最佳弱分类器），最后将每轮得到的最佳弱分类器按照一定方法提升（Boosting）为强分类器4 弱分类器的训练及选取训练一个弱分类器（特征f）就是在当前权重分布的情况下，确定f 的最优阈值，使得这个弱分类器（特征f）对所有训练样本的分类误差最低。选取一个最佳弱分类器就是选择那个对所有训练样本的分类误差在所有弱分类器中最低的那个弱分类器（特征）。对于每个特征 f，计算所有训练样本的特征值，并将其排序。通过扫描一遍排好序的特征值，可以为这个特征确定一个最优的阈值，从而训练成一个弱分类器。具体来说，对排好序的表中的每个元素，计算下面四个值：5. 强分类器注意，这里所说的T=200个弱分类器，指的是非级联的强分类器。若果是用级联的强分类器，则每个强分类器的弱分类器的个数会相对较少。一般学术界所说的级联分类器，都是指的是级联强分类器，一般情况有10个左右的强分类器，每个强分类有10-20个弱分类器。当然每一层的强分类器中弱分类器的个数可以不相等，可以根据需要在前面的层少放一些弱分类器，后面的层次逐渐的增加弱分类器的个数。6. 图像检测过程在对输入图像进行检测的时候，一般输入图像都会比20*20的训练样本大很多。在Adaboost 算法中采用了扩大检测窗口的方法，而不是缩小图片。为什么扩大检测窗口而不是缩小图片呢，在以前的图像检测中，一般都是将图片连续缩小十一级，然后对每一级的图像进行检测，最后在对检测出的每一级结果进行汇总。然而，有个问题就是，使用级联分类器的AdaBoost的人脸检测算法的速度非常的快，不可能采用图像缩放的方法，因为仅仅是把图像缩放11级的处理，就要消耗一秒钟至少，已经不能达到Adaboost 的实时处理的要求了。&因为Haar特征具有与检测窗口大小无关的特性（想要了解细节还要读一下原作者的文献），所以可以将检测窗口进行级别方法。&在检测的最初，检测窗口和样本大小一致，然后按照一定的尺度参数（即每次移动的像素个数，向左然后向下）进行移动，遍历整个图像，标出可能的人脸区域。遍历完以后按照指定的放大的倍数参数放大检测窗口，然后在进行一次图像遍历；这样不停的放大检测窗口对检测图像进行遍历，直到检测窗口超过原图像的一半以后停止遍历。因为 整个算法的过程非常快，即使是遍历了这么多次，根据不同电脑的配置大概处理一幅图像也就是几十毫秒到一百毫秒左右。&在检测窗口遍历完一次图像后，处理重叠的检测到的人脸区域，进行合并等操作。&程序代码样例请到第一节找下载地址。
TA的最新馆藏[转]&[转]&[转]&本类论文推荐AdaBoost学习总结 - 推酷
AdaBoost学习总结
三个凑皮匠，顶一个诸葛亮 ，打一算法: AdaBoost
本文是自己对 AdaBoost 的理解，健忘-_-!! 故记录在此.
痛点:大部分强分类器( LR ， svm )分类效果还不错，但是可能会遇到过拟合问题，并且训练相对复杂，耗时~
另外大部分弱分类器( 阈值分类器 , 单桩决策树(decision stump) 等)，他们分类的效果差，可能是极差，只会出现欠拟合，但是他们训练预测快，很快~
天下武功，唯快不破 ， 做减法不易，但是做加法就相对简单了 ^_^ 这就是 提升方法 .
提升方法 需要解决的两个问题:
在每一轮训练时如何改变数据的权值或概率分布?
如何将弱分类器组合成一个强分类器?
AdaBoost 对此进行了很好的解决:
分而治之 :将前一轮分错的样本加大权重，迫使在第二轮中对这些样本尽量分队，同时减少分对样本的权重.
加权多数表决 :加大错误率小的弱分类器的权重，使其在最终表决中占较大作用，同时减少错误率较大的弱分类器的权重.
前向分步算法
讲 AdaBoost 之前，就不得不提到 前向分步算法 ,先来看一个加法模型:
$$f(x)=\sum_{m=1}^M \beta_m b(x;\gamma_m)$$其中:
$b(x;\gamma_m)$表示基函数
$\gamma_m$表示基函数的参数
$\beta_m$表示基函数的系数
最终加权求和之后形成最终的函数(强模型)
假设损失函数为$L(y,f(x))$,则在训练$f(x)$时就是优化损失函数到最小化的问题:$$\underset{\beta,\gamma}{min} \sum_{i=1}^N L\left( y_i,\sum_{m=1}^M \beta_m b(x;\gamma_m) \right)$$
如果直接优化这个损失函数无疑是一个相当复杂的问题:里面嵌入有太多了函数了…，而 前向分步算法 的策略是:
如果从前往后每一步都是学习一个基函数以及系数，令其逐步逼近优化目标函数，那么复杂度就可以大大简化了[分而治之]
因此每一步只需要如下的损失函数即可:$$\underset{\beta,\gamma}{min} \sum_{i=1}^N L \left( y_i,\beta b(x;\gamma) \right)$$
下面就是 前向分步算法 的具体步骤:
训练数据集$T=\{(x_1,y_1),(x_2,y_2)…(x_N,y_N)\}$，其中$y_i \in \{+1,-1\}$
损失函数:$L(y,f(x))$
基函数数量:$M$
基函数集合$\{b(x;\gamma_m)\}$
加法模型$f(x)$
procedure:
初始化$f_0(x)=0$
循环$m \in \{1….M\}$
最小化基函数损失函数:$$\underset{\beta_m,\gamma_m}{argmin} \sum_{i=1}^N L\left( y_i,\beta_m b(x;\gamma_m) \right)$$
更新加法模型:$$f_m(x)=f_{m-1}(x)+\beta_m b(x;\gamma_m)$$
最终得到加法模型:$$f(x)=f_M(x)=\sum_{m=1}^M \beta_m b(x;\gamma_m)$$
前向分步算法 通过分而治之的方式求得了损失函数值最小的 加法函数
整个算法的学习过程可以有很大的想象空间^_^
AdaBoost算法逻辑
上面一小节介绍了 前向分步算法 ，但是留下来三个问题:
对其损失函数$L(y,f(x))$有啥要求?
基函数的系数$\beta$又是怎么计算的?
基函数$b(x;\gamma)$如何设计比较合理?
AdaBoost 正是对此进行一一填坑，它使用 指数损失函数 、 根据分类错误类来计算基函数系数 和 。。 基函数到没有指定，不过一般使用 阈值函数 或者 单桩决策树 来作为基函数
因此也可认为 AdaBoost 是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法.
先来看下 AdaBoost 的算法逻辑图:
说明:此图来自 PRML Fig14.1 [2]，本文的数学符号主要采用[1]的风格，因此有:$y_m(x)\rightarrow G_m(x)$、$Y_M(x) \rightarrow G(x)$
从图中大致可以发现 AdaBoost 依次训练多个弱分类器，每个分类器训练完成之后产出一个权重给予下个分类器，下个分类器在此权重上继续进行训练，全部训练完成之后根据弱分类器的系数组合成强分类器，也就是最终的分类模型~
下面就是 AdaBoost 的具体步骤:
训练数据集$T=\{(x_1,y_1),(x_2,y_2)…(x_N,y_N)\}$，其中$y_i \in \{+1,-1\}$
弱分类器数量:$M$
弱分类器集合$\{G_m(x)\}$
最终模型$G(x)$ （注意： 产出的最终模型并不直接是加法模型哦 ~）
procedure:
初始化训练权值的分布:$$D_1=(w_{1,1},\cdot \cdot \cdot , w_{1,i},\cdot \cdot \cdot ,w_{1,N}),w_{1,i}=\frac{1}{N}$$
ps.其实初始化还有其他方式的 such as:初始化为$\frac{0.5}{N_+}$和$\frac{0.5}{N_-}$，其中$N_+$和$N_-$分别代表正负样本的数量，有$N=N_++N_-$
循环$m \in \{1….M\}$
使用带权重分布$D_m$的训练集进行训练，得到基本的弱分类器:$G_m(x)$
计算$G_m(x)$在训练数据集上的分类误差率:$$e_m=P(G_x(x) \neq y_i) = \sum_{i=1}^N w_{m,i} I(G_m(x_i) \neq y_i)$$其中$$ I(G_m(x_i) \neq y_i)=\left\{
\begin{aligned}
0 & \quad if \quad G_m(x_i) = y_i \\
1 & \quad if \quad G_m(x_i) \neq y_i\\
\end{aligned}
其实就是 错误率 :分错样本数量占总样本量的比例.
计算$G_m(x)$的系数:$$\alpha_m = \frac{1}{2} ln \frac{1-e_m}{e_m}$$
更新训练数据集的权值分布(这点是核心) :$D_{m+1}=(w_{m+1,1},\cdot \cdot \cdot , w_{m+1,i},\cdot \cdot \cdot ,w_{m+1,N})$
其中:$$w_{m+1,i} = \frac{w_{m,i}}{Z_m} e^{-\alpha_m y_i G_m(x_i)}$$ 这里$Z_m$为规范化因子:$$Z_m = \sum_{i=1}^{N} w_{m,i} e^{-\alpha_m y_i G_m(x_i)}$$
构建加法模型:$$f(x)=\sum_{m=1}^M \alpha_m G_m(x)$$产出最终的分类器:$$G(x)=sign(f(x))=sign\left( \sum_{m=1}^M \alpha_m G_m(x) \right)$$其中:$$sign(f(x))=\left\{
\begin{aligned}
-1 & \quad if \quad f(x) & 0 \\
1 & \quad if \quad f(x) \geq 0\\
\end{aligned}
对算法过程中几个重要的点进行一个简单的解释:
分类器误差率$e_m$对其权重$\alpha_m$的影响:
从图中可以发现:
$e_m$为0.5时其权重$\alpha_m$为0，表示此分类器在最终模型中不起任何作用
$e_m & 0.5$时其$\alpha_m & 0$，表示对最终模型起正向作用,$e_m$的值越小，起到的作用越大
$e_m & 0.5$时其$\alpha_m & 0$，表示对最终模型起父向作用，$e_m$的值越大,起到的负作用也越大
$e_m$不会出现等于0 的情况，因为到了0的时候弱分类器已经全部分正确，也不需要继续更新权重再次训练了
$e_m$也不会出现等于1的情况，因为1表示弱分类器全错，除了程序出问题，应该任何一个弱分类器不会训练到全错的情况吧^_^
数据权重的更新策略:
原始的更新策略是这样的:$$w_{m+1,i} = \frac{w_{m,i}}{Z_m} e^{-\alpha_m y_i G_m(x_i)}$$原始标签$y_i$和弱分类器结果的输出$G_m(x)$都是$\{+1,-1\}$二值，因此可以将上述更新方式写成:$$w_{m+1,i}= \left\{
\begin{aligned}
\frac{w_{m,i}}{Z_m} \times e^{\alpha_m} & \quad if \quad y_i \neq G_m(x)\\
\frac{w_{m,i}}{Z_m} \times \frac{1}{e^{\alpha_m}} & \quad if \quad y_i = G_m(x)\\
\end{aligned}
观察$w_{m+1,i}$更新时三个元素均恒大于0（$w_{m,i}$可以从$w_1$开始推），因此$w_{m+1,i}$也是恒大于0 ，并且$\sum_{i=1}^N w_{m,i}=1$我们将分类错误率小于0.5的弱分类器称为好分类器，其系数$\alpha_{good}&0$，同时将分类错误率小于0.5的弱分类器称为坏分类器，则其系数$\alpha_{had}&0$，则再观察变形了的权重更新:
如果当前分类器是好分类器，样本$(x_i,y_i)$被错误分类时,$e^{\alpha_m} & 1$,其$w_{m+1,i}$将会被放大，反之正确分类样本的权值将会被缩小
如果当前分类器为坏分类器，样本$(x_i,y_i)$被错误分类时,$e^{\alpha_m} & 1$,其$w_{m+1,i}$将会被缩小，反之正确分类样本的权值将会被放大
这其实应该与误分类样本的权值被放大$e^{2\alpha_m}=\frac{e_m}{1-e_m}$倍一个道理，因为$\frac{e_m}{1-e_m}$不一定恒大于1啊~^_^
弱分类器的权重系数$\alpha_m$: 这个权重系数表示了弱分类器$G_m(x)$的重要性，但是$a_m$之和并不为1，另外$G_m(x)$输出的是-1或者1的分类，所以最终模型可以看做一个加权的投票系统^_^
AdaBoost-最小化指数误差
假如 AdaBoost 使用的是指数损失函数，则其损失函数为:$$L(y,f(x))=\sum_{i=1}^N e^{-y_if(x)}$$为了优化其损失函数， AdaBoost 采用了前向分步算法进行逐步优化,第 m 轮的迭代需要得到的$\alpha_m$,$G_m$和$f_m(x)$，其中有$$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$$，假设前面的$f_{m-1}(x)$已经为最优，则当前需要优化的是:
$$L(y,f_m(x))=\sum_{i=1}^N e^{-y_i(f_{m-1}(x)+\alpha_m G_m(x))}$$因为有$\bar{w}_{m,i}=e^{-y_if(x)}$（关于这个式子的成立并不是很理解-_-）所以上述优化目标可以写为$$L(y,f_m(x))= \sum_{i=1}^N \bar{w}_{m,i} e^{-y_i\alpha_m G_m(x)}$$
因为我们求的是关于$\alpha_m$和$G_m(x)$的最优化，所以$\bar{w}_{m,i}$相对来说就是常量了.现在假设第$m$轮迭代中有$T_m$个样本分类正确，有$M_m$个样本分类错误，则其优化目标又可以写为:
$$\begin{equation}\begin{split} L(y,f_m(x))&=e^{-\alpha_m} \sum_{n \in T_m} w_{m,n}+e^{\alpha_m} \sum_{n \in M_m} w_{m,n}\\
&= \left( e^{-\alpha_m} \sum_{n \in T_m} w_{m,n} + e^{-\alpha_m} \sum_{n \in M_m} w_{m,n} \right)+ \left( e^{\alpha_m} \sum_{n \in M_m} w_{m,n} - e^{-\alpha_m} \sum_{n \in M_m} w_{m,n} \right) \\
&= e^{-\alpha_m} \sum_{i=1}^N w_{m,i} + (e^{\alpha_m}-e^{-\alpha_m}) \sum_{n=1}^N w_{m,i}I(y_i \neq G_m(x_i))
\end{split}\end{equation}$$
接下来惯例的方法就是对$L(y,f_m(x))$求$\alpha$和$G_m(x)$的偏导数，其实在求$G_m(x)$最优时可以发现可以发现第一项和第二项前面的系数并不影响最优化，所以需要求的就是上面步骤中 误差率 的最优化:$$e_m=P(G_x(x) \neq y_i) = \sum_{i=1}^N w_{m,i} I(G_m(x_i) \neq y_i)$$
而得到了最优的$G_m(x)$之后代入$L(y,f_m(x))$求偏导又可以得到最小的$\alpha_m$为:$$\alpha_m = \frac{1}{2} ln \frac{1-e_m}{e_m}$$
又是一面熟悉的场景^_^
所以可以说 AdaBoost 整个过程是一直在优化最新函数的指数误差，只是在实际训练时按 前向分步算法 只需优化当前的误差率即可.
AdaBoost训练误差分析
这里的边界是我自己的理解，与[1]稍有区别
上一小节我们知道在每一步求$\sum_{i=1}^N w_{m,i} I(G_m(x_i) \neq y_i)$的最小化时，其实是在优化最终模型的损失函数$\sum_{i=1}^N e^{-y_if(x)}$,关于模型最终的损失函数有这样一个界限:
$$\frac{1}{N} \sum_{i=1}^N I(f(x) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^N e^{-y_if(x)} = \prod_m Z_m$$
因为$e^{-y_if(x)}$一定不会小于0，并且当$f(x) \neq y_i$时，$e^{-y_if(x)}$恒大于1，因此第一、二项的不等式是成立的。接下来看后面的那个等式：
这里的推导需要用到$Z_m$的变形:$w_{m,i}e^{-\alpha_my_iG_m(x)} = Z_mw_{m+1,i}$
$$\begin{equation}\begin{split} \frac{1}{N} \sum_{i=1}^N e^{-y_if(x)} &= \frac{1}{N} \sum_{i=1}^N e^{-\sum_{m=1}^M \alpha_my_iG_m(x_i)} \\
&= \sum_{i=1}^N w_{1,i} \prod_{m=1}^M e^{-\alpha_m y_i G_m(x_i)} \\
&= Z_1 \sum_{i=1}^N w_{2,i} \prod_{m=2}^M e^{-\alpha_my_iG_m(x_i)} \\
&= Z_1 Z_2 \sum_{i=1}^N w_{3,i} \prod_{m=2}^M e^{-\alpha_my_iG_m(x_i)} \\
&= Z_1 Z_2 … Z_{m-1}\sum_{i=1}^N w_{M,i} e^{-\alpha_My_iG_M(x_i)} \\
&= \prod_{m=1}^M Z_m
\end{split}\end{equation}$$
因此可以发现最优化(最小化)损失函数可以降低最终模型的错误率，同时其错误率与$Z_m$也是有关系的.
AdaBoost黑科技
Real AdaBoost
上面的 AdaBoost 的介绍中可以发现$G_m(x)$返回的是-1 或者1 （也就是直接离散值），其实这种方式的返回始终会有一定的 gap ，那么假如$G_m(x)$输出的是$p(x)=P(y=1|x)$,也就是$x$特征下输出值为1的概率.此时我们最优化的函数为:$$e^{-y \left(f_{m-1}(x)+G_m(p(x) \right)}$$而$G_m(x)=\frac{1}{2} ln \frac{x}{1-x}$
这种方式将会修复一定的 gap ，并且在某些实验中效果也是要好于直接离散的 AdaBoost
一般情况下是弱分类器训练$M$个才停止，而提前终止只是在训练多个层之后组成的最终分类器的结果已经小于一个置信度的误差，有一种方法可以加快这种判断:
一般训练数据里面负样本会远多于正样本
在多个级联的弱分类器在被训练之后，如果正样本被误分为负样本了，则人工将这样正样本进行标记并去去除（质量差的）
那么如果每一轮都是有50%的负样本被监测去重，那么久可以大大减小计算量
最终看假阳性和假阴性来判断是否终止
这种方式靠谱吗？要不就是我理解/翻译错了
这种提前终止的方法可以降低过拟合的可能性^_^
剪枝指的是去除性能较差的弱分类器，提升效率。最简单的方法是:每个弱分类器都自己的系数和测试误差率极其分布， margineantu 则提出的建议为:
弱分类器的选择应该分类多样性
如果两个弱分类器很相似，则可以将其中一个给去掉,同时增加相似弱分类器的系数(这里其实就是相当于剪枝了)
AdaBoost 秉承 三个凑皮匠，顶个诸葛亮 的原则，与其说 AdaBoost 是一个机器学习算法，我更觉得他应该是一个经典的机器学习框架，其优点有:
可以较为方便的控制过拟合(不能说避免过拟合，在弱分类器很强的情况下还真会过拟合的吧？看$GBRT$)
有非常强的自适应性
如果弱分类器很简单，则训练预测速度将会很快，毕竟最终复杂度是在弱分类器上乘以$M$
分类效果好，实现简单
可扩展性强~弱分类器可以随意换，甚至损失函数也可以换(比如换最小平方误差)
当然也有缺点:
相邻两个分类器训练有依赖关系，所以在并行实现下还是需要精心设计。
[1] 《统计学习方法》.李航.第八章
[2] 《Pattern Recognition And Machine Learning》.Christopher Bishop.chapter 14
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}