Adaboost

我默认大家已经掌握了 $Adaboost$ 的基本操作方法。这篇博客中我将会首先简要介绍一下 $Adaboost$ 的具体流程，接下来将会用大段的推导解决这两个问题：

• $Adaboost$ 的误差上界是多少，收敛速率如何。
• $Adaboost$ 中最重要的两个参数：第 $m$ 轮得到分类器 $G_m(x)$ 与其对应的权重 $\alpha_m$ 是如何求得的。

$Adaboost$ 算法流程

定义变量：

• $G_m(x)$ 为第 $m$ 次迭代得到的弱分类器，是一种映射：$x_i \to \{-1,+1\}$
• $f_m(x) = \sum_m^{M} G_m(x)$ 是当前得到的强分类器。即弱分类器的线性组合，值域是连续的而非只有 $\pm1$.
• $w_{m,i}$ 为第 $m$ 次迭代时第 $i$ 个样本的权重.
• $\alpha_m$ 为对应 $G_m(x)$ 的权重.
• $I(x)$ 为判断函数，当 $x$ 为真则返回 $1$，否则返回 $0$.
• $e_m$ 为 $G_m(x)$ 的得到的误差.
• $Z_m = \sum_i w_{m,i}\exp(-\alpha_my_iG_m(x_i))$ 是规范化子，为了让权重归一化。

此算法的循环过程是这样的：

1. 在当前数据集下训练一个简单的分类模型 $G_m(x)$ 使得误差最小 $\min(\sum_i w_{m,i} I(y_i \neq G_m(x_i)))$
2. 计算当前分类误差 $e_m=\sum_i w_{m,i} I(y_i \neq G_m(x_i))$
3. 计算当前分类器的权重 $\alpha_m = \frac{1}{2}ln(\frac{1-e_m}{e_m})$
4. 更新样本权重 $w_{m+1,i}=\frac{w_{m,i}\exp(-\alpha_my_iG_m(x_i))}{Z_m}$
5. 将弱分类器加入到强分类器中 $f_m(x) = f_{m-1}(x) + \alpha_mG_m(x)$
6. 若迭代未结束，则返回第一步，在新的权值下去寻找新的弱分类器。

$Adaboost$ 的误差上界与收敛速率

在这个部分中我将首先推导出 $Adaboost$ 的误差上界，并通过误差上界进行放缩，得出其收敛速率随着新弱分类器的加入是指数下降的结论。

$Adaboost$ 误差上界

先给出结论，然后我们对其进行证明。对于最终的误差 $Loss=\frac{1}{N}\sum_{i=1}^{N}I(G(x_i)\neq y_i)$ 有：
$$
\begin{aligned}\frac{1}{N}\sum_{i=1}^{N}I(G(x_i)\neq y_i)\leq\frac{1}{N}\sum_{i}exp(-y_if(x_i))=\prod_{m}Z_m\end{aligned}
$$

首先证明第一个不等号是成立的

• 当 $G(x_i)= y_i$ 时，$I(G(x_i)\neq y_i)= 0$ 而 $exp(-y_if(x_i))>0$
• 当 $G(x_i)\neq y_i$ 时，$I(G(x_i)\neq y_i)= 1$，但因为 $-y_if(x_i) \ge 0$，所以 $exp(-y_if(x_i))\ge 1$

综上，$I(G(x_i)\neq y_i)\le exp(-y_if(x_i))$ 总是成立的，因此第一个不等号得证。

接下来证明第二个等号是成立的

考虑在更新权重的时候，为了使得权重归一化，因此权重 $w_{m+1, i}$ 与规范化子 $Z_m$ 有如下关系：
$$
w_{m+1,i}=\frac{w_{m,i}exp(-\alpha_my_{i}G_m(x_i))}{Z_{m}}
$$
因此：
$$
w_{m,i}exp(-\alpha_my_{i}G_m(x_i))=Z_{m}w_{m+1,i}
$$
先做一个简单的变换，为我们后续证明做一个铺垫：
$$
\begin{aligned}
&\sum_iw_{m,i}exp(-\alpha_my_iG_m(x_i))
\\=&\sum_iZ_mw_{m+1,i}
\\=&Z_m\sum_iw_{m+1,i}
\end{aligned}
$$
所以对于待证明不等式组的中间式子，做如下变形。其中有两点注意：1. 在初始时刻样本权重均为 $\frac1N$，即 $w_{1,i} = \frac1N$，2. 所有权重和为1，即 $\sum_iw_{m,i}=1$：
$$
\begin{aligned}
&\frac1N\sum_iexp(-y_if(x_i)) \\
=&\frac1N\sum_iexp(-\sum_{m=1}^M\alpha_my_iG_m(x_i)) \\
=&\sum_{i}w_{1,i}\cdot exp[-\alpha_{1}y_{i}G_{1}\left(x_{i}\right)-\alpha_{2}y_{i}G_{2}\left(x_{i}\right)-\ldots-\alpha_{M}y_{i}G_{M}\left(x_{i}\right)] \\
=&\sum_iw_{1,i}\prod_{m=1}^Mexp(-\alpha_my_iG_m(x_i)) \\
=&Z_1\sum_iw_{2,i}\prod_{m=2}^Mexp(-\alpha_my_iG_m(x_i)) \\
=&Z_1Z_2\sum_iw_{3,i}\prod_{m=3}^Mexp(-\alpha_my_iG_m(x_i)) \\
=&\ldots \\
=&Z_1Z_2 \cdots Z_{M-1}\sum_iw_{M,i}exp(-\alpha_My_iG_M(x_i)) \\
=&Z_1Z_2 \cdots Z_{M}\sum_iw_{M+1,i}\\
=&\prod_m^MZ_m
\end{aligned}
$$
因此我们证明了第二个等号是成立的。

$Adaboost$ 收敛速率

那么收敛速率如何呢？在我们解决这个问题之前，我们首先要找到 $Z_m$ 与误差 $e_m$ 之间的关系。

在求解过程中我们需要用的 $\alpha_m=\frac{1}{2}ln(\frac{1-e_m}{e_m})$ 这个结论。至于为什么 $\alpha_m$ 是这个值，我将会在第三部分讲到。
$$
\begin{aligned}
Z_{m}& =\sum_{i=1}^{N}\left.w_{m,i}\exp(-\alpha_{m}\left.y_{i}\left(x_{i}\right)\right)\right. \\
&=\sum_{y_i=G_m{(x_i)}}w_{m,i}e^{-\alpha_m}+\sum_{y_i\neq G_m{(x_i)}}w_{m,i}e^{\alpha_m} \\
&=e^{-\alpha_m}\sum_{y_i=G_m\left(x_i\right)}w_{m,i}+e^{\alpha_m}\sum_{y_i\neq G_m\left(x_i\right)}w_{m,i} \\
&=\sqrt{\frac{e_m}{1-e_m}}(1-e_m) + \sqrt{\frac{1-e_m}{e_m}}e_m\\
&=2\sqrt{e_m\left(1-e_m\right)} \\
&=\sqrt{1-4{\gamma}_m^2}
\end{aligned}
$$
其中我们令 $\gamma_m = \frac12 - e_m$。事实上 $\gamma_m$ 一定是正值，我们考虑某分类器得到的误差 $e_m > \frac12$ ，则将这个分类器的分类结果加个负号得到新分类器，而此时 $e_m’=1-e_m$，即误差小于 $\frac12$ ，因此在得到最优的 $G_m(x)$ 时 $\gamma_m > 0$ 一定成立。

下面我们来证明指数收敛，我们先证明：
$$
\sqrt{(1-4\gamma_m^2)}\leq exp(-2\gamma_m^2)
$$
通过泰勒展开，我们能够较容易的证明这个命题：
$$
\sqrt{1-4r^2}=1-2r^2-2r^4+O(r^4)\\
e^{-2r^2}=1-2r^2+2r^4+O(r^4)
$$
通过图像我们能够更直观的看出两者的大小关系：

因此我们再次对误差进行放缩，能够得到：
$$
\prod_{m=1}^M\sqrt{(1-4\gamma_m^2)}\leq\prod_{m=1}^Mexp(-2\gamma_m^2)=exp(-2\sum_{m=1}^M\gamma_m^2)
$$
也就是说，随着分类器的增多，指数项上不断减小，这也就表明了 $Adaboost$ 的训练误差是以指数速度下降的。

$Adaboost$ 中分类器与权重的选取——以加法模型解释

对于分类器来说：
$$
f(x)=\sum_{m=1}^M \alpha_mG_m(x)
$$
我们针对此问题选择损失函数为：
$$
Loss = \sum_{i=1}^N exp(-y_if(x_i))
$$
设强分类器一共有 $M$ 个弱分类器组成，如果直接优化的话，我们需要同时优化 $2M$ 个参数，体量是大的。所以我们采取逐步学习的方法——一次只学习一组 $\alpha_m,G_m(x)$ ，然后加到强分类器中。在这种情况下我们的优化问题变为：
$$
\begin{aligned}
(\alpha_m,G_m(x))&=\arg\min_{\alpha,G_m}\sum_{i=1}^{N}exp[-y_i\left(f_{m-1}\left(x_i\right)+{\alpha_m}G_m(x_i)\right)]\\
&=\arg\min_{\alpha,G_m}\sum_{i=1}^N\bar{w}_{m,i}exp[-y_i{\alpha_m}G_m(x_i)]
\end{aligned}
$$

此时 $\bar w_{m,i}$ 对优化问题来说是一个定值，$\bar w_{m,i} = \prod_{m=1}exp(-\alpha_my_iG_m(x_i))=w_{m,i}N\prod_{m=1}Z_m=Aw_{m,i}$。值得注意的是 $\bar w_{m+1,i}=\bar w_{m,i}exp(-\alpha_my_iG_m(x_i))$ 这就是 $Adaboost$ 的权重更新关系。

$G_m(x)$ 的选择

我们希望误差最小，观察上面式子，此时 $\alpha_m$ 作为常量看待。因此最优化上式等价于：
$$
G_m^*(x)=\arg\min_G\sum_{i=1}^N\bar w_{m,i}I(y_i\neq G(x_i)) = \arg\min_G\sum_{i=1}^N w_{m,i}I(y_i\neq G(x_i))
$$
此分类器 $G_m^*(x)$ 即为 $AdaBoost$ 算法的基分类器 $G_m ( x )$ ，它是使得第m次迭代时加权训练数据分类误差最小的基分类器。

$\alpha_m$ 的求解

$$
\sum_{i=1}^N\bar w_{m,i}exp(-y_i \alpha_m G(x_i))=\sum_{y_i=G_m(x_i)}\bar w_{m,i}e^{-\alpha_m}+\sum_{y_i\neq G_m(x_i)}\bar w_{m,i}e^{\alpha_m}
$$

求极值我们需要令其对 $\alpha_m$ 求偏导等于0：
$$
e^{-\alpha_m}\sum_{y_i=G_m(x_i)}\bar w_{m,i}=e^{\alpha_m}\sum_{y_i\neq G_m(x_i)}\bar w_{m,i}
$$
等式两边取对数：
$$
\begin{aligned}
-\alpha_m + ln(\sum_{y_i=G_m(x_i)}\bar w_{m,i})&=\alpha_m+ ln(\sum_{y_i\neq G_m(x_i)}\bar w_{m,i}) \\
2\alpha_m&=ln(\frac{\sum_{y_i= G_m(x_i)}\bar w_{m,i}}{\sum_{y_i\neq G_m(x_i)}\bar w_{m,i}}) \\
2\alpha_m&=ln(\frac{\sum_{y_i= G_m(x_i)} w_{m,i}}{\sum_{y_i\neq G_m(x_i)} w_{m,i}}) \\
2\alpha_m&=ln(\frac{1-\sum_{y_i\neq G_m(x_i)} w_{m,i}}{\sum_{y_i\neq G_m(x_i)} w_{m,i}}) \\
\alpha_m&=\frac12 ln(\frac{1-e_m}{e_m}) \\
\end{aligned}
$$
综上我们就能够得到 $\alpha_m$ 的取值了。

因此我们知道了 $Adaboost$ 实际上就是以 $Loss = \sum_{i=1}^N exp(-y_if(x_i))$ 为目标函数的加法模型。