Boosting（提升方法）

提升方法（boosting）简介
AdaBoost 算法
GBDT 算法
python 代码实现
提升方法（boosting）相关面经和其他资料
小结

提升方法（boosting）简介

提升（boosting）方法是一种常用的统计学习方法，应用十分广泛。在处理分类问题的时候，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

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

AdaBoost算法

提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中的任何一个专家单独的判断好，也就是“三个臭皮匠顶个诸葛亮”的道理。

基本思路

历史上，Kearns 和 Valiant 首先提出了 “强可学习” 和 “弱可学习” 的概念。指出：在概率近似正确学习的框架中，一个类，如果存在一个多项式的学习算法能够学习它，并且准确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是 Schapire 后来证明强可学习是等价的，也就是说，在 PAC 学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

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

但是，对于提升方法来说，有两个问题需要回答：

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

第一个问题，AdaBoost 的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有被正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。

第二个问题，即弱分类器的组合，AdaBoost 采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用；减少分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

算法详解

假设给定一个二类分类的训练数据集

$T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$

其中，每个样本点由实例与标记组成。实例 $x_i \subset R^n$ 。AdaBoost 利用算法如下，从训练集中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。

输入：训练集；弱学习算法；
输出：最终分类器 $G(x)$ 。

初始化训练数据的权值分布
$D_1 = (w_{11}, \cdots, w_{1i}, \cdots, w_{1N}), \ w_{1i} = \frac{1}{N}, \ i = 1,2,\cdots,N$
对 $m = 1,2,\cdots,M$
（a）使用具有权值分布 $D_m$ 的训练集学习，得到基本分类器
$G_m(x) : \mathcal X \rightarrow \{-1,+1\}$
（b）计算 $G_m(x)$ 在训练集上的分类误差率
$e_m = \sum_{i=1}^{N}P(G_m(x_i) \neq y_i) = \sum_{i=1}^{N}w_{mi}I(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}, \cdots, w_{m+1,i}, \cdots, w_{m+1,N})$
$W_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), \ i = 1,2,\cdots, N$
这里， $Z_m$ 是规范化因子
$Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i))$
它使 $D_{m+1}$ 成为一个概率分布。
构建基本分类器的线性组合
$f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)$
得到最终分类器
$G(x) = sign\Bigg(\sum_{m=1}^{M}\alpha_mG_m(x)\Bigg)$

注意：
步骤（1） 假设训练数据具有均匀的权值分布，姐妹个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器 $G_1(x)$ 。

步骤（2） AdaBoost 反复学习基本分类器，在每一轮 $m = 1,2,\cdots,M$ 顺次地执行下列操作：
（a）使用当前分布 $D_m$ 加权的训练数据集，学习基本分类器 $G_m(x)$ 。
（b）计算基本分类器 $G_m(x)$ 在加权训练集上的分类误差率：
$e_m = \sum_{i=1}^{N}P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i) \neq y_i} w_{mi}$
这里， $w_{mi}$ 表示第 $m$ 轮中第 $i$ 个实例的权值， $\sum_{i=1}^{N}w_{mi} = 1$ 。这表明， $G_m(x)$ 在加权的训练数据集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和，由此可看出数据权值分布 $D_m$ 与基本分类器 $G_m(x)$ 的分类误差率的关系。
（c）计算基本分类器 $G_m(x)$ 的系数 $\alpha_m$ 。 $\alpha_m$ 表示 $G_m(x)$ 在最终分类器的权重，表示其重要性。并且 $\alpha_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
（d）更新训练数据的权值分布为下一轮作准备。注意到：
$W_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), \ i = 1,2,\cdots, N$
$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) \neq y_i \end{aligned} \right.$
所以，被基本分类器 $G_m(x)$ 误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是 AdaBoost 的一个特点。

步骤（3） 线性组合 $f(x)$ 实现 $M$ 个基本分类器的加权表决。系数 $\alpha_m$ 表示了基本分类器 $G_m(x)$ 的重要性，这里，所有 $\alpha_m$ 之和并不为 1。 $f(x)$ 的符号决定实例 $x$ 的类， $f(x)$ 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是 AdaBoost 的另一个特点。

AdaBoost 实例

给定表中所示的训练数据。假设弱分类器由 $x<v$ 或 $x>v$ 产生，其阈值 $v$ 使该分类器在训练数据集上分类误差率最低。试用 AdaBoost 算法学习一个强分类器。

x	y
0	1
1	1
2	1
3	-1
4	-1
5	-1
6	1
7	1
8	1
9	-1

解：首先定义初始化数据权值分布

$D_1 = (w_{11}, w_{12}, \cdots, w_{110})$
$w_{1i} = 0.1, \ i = 1,2,\cdots,10$

对 $m=1$ ，

在权值分布为 $D_1$ 的训练数据上，阈值 $v$ 取 2.5 时分类误差率最低，故基本分类器为
$G_1(x)=\left\{ \begin{aligned}1, x<2.5\\ -1, \ x>2.5 \end{aligned} \right.$
$G_1(x)$ 在训练数据集上的误差率 $e_1 = P(G_1(x_i) \neq y_i) = 0.3$ 。因为只有 $x = 6,7,8$ 三个数据分类错误，所以概率为 0.3。
计算 $G_1(x)$ 的系数： $\alpha_1 = \frac{1}{2}log\frac{1-e_1}{e_1} = 0.4236$ 。
更新训练数据的权值分布：
$D_2 = (w_{21}, \cdots, w_{2i}, \cdots, w_{210})$
$w_{2i} = \frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x_i)), \ i = 1,2,\cdots,10$
$D_2 = (0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)$
$f_1(x) = 0.4236G_1(x)$
分类器 $sign[f_1(x)]$ 在训练数据集上有 3 个误分类点。

对 $m=2$ ，

在权值分布为 $D_2$ 的训练数据上，阈值 $v$ 取 8.5 时分类误差率最低，故基本分类器为
$G_1(x)=\left\{ \begin{aligned}1, x<8.5\\ -1, \ x>8.5 \end{aligned} \right.$
$G_2(x)$ 在训练数据集上的误差率 $e_2 = P(G_2(x_i) \neq y_i) = 0.2143$ 。
计算 $\alpha_2 = 0.6496$ 。
更新训练数据权值分布：
$D_3 = (0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)$
$f_2(x) = 0.4236G_1(x)+0.6496G_2(x)$
分类器 $sign[f_x(x)]$ 在训练数据集上有 3 个误分类点。

对 $m=3$ ，

对权值分布为 $D_3$ 的训练数据上，阈值 $v$ 是 5.5 时分类误差率最低，基本分类器为
$G_3(x)=\left\{ \begin{aligned}1, x>5.5\\ -1, \ x<5.5 \end{aligned} \right.$
$G_3(x)$ 在训练样本集上的误差率 $e_3 = 0.1820$
计算 $\alpha_3 = 0.7514$
更新训练数据的权值分布：
$D_4 = (0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)$
于是得到：
$f_3(x) = 0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$
分类器 $sign[f_3(x)]$ 在训练数据集上误分类个数为 0。
于是最终分类器为
$G(x) = sign[f_3(x)] = sign[0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)]$

AdaBoost 算法解释

AdaBoost 算法还有另一个解释，即可以认为 $AdaBoost$ 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二类分类学习方法。

前向分布算法

考虑加法模型（additive model）

$f(x) = \sum_{m=1}^{M}\beta_mb(x; \gamma_m)$

其中， $b(x;\gamma_m)$ 为基函数， $\gamma_m$ 为基函数的参数， $\beta_m$ 为基函数的系数。显然， $f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)$ 是一个加法模型。

在给定训练数据以及损失函数 $L(y,f(x))$ 的条件下，学习加法模型 $f(x)$ 成为经验风险极小化即损失函数极小化的问题：

$\min_{\beta_m,\gamma_m}\sum_{i=1}^{N}L\bigg(y_i,\sum_{m=1}^{M}\beta_mb(x_i;\gamma_m))\bigg)$

通常这是一个复杂的优化问题。前向分布算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，若果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度，每步只需要优化

$\min_{\beta,\gamma}\sum_{i=1}^{N}L\big(y_i,\beta b(x_i;\gamma))\big)$

其中， $L(y,f(x))$ 为损失函数， $b(x;\gamma)$ 为基函数的集合。

GBDT 算法

提升树

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

我们知道提升方法实际是采用基函数的线性组合和前向分步算法。以决策树为基函数的提升方法为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型：

$f_M(x) = \sum_{m=1}^{M}T(x;\Theta_m)$

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

其实，提升树算法也采用前向分步算法。首先确定初始提升树 $f_0(x) = 0$ ，第 $m$ 步的模型是

$f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$

我们通过经验风险最小化来确定下一棵决策树的参数 $\Theta_m$ ：

$\hat\Theta_m = arg\min_{\Theta_m}\sum_{i=1}^{N}L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))$

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

GBDT 回归算法

其实对于一般损失函数，往往每一步优化并不那么容易。针对这一情况，Freidman 提出了梯度提升（gradient boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值

$-\Bigg [\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\Bigg]_{f(x) = f_{m-1}(x)}$

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

输入：训练数据集；损失函数 $L(y,f(x))$
输出：回归树 $\hat f(x)$

（1）初始化
$f_0(x) = arg \min_c \sum_{i=1}^{N}L(y_i,c)$
（2）对 $m = 1,2,\cdots,M$

对 $i = 1,2,\cdots,N$ ，计算
$r_{mi} = -\Bigg [\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\Bigg]_{f(x) = f_{m-1}(x)}$
对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶节点区域 $R_{mj}$ ， $j = 1,2,\cdots,J$ 。
对 $j = 1,2,\cdots,J$ ，计算
$c_{mj} = arg \min_c \sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$
更新 $f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J}c_{mj}I(x \in R_{mj})$

（3）得到回归树
$\hat f(x) = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^{J}c_{mj}I(x \in R_{mj})$

GBDT 分类算法

GBDT的分类算法从思想上和 GBDT 的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数（log loss）的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。

对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：

$L(y,f(x))=log(1+exp(−yf(x)))$

其中 y∈{−1,+1}。则此时的负梯度误差为

$r_{mi} = -\Bigg [\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\Bigg]_{f(x) = f_{m-1}(x)} = \frac{y_i}{1+exp(y_if(x_i))}$

对于生成的决策树，各个叶子节点的最佳负梯度拟合值为

$c_{mj}=arg \min_c ∑_{x_i \in R_{mj}}log(1+exp(−y_i(f_{m−1}(x_i)+c)))$

由于上式比较难优化，我们一般使用近似值代替

$c_{mj}=\frac{∑_{x_i∈Rmj}r_{mi}}{∑_{x_i∈Rmj}|r_{mi}|(1−|r_{mi}|)}$

除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。

Python 代码实现

AdaBoost

AdaBoost算法工作原理：开始时，赋予训练数据中的每个样本一个相等的初始权重值，首先在训练数据上训练出一个弱分类器并计算该分类的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练中，将第一次分对的样本的权重降低，将第一次分错的样本的权重提高。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。反复学习，不断调整样本权重，最终得到一个强分类器。

Python from scratch
链接: https://pan.baidu.com/s/1qW9-YSeSv4Hvjn5g6CaX-A 提取码: c67e
AdaBoost Classifier in Python – DataCamp
scikit-learn Adaboost类库使用小结

GBDT（Gradient Boosting Decision Tree）

GBDT 也是集成学习Boosting家族的成员，但是却和传统的 Adaboost 有很大的不同。回顾下 Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT 也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用 CART 回归树模型，同时迭代思路和Adaboost 也有所不同。

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 $f_{t−1}(x)$ , 损失函数是 $L(y,f_{t−1}(x))$ , 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器 $h_t(x)$ ，让本轮的损失函数
$L(y,f_t(x))=L(y,f_{t−1}(x)+h_t(x))$ 最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

提升方法（boosting）相关面经和其他资料

小结

提升方法是将弱学习算法提升为强学习算法的统计学习方法，其通过反复修改训练数据的权值分布，构建一系列弱分类器，将其线性组合，形成一个强分类器。
AdaBoost 算法特点在于其通过迭代每次学习一个基本分类器。每次迭代，提高那些被前一轮分类器错误分类数据的权值，降低被正确分类的数据的权值。
GBDT 是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。GBDT 通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。