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

需要解决的两个问题：1. 在每一轮如何改变训练数据权值或者概率分布；2.如何将这些弱分类器组合成一个强分类器。
AdaBoost做法：1.提高那些被前一轮弱分类器错误分类样本权值，降低那些被正确分类样本的权值。2.加权多数表决。

Ada算法

1. 初始化训练数据的权值分布
   $$D_1 = (w_{11},…,w_{1i},…,w_{1N}) \quad w_{1i} = \frac{1}{N}$$
2. 对m =1,2,…M
   (a)使用具有权值分布D_m的训练数据集学习，得到基本分类器$G_m(X):\mathcal{X}\to \{-1,1\}$
   (b)计算$G_m(X)$在训练数据集上的分类误差率
   $e_m = P(G_m(x_i)\neq y_i) = \sum_{i=1}^N w_{mi}(G_m(x_i)\neq y_i)$
   (c)计算$G_m(X)$的系数
   $$\alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m}$$
   这里的对数是自然对数
   (d) 更新训练数据集的权值分布
   $D_{m+1} = (w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N}) $
   $ w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(x_i))$
   Zm是规范化因子，使得Dm+1成为一个概率分布
3. 构建基本分类器的线性组合

AdaBoost算法解释

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

提升树

提升树是以分类树或回归树为基本分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。

提升树模型

提升方法采用加法模型（基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型：
$$f_m(x) = \sum{m=1}^M = T(x;\Theta_m)$$

提升树的算法

提升树采用前向分布算法，首先确定初始提升树，然后通过经验风险极小化确定下一棵决策树的参数$\Theta_m$。
由于树的线性组合可以很好的拟合训练数据，即时数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

不同提升树的算法主要区别在使用的损失函数的不同。包括用平方误差损失函数的回归问题，用指数损失函数的分类问题以及一般损失函数的一般决策问题。

对于二类分类问题，提升树算法只需将AdaBoost中基本分类器限制为二类分类树即可。