一句话介绍：对加法模型，使用前向分布算法实现从弱分类器到强分类器的提升。

0 提升方法

分类问题中，通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，可以提高分类的性能。

抽象一下：找一些比较粗糙的分类规则（弱学习方法、弱分类器）是相对容易的，那么可以从这些弱学习方法出发，将一系列弱分类器组合，构成一个强分类器。

两个关键问题

• 在每一轮中如何改变训练数据的权值或概率分布
• 如何将弱分类器组合成强分类器

1 - AdaBoost

解决两个问题的方法：

• 提高被前一轮弱分类器错误分类样本的权值 【这样就会收到后一轮弱分类器的更大关注】，同时，降低那些被正确分类样本的权值；
• 采取加权多数表决，加大分类误差小的弱分类器在表决中的权值。

算法的简单理解：

在一开始，各训练数据的权值分布初始化较为均匀；

通过一轮计算，根据误分类情况，将误分类的实例的权值相加，得到基本分类器本轮的分类误差率

$e_m=\Sigma_{G_m(x_i)\not=y_i}w_{mi}$

更新基本分类器 $G_m(x)$ 的系数，也就是在最终分类器中的重要性，$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$，特点是误差越大，这个系数值会越小【减小错误分类器的影响力】

更新训练样本的权值分布，也就是下一轮中的训练数据的权值

$w_{m+1, i}=\left { \begin{aligned} {\frac{w_{mi}}{Z_m}e^{-\alpha_m}, G_m(x_i)=y_i \ \frac{w_{mi}}{Z_m}e^{\alpha_m}, G_m(x_i)\not=y_i}\end{aligned} \right.$

特点是误差越大，这个权值会越大【加强对这样的样本的训练】

要注意的是，每一轮求解得出的分类器并不是不断迭代的，而是把所有轮求解出的分类器组合起来（加起来是一种办法），得到最终的分类器

所以最终分类器的效果是各轮分类器的效果的加和和调整【有趣的是各分类器的权值之和并不为1】

2 - AdaBoost算法的训练误差分析

用数学方法能够证明以下几点：

• AdaBoost的训练误差有上界
• 可以在每一轮选取适当的基本分类器，使得训练误差下降更快
• 在一定条件下，AdaBoost的训练误差是以指数速率下降的

3 - AdaBoost算法的解释

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

前向分布算法

前向分布算法是针对加法模型 $f(x)=\Sigma^M_{m=1}\beta_mb(x;\gamma_m)$

将复杂的优化问题，通过从前往后，每一步只学习一个基函数及其系数的方式，逐步逼近优化目标函数式，从而简化优化的复杂度

4 - 提升树【和第5章相关】

以分类树或回归树作为基本分类器的提升方式

以决策树为基函数的提升方式——提升树

• 分类问题决策树：二叉分类树
• 回归问题决策树：二叉回归树

决策树的加法模型：$f_M(x)=\Sigma_{m=1}^MT(x;\Theta_m)$

采用前向分布算法，首先确定初始提升树：$f_0(x)=0$

第m步的模型：$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

其中，$T(x;\Theta_m)$表示决策树，$\Theta_m$是决策树的参数，M 是决策树的个数

所以该算法就是通过经验风险极小化的方法确定下一棵决策树的参数

计算残差：$r_{mi}=y_i-f_{m-1}(x_i), i=1, 2,..,N$

拟合残差学习回归树，更新模型，并迭代。

• 在实际的实现过程中，第一轮对实际值和预测值进行学习；第二轮使用第一轮模型结果与实际值的残差，以及新的残差预测值进行学习；…；最后，多轮的模型应该相加，得到最终的模型。

• 也就是说，整个过程中，第一轮拟合实际值，然后后面每一轮进行优化调整拟合细节（残差、残差的残差），最终加合起来实现最好的优化器

针对不同问题的提升树学习方法的主要区别在于损失函数：

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

梯度提升

是针对一般损失函数的优化方法，利用了最速下降法

关键：利用损失函数的负梯度在当前模型中的值，作为回归问题提升树算法中的残差的近似值，拟合回归树。