一、提升方法AdaBootst算法
1、提升方法的基本思路
1984年，Kearns和Valiant提出：强可学习和弱可学习
在概率近似正确（PAC）学习的框架中个，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，称这个概念是强可学习的
一个概念（类），如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，则称这个概念是弱可学习的。
1989，Schapire证明：在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习。
提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（基本分类器），然后组合这些弱分类器，构成强分类器。大多数提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
提升方法需要解决两个问题：
- 一是在每一轮如何改变训练数据的权值或概率分布？
AdaBoost算法是提高那些前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值， - 二是如何将弱分类器组合成一个强分类器？
AdaBoost采取加权多数表决的方法，即加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的若分类器的权值，使其在表决中起较小的作用。
2、AdaBoost算法
算法说明：
二、AdaBoost的训练误差分析
由：
定理：AdaBoost的训练误差界
定理：二类分类问题AdaBoost的训练误差界
推论：
三、AdaBoost算法的解释
模型：加法模型
损失函数：指数函数
学习算法：前向分步算法的二分类学习算法
1、前向分步算法
加法模型：
给定训练数据和损失函数L(y,f(x))，学习加法模型f(x)成为经验风险极小化即损失函数极小化问题：
（复杂的优化问题）
前向分步算法求解这一优化问题的思路：
根据学习的是加法模型，如果能够从前向后每一步只学习一个基函数及其系数，逐步逼近优化目标函数式（8.14）。
具体，每步只需优化如下损失函数
前向分步算法
2、前向分步算法与AdaBoost
定理：
image.png
求解image.png
可分两步：
image.png
image.png
四、提升树
提升树是以分类树或回归树为基本分类器的提升方法。
1、提升树模型
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法，以决策树为基函数。
对分类问题决策树是二叉分类树
对回归问题决策树是二叉回归树
2、提升树算法
提升树算法采用前向分步算法
由于树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
针对不同问题的提升树学习算法，使用的损失函数不同：
- 用平方误差损失函数的回归问题
- 用指数损失函数的分类问题
- 用一般损失函数的一般决策问题
对二分类问题：
提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，这时的提升树算法是AdaBoost算法的特殊情况。
讨论回归问题提升树：
回归问题的提升树算法
3、梯度提升
提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的，但对一般损失函数而言，往往每一步优化并不那么容易。
针对这一问题，Freidman提出梯度提升算法。
这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值：
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
梯度提升算法
