分类器融合（2）：AdaBoost

基于样本加权的误差度量

bootstrapping 重采样数据集$\mathcal D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),(\mathbf x_3,y_3),(\mathbf x_4,y_4)\}$，可能得到$\tilde{\mathcal D}_t=\{(\mathbf x_1,y_1),(\mathbf x_1,y_1),(\mathbf x_2,y_2),(\mathbf x_4,y_4)\}$，那么$\tilde{\mathcal D}_t$上的 in-sample 误差是$E_{in}^{0/1}(h)={1\over 4}\sum_{(\mathbf x,y)\in\tilde{\mathcal D}_t}[[y\neq h(\mathbf x)]]$，令$\mathbf u^{(t)}=[2,1,0,1]^T$，该误差也可以直接用$\mathcal D$上的加权误差$E_{in}$表示，$E_{in}^{\mathbf u^{(t)}}(h)={1\over 4}\sum_{n=1}^4u_n^{(t)}\cdot[[y_n\neq h(\mathbf x_n)]]$。这就是 bagging 通过最小化 bootstrap-weighted 误差得到不同$g_t$的方法。

通常需要最小化的加权误差为 \begin{equation} E_{in}^{\mathbf u}(h)={1\over N}\sum_{n=1}^Nu_n\cdot err(y_n, h(\mathbf x_n))， \label{eq:weighted-Ein} \end{equation} 把$\mathbf u$放回算法并不困难。对于 SVM，利用对偶 QP 最小化误差$E_{in}^{\mathbf u}\varpropto C\sum_{n=1}^Nu_n\widehat{err}_{SVM}$，可以通过调整原方法的上界为$0\leq \alpha_n\leq Cu_n$来实现；对于 logistic 回归，利用 SGD 最小化误差$E_{in}^{\mathbf u}\varpropto C\sum_{n=1}^Nu_n\widehat{err}_{CE}$，可以通过按不同倍率$u_n$的概率采样$(\mathbf x_n,y_n)$来实现。

这里是基于不同样本点加权的误差度量方式，与基于不同类别加权的误差度量方式的加权对象不同。如何将$\mathbf u$放回原算法是这类加权算法要处理的重要问题。

权重调整策略

如果算法会根据$\mathbf u$决定$g$，那么怎样改变$\mathbf u$使得$g$越不一样越好？越不一样的$g$，通过聚合（aggregation）机制，越有可能得到更好的结果。

通过$u_n^{(t)}$得到$g_t$，$u_n^{(t+1)}$得到$g_{t+1}$， \[ \left\{ \begin{aligned} g_t&\leftarrow\arg\min_{h\in\mathcal H}\left(\sum_{n=1}^Nu_n^{(t)}[[y_n\neq h(\mathbf x_n)]]\right)\\ g_{t+1}&\leftarrow\arg\min_{h\in\mathcal H}\left(\sum_{n=1}^Nu_n^{(t+1)}[[y_n\neq h(\mathbf x_n)]]\right)。 \end{aligned} \right. \] 如果先选定$g_t$（当作$h$），调整权重$u_n^{(t+1)}$使得$g_t$效果非常差，$g_t$以及与$g_t$相似的假设都不会被当作$g_{t+1}$，这样就能选择到一个与$g_t$很不一样的$g_{t+1}$。这就是获得不一样$g$的基本思想。理想的情况就是构造$\mathbf u_n^{(t+1)}$，使得$g_t$的表现就像随机猜想一样 \[ \frac{\sum_{n=1}^Nu_n^{(t+1)}[[y_n\neq g_t(\mathbf x_n)]]}{\sum_{n=1}^Nu_n^{(t+1)}}={1\over 2}， \] 也就是期望 \[ \frac{\sum_{n=1}^Nu_n^{(t+1)}[[y_n\neq g_t(\mathbf x_n)]]}{\sum_{n=1}^Nu_n^{(t+1)}}=\frac{\clubsuit_{t+1}}{\clubsuit_{t+1}+\spadesuit_{t+1}}={1\over 2}， \] 其中 \[ \clubsuit_{t+1}=\sum_{n=1}^Nu_n^{(t+1)}[[y_n\neq g_t(\mathbf x_n)]]\qquad\spadesuit_{t+1}=\sum_{n=1}^Nu_n^{(t+1)}[[y_n= g_t(\mathbf x_n)]]。 \]

假设犯错误的样本点有 $1126$ 个，正确的样本点有 $6211$ 个，对于错分的样本点就可以用 $u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot {6211\over 7337}$ 更新，对于正确分类的样本点就可以用 $u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot {1126\over 7337}$ 更新。更新权重$\mathbf u^{(t+1)}$时，设错误率为 \begin{equation} \epsilon_t=\frac{\sum_{n=1}^Nu_n^{(t)}[[y_n\neq g_t(\mathbf x_n)]]}{\sum_{n=1}^Nu_n^{(t)}}， \label{eq:epsilon-t} \end{equation} 错误的点原来的权重乘以系数$\varpropto(1-\epsilon_t)$，正确的点原来的权重乘以系数$\varpropto\epsilon_t$。

通常的做法是定义缩放因子 \begin{equation} \blacklozenge_t=\sqrt{1-\epsilon_t\over\epsilon_t}， \label{eq:blacklozenge-t} \end{equation} 其中$\epsilon_t$按\eqref{eq:epsilon-t}计算，权重更新方法为 \[ \mbox{incorrect}\leftarrow\mbox{incorrect}\cdot\blacklozenge_t\qquad\mbox{correct}\leftarrow\mbox{correct }/\blacklozenge_t。 \] 当$\epsilon\leq{1\over 2}$时，$\blacklozenge_t\geq 1$，放大错误的作用，缩小正确的影响，更关注错分的样本。

AdaBoost

AdaBoost¹ ＝ 弱的基础学习算法$\mathcal A$（学生）＋最优的权重调整因子$\blacklozenge_t$（老师）＋神奇的线性聚合$\alpha_t$（班级集体智慧）。

AdaBoost（adaptive boosting）算法²

---

首先，初始化$\mathbf u^{(1)}=\left[{1\over N},{1\over N},\ldots,{1\over N}\right]$；

其次，对于$t=1,2,\ldots,T$执行以下步骤：

1. $g_t\leftarrow\mathcal A(\mathcal D, \mathbf u^{(t)})$，通过算法$\mathcal A$在最小化$\mathbf u^{(t)}$加权0/1误差约束下得到$g_t$；
2. 将$\mathbf u^{(t)}$更新为$\mathbf u^{(t＋1)}$³： \begin{equation} u_n^{(t+1)}\leftarrow\left\{ \begin{aligned} u_n^{(t)}\cdot\blacklozenge_t&\quad\mbox{if }[[y_n\neq g_t(\mathbf x_n)]]\\ u_n^{(t)}/\blacklozenge_t&\quad\mbox{if }[[y_n= g_t(\mathbf x_n)]]， \end{aligned} \right. \label{eq:adaboost-update-u} \end{equation} 其中$\blacklozenge_t$按\eqref{eq:blacklozenge-t}计算；
3. 计算系数$\alpha_t=\ln(\blacklozenge_t)$；

最后，返回 \begin{equation} G(\mathbf x)=\mbox{sign}\left(\sum_{t=1}^T\alpha_tg_t(\mathbf x)\right)， \label{eq:adaboost-Gx} \end{equation} 也就是$T$个分类器和$T$个系数。

好的$g_t$应该有大的$\alpha_t$。对于$\epsilon_t={1\over 2}$，近似于随机猜想，$\alpha_t=0$；对于$\epsilon_t=0$，完全正确的分类器，$\alpha_t=\infty$。

AdaBoost 的 VC 界是 \[ E_{out}(G)\leq E_{in}(G)+O\left(\sqrt{O\left(d_{VC}(\mathcal H)\cdot T\log T\right)\cdot{\log N\over N}}\right)， \] 其中$d_{VC}(\mathcal H)$是为了$g_t$所要付出的代价。当$g_t$的性能优于随机猜想$\left(\epsilon_t\leq\epsilon<{1\over 2}\right)$时，经过$T=O(\log N)$轮迭代就可以达到$E_{in}(G)=0$。由于总共的$d_{VC}=O\left(d_{VC}(\mathcal H)\cdot T\log T\right)$随$T$增长缓慢，不等式右边第二项也可以做到很小。

AdaBoost 是一种提升算法（boosting）的实现，从 boosting 的角度，若$\mathcal A$略优于随机猜想$\left(\epsilon_t\leq\epsilon<{1\over 2}\right)$，AdaBoost＋$\mathcal A$可以达到很强大的性能（$E_{in}(G)=0$，$E_{out}$很小）。

AdaBoost-Stump

对于一个 decision stump 分类器 \begin{equation} h_{s,i,\theta}(\mathbf x)=s\cdot\mbox{sign}(\mathbf x_i-\theta)， \label{eq:decision-stump} \end{equation} $i$表示特征维，$\theta$表示阈值，$s$控制方向，在 2D 空间该分类器就是水平或竖直线，该算法优化的时间复杂度为$O(d\cdot N\log N)$。decision stump 能够高效的最小化$E_{in}^\mathbf u$，但是自身的性能却很弱。 将 decision stump 作为基础分类器，可以组合出功能强大的AdaBoost-Stump。

图：AdaBoost-Stump 示例

上图展示了基于 decision stump 构造的 AdaBoost-Stump，当$t=5$时就能完美的分类。AdaBoost-Stump 能够比核SVM更高效地得到非线性分类器。

世界上第一个实时人脸识别程序就是基于 AdaBoost-Stump。从$24\times 24$规格的 162336 张候选图片中通过 decision stump 挑选关键图片，在此基础上进行线性聚合（linear aggregation）⁴。为了提高速度，人脸识别采用的$G$会尽早排除非人脸。

在实际应用中，特征维数可能很高，AdaBoost-Stump 能够有效的进行特征选择和聚合。上例是2维的低纬度情况，进行了 5 次迭代，没有特征选择的功能。

参考资料

脚注