统计学习方法

Adaboost

简介

这不是一个具体的算法，而是一个进化方法。基于某一个已经有的算法，Adaboost能让它变强

弱分类器：就是一个分类算法，只不过它比较菜，菜到什么程度呢？菜到就比依概率随机分类要强那么一点，比如一个正确率55%的二分类算法

Adaboost的思想是什么呢？和听写一个道理，初始，字都不会写，第一次错了很多，订正的时候把写错的字罚抄10遍，第二次听写时，你着重关注了上次写错的字，把它们写对了，但由于轻视第一次对的字，又把它们写错了，然后再把罚抄10遍……一遍一遍罚抄下来，你就能全对了

思路：

给定训练集，假设已经找到了一个弱分类器，先拿它分分看，发现有一些点分错了，那么就加大这些错分数据点的权重，以示额外关注
调整分类器参数，使得赋权分类误差率最小，得到新的分类器
再拿新的分类器分分看，回到第一步

注意：下面的Adaboost均指二分问题，标签$y\in \set{1,-1}$（多分类问题的Adaboost也是有的，大作业AdaKNN中，就用了多分类的Adaboost）

从前向分步算法说起

前向分步算法

先明确最终要得到的模型长这样，称为加法模型：
$$
f(x)=\sum_{m=1}^M \beta_m b(x,\gamma_m)
$$

其中$b(x,\gamma_m)$为“基函数”，$\gamma_m$是它的参数，$\beta_m$是它的话语权。“基函数”其实指的就是一个分类器，所以上式的意思是：最终的分类器是很多小分类器群策群力的结果，每个小分类器都能投出$\beta_m$票，其和决定了最终分类结果

如何学习出这么一个分类器呢？前向分步算法这样说：

对一个训练集$\set{(x_1,y_1),\dots,(x_N,y_N)}$先规定一个损失函数$\sum\limits_{i=1}^N L(y_i,f(x_i))$，然后走一步看一步，每一步都最小化损失函数，求$\min\limits_{\beta,\gamma} \sum\limits_{i=1}^N L(y_i,f_{m-1}(x_i)+\beta b(x_i,\gamma))$，意思是前面$m-1$步的模型成果予以保留，在其基础上看看如何加上新的$\beta b(x,\gamma)$使损失最小

初始，已知一个$b(x,\gamma_0)$（比如它是个以$w_0,b_0$为参数的支持向量机）
第$m$步，求解$\beta_m,\gamma_m = \arg\min\limits_{\beta,\gamma} \sum\limits_{i=1}^N L(y_i,f_{m-1}(x_i)+\beta b(x_i,\gamma))$
更新模型$f_m(x)=f_{m-1}(x_i)+\beta_m b(x_i,\gamma_m)$

你可能觉得，这和Adaboost好像有点不像，之前说的什么“增大错分数据的权重”在哪里体现呢？别急，根据前向分步算法的要求慢慢推导，就能得出Adaboost，这个权重会自动浮现！

推导出Adaboost

使用前向分步算法训练加法模型，并把损失函数规定为：$L(y,f(x))=\exp(-y f(x))$，用的基函数记作$G(x)$，权重为$\alpha$

按前向分步算法要求，在第$m$步应该求：
$$
\begin{align*}
\alpha_m,G_m(x) &=\arg\min\limits_{\alpha,G} \sum\limits_{i=1}^N L(y_i,f_{m-1}(x_i)+\alpha G(x_i))
\newline
&=\arg\min\limits_{\alpha,G} \sum\limits_{i=1}^N \exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))]
\end{align*}
$$

由于此时，前面$m-1$步的模型成果予以保留，因此$\exp( -y_i f_{m-1}(x_i))$这一项与优化$\alpha$和$G$无关，只是常数，记它为$w_{mi}$

上式右边的求和部分写为“分类正确”和“分类错误”两部分加和，并且观察到，当分类正确时$G(x_i)=y_i$，因此同为$1$或$-1$，所以正确点处有$G(x_i)y_i=1$，上式右边即为：

$$
\sum_{y_i = G(x_i)} w_{mi} e^{-\alpha}+\sum_{y_i \neq G(x_i)} w_{mi} e^{\alpha}
$$

进行配凑并且化简：
$$
\begin{align*}
&\sum_{y_i = G(x_i)} w_{mi} e^{-\alpha}+\sum_{y_i \neq G(x_i)} w_{mi} e^{\alpha}-\sum_{y_i \neq G(x_i)} w_{mi} e^{-\alpha}+\sum_{y_i \neq G(x_i)} w_{mi} e^{-\alpha}
\newline
=&(e^{\alpha}-e^{-\alpha} )\sum_{i=1}^N w_{mi} I(y_i\notin G(x_i)) +e^{-\alpha}\sum_{i=1}^N w_{mi}
\end{align*}
$$

先一维搜索$G$，尾项与之无关，只关心：

$$
\begin{equation}
G_m(x) =\arg\min_G \sum_{i=1}^N w_{mi} I(y_i\notin G(x_i))
\end{equation}
$$

含义很明显了，就是要找的分类器$G_m$，在赋权$w_{mi}$意义下的错分最少。这里，$w_{mi}$可被诠释为权重，比如，$w_{mi}$全部等于一的话，上式就指的是错误率；又比如，若某一个$x_j$的权重$w_{mj}$特别大的话，要优先把它分对，才能让上式的右侧整体取到minimum。这就是赋权错分率

定下$G=G_m$后再搜寻$\alpha$：

$$
\arg\min_\alpha (e^{\alpha}-e^{-\alpha} )\sum_{i=1}^N w_{mi} I(y_i\notin G_m(x_i)) +e^{-\alpha}\sum_{i=1}^N w_{mi}
$$

右侧对$\alpha$求偏导并使之为零即可，解得：

$$
\begin{align}
&\alpha_m =\frac{1}{2} \log \frac{1-e_m}{e_m}
\newline
&\text{where } e_m=\frac{\sum_{i=1}^N w_{mi} I(y_i\notin G_m(x_i)) }{\sum_{i=1}^N w_{mi}}
\end{align}
$$

因此，$\alpha_m$与$G_m(x)$按照(1)和(2)的取法，是最优的，记住它们

再来关注一下$w_{mi}$的定义，是$\exp( -y_i f_{m-1}(x_i))$，会随着每一轮新分类器的加入而变化，递推关系为：
$$
\begin{align}
w_{m+1, i}&=\exp(-y_i f_{m}(x_i))=\exp[-y_i (f_{m-1}(x_i)+\alpha_m G_m(x_i))]
\newline
&=w_{mi}\exp(-y_i \alpha_m G_m(x_i))
\end{align}
$$

这就表示权重会更新。一开始我们只是把过往的信息绑定成一个常数，没想到后面这个常数竟然能诠释成分类点的权重，非常神奇啊

励志的Adaboost

为什么说Adaboost很励志呢？

一方面，前向分步训练模型的方法就像人的轨迹一样，没有回头路。曾经某步产生的子分类器将永远含在最终分类器里，无法抹去。不能因为现在觉得某个子分类器表现不佳就把它删除，要知道在当时的语境下，这个子分类器可是靠着最小化全局损失函数产生出来的，已经尽最大的努力了，所以不能责怪曾经的自己
另一方面，怎样能在当下做出最好的决策，让损失函数最小呢？靠的是吸收教训，每一次都把前一次犯错的地方放大来看，加深印象

综合上面的(1)-(5)式理一下Adaboost算法（和原始的(1)-(5)式相比，做了scaling）：

训练数据点为$\set{(x_1,y_1),\dots,(x_N,y_N)},y_i\in\set{1,-1}$

初始化训练数据权重$w_{1i}=\frac{1}{N}$
在第$m$步后，在权值分布为$w_{mi}$的情况下找到$G_m$使得赋权错分率$\sum_{i=1}^N w_{mi} I(y_i\notin G(x_i))$最小
此时这个最小的错分率$\sum_{i=1}^N w_{mi} I(y_i\notin G_m(x_i))$记为$e_m$，按照公式$\alpha_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$算出$\alpha_m$，是这个子分类器的话语权
更新权重分布：$w_{m+1, i}=\frac{w_{mi}}{Z_m}\exp(-y_i \alpha_m G_m(x_i))$，（这里的$Z_m$是归一化因子）返回第二步

结束后，把沿途产生的所有子分类器都按照各自的话语权线性加和，前向分步的结果就是：$f(x)=\sum\limits_{m=1}^M \alpha_m G_m(x)$，这里的$\alpha_m$并不是归一化的，因为没必要归一化，重要的是相对而非绝对大小，最终的分类器就是：
$$
G(x)=\text{sign}(\sum\limits_{m=1}^M \alpha_m G_m(x))
$$

训练误差界—蜗牛的成功

非常完美的一点是，理论可算Adaboost的误差上界：

$$
\frac{1}{N}\sum_{i=1}^N I(G(x_i)\neq y_i)\leq \prod_m Z_m \leq \exp\left( -2\sum_{m=1}^M \gamma_m^2 \right)
$$

这里的$Z_m$是当时的归一化系数，$\gamma_m$是第$\frac{1}{2}-e_m$，即第$m$个子分类器的表现比50%好多少

证明：待填

这个定理之所以非常好，是因为它证明了，只要存在$\epsilon >0$能保证每一次都能有$\gamma_m\geq \epsilon$，那么$\frac{1}{N}\sum\limits_{i=1}^N I(G(x_i)\neq y_i)\leq \exp\left( -2M\epsilon^2 \right)$

这随着训练次数$M \to \infty$，竟然是趋于0的！即：只要保证每次都能比50%好$\epsilon$，那随着训练次数增多，也能臻于完美，这真是励志的蜗牛啊