《统计学习方法》第 8 章“提升方法”学习笔记

集成学习

集成学习主要有下面 3 种思路：

1、袋装法 Bagging：随机森林是 Bagging 的典型代表，Bagging 的特点是不同分类器可以并行执行。

2、Boosting：Boosting 类算法的特点是：不同分类器串行执行。

3、Stacking：类似于神经网络一样的堆叠算法。

AdaBoost

AdaBoost 算法是前向分步算法的特例，AdaBoost 模型等价于损失函数为指数函数的加法模型（李航《统计学习方法》P144）。

AdaBoost 算法：样本有权重，分类器也有权重，更关注错误的样本。

1、我们对错误的样本给予更高的关注；

2、后面的分类器对这些错误的样本给予更多的关注，即权重更大；

3、具体来说，我们会计算一个分类器的错误率，如果错误率越低，这个分类器的权重就会越高。

1、加法模型

加法模型形如：
$f(x) = \sum\limits_{m=1}^{M}\alpha_mG_{m}(x)$
递推公式形如：
$f_m(x) = f_{m-1}(x) + \alpha_mG_{m}(x)$
递推公式在推导中会多次用到。

2、损失函数

损失函数定义成指数函数：
$L(y,f(x)) = \exp[-yf(x)]$
把上面的递推公式代入的时候，指数部分的加法就可以变成带底数的乘法，分离出一个在前面几轮已经得出，并且视为确定的乘法因子，我们把这个乘法因子叫做权重。

3、两个权重

样本的权重决定了分类器和错误率，由错误率可以计算出分类器的权重。

1、根据当前训练的分类器更新样本的权重；

2、根据当前训练的分类器得到这个分类器在最终加法因子中的权重。

我在学习过程中遇到的难点：

1、每一次迭代希望得到的是一个基础分类器 $G_m(x)$ 和这个分类器在最终加和模型中的权重 $\alpha_m$ ，那么之前的权重和基础分类器都应该视为已知；

2、训练当前分类器的时候，损失函数应该是带“权重”的，这是因为我们在定义损失函数的时候，考虑了之前迭代的结果，我们看一看之前确定的那部分，即权重的表达式： $\overline w_{mi} =\exp[-y_if_{m-1}(x_i)]$ ，分类正确的这个值小，分类错误的这个值大，这也符合逻辑。这里 $f_{m-1}(x)$ 是之前 $m-1$ 个分类器带权重的加和。

说这些要强调的结论就是：训练基分类器的时候，是要考虑“权重”的，这个“权重”表达了之前的训练结果在训练样本上的好坏。于是，这一轮训练的基础分类器会重点看之前分错的样本。

损失函数的表达式如下：
$L(y,f(x)) = \sum_{i=1}^{N}\overline w_{mi} \exp(-y_i\alpha_mG_{m}(x))$
训练 $G_m(x)$ 即找到：
$G_{m}^*(x) = \underbrace{arg\;min\;}_{G} \sum_{i=1}^{N}\overline w_{mi} I(y_i \neq G(x_i))$
理解这个式子就从损失函数的定义出发，即：损失函数就是计算预测值和真实值不等的样本的总和，用指数和用示性函数表达其实是一样的，只不过用指数更放大了损失。

这里关键是在于：训练基础分类器的时候，一定是带样本权重的，如果不带上样本权重，就不是 Boosting 的思想了。

3、从损失函数出发，先确定当前最优的 $G_m(x)$ ，再确定其系数 $\alpha_m$ ，方法是求导。具体是把样本从 $1$ 到 $N$ 分成两部分，即“分对的部分”和“分错的部分”，然后加一项减一项，推导出下面的等式。
$\begin {aligned} L(y,f(x)) &= \sum_{i=1}^{N}\overline w_{mi} \exp(-y_i\alpha_mG_{m}(x)) \\ &=\sum_{y_i = G_m(x_i)}\overline w_{mi} e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}\overline w_{mi} e^{\alpha} \\ &=\sum_{y_i = G_m(x_i)}\overline w_{mi} e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}\overline w_{mi} e^{-\alpha} - \sum_{y_i \neq G_m(x_i)}\overline w_{mi} e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}\overline w_{mi} e^{\alpha} \\ &= e^{-\alpha}\sum_{i=1}^{N}\overline w_{mi} + (e^{\alpha} - e^{-\alpha})\sum_{y_i \neq G_m(x_i)}\overline w_{mi} \\ &= e^{-\alpha}\sum_{i=1}^{N}\overline w_{mi} + (e^{\alpha} - e^{-\alpha})\sum_{i=1}^N \overline w_{mi} I(y_i \neq G_m(x_i)) \end {aligned}$
然后上面的式子对于 $\alpha$ 求导数，并令导函数为 $0$ 。具体过程是这样的：

公式推导

其中
$\cfrac{\sum_{i=1}^N \overline w_{mi} I(y_i \neq G_m(x_i))}{\sum_{i=1}^{N}\overline w_{mi}}$

就是错误率，每一个都带权重，分布正好是权重之和，符合错误率的定义，因此，这里干脆我们就把分子分母同时除以
$\sum_{i=1}^{N}\overline w_{mi}$
也就是即分母，让分母为 $1$ ，这样分子就得到了一个新的权重，这就是归一化的过程。

4、权重更新公式，即如何根据当前权重得到下一轮的权重

要根据当前基分类器的结果和基础分类器的权重计算得到，并且还要归一化。已知加法模型的递推公式：

$f_m(x) = f_{m-1}(x) + \alpha_mG_{m}(x)$

和

$\overline w_{mi} =\exp[-y_if_{m-1}(x_i)]$

它们二者都是定义，可以得到递推公式：

$\begin {aligned} \overline w_{m+1,i} &=\exp[-y_if_{m}(x_i)] \\ &=\exp[-y_i[f_{m-1}(x_i) + \alpha_mG_{m}(x_i)]]\\ &=\exp[-y_if_{m-1}(x_i)]\exp[-y_i\alpha_mG_{m}(x_i)]\\ &=\overline w_{m,i}\exp[-y_i\alpha_mG_{m}(x_i)] \end {aligned}$

5、分类错误率越小，分类器的权重就越大，这一点是合理的，公式推导中结论也是合理的。
$\alpha_m = \cfrac{1}{2}\log\cfrac{1 - e_m}{e_m}$
说明：对数函数是增函数， $1-e_m$ 表示正确率，与 $e_m$ 是此消彼长的，正确率越高， $\alpha_m$ 的值就越大。

数学公式的部分我写在了简书上了： AdaBoost 公式推导。

4、AdaBoost 算法优点

很好的利用了弱分类器进行级联（弱分类器串行，并且后面的分类器训练的是“残差”）。
可以将不同的分类算法作为弱分类器。
AdaBoost具有很高的精度。
相对于bagging算法和Random Forest算法，AdaBoost充分考虑的每个分类器的权重。

5、Adaboost 算法缺点

AdaBoost迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定。
数据不平衡导致分类精度下降。
训练比较耗时，每次重新选择当前分类器最好切分点。

6、AdaBoost 应用领域

模式识别，计算机视觉领域，用于二分类和多分类场景。

7、AdaBoost 和 Gradient-Boosting

AdaBoost 基于权重；
Gradient-Boosting 基于残差。

下面是手写笔记：

image-20190220134627498

手写笔记1

手写笔记2

手写笔记3

image-20190222095622040

image-20190222095644447

image

梯度提升树 GBDT ：通过不断地拟合残差 (residual)来“纠错”基学习器

GBDT 即 Gradient Boosting Decision Tree。基础是 GBM，当 M 成为 DT 的时候，就是 GBDT。

GBDT 的基模型是决策树（CART），所以“GBDT”最后两个字母是“DT”；

GBDT 每一轮迭代拟合残差，即每一轮找到的 CART，即下面的 $h_t(x)$ ，每一轮就是学习它，要让样本的损失变得更小：损失函数： $L(y,f_{t}(x))=L(y,f_{t-1}(x)+h_t(x))$

可以这样认为：每一轮加上一个函数，就可以让预测结果越来越接近真实值 $y$ 。

基本思想非常简单：基学习器存在着预测错误的情况，在下一轮基学习器学习时努力地纠正这个错误。

在回归问题中，这个错误被称为残差。比如，在学习样本 $(x,y)$ 得到一个模型 $f$ ，预测值为 $\hat{y} = f(x)$ ，那么残差为：
$y - \hat{y} = y- f(x)$
如果定义损失函数为平方损失函数： $\cfrac{1}{2}(y-f(x))^2$ ，那么其梯度为：
$\frac{\partial \frac{1}{2}(y-f(x))^2}{\partial f(x)} = f(x) - y$
可以发现：残差为负梯度方向。理解这里对函数 $f(x)$ 求导。

其实思想还是很简单的，差多少，就加一个模型去拟合多少。所以提升树可以看成是决策树的加法模型。

image

最速下降法与梯度下降法的区别

引用：http://sofasofa.io/forum_main_post.php?postid=1001153

维基百科这个说法不是太严谨。准确来说，它们并不是完全等价。对于梯度下降法，我们需要预先设定步长 $\alpha$ 。而最速下降法的这个步长 $\alpha_k$ 是通过一个优化函数计算得到的。
$\alpha_k=\text{argmin}_{\alpha_k} \; f(x_i-\alpha_k \nabla f{x_i})$
参考资料：自己动手用 python 写梯度下降。

以下为草稿，我自己留着备用，读者可以忽略，欢迎大家批评指正。

参考资料

1、https://scikit-learn.org/stable/modules/ensemble.html#adaboost

2、刘建平：集成学习之Adaboost算法原理小结

3、刘建平：scikit-learn Adaboost类库使用小结

4、https://blog.csdn.net/Cdd2xd/article/details/77342350

5、https://zhuanlan.zhihu.com/p/43443518

6、Adaboost 算法的原理与推导

三张简图搞懂GBDT
https://blog.csdn.net/accumulate_zhang/article/details/82178494#comments
GBDT 是决策树，后一步基于之前的结果，拟合残差。

Boosting决策树：GBDT ：https://www.cnblogs.com/en-heng/p/6927620.html

image-20190221124022232

这篇文章还提到了 Shrinkage 。

Gradient Boosting梯度提升-GBDT与XGBoost解析及应用

地址：https://mp.weixin.qq.com/s/xV0LnPEofxB3PjsNqeh8Iw

通俗、有逻辑的写一篇说下Xgboost的原理，供讨论参考

https://blog.csdn.net/github_38414650/article/details/76061893

GBDT：梯度提升决策树

https://www.jianshu.com/p/005a4e6ac775

GBDT算法原理深入解析

https://blog.csdn.net/yangxudong/article/details/53872141

https://www.zybuluo.com/yxd/note/611571

从0开始机器学习-随机森林和GBDT
https://zhuanlan.zhihu.com/p/37676630

xgboost中的数学原理：

https://blog.csdn.net/a358463121/article/details/68617389

说明：这篇文章讲得还比较清楚，还提到了 Shrinkage 与采样

http://kaggle比赛必备算法XGBoost入门及实战

www.manongjc.com/article/57510.html

GBM 与 GBDT 与 XgBoost

https://blog.csdn.net/Cdd2xd/article/details/77426622

这篇文章内容比较全面，不是抄书。

七月的文章，可以好好看一下

https://blog.csdn.net/v_JULY_v/article/details/81410574

Machine Learning笔记 - XGBOOST 教程

http://codewithzhangyi.com/2018/06/01/XGBOOST%E4%BD%BF%E7%94%A8%E8%AF%B4%E6%98%8E/

XGBoost算法原理

https://zxth93.github.io/2017/09/29/XGBoost算法原理/index.html

Machine Learning笔记 - XGBOOST 教程

https://blog.csdn.net/huangdunxian/article/details/70570982

知乎“忆臻” ：https://zhuanlan.zhihu.com/p/32709034；
解释了为什么负梯度的范数小于一个很小的数的时候，搜索就可以停止了；
最后举了一个例子，很直观地体现了，其实每一步求解的是关于步长的一元函数的最优值，这是直线搜索，在这篇文章中有提到。http://www.sigai.cn/paper_43.html；

最速下降法 = 解析法 + 迭代法；

理解梯度提升算法1-梯度提升算法
http://www.sigai.cn/paper_43.html

凸优化(六)——最速下降法
说明：来自简书 https://www.jianshu.com/p/1238602a2720，是《凸优化》那本书的笔记。

刘建平：梯度提升树(GBDT)原理小结

https://www.cnblogs.com/zengzhen94/p/8744970.html