Boosting之Adaboost原理

1 Boosting框架

Boosting可以看成多个不同的基分类器的线性加权和的形式,那么自然需要知道每个基分类器及其对应的权重，具体的算法逻辑见下图。

Boosting之Adaboost原理

如上图所示，在boosting算法中每一个基分类器都依赖于前面已经生成的基分类器，所以Boosting是一种迭代的算法。根据基分类器迭代方式和权重的不同，Boosting可以分为Adaboost、GBDT、XGBoost三种方式。本文就Adaboost做原理部分的介绍，主要侧重于直观上的理解，比如权重计算的合理性等等。
Boosting算法需要解决下面两个问题：
1. 样本权重或概率分布 $D$ 的计算
2. 基分类器权重 $α$ 的计算

2 Adaboost算法逻辑

以二分类为例，介绍Adaboost算法

2.1 符号标记

训练集样本: $T = {(x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{n}, y_{n})}$
第 $m$ 个分类器or第 $m$ 次迭代: $G_{m}$
迭代次数or基分类器个数: $M$
第 $m$ 次迭代第i个样本的权值，即抽样概率: $w_{m i}$
第 $m$ 次迭代样本的权值分布: $D_{m}$ ,即为 $w_{m 1}, w_{m 2}, . . ., w_{m n}$ ，且 $\sum_{i = 1}^{n} w_{m i} = 1$
第 $m$ 个分类器的权重: $α_{m}$
最终的分类器: $G (x)$

2.2 算法流程

输入：训练数据集 $T = {(x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{n}, y_{n})}$ ，弱学习算法；
输出：最终分类器 $G (x)$
1. 初始化训练样本的权值分布
$D_{m} = w_{11}, w_{12}, . . ., w_{1 n}$ ，且 $w_{1 i} = \frac{1}{n}$
即第一次迭代时，所有样本的权值相同
2. 对 $m = 1, 2, . . ., M$ 即每一轮的迭代
(a)使用具有权值分布 $D_{m}$ 的训练数据集学习，得到基本分类器
$G_{m} (x) : X \to {- 1, + 1}$
样本权重怎么具体影响基分类器，稍后再提。
(b)计算 $G_{m} (x)$ 在训练集上的分类误差率
$e_{m} = P (G_{m} (x_{i}) \neq y_{i}) = \sum_{i = 1}^{n} w_{m i} I (G_{m} (x_{i}) \neq y_{i})$
这个误差率相当于对错误样本的加权求和，符合我们的直觉。
(c)计算 $G_{m} (x)$ 的系数，即基分类器的权重
$α_{m} = \frac{1}{2} \log (\frac{1 - e_{m}}{e_{m}})$
(d)更新训练样本的权值分布
$D_{m + 1} = (w_{m + 1, 1}, w_{m + 1, 2}, . . ., w_{m + 1, n})$
$w_{m + 1, i} = \frac{w_{m i}}{Z_{m}} \exp (- α_{m} y_{i} G_{m} (x_{i}))$
其中 $Z_{m}$ 是规范化因子，使得更新后的权值的和为1
$Z_{m} = \sum_{i = 1}^{n} w_{m i} \exp (- α_{m} y_{i} G_{m} (x_{i}))$
(b)(c)(d)三个公式稍后给出直观上面的解释
3. 构建基本分类器的线性组合
$f (x) = \sum_{m = 1}^{M} α_{m} G_{m} (x)$
$G (x) = s i g n (f (x)) = s i g n (\sum_{m = 1}^{M} α_{m} G_{m} (x))$

(1)样本权重更新的在分类器中的应用
之前提到每一次迭代都要更新样本权重，那么样本权重怎么影响基分类器呢？有两种方式：
1. 通过修改基本分类器源码，对于树模型修改信息增益或者基尼系数的公式引入权值，这里有点像代价敏感学习
2. 对训练样本进行bootstrao抽样，抽样概率等于样本权值
上述解释来自知乎高票答主萧瑟的回答
在Sklearn中是通过resample实现的，源码[见此]1010行(https://github.com/scikit-learn/scikit-learn/blob/a24c8b46/sklearn/ensemble/weight_boosting.py#L297)
(2)样本权重更新的计算逻辑
只看 $w_{m + 1, i} = \frac{w_{m i}}{Z_{m}} \exp (- α_{m} y_{i} G_{m} (x_{i}))$ ，如果第 $i$ 个样本，在第 $m$ 次的迭代中判断错误，那么 $\frac{w_{m i}}{Z_{m}} \exp (α_{m})$ ，即该样本的权重会增大；反之，在第 $m$ 次的迭代中判断正确，那么 $\frac{w_{m i}}{Z_{m}} \exp (- α_{m})$ ，即该样本的权重会减小。
基分类器误差率 $e_{m}$ 越小，该分类器 $G_{m}$ 的投票权重越大。在实际操作中，如果误差率 $e_{m} > 0.5$ ，迭代会从等权重重新开始。

具体流程如下(符号有些许不同)
Boosting之Adaboost原理

3 Adaboost算法的解释

都说Boosting更关注偏差，前面Adaboost的流程只能从直观上讲，怎么从损失函数的角度思考这一问题呢？

Adaboost算法可以看成加法模型，损失函数为指数函数、学习算法为前向分布算法。下面围绕这三个方面谈一谈。

3.1 加法模型

给出加法模型的形式定义：
$f (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m})$
其中， $b (x; γ_{m})$ 是基函数， $γ_{m}$ 为基函数的参数， $β_{m}$ 是基函数的系数
显然Adaboost模型是一个加法模型，基函数—基分类器，基函数的参数—基分类器的参数，基函数的系数—基分类器的权重

3.2 损失函数

在给定训练样本和损失函数 $L (y, f (x))$ 的条件下，学习加法模型 $f (x)$ 的需要解决的问题变为损失函数极小化问题：

min_{β_{m}, γ_{m}} \sum_{i = 1}^{n} L (y_{i}, f (x_{i}))

求解最优化问题需要明确两点：
1. 损失函数怎么定义
在Adaboost算法中，可以把损失函数理解为指数损失函数。后面再谈
2. 如何求解
上面的优化问题比较复杂，一般采用前向分步算法，该算法的逻辑为：从前向后每一步只学习一个基函数及其系数，逐步优化目标函数

3.3 前向分步算法

输入：训练样本 $T = {(x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{n}, y_{n})}$ ；损失函数 $L (y, f (x))$ ；基函数集 ${b (x; γ)}$
输出：加法模型 $f (x)$
(1)初始化 $f_{0} (x) = 0$
(2)对 $m = 1, 2, . . ., M$
(a)极小化损失函数
$(β_{m}, γ_{m}) = \arg min_{β, γ} \sum_{i = 1}^{n} L (y_{i}, f_{m - 1} (x_{i}) + β b (x; γ))$
得到参数 $β_{m}, γ_{m}$
(b)更新
$f_{m} (x) = f_{m - 1} (x) + β_{m} b (x; γ_{m})$
(3)得到加法模型
$f (x) = f_{M} (x) = \sum_{m = 1}^{M} β_{m} b (x; γ_{m})$

这样，前向分步算法将同时求解从 $m = 1$ 到 $M$ 所有参数 $β_{m}, γ_{m}$ 的优化问题简化为逐次求解各个 $β_{m}, γ_{m}$ 的优化问题。
从(a)步可以看出，每一轮迭代的新分类器，都是在找一个使得损失函数最低的分类器。所以，Adaboost算法的关注点是逐步降低偏差。那么Adaboost的逻辑和前向分步算法有什么关系呢？

3.4 前向分步算法和Adaboost

前向分步算法和Adaboost是否是一致的，那么关注点显然是每一次迭代时，Adaboost中的表达式 $α_{m}, G_{m}$ ，是不是损失函数最小化的参数 $β_{m}, γ_{m}$ 。
下面证明当损失函数为指数损失函数，基函数为基分类器时，Adaboost是加法模型的前向分步算法的特例。
加法模型
Adaboost最终的分类器 $f (x) = \sum_{m = 1}^{M} α_{m} G_{m} (x)$
形式和加法模型一致，那么需证迭代方式与前向分步算法一致
损失函数
损失函数采用指数损失函数：

L (y, f (x)) = \exp [- y f (x)]

损失函数定义有多种，在逻辑上要能讲的通，对于二分类问题而言，预测准确，且

| f (x) |

越大(参照SVM的几何间隔，说明预测的更好)，指数部分为负，所以

L

越小。反之，预测错误，且

| f (x) |

越大(预测错误更加离谱)，指数部分为正，所以

L

越大。至此，可以从直观上体现指数损失函数的合理性。
如果基分类器or基函数返回的结果是

{- 1 ， + 1}

，那么损失函数为：

L = {\begin{cases} e f (x) \neq y \\ \frac{1}{e} f (x) = y \end{cases} (1)

Why指数损失函数
1. 方便计算，指数损失函数有比较好的数学性质，连续可微
2. 使得样本权重的更新更加简洁
3. 此时目标函数最小化等价于后验概率最大化(贝叶斯分类器)
迭代方式
这里是关键的地方，即证明Adaboost中的表达式

α_{m}, G_{m}

和前向分步算法迭代时损失函数最小化的参数

β_{m}, γ_{m}

的一致性。
假设经过

m - 1

次迭代前向分步算法已经得到

f_{m - 1} (x)

\begin{array}{l} f_{m - 1} (x) = f_{m - 2} (x) + α_{m - 1} G_{m - 1} (x) \\ = α_{1} G_{1} (x) + \dots + α_{m - 1} G_{m - 1} (x) \end{array}

在第

m

次迭代时，得到

α_{m}, G_{m} (x), f_{m} (x)

f_{m} (x) = f_{m - 1} (x) + α_{m} G_{m} (x)

按照前向分步算法的逻辑，求解

α_{m}, G_{m} (x)

即求下面目标函数最小化时的参数值：

\begin{array}{l} (α_{m}, G_{m}) = \arg min_{α, G} \sum_{i = 1}^{n} L (y_{i}, f (x)) \\ = \arg min_{α, G} \sum_{i = 1}^{n} \exp [- y_{i} f (x)] \\ = \arg min_{α, G} \sum_{i = 1}^{n} \exp [- y_{i} (f_{m - 1} (x_{i}) + α G (x))] \\ = \arg min_{α, G} \sum_{i = 1}^{n} \exp [- y_{i} f_{m - 1} (x_{i})] * \exp [- y_{i} α G (x)] \\ = \arg min_{α, G} \sum_{i = 1}^{n} {\bar{w}}_{m i} * \exp [- y_{i} α G (x)] \end{array}

其中

{\bar{w}}_{m i} = \exp [- y_{i} f_{m - 1} (x_{i})]

，注意这里下标出现了点变化。

{\bar{w}}_{m i}

只和

f_{m - 1} (x), y

有关，且

f_{m - 1} (x)

每一轮迭代之后都产生变化。但是与

α, G

无关，所以不影响最小化求解。换言之，如果目标函数除以

\sum_{i = 1}^{n} {\bar{w}}_{m i}

也不影响最终求解，为什么要插一句，后面见分晓。
下面证明最小化求解的参数就是Adaboost中所得到的

α_{m}, G_{m} (x)

。
求解可以分两步：
1. 求

G_{m}^{*} (x)

对于任意

α > 0

(实际算法流程中可以设置如果分类器误差率大于0.5，会初始化再迭代，也就是说保证

α > 0

)，最小化可以由下式得到：

G_{m}^{*} (x) = \arg min_{G} \sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G (x_{i}))

这里有两点需要明确：
(1)极小化指数损失函数为什么等价于最小化加权分类误差
如果基函数or基分类器返回的是

{- 1, + 1}

，那么损失函数为式(1)，原始最小化公式可以化简为：

\begin{array}{l} L o s s = \sum_{i = 1}^{n} {\bar{w}}_{m i} \exp [- y_{i} α G_{m} (x)] \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{α} {\bar{w}}_{m i} \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α} + e^{- α}) {\bar{w}}_{m i} \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + (e^{α} - e^{- α}) \sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i})) \end{array}

就本次优化问题而言，

α, {\bar{w}}_{m i}

都是固定不变的，化简的时候可以去掉，因此由上面的推导就可以得到指数损失函数等价于最小化加权分类误差。

(2)样本权重怎么影响目标函数
后面会讲到 ${\bar{w}}_{m i}$ 和Adaboost中的 $w_{m i}$ 只相差一个规范化因子 $Z_{m}$ ，所以其本身不影响损失函数的最小化，那么样本权重是可以直接影响到最小化的求解过程，至于具体的求解，李航书里的例子只用一层的决策树桩，所以相当于是直接求解，至于更复杂的分类器可能就是上面提到的改变基分类器损失函数和进行重抽样来实现的[这里需要再确认下]。
2. 求 $α_{m}^{*}$

\begin{array}{l} G_{m}^{*} (x) = \arg min_{G} \sum_{i = 1}^{n} {\bar{w}}_{m i} \exp [- y_{i} α G (x)] \\ = \arg min_{G} \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{α} {\bar{w}}_{m i} \\ = \arg min_{G} \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α} + e^{- α}) {\bar{w}}_{m i} \\ = \arg min_{G} \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \arg min_{G} \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \arg min_{G} \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + (e^{α} - e^{- α}) \sum_{y_{i} \neq G (x_{i})} {\bar{w}}_{m i} I (y_{i} \neq G (x_{i})) \end{array}

将已求得的

G_{m}^{*} (x)

代入上式，并对

α

求导，令其为0，即可得

α_{m}^{*}

:
对loss做化简：

\begin{array}{l} L o s s = \sum_{i = 1}^{n} {\bar{w}}_{m i} \exp [- y_{i} α G_{m} (x)] \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{α} {\bar{w}}_{m i} \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α} + e^{- α}) {\bar{w}}_{m i} \\ = \sum_{y_{i} = G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + \sum_{y_{i} \neq G (x_{i})} (e^{α} - e^{- α}) {\bar{w}}_{m i} \\ = \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + (e^{α} - e^{- α}) \sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i})) \end{array}

对

α

求导：

\begin{array}{l} \frac{\partial L o s s}{\partial α} = - \sum_{i = 1}^{n} e^{- α} {\bar{w}}_{m i} + (e^{α} + e^{- α}) \sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i})) = 0 \\ e^{- α} \sum_{i = 1}^{n} {\bar{w}}_{m i} = (e^{α} + e^{- α}) \sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i})) \\ \frac{e^{- α}}{e^{α} + e^{- α}} = \frac{\sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i}))}{\sum_{i = 1}^{n} {\bar{w}}_{m i}} \\ s e t e_{m} = \frac{\sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i}))}{\sum_{i = 1}^{n} {\bar{w}}_{m i}} \\ s o \\ \frac{e^{α} + e^{- α}}{e^{- α}} = \frac{1}{e_{m}} \\ e^{2 α} + 1 = \frac{1}{e_{m}} \\ \log (e^{2 α}) = \log (\frac{1}{e_{m}} - 1) \\ α_{m}^{*} = \frac{1}{2} \log (\frac{1 - e_{m}}{e_{m}}) \end{array}

观察每一轮样本权值的更新。由

\begin{array}{l} {\begin{cases} f_{m} (x) = f_{m - 1} (x) + α_{m} G_{m} (x_{i}) \\ {\bar{w}}_{m i} = \exp [- y_{i} f_{m - 1} (x_{i})] \end{cases} \\ ∴ \\ {\bar{w}}_{m + 1, i} = \exp [- y_{i} f_{m} (x_{i})] \\ = \exp [- y_{i} (f_{m - 1} (x) + α_{m} G_{m} (x_{i}))] \\ = \exp [- y_{i} f_{m - 1} (x)] * \exp [- y_{i} α_{m} G_{m} (x_{i})] \\ = {\bar{w}}_{m i} * \exp [- y_{i} α_{m} G_{m} (x_{i})] \end{array}

这与Adaboost算法第2(d)步的权值更新，只差规范因子，因而等价。等价的原因是：对于前面第

m

轮最小化求解问题，

{\bar{w}}_{m i}

是固定的，所以目标函数同时除以

\sum_{i = 1}^{n} {\bar{w}}_{m i}

并不影响求解，我们可以在前面修改目标函数的表达式，从而形式上和Adaboost保持一致。
前面还有一个遗留问题：

α_{m}^{*}

与Ada中形式上一致，那么

e_{m}

是否一致呢？
在Adaboost中：

e_{m} = P (G_{m} (x_{i}) \neq y_{i}) = \sum_{i = 1}^{n} w_{m i} I (G_{m} (x_{i}) \neq y_{i})

在前向分步算法中：

e_{m} = \frac{\sum_{i = 1}^{n} {\bar{w}}_{m i} I (y_{i} \neq G_{m} (x_{i}))}{\sum_{i = 1}^{n} {\bar{w}}_{m i}}

若两者等价，则需证明

\frac{{\bar{w}}_{m i}}{\sum_{i = 1}^{n} {\bar{w}}_{m i}} = w_{m i}

从前面样本权重的迭代公式可以看出，前向分步算法和Adaboost的样本权重迭代是一致的，也就是说，只要去相同的初始值

w_{0}

，后面迭代的结果也是一致的。

\begin{array}{l} \frac{{\bar{w}}_{m i}}{\sum_{i = 1}^{n} {\bar{w}}_{m i}} = \frac{{\bar{w}}_{m - 1, i} * \exp [- y_{i} α_{m - 1} G_{m - 1} (x_{i})]}{\sum_{i = 1}^{n} {\bar{w}}_{m - 1, i} * \exp [- y_{i} α_{m - 1} G_{m} - 1 (x_{i})]} \\ w_{m i} = \frac{w_{m - 1, i} \exp [- y_{i} α_{m - 1} G_{m - 1} (x_{i})]}{Z_{m - 1}} \\ = \frac{w_{m - 1, i} \exp [- y_{i} α_{m - 1} G_{m - 1} (x_{i})]}{\sum_{i = 1}^{n} w_{m - 1, i} \exp [- y_{i} α_{m - 1} G_{m - 1} (x_{i})]} \end{array}

至此，所有证明结束，从损失函数角度理解Adaboost算法逻辑性更强。

4 Adaboost的正则化

这部分内容了解的不多，先占个坑。有资料写正则主要是在迭代时对基分类器加了步长 $v$ 进行调整， $0 < v < 1$ 。

f_{m} (x) = f_{m - 1} (x) + v α_{m} G_{m} (x)

也许步长和迭代次数是两个比较重要的参数，下次去看sklearn的文档再回来补。

5 Summary

周一看到周四，磨磨蹭蹭，写了两篇笔记，对Adaboost的逻辑还算比较清楚。后面争取写下GBDT和XGBoost以及python调参。对这篇笔记做一点总结。
1. Adaboost损失函数—指数损失函数
2. 为什么可以减少偏差—更关注错分的样本，并且体现在目标函数中
3. 样本权重和基分类器权重如何影响算法—样本权重影响损失函数，分类器权重影响最终投票权重
还有一些问题不太清楚：
1. Adaboost是否存在过拟合问题，怎么处理
2. Adaboost的基分类器是否可以用其他的分类器，强弱分类器做基分类器有什么不同

6 Ref

[1] 李航《统计学习方法》
[2] 刘建平Pinard博客

2018-04-26 于杭州

Boosting之Adaboost原理

Boosting之Adaboost原理

1 Boosting框架

2 Adaboost算法逻辑

2.1 符号标记

2.2 算法流程

3 Adaboost算法的解释

3.1 加法模型

3.2 损失函数

3.3 前向分步算法

3.4 前向分步算法和Adaboost

4 Adaboost的正则化

5 Summary

6 Ref

相关推荐