AdaBoost 算法

提升方法，AdaBoost 算法背景

 AdaBoost算法， 是一种经典的提升算法。提升算法基于一个很简单的想法，三个臭皮匠抵个诸葛亮。要解决一个复杂的问题，多个专家的判断的综合结果要比任何一个单一的专家的判断好。
 首先介绍两个概念，强可学习，弱可学习。强可学习: 一个概念，如果存在一个多项式学习的算法能够学习他，并且准确率很高，则认为这个概念是强可学习的。弱可学习: 一个概念，如果存在一个多项式学习算法可以学习它，但准确率只是比随机猜测略好，则这个概念就是弱可学习。从这里看，强可学习和弱可学习似乎差别很大，学习到的准确率天差地别，然而其实，两者有相通之处。后来有人证明了一个很有趣的事实：一个概念是强可学习的充要条件就是这个概念是弱可学习的。
 对一个复杂问题，虽然一次性找到一个准确率很高的学习算法是一件很困难的事情，不过找一个弱可学习的算法并不难。由于上面提到的强可学习和弱可学习等价性，就可以想到，先找到弱可学习算法， 然后将它提升为强可学习算法，这也就是提升算法。简而言之，假设对于分类问题，给定一个训练样本集，利用弱学习算法，反复学习得到一系列的弱分类器，然后组合这些弱分类器得到一个强分类器。大多数的提升算法，使用不同的训练数据分布调用弱学习算法来学习这一系列的分类器，也就是说不同的分类器，训练数据的分布不同。
 由上面可知，提升算法面临两个问题：一是如何在每一轮的弱分类器的学习中改变训练数据的概率分布；二是如何将弱分类器组合成强分类器。问题一， AdaBoost算法的做法是提高上一轮弱分类器错误分类样本的权值，降低正确分类样本的权值，这样上一轮错误分类的数据在这一轮分类器学习中会得到重视。问题二，AdaBoost采用加权多数表决的方法，即分类准确率高的弱分类器权值高，反之权值小。

AdaBoost 算法步骤

AdaBoost算法：
** 输入： **
二分类训练数据集，T = {(x1,y1), (x2,y2), …,(xN,yN) },共 N 个数据对。
弱学习算法，M 个基本分类器 G1， G2，… ，GM
** 学习参数： **
训练数据的权值分布，D1，D2…DM。第m个分类器的数据权值分布： Dm = (w11,w12, … w1i, …,w1m)
弱分类器的权值，也是 M 个。α ,1~M个。
** 输出： **
最终的强分类器 G(x)。

算法步骤：

1. 初始化第一个弱分类器的的训练数据权值分布：
    
   这里假设的训练数据是均匀的权值分布，来学习第一个分类器。
2. 依序训练 1～M个弱分类器，每个分类器都顺序执行下面几个步骤：
   • 对第m个分类器，使用权值分布为Dm的训练数据集学习，得到基本分类器Gm：
      
      不同的权重分布，对于不同的决策函数，都对应着最佳的分类决策，即 em 最小。
   • 计算Gm(x)在训练集数据上的分类误差率：
      
      Wmi表示第m轮的第i个实例的权值，由式子可以知道Gm(x)在加权训练数据集上的分类误差率是被Gm(x)误分类的样本的权值之和。
   • 计算Gm(x)的加权系数：
      
      这里的对数是指自然对数.由公式也可以发现，分类误差率越小的，基本分类器的权值越大,而且当em<=1/2时,α 才大于0。所以分类误差率越小的分类器在最终的分类器中的作用越大。
   • 更新训练数据集的权值分布：
      
      
     更新的训练数据权重值为下一轮的分类器学习做准备，其中，Zm是规范化因子：
      
3. 构建最终的分类器，强分类器：
    
   其中f(x)是基本分类器的加权线性组合， sign是sigmoid非线性变换。

值得注意的是，分别对与每个m，wim，i=1~N,之和是1 ，但是所有的 αm(m=1~M) 之和不为1。

训练误差分析

 AdaBoost最基本的性质是算法能在学习过程中不断减少训练误差，即在训练数据集上的误差。