本文中“提升算法”一词皆使用英文原文boosting代替
Boosting算法的动机
假设幼儿园老师要教小孩子辨认是什么苹果，那么每次他会给出若干张“是苹果”的照片，另若干张”不是苹果“的照片，让学生给出如何分辨哪些是苹果。有的学生可能会说”圆形的是苹果“，那么老师会高亮犯错的照片，让别的学生继续提出分辨方法，再高亮新分辨方法犯错误的样本，以此类推
Boosting算法的思想和动机就类似上述过程：用一些很弱的模型\(g_t\)（称作基分类器）聚合起来，形成一个复杂的\(G\)。这个聚合的算法主要让基分类器专注在重要的（犯过错的）数据上
权重重设造成的多样性
首先回顾之前讲过的bootstrapping方法。假设原始数据集一共有4条数据，\(\mathcal{D} = \{({\bf x}_1, y_1), ({\bf x}_2, y_2), ({\bf x}_3, y_3), ({\bf x}_4, y_4)\}\)，在第\(t\)步使用bootstrapping方法得出来的数据集为\(\tilde{\mathcal{D}}_t = \{({\bf x}_1, y_1), ({\bf x}_1, y_1), ({\bf x}_2, y_2), ({\bf x}_4, y_4)\}\)，则在计算\(\tilde{\mathcal{D}}_t\)上的\(E_{\rm in}^{0/1}=\frac{1}{4}\sum_{({\bf x}, y) \in \tilde{\mathcal{D}}_t}[\![y \not= h({\bf x})]\!]\)时，\(({\bf x}_1, y_1)\)会被计算两次，\(({\bf x}_3, y_3)\)不会被计算。从另一个角度看待这个问题，可以说此时自助法实际对原始数据中每个数据点\(({\bf x}_n, y_n)\)隐含地给出了一个权重\(u_n^{(t)}\)。对于本例，有\(u_1= 2, u_2= 1, u_3=0, u_4=1\)。此时\(E_{\rm in}\)的计算方法等价于计算\(E_{\rm in}^{\bf u}(h) = \frac{1}{4}\sum_{n=1}^4 u_n^{(t)}\cdot [\![y_n \not= h({\bf x}_n)]\!]\)。也就是说，bagging算法也可以理解为每轮产生一个各个样本的权重分配，该轮的\(g_t\)通过最小化加权（该轮权重）的bootstrapping误差来产生不同的分类结果
推而广之，可以通过对各个基算法赋予权重，得到一个基算法的加权 \[ E_{\rm in}^{\bf u}(h) = \frac{1}{N}\sum_{n=1}^N u_n\cdot {\rm err}(y_n, h({\bf x}_n)) \] 当基算法是SVM时，由对偶二次规划问题可知\(E_{\rm in}^{\bf u} \propto C\sum_{n=1}^N u_n \widehat{\rm err}_{\rm SVM}\)，因此最后\(\alpha_n\)的上限被调整为\(Cu_n\)。当基算法是Logistic回归时，\(E_{\rm in}^{\bf u} \propto \sum_{n=1}^N u_n {\rm err}_{\rm CE}\)，而算法一般是使用随机梯度下降SGD，为了体现权重的影响，某个点权重越高，其在SGD时被抽中的机会就应该越大。权重高了几倍，SGD时该点被抽中的机会就应该高几倍。这种调整方法可以看作是本系列课程第八讲中”类别权重“的扩展
既然\(u\)的不同可以导致基算法回传的\(g\)不同，接下来的问题自然就是如何合理地设置\(u\)使得\(g\)越不一样越好。根据刚才的分析，有 \[ \begin{align*} g_t &\leftarrow \mathop{\rm arg\min}_{h\in \mathcal{H}}\left(\sum_{n=1}^N u_n^{(t)}[\![y_n \not= h({\bf x}_n)]\!]\right) \\ g_{t+1} &\leftarrow \mathop{\rm arg\min}_{h\in \mathcal{H}}\left(\sum_{n=1}^N u_n^{(t+1)}[\![y_n \not= h({\bf x}_n)]\!]\right) \end{align*} \] 如果\(g_t\)在使用\({\bf u}^{(t+1)}\)时非常不好，在\(g_{t+1}\)的最小化过程中，就不应该选到\(g_t\)，也不应该选到和\(g_t\)很像的假设函数，此时\(g_{t+1}\)和\(g_t\)就非常不像了。为了做到这一点，可以考虑构造一个最优的\({\bf u}^{(t+1)}\)，使得此时\(g_t\)的表现就像在随机瞎猜，即 \[ \frac{\sum_{n=1}^N u_n^{(t+1)}[\![y_n \not= g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t+1)}} = \frac{1}{2} \] 将分母展开，有 \[ \frac{\sum_{n=1}^N u_n^{(t+1)}[\![y_n \not= g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t+1)}[\![y_n \not= g_t({\bf x}_n)]\!] + \sum_{n=1}^N u_n^{(t+1)}[\![y_n = g_t({\bf x}_n)]\!]} = \frac{1}{2} \] 也就是说，让\(g_t\)犯过错误的样本的总权重，等于其正确分类的样本的总权重就可以了。假设前者的总权重是\(a\)，后者的总权重是\(b\)，那么让前者乘以\(b\)，后者乘以\(a\)就可以达到想要的效果。或者说，假设\(g_t\)在\(t\)时犯错的比例为\(\epsilon_t\)，则令每个犯错的点权重都\(\propto (1-\epsilon_t)\)，每个正确的点权重都\(\propto \epsilon_t\)即可得到一个最优的权重调整方法
自适应Boosting算法
根据上一节最后推出来的结论，可以定义一个缩放因子\(\blacklozenge_t\)： \[ \blacklozenge_t = \sqrt{\frac{1-\epsilon_t}{\epsilon_t}} \] 其中 \[ \epsilon_t = \frac{\sum_{n=1}^N u_n^{(t)}[\![y_n \not= g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t)}} \] 每个错分的数据点的权重乘以\(\blacklozenge_t\)，正确分类点的权重除以\(\blacklozenge_t\)即可。这种调整方法跟刚才提到的最优权重调整法是一样的，而且透露了更多的物理意义：当且仅当\(\epsilon_t \le \frac{1}{2}\)时，才有\(\blacklozenge_t \ge 1\)。这意味着错分样本会被放大，正确样本会被缩小。这也是自适应提升算法（Adaboost）得到各种不一样的\(g_t\)的方法
这样可以得到一个初始的算法的核心部分：每一轮\(t\)通过让算法\(\mathcal{A}\)最小化\({\bf u}^{(t)}\)加权的0-1误差，可以得到该轮情况下最优的\(g_t\)。然后，使用上述缩放动作，将\({\bf u}^{(t)}\)更新为\({\bf u}^{(t+1)}\)，为下一轮训练做准备。这里还有两个问题没有解决：
- 初始的\({\bf u}^{(1)}\)怎么获得
- 最后如何聚合这些\(g_t\)得到\(G({\bf x})\)
第一个问题比较直接，要是最开始的\(E_{\rm in}\)最差，只需要让每个样本的权重都一样就可以，即\(u_n^{(1)} = 1/N\)。第二个问题稍微要绕一下：直观的方法是跟每个\(g_t\)相同的票数，但是仔细想一想，\(g_1\)的\(E_{\rm in}\)可能会比较好，\(g_2\)的\(E_{\rm in}\)可能会比较差，让这两个效果不同的分类器票数相同，不太公平。因此最适合的方法是使用线性或者非线性的方法将这些\(g_t\)混合起来。
下面讲的方法就是一种在训练出\(g_t\)时就能顺便求出\(\alpha_t\)的算法。确定各个\(g_t\)时核心思想是对好的\(g_t\)权重\(\alpha_t\)更大，给坏的\(g_t\)权重\(\alpha_t\)更小。什么样的\(g_t\)是好的\(g_t\)呢？很自然，\(E_{\rm in}\)越小的\(g_t\)应该越好，因此\(\epsilon_t\)应该越小越好，即\(\blacklozenge_t\)应该越大越好。这也就意味着，\(\alpha_t\)应该是\(\blacklozenge_t\)的单调（增）函数。这里使用了\(\alpha_t = \ln(\blacklozenge_t)\)来确定，而且通过两个特例可以看出选择这个函数的合理性：
- 如果\(\epsilon_t = \frac{1}{2}\)，说明此时这个\(g_t\)其实就是在瞎猜。其对应的\(\blacklozenge_t = 1, \alpha_t = 0\)，因此这个分类器没有话语权
- 如果\(\epsilon=0\)，说明一个\(g_t\)就能搞定这个数据集，其对应的\(\blacklozenge_t = \infty, \alpha_t = \infty\)，它的意见压倒一切
因此，最后得到的这个算法，称为自适应boosting（AdaBoost）算法，其实包含了三个重要的组成成分
- 很弱的基分类算法\(\mathcal{A}\)
- 最优的重赋权因子\(\blacklozenge_t\)
- 神奇的线性组合系数\(\alpha_t\)
AdaBoost算法的流程可整理如下
初始化\({\bf u}^{(1)} = [\frac{1}{N}, \frac{1}{N}, \ldots, \frac{1}{N}]\)
对\(t = 1, 2, \ldots, T\)
通过\(\mathcal{A}(\mathcal{D}, {\bf u}^{(t)})\)得到\(g_t\)。其中\(\mathcal{A}\)是要减小\({\bf u}^{(t)}\)加权的0/1误差
使用如下方法将\({\bf u}^{(t)}\)更新为\({\bf u}^{(t+1)}\) \[ \begin{align*} [\![y_n \not= g_t({\bf x}_n)]\!]: u_n^{(t+1)} &\leftarrow u_n^{(t)} \cdot \blacklozenge_t \hspace{2ex}(\rm incorrect\ examples)\\ [\![y_n = g_t({\bf x}_n)]\!]: u_n^{(t+1)} &\leftarrow u_n^{(t)} /\ \blacklozenge_t \hspace{2ex}(\rm correct\ examples) \\ \blacklozenge_t &= \sqrt{\frac{1-\epsilon_t}{\epsilon_t}} \\ \epsilon_t &= \frac{\sum_{n=1}^N u_n^{(t)}[\![y_n \not= g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t)}} \end{align*} \]
计算\(\alpha_t = \ln(\blacklozenge_t)\)
返回\(G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T\alpha_tg_t({\bf x})\right)\)
AdaBoost比较引人关注的地方是，它存在一个理论保证，即对最后返回的聚合模型\(G\)，有 \[ E_{\rm out}(G) \le E_{\rm in}(G) + O\left(\sqrt{O(d_{\rm VC}(\mathcal{H})\cdot T\log T)\cdot \frac{\log N}{N}}\right) \] 原文证明，如果能保证总有\(\epsilon_t \le \epsilon < \frac{1}{2}\)，则经过\(T=O(\log N)\)就能有\(E_{\rm in}(G) = 0\)，也就是说上式中上界的第一项可以非常小。在上界的第二项中，\(O(d_{\rm VC}(\mathcal{H})\cdot T\log T)\)实际是所有可能\(G\)的VC维，随着\(T\)的增长其增长比较慢，因此第二项也会很小。这意味着，即便是对很弱的\(\mathcal{A}\)，只要其效果比瞎猜的好，哪怕只是好一点，在AdaBoost的作用下最后的\(G\)就可以特别强（\(E_{\rm in} = 0\)且\(E_{\rm out}\)很小）
自适应Boosting实战
（本节只是算法演示，唯一的一点就是重新提了作业2中的决策树桩decision stump。这个模型的核心思想就是在空间里做水平/竖直切面，而且其很容易优化：如果数据集的大小为\(N\)，维度为\(d\)，则优化这个模型的时间复杂度仅为\(O(d\cdot N\log N)\)。最后，AdaBoost还有特征选择的功能，例如人脸识别的那个例子）
