一、提升方法adaboost算法

1.提升算法的基本思路

提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好，“三个臭皮匠顶个诸葛亮”。

强可学习与弱可学习
一个问题，多项学习之后效果非常好就是强可学习
一个问题，多项学习之后效应只比随机好一点就是弱可学习

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

有两个问题——每一轮如何改变训练数据的权值或概率分布？如何将弱分类器组合成一个强分类器。

AdaBoost的做法是——提高哪些被前一轮弱分类器错误分类的数据，由于其权值加大之后而受到后一轮的弱分类器的更大关注，于是分类问题被一系列弱分类器分而治之

弱分类器的组合——AdaBoost采取加权多数表决的方法，具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用

AdaBoost算法

输入：训练数据集，弱学习算法
输出：最终分类器G(x)

(1)初始化训练数据的权值分布
一开始所有样本的权重相同，为1/n，这一假设能够保证第一步能够子啊原始数据上学习基本分类器
（2）对于迭代轮次m=1,2,3，。。。m
（a)使用权值分布为Dm的训练数据集学习，得到基本分类器Gm(x)
（b)计算Gm(x)进行在训练集上的分类误差率
（c)计算Gm(x)的系数am
（d）更新训练数据集的权值分布，得到Dm+1的概率分布
（3）构建基本分类器的线性组合，得到最终分类器
am代表重要性，但是am的和并不是1，利用基本分类器的线性组合构建分类器是AdaBoost的另一个特点

二、AdaBoost算法的训练误差分析

AdaBoost的最基本的性质是他能够在学习过程中不断减少训练误差，即在训练数据集上的分类误差率
定理AdaBoost的训练误差界，这一定理说明每一轮可以选取适当的Gm使得Zm最小，从而使训练误差下降最快。

二分类问题的AdaBoost训练误差界

如果y大于0，对所有m有ym大于y表明此条件下AdaBoost的训练误差是以指数速率下降的。AdaBoost不需要知道下界，因为他具有适应性，

三、AdaBoost算法的解释

AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型，损失函数为指数函数，学习算法为前向分步计算时的二类分类学习方法。

前向分步算法求解经验风险极小化的优化问题的想法是：因为学习是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化复杂度。

前向分步算法
输入：训练数据集，损失函数，基函数集
输出：加法模型
（1）初始化加法模型f0(x)=0
（2）对每一轮m=1，2,3，。。。m
（a)极小化损失函数，得到这一轮的基函数的参数
（b）更新加法模型
（3）得到加法模型
这样前向分步算法将同时求m从1到M的所有参数的优化问题简化为逐次求解各个参数的优化问题

前向分步算法与AdaBoost

由前向分步算法可以推导出AdaBoost
AdaBoost是前向分步加法算法的特例，这是，模型是有基本分类器组成的加法模型，损失函数是指数函数
前向分步学习的过程与AdaBoost算法学习的过程一致