内容
一、Adaboost简介
二、Adaboost算法过程
三、Adaboost算法的训练误差分析
四、Adaboost算法的解释
五、提升树
六、详细理解“梯度提升算法”
##############################################################################
一、Adaboost简介
AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
对于提升方法来说，有两个问题需要回答：
（1）在每一轮如何改变训练数据的权值和概率分布？
提高那些被前一轮分类器错误分类样本的权值,而降低那些被正确分类的样本的权值。
这样大权值的分类样本在后一轮的分类器会被更加关注。
（2）如何将弱分类器组合成强分类器？
强分类器是弱分类器的组合，adaboost采取多数表决的方法。加大误差小的分类器的权 值，使其在表中其较大作用，减小误差大的分类器的权值，使其在表中其较小作用。
二、Adaboost算法过程
1.具体说来，整个Adaboost 迭代算法就3步：
（1）初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
（2）训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
（3）将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。
2. Adaboost算法流程
给定训练数据集：（x1,y1）...(xn,yn),其中yi属于{-1,1}。用于表示训练样本的类别标签，i=1,...,N。Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。
相关符号说明：
算法流程如下：
相关说明：
综合上面的推导，可得样本分错与分对时，其权值更新的公式为：
另外，Z的推导过程如下；
3.Adaboost算法实例
例：给定如图所示的训练样本，弱分类器采用平行于坐标轴的直线，用Adaboost算法的实现强分类过程。
数据分析：
将这10个样本作为训练数据，根据 X 和Y 的对应关系，可把这10个数据分为两类，图中用“+”表示类别1，用“O”表示类别-1。本例使用水平或者垂直的直线作为分类器，图中已经给出了三个弱分类器，即：
初始化：
首先需要初始化训练样本数据的权值分布，每一个训练样本最开始时都被赋予相同的权值：wi=1/N，这样训练样本集的初始权值分布D1(i)：
令每个权值w1i= 1/N= 0.1，其中，N= 10，i= 1,2, ..., 10，然后分别对于t= 1,2,3, ...等值进行迭代（t表示迭代次数，表示第t轮），下表已经给出训练样本的权值分布情况：
第1次迭代t=1：
初试的权值分布D1为1/N（10个数据，每个数据的权值皆初始化为0.1），
D1=[0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1]
在权值分布D1的情况下，取已知的三个弱分类器h1、h2和h3中误差率最小的分类器作为第1个基本分类器H1(x)（三个弱分类器的误差率都是0.3，那就取第1个吧）
在分类器H1(x)=h1情况下，样本点“5 7 8”被错分，因此基本分类器H1(x)的误差率为：
可见，被误分类样本的权值之和影响误差率e，误差率e影响基本分类器在最终分类器中所占的权重α。
然后，更新训练样本数据的权值分布，用于下一轮迭代，对于正确分类的训练样本“1 2 3 4 6 9 10”（共7个）的权值更新为：
这样，第1轮迭代后，最后得到各个样本数据新的权值分布：D2=[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14]
由于样本数据“5 7 8”被H1(x)分错了，所以它们的权值由之前的0.1增大到1/6；反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到1/14，下表给出了权值分布的变换情况：
可得分类函数：f1(x)= α1H1(x) = 0.4236H1(x)。此时，组合一个基本分类器sign(f1(x))作为强分类器在训练数据集上有3个误分类点（即5 7 8），此时强分类器的训练错误为：0.3。
第二次迭代t=2：
在权值分布D2的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第2个基本分类器H2(x)：
① 当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：误差率e=1/6+1/6+1/6=3/6=1/2；
② 当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：误差率e=1/14+1/14+1/14=3/14；
③ 当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：误差率e=1/14+1/14+1/14=3/14；
因此，取当前最小的分类器h2作为第2个基本分类器H2(x)
显然，H2(x)把样本“3 4 6”分错了，根据D2可知它们的权值为D2(3)=1/14，D2(4)=1/14， D2(6)=1/14，所以H2(x)在训练数据集上的误差率：
这样，第2轮迭代后，最后得到各个样本数据新的权值分布：
D3=[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22]
下表给出了权值分布的变换情况：
可得分类函数：f2(x)=0.4236H1(x) + 0.6496H2(x)。此时，组合两个基本分类器sign(f2(x))作为强分类器在训练数据集上有3个误分类点（即3 4 6），此时强分类器的训练错误为：0.3
第三次迭代t=3:
在权值分布D3的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第3个基本分类器H3(x)：
① 当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：误差率e=7/66+7/66+7/66=7/22；
② 当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：误差率e=1/6+1/6+1/6=1/2=0.5；
③ 当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：误差率e=1/22+1/22+1/22=3/22
这样，第3轮迭代后，得到各个样本数据新的权值分布为：
D4=[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38]
下表给出了权值分布的变换情况：
可得分类函数：f3(x)=0.4236H1(x) + 0.6496H2(x)+0.9229H3(x)。此时，组合三个基本分类器sign(f3(x))作为强分类器，在训练数据集上有0个误分类点。至此，整个训练过程结束。
整合所有分类器，可得最终的强分类器为：
这个强分类器Hfinal对训练样本的错误率为0！
三、Adaboost算法的训练误差分析
Adaboost最基本的性质它能够在学习中不断减少训练误差，即在训练数据集上的分类误差率。关于训练误差界有如8.5定理。
证明过程如下：
关于（8.5）、（8.6）以及（8.7）式子如下所示：
该式子的推导过程分为两个步骤：左边“<=”和右边“=”
对于红色框I(x)是指示函数所以取值是{-1,1}，故左边的证明成立。
对于绿色框内更加详细的证明过程：
从推导过程可以看出在每一轮选取适当的G(x)使得Zm最小，从而使训练误差最快。因为选取的G（x）影响am的值，所以在推导的过程可以看出G（x）是对误差率起决定性作用。
注：这里边我们对adaboost算法的描述以及adaboost算法的例子都是假设在给定二分类训练数据集的。若不是二分类的数据集也可以，只不过是在做具体阐述的时候会简单明了。
证明用到的相关公式：
四、Adaboost算法的解释
Adaboost算法还有另外一种解释，即可以认为Adaboost算法是模型为加法模型、损失函数为指数函数、学习算法为前向算法时的二分类学习方法。
前向分布算法的大致描述：
前向算法的具体流程（前向）：
五、提升树
提升树是以分类树或者回归树为基本分类器的提升算法。提升树被认为是统计学习中性能最好的方法之一。
提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。
以决策树为基函数的提升算法称为提升树。
对于分类问题的决策树是二叉分类树，对于回归问题的决策树是二叉回归树。
提升树的模型可以表示为决策树的加法模型（决策树是二叉分类树或者二叉回归树）：
提升树算法：
讨论不同问题的提升树模型的学习算法，主要区别在于使用的损失函数不同：
1.平方误差损失函数的回归问题
2.指数损失函数的分类问题
3.一般损失函数的一般决策问题
注：就是通过最小化各种损失函数来更新对应的提升树模型的参数，即对提升树模型学习的过程。
回归问题的提升树算法的描述：
回归树提升算法的具体过程：
详细例子见李航，adaboost算法的大框没变，知识这里边加了回归和树。所以就命名为回归树提升算法。
六、详细理解“梯度提升算法”
提升树利用加法模型与前向分布算法实现学习的优化过程。当损失函数是平方损失函数和指数损失函数，利用前向算法每一步的优化是很简单的。
但对一般的损失函数而言。往往不是那么容易。针对这一问题的存在，Freidman提出了梯度提升算法。
梯度提升算法：
注：红色框内代表梯度提升算法的初始化；
绿色框内代表计算伪残差
蓝色框内代表利用线性搜索估计叶节点区域的值，使损失函数极小化
黄色框内代表更新树
黑色代表得到最后的回归树
结合图表理解下该算法：
详细地址转到：https://www.jianshu.com/writer#/notebooks/29268484/notes/34244677
