一、提升方法AdaBootst算法

1、提升方法的基本思路

1984年，Kearns和Valiant提出：强可学习和弱可学习
在概率近似正确（PAC）学习的框架中个，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，称这个概念是强可学习的
一个概念（类），如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，则称这个概念是弱可学习的。
1989，Schapire证明：在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习。

提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（基本分类器），然后组合这些弱分类器，构成强分类器。大多数提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

提升方法需要解决两个问题：

• 一是在每一轮如何改变训练数据的权值或概率分布？
  AdaBoost算法是提高那些前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值，
• 二是如何将弱分类器组合成一个强分类器？
  AdaBoost采取加权多数表决的方法，即加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的若分类器的权值，使其在表决中起较小的作用。

2、AdaBoost算法

image.png

算法说明：

image.png

二、AdaBoost的训练误差分析

由：

image.png

定理：AdaBoost的训练误差界

image.png

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

image.png

推论：

image.png

三、AdaBoost算法的解释

模型：加法模型
损失函数：指数函数
学习算法：前向分步算法的二分类学习算法

1、前向分步算法

加法模型：

image.png
给定训练数据和损失函数L(y,f(x))，学习加法模型f(x)成为经验风险极小化即损失函数极小化问题：
（复杂的优化问题）
image.png

前向分步算法求解这一优化问题的思路：

根据学习的是加法模型，如果能够从前向后每一步只学习一个基函数及其系数，逐步逼近优化目标函数式（8.14）。
具体，每步只需优化如下损失函数

image.png

前向分步算法

image.png

2、前向分步算法与AdaBoost

定理：

image.png

image.png
求解 image.png

可分两步：

image.png
image.png

四、提升树

提升树是以分类树或回归树为基本分类器的提升方法。

1、提升树模型

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法，以决策树为基函数。
对分类问题决策树是二叉分类树
对回归问题决策树是二叉回归树

image.png

2、提升树算法

提升树算法采用前向分步算法

image.png

由于树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

针对不同问题的提升树学习算法，使用的损失函数不同：

• 用平方误差损失函数的回归问题
• 用指数损失函数的分类问题
• 用一般损失函数的一般决策问题

对二分类问题：

提升树算法只需将AdaBoost算法中的基本分类器限制为二类分类树即可，这时的提升树算法是AdaBoost算法的特殊情况。

讨论回归问题提升树：

image.png
image.png

回归问题的提升树算法

image.png

3、梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的，但对一般损失函数而言，往往每一步优化并不那么容易。

针对这一问题，Freidman提出梯度提升算法。
这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值：

image.png
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

梯度提升算法

image.png