AdaBoost模型

集成学习是目前很流行的一种机器学习方法，kaggle比赛取得好成绩的队伍几乎都是用的集成学习。

一、集成学习

集成学习的主要思想是利用一定的手段学习出多个弱分类器，然后将多个分类器进行组合。
目前集成学习有2种框架思想，Bagging和Boosting。

Bagging算法：从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中），共进行k轮抽取，得到k个训练集。基于这k个训练集共得到k个模型，最后用这k个模型共同去做决策（每个模型权重一样）。

Boosting算法：首先从原始数据集中训练出一个基学习器，再根据该基学习器的表现，对原始样本分布进行调整（调整的思想是：让先前基学习器分对的样本权重变小，错分的样本权重变大，使得错位样本在下一次的训练学习器中受到更多关注），基于调整后的样本分布训练下一个基学习器，以此，训练出M个基学习器，并加权求和M个基学习器，利用sign函数得出最后的分类结果。

Bagging最具有代表性的算法是随机森林，Boosting最具有代表性的算法有AdaBoost和梯度提升树。

接下来，我们重点讲解一下AdaBoost算法流程及其推导。

二、AdaBoost算法流程

从上面我们知道了AdaBoost是一种集成模型，使用的是boosting框架思想。

用更详细的语言去描述就是：
Adaboost是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的算法。
加法模型就是基学习器的组合方式是通过相加的形式；
前向分步学习算法是用来解决加法模型优化问题的，通过循环迭代，每一步只学习一个基函数 $h_{t}(x)$ 及其系数 $\alpha _{t}$ ，然后逐步逼近优化目标式，就可以简化优化的复杂度。
指数损失函数为 $E(h(x),y,i)=e^{-y_{i}h(x_{i})}$

所以Adaboost模型的公式可以表示为：
$H _{t}(x)=H _{t-1}(x)+\alpha _{t}h_{t}(x)$
其中 $h_{t}$ 的输出为{-1，1}， $\alpha _{t}$ 是每一个基学习器的权重系数

只要是Boosting大家族的算法，都要解决以下这4个问题。

如何计算学习误差率 $\epsilon$ ?
如何得到基学习器的权重系数α?
如何更新样本权重D?
使用何种结合策略？

那么Adaboost是怎么解决的呢？

算法流程-分类：

输入:
　　训练集 $D=\{(\boldsymbol{x}_{1},y_{1}),(\boldsymbol{x}_{2},y_{2}),...,(\boldsymbol{x}_{N},y_{N})\}$ ，其中 $y \in \{-1, 1 \}$
　　初始化数据的权重分布
　　 $D_{1}=(w_{11},...,w_{1i},..,w_{1N}),\ w_{1i}=\frac{1}{N},\ i=1,2,...N$
过程：
For $t$ in 1,..., $T$ :
　　1. 使用带有权重分布 $D_{t}$ 的训练集训练基学习器 $h_{t}(\boldsymbol{x})$
　　2. 计算训练集在 $h_{t}(\boldsymbol{x})$ 上的误差率：
　　　 $\epsilon _{t}=P_{\boldsymbol{x}\ _{\widetilde{}}D_{t}}(h_{t}(x_{i})\neq y_{i}) =\sum_{i=1}^{N}w_{ti}I(h_{t}(x_{i})\neq y_{i})$
　　　if $\epsilon _{t}$ >0.5 then 停止运行
　　3. 计算 $h_{t}(\boldsymbol{x})$ 的系数 $\alpha _{t}=\frac{1}{2}ln\frac{1-\epsilon _{t}}{\epsilon_{t}}$ 　,当 $\epsilon _{t}$ <0.5时， $\alpha _{t}$ 是一个大于0的值
　　4. 更新样本权重：
　　　 $D_{t+1}(\boldsymbol{x})=\frac{D_{t}(\boldsymbol{x})}{Z_{t}}\times \begin{cases} \text{exp}(-\alpha_{t}), & \text{ if } h_{t}(\boldsymbol{x}_{i})=y_{i} \\ \text{exp}(\alpha_{t}), & \text{ if } h_{t}(\boldsymbol{x}_{i})\neq y_{i} \end{cases}$
　　　
　　　又因为 $y \in \{-1,1\}$ ， $h(x) \in \{ -1,1 \}$ ，所以上式可写成
　
　　　 $D_{t+1}(\boldsymbol{x})=\frac{D_{t}(\boldsymbol{x})}{Z_{t}}\times \exp[-y_{i}\alpha _{t}h_{t}(x_{i})]$
　
　　　其中 $Z_{t}$ 是归一化因子，目的是让样本集的权重和为1：
　　　 $Z_{t}=\sum_{i=1}^{N}w_{ti}\exp (-\alpha_{t}y_{i}h_{t}(\boldsymbol{x}_{i}))$
　　　权重更新的含义是：
　　　当样本分对时，权重缩小 $\exp (-\alpha_{t})$ 倍；
　　　当样本分错时，权重扩大 $\exp (\alpha_{t})$ 倍；
输出：最终分类器 $H(\boldsymbol{x})=sign(\sum_{t=1}^{T}\alpha _{t}h_{t}(\boldsymbol{x}))$

算法流程-回归：

Adaboost的回归问题有很多变种，这里我们以Adaboost.R2算法为准。

输入:
　　训练集 $D=\{(\boldsymbol{x}_{1},y_{1}),(\boldsymbol{x}_{2},y_{2}),...,(\boldsymbol{x}_{N},y_{N})\}$ ，其中 $y \in \R$
　　初始化数据的权重分布
　　 $D_{1}=(w_{11},...,w_{1i},..,w_{1N}),\ w_{1i}=\frac{1}{N},\ i=1,2,...N$
过程：
For $t$ in 1,..., $T$ :
　　1. 使用带有权重分布 $D_{t}$ 的训练集训练基学习器 $h_{t}(\boldsymbol{x})$
　　2. 计算训练集在 $h_{t}(\boldsymbol{x})$ 上的回归误差率：
　　　　(1) 先计算训练集在 $h_{t}(\boldsymbol{x})$ 上的最大误差：
　　　　　 $E_{t}=max|y_{i}-h_{t}(\boldsymbol{x}_{i})|\ ,\ i=1,2,...N$
　　　　(2) 再计算每个样本的相对误差
　　　　　如果是线性误差，则 $\epsilon_{ti}=\frac{|y_{i}-h_{t}(\boldsymbol{x}_{i})|}{E_{t}}$
　　　　　如果是平方误差，则 $\epsilon_{ti}=\frac{(y_{i}-h_{t}(\boldsymbol{x}_{i}))^{2}}{E_{t}^{2}}$
　　　　　如果是指数误差，则 $\epsilon_{ti}=1-\exp(\frac{-|y_{i}-h_{t}(\boldsymbol{x}_{i})|}{E_{t}})$
　　　　(3) 最后回归误差率为
　　　　　　　　 $\epsilon_{t}=\sum_{i=1}^{n}w_{ti}\epsilon_{ti}$
　　3. 计算 $h_{t}(\boldsymbol{x})$ 的系数 $\alpha _{t}=\frac{\epsilon_{t}}{1-\epsilon_{t}}$ 　
　　4. 更新样本权重：
　　　 $D_{t+1}(\boldsymbol{x})=\frac{D_{t}(\boldsymbol{x})}{Z_{t}}\times \alpha _{t}^{1-\epsilon_{ti}}$
　　　
　　　其中 $Z_{t}$ 是归一化因子，目的是让样本集的权重和为1：
　　　 $Z_{t}=\sum_{i=1}^{N}w_{ti}\alpha _{t}^{1-\epsilon_{ti}}$
输出：最终分类器 $f(\boldsymbol{x})=h_{t^{*}}(\boldsymbol{x})$
其中， $h_{t^{*}}(\boldsymbol{x})$ 是所有 $ln\frac{1}{\alpha _{t}},t=1,2,..,T$ 的中位数对应序号 $t^{*}$ 对应的基学习器。

如上可知，AdaBoost回归算法没有使用像分类算法那样的加法集成形成最终分类器，而是选用基分类器中权重排序中位数对应的基学习器作为最终的模型。

三、Adaboost公式推导

接下来，我们以分类问题作为示例，来进行推导：

由于Adaboost使用的前向分步学习算法思想，通过循环迭代来简化优化问题，所以每次迭代的时候，都只需要求出该轮下的基函数 $h_{t}(x)$ 及其系数 $\alpha _{t}$ 即可。

准备工作

假设经过 $t-1$ 轮训练后，模型为 $H _{t-1}(x)=H _{t-2}(x)+\alpha _{t-1}h_{t-1}(x)$
在第 $t$ 轮时，我们需要求出这轮的基学习器 $h_{t}(x)$ 和基学习器的权重系数 $\alpha _{t}$ ，这时分类器变为： $H _{t}(x)=H _{t-1}(x)+\alpha _{t}h_{t}(x)$
我们知道，机器学习训练模型的方法就是定义一个损失函数，然后求出让损失函数最小的那个参数，该参数就是我们的目标参数。Adaboost模型的损失函数是指数损失函数，在第 $t$ 轮时：
损失函数 $J_{t}(\alpha ,h(x))=\sum_{i=1}^{N}\exp[-y_{i}(H_{t-1(x_{i})}+\alpha h(x_{i}))]$
最优 $(\alpha_{t} ,h_{t}(x))= \arg\mathop{\min}_{\alpha,h(x)} \sum_{i=1}^{N}\exp[-y_{i}(H_{t-1(x_{i})}+\alpha h(x_{i}))]$
运用指数损失函数的 $a^{m+n}=a^{m}a^{n}$ 运算法则，上式可进一步可表示为:
$(\alpha_{t} ,h_{t}(x))=\arg \mathop{\min}_{\alpha,h(x)} \sum_{i=1}^{N} c_{ti}\exp[-y_{i}\alpha h(x_{i}))]$
其中 $c_{ti}= \exp[-y_{i}H_{t-1}(x_{i}))]$ ，由于前 $t-1$ 轮的学习器是固定了的，所以 $c_{ti}$ 是一个常数，可以看做是经过 $t-1$ 轮后，每个样本的原始权重（未归一化）。

接下来，我们分2步来求解让损失函数最小的 $\alpha_{t}$ 和 $h_{t}(x)$

我们先来对损失函数进行一个转化
　 $\sum_{i=1}^{N} c_{i}\exp[-y_{i}\alpha h(x_{i}))]$
$=\sum_{y_{i}=h(x_{i})}^{}c_{i}e^{-\alpha}+\sum_{y_{i}\neq h(x_{i})}^{}c_{i}e^{\alpha}$
$=e^{-\alpha}\sum_{y_{i}=h(x_{i})}^{}c_{i}+e^{\alpha}\sum_{y_{i}\neq h(x_{i})}^{}c_{i}$
$=e^{-\alpha}\sum_{i=1}^{N}c_{i}I(y_{i}=h(x_{i}))+e^{\alpha}\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))$
$=e^{-\alpha}\sum_{i=1}^{N}c_{i}+(e^{\alpha}-e^{-\alpha})\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))$

(1) 对于任意的 $\alpha_{t}$ >0，
由上式可得， $h_{t}(x)=\arg \mathop{\min}_{h(x)}\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))$
它是使第 $t$ 轮误分类错误样本的权重 $c_{i}$ 和最小的分类器

(2) 求解最优 $\alpha_{t}$
令 $g(\alpha)=e^{-\alpha}\sum_{i=1}^{N}c_{i}+(e^{\alpha}-e^{-\alpha})\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))$

$\frac{\partial g(\alpha)}{\partial \alpha}=\frac{\partial}{\partial \alpha}[e^{-\alpha}\sum_{i=1}^{N}c_{i}+(e^{\alpha}-e^{-\alpha})\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))]$
　　　　 $=-e^{-\alpha}\sum_{i=1}^{N}c_{i}+(e^{\alpha}+e^{-\alpha})\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))$

令 $\frac{\partial g(\alpha)}{\partial \alpha}=0$ ，则
$(e^{\alpha}+e^{-\alpha})\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))=e^{-\alpha}\sum_{i=1}^{N}c_{i}$
令 $\epsilon =\frac{\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))}{\sum_{i=1}^{N}c_{i}}　　　(1)$

则： $(e^{\alpha}+e^{-\alpha})\epsilon =e^{-\alpha}$

可求出：
$\alpha =\frac{1}{2}ln\frac{1-\epsilon }{\epsilon }$

现在我们来分析一下 $\epsilon$

$\epsilon$ 的分母好像是在做一个归一化的操作。

因为 $c_{ti}= \exp[-y_{i}H_{t-1}(x_{i}))]$ ，把 $c_{ti}$ 看成是经过前 $t-1$ 轮训练之后每个样本的原始权重，那么经过归一化之后的每个样本的权重 $w_{ti}=\frac{c_{ti}}{\sum_{i=1}^{N}c_{ti}}$ ，
代入(1)式得： $\epsilon=\sum_{i=1}^{N}w_{i}I( y_{i} \neq h(x_{i}))$ ，可以看作是每一步迭代时，样本的加权误差率。

经过 $t$ 轮训练后，每个样本的原始权重

$c_{(t+1)i}= \exp[-y_{i}H_{t}(x_{i}))]$
　　　　 $= \exp[-y_{i}(H_{t-1}(x_{i})+\alpha _{t}h_{t}(x_{i})]$
　　　　 $= \exp[-y_{i}(H_{t-1}(x_{i})]\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]$
　　　　 $= c_{ti}\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]$

最后归一化权重变成了
$w_{(t+1)i} = \frac{c_{ti}\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]}{\sum_{i=1}^{N}c_{ti}\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]}$
　　　　　 $= \frac{w_{ti}}{\sum_{i=1}^{N} w_{ti}\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]} \exp[-y_{i}\alpha _{t}h_{t}(x_{i})]$ 　　（分子和分母同时除以 $\sum_{i=1}^{N}c_{ti}$ ）

到这里，我们推导出了每步迭代时

基学习器权重系数为：
$\alpha =\frac{1}{2}ln\frac{1-\epsilon }{\epsilon }$ ，其中 $\epsilon=\sum_{i=1}^{N}w_{i}I( y_{i} \neq h(x_{i}))$

每步迭代，基学习器的目标是使本轮误分类错误样本的加权误差率 $\epsilon$ 最小：
$h_{t}(x)=\arg \mathop{\min}_{h(x)}\sum_{i=1}^{N}c_{i}I(y_{i}\neq h(x_{i}))=\arg \mathop{\min}_{h(x)}\sum_{i=1}^{N}w_{i}I(y_{i}\neq h(x_{i}))$ 　　 ( $w_{i}$ 和 $c_{i}$ 等价，一个是归一化前的，一个是归一化后的)

样本权重更新公式为：
$w_{(t+1)i} = \frac{w_{ti}}{\sum_{i=1}^{N} w_{ti}\exp[-y_{i}\alpha _{t}h_{t}(x_{i})]} \exp[-y_{i}\alpha _{t}h_{t}(x_{i})]$

AdaBoost模型

一、集成学习

二、AdaBoost算法流程

三、Adaboost公式推导

推荐阅读更多精彩内容