此文是本人学习林轩田老师教授的机器学习技法第八课——Adaptive Boosting——的笔记。
不同于 Blending and Bagging，Boosting 提供一种增强式集成学习方法，它在顺序训练各模型时，要求后面的模型着重训练前面的模型失误的数据，使得总的模型误差不断减小。Adaptive Boosting，简称 AdaBoost， 是 Boosting 中的一种。
参考
AdaBoost 的形象类比与流程概要
课上举的例子实在太形象了，一定得记下啊。Boosting 好比老师教一群小学生（多个模型）学习如何辨识苹果（集成学习）。这里有一堆图片（数据），其中有的是苹果的，还有不是苹果的。老师让学生 A 讲一条辨识苹果的规则（训练一个模型），然后特别指出他/她出错的图片（强调标识失败数据），让下一个同学提出新的规则（训练下一个模型），如此往复，最终可以得到一系列规则，虽然每条规则的辨识能力可能都很弱，但组合起来可能就是很强了（一系列弱模型集成为强模型）。
那么，AdaBoost 的流程就比较清楚了。模型 $g$ 辨识失败的数据， $g(\mathbf{x_n}) \ne y_n$ ，称为问题数据, 辨识正确的数据，称简单数据。以下是大致流程：
- 依次训练各模型
- 在一个模型训练完成后，向下一个模型强调问题数据
- 为每个模型分配权重，集成各模型
“强调”问题数据
明显流程第二点是关键。如何才能做到对模型”强调”问题数据呢？这里的“强调”，可以翻译为增加模型在问题数据上犯错的代价。在机器学习基石，老师提到过一些方法。比如，在训练前，复制问题数据 $n$ 份，如果模型在其中一个数据上犯错，就相当于犯了 $n$ 次错，达到“强调”的目的。这里使用的方法是，如果抽取到问题数据做训练，就对 error function 乘上一个系数 $u$ （大于一）。这样，如果模型在问题数据上犯错，error 会扩大 $u-1$ 倍。以下把这种处理方法称为“为数据分配权重”。
实际上，AdaBoost 不仅为问题数据分配权重，也为简单数据分配权重。不过没差，只要能达到“强调”问题数据的效果就行。这里引入 $m$:
$$m = \sqrt{\frac{1-e}{e}}$$
其中 $e$ 表示模型的失误率。AdaBoost 对问题数据乘以 $m$ ，对简单数据除以 $m$ 。其中有两点值得注意。
第一，如果 $e \lt 0.5$， 则 $m \gt 1$，问题数据确实会被“强调”；而当 $e \gt 0.5$ 时， $m \lt 1$ ，问题数据似乎不被“强调”，反而简单数据被“强调”了。其实不差，当 $e \gt 0.5$ 时，意味着模型辨识能力比瞎猜（ $e=0.5$ ）都不如，在最后模型结合时给它分配负权重，把它的辨识结果反过来，这时就应该向后面的模型“强调”简单数据。
第二，注意 $m(e)\;with\;e \gt 0$ 是一个单调下降的函数。这意味着， $e$ 越小，辨识越准确，模型出错也越少， $m$ 也会越大，AdaBoost “强调问题数据”越是“厉害”。为什么在模型出错更少时“更强调”问题数据呢？这是为了平衡简单数据与问题数据的影响，进而训练出更不同（diverse）的模型（对集成学习来说，模型 diversity 越高，效果越好）。（?-?对这话的因果关系存疑）实际上， $m$ 是推导的结果（参见 AdaBoost），在推导过程中似乎并未对此解释或假设，但以上论点也是比较合理的假说。
模型权重公式
$$ \alpha = \ln m = \ln \sqrt{\frac{1-e}{e}}$$
当 $e \gt 0.5$ 时， $\alpha \lt 0$。 所以在预测能力小于0.5时，模型被分配负权重，反之，权重为正。
AdaBoost 流程
- $\mathbf{u}=[\frac{1}{N},\frac{1}{N},\frac{1}{N},…]$，长度为 $N$ ，记录每个数据的权重
for t=1,2,…,T
- 根据训练数据与 $\mathbf{u}$ 训练出模型 $g_t$
- 计算
$$m = \sqrt{\frac{1-e}{e}}\quad with\; e=\frac{\sum u_n[y_n \ne g_t(\mathbf{x_n})]}{\sum u_n}$$
更新 $\mathbf{u}$
$$u_n = \left{ \begin{array}{l}
u_n \cdot m,\quad y_n \ne g_t(\mathbf{x_n})\
u_n / m,\quad y_n = g_t(\mathbf{x_n})
\end{array} \right.$$计算 $\alpha_t = \ln (m)$
- 返回模型 $G(\mathbf{x})=sign (\sum \alpha_t g_t(\mathbf{x}))$
AdaBoost 的理论保证
VC Bound：
$$E{out}(G)\le E{in}(G) + O\left( \sqrt{O(d_{vc}(H) \cdot T\log T) \cdot \frac {\log N}{N}} \right)$$
$T$ 表示迭代的次数，实践证明，当迭代达到 $T=\log N$ 时， $E{in}$ 会比较小，而此时的 VC Bound 也不太大，所以 $E{out}$ 可以做得比较小。
基础模型选择——决策树桩
流行选择 决策树桩（decision stump） 作为基础模型（base algorithm）。决策树桩是深度为一的决策树，典型的弱分类器，常被用作集成学习中的基础模型。它的分类器为：
$$h_{s,i,\theta}(\mathbf{x}) = s \cdot sign(x_i - \theta)$$