提升方法-Adaboost算法

01|基本概念：

提升方法的基本思想：对于任何一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比任何一个专家单独的判断好。

先来看两个概念：强可学习和弱可学习。

在概率近似正确学习的框架中(简称PAC)，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

弱可学习与强可学习之间是有一定的差距，如果已经发现弱可学习算法，那么能否将它提到强可学习算法，这里的如何提升就是提升方法需要解决的问题。最具代表性的就是AdaBoost算法。

对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确地分类规则（强分类器）容易的多。提升方法就是从弱学习算法，反复学习，得到一系列分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

这样，对于提升方法来说，有两个问题需要解决：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组成一个强分类器。

对于第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

02|AdaBoost算法：

假设给定一个二分类的训练数据集

其中，每个样本点由实例和标记组成。x是实例空间，y是标记集合。AdaBoost利用以下算法，从训练数据集中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成一个强分类器。

算法步骤：

1.初始化训练数据的权值分布，让训练数据集中的每一个样本均等于1/N。

2.对m=1,2,...,M(m表示反复训练的次数)

(a)使用具有权值分布的 Dm的训练数据集学习，得到基本分类器

(b)计算Gm(x)在训练数据集上的分类误差率（误分类样本权值之和）

上式中

表示第m轮中第i个实例的权值。

(c)计算Gm(x)的系数

上式中的对数为自然对数，上式的结果是该分类器在最终分类器的所占的权重，即多项式的系数。

由上式可得，当

时，

,且

随着

的减小而增大，意味着分类误差越小的基本分类器在最终分类器中的作用越大。

(d)更新训练数据集的权值分布

这里，

是规范化因子

3.构建基本分类器线性组合

得到的最终分类器

系数

表示了基本分类器

的重要性，这里，所有的

之和并不为1。f(x)的符号决定实例x的分类，f(x)的绝对值表示分类的确信度。

03|前向分布算法：

考虑加法模型(每一轮迭代的分类函数的加和)

其中，

为基函数，

为基函数的参数，

为基函数的系数。

在给定训练数据及损失函数L(y,f(x))的条件下，学习加法模型f(x)成为经验风险极小化即损失函数最小化问题：

通常这是一个复杂的优化问题。前向分步算法求解这一优化问题的想法是：因学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，那么就可以简化优化的复杂度。具体地，每步只需要优化如下目标函数：

前向分步算法步骤：

输入：训练数据集

;损失函数L(y,f(x))；基础函数集

;

输出：加法模型f(x)

1.初始化

2.对m=1,2,...,M

(a)极小化损失函数

得到参数

，

(b)更新

3.得到加法模型

这样，前向分布算法将同时求解从m=1到M所有参数

，

的优化问题简化为逐个求解各个

，

的优化问题。

04|前向分步算法与AdaBoost关系：

AdaBoost 算法可以认为是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。