算法
也是一种集成方法，但是与bagging有所差别
- Bagging：不同分类器并行在bootstrap出来的样本集上跑，互相不依赖
- Boosting：后一个分类器依赖前一个分类器的结果以及加权误差。每个分类器也有自己的权重
AdaBoost算法（抽样版） 给定数据点\((x_1, y_1), \ldots, (x_n, y_n), x\in \mathcal{X}, y \in \{-1, +1\}\)，令\(w_1(i) = \frac{1}{n}\) 对\(t=1,\ldots,T\) 1. 根据分布\(w_t\)，取样得出大小为\(n\)的bootstrap数据集\(\mathcal{B}_t\)。注意选出\((x_i,y_i)\)的概率是\(w_t(i)\)，并不是\(\frac{1}{n}\) 2. 使用\(\mathcal{B}_t\)中的数据学习出分类器\(f_t\) 3. 使用以下公式求出该分类器的错误率\(\epsilon_t\)和权重\(\alpha_t\) \[ \epsilon_t = \sum_{i=1}^n w_t(i)1\{y_i \not= f_t(x_i)\} \\ \alpha_t = \frac{1}{2}\ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right) \] 4. 更新权重 \[ \hat{w}_{t+1}(i) = w_t(i)e^{-\alpha_t y_i f_t(x_i)} \\ w_{t+1}(i) =\ \frac{\hat{w}_{t+1}(i)}{\sum_j \hat{w}_{t+1}(j)} \]
分类规则设为 \[ f_{\rm boost}(x_0) = {\rm sign}\left(\sum_{t=1}^\mathsf{T} \alpha_tf_t(x_0)\right) \]
考虑权重更新公式，假设是二分类问题，\(y_i \in \mathcal{Y} = \{-1, +1\}\)，有 \[ w_{t+1}^{(i)} = w_t^{(i)}e^{-\alpha_i y_i f_i(x_i)} \]
- 由\(\alpha_i\)的定义以及所有基分类器都能比瞎猜效果好一点，因此所有\(\alpha_i\)都会大于0。假设\(f_i(x_i)\)被正确分类，那么指数最后会是一个负数，该值对应权重小于1，在下一轮被“降级”
- 反之，如果\(f_i(x_i)\)是错误分类，指数会是正数，该值对应权重大于1，在下一轮被“升级”
令\(\phi(x) = [f_1(x), \ldots, f_T(x)]^\top\)，其中\(f_t(x) \in \{-1, +1\}\)，则可以把\(\phi(x)\)看作是\(x\)到高维特征的一个映射，而向量\(\mathbf{\alpha} = [\alpha_1, \ldots, \alpha_T]^\top\)则对应于一个超平面，因此分类器可以写为 \[ f_{\rm boost}(x_0) = {\rm sign}(\phi(x_0)^\top \mathbf{\alpha}) \] 即boosting同时学习特征映射规则和超平面
分析
主要就是要证明一个定理： > 使用AdaBoost算法，如果\(\epsilon_t\)是分类器\(f_t\)的加权误差，则对分类器\(f_{\rm boost}(x_0) = {\rm sign}\left(\sum_{t=1}^\mathsf{T} \alpha_tf_t(x_0)\right)\)，其训练误差有上界： \[ \frac{1}{n} \sum_{i=1}^n 1\{y_i \not= f_{\rm boost}(x_i)\} \le \exp\left(-2\sum_{i=1}^\mathsf{T}(\frac{1}{2}-\epsilon_t)^2\right) \]
这意味着即便组成boosting的基分类器，即便其准确度仅略高于瞎猜，在有足够多样本的前提下，也可以把训练误差降到一个非常小的值
证明： 令\(Z_t = \sum_j \hat{w}_{t+1}(j)\)， 第一步，有 \[ \begin{align*} w_{T+1}(i) &= w_1(i) \times \frac{e^{-\alpha_1y_if_1(x_i)}}{Z_1} \times \ldots \times \frac{e^{-\alpha_Ty_if_T(x_i)}}{Z_T} \\ &= \frac{1}{n}\frac{e^{-y_i\sum_{t=1}^\mathsf{T} \alpha_tf_t(x_i)}}{\prod_{t=1}^\mathsf{T}Z_t} \\ &= \frac{1}{n}\frac{e^{-y_if_{\rm boost}^{(T)}(x_i)}}{\prod_{t=1}^\mathsf{T}Z_t} \end{align*} \] 第二步，首先从上一步有 \[ w_{T+1}(i)\prod_{t=1}^\mathsf{T}Z_t = \frac{1}{n}e^{-y_if_{\rm boost}^{(T)}(x_i)} \] 接下来，对于第\(i\)个样本，
- 如果分类正确，则\(y_if_{\rm boost}^{(T)}(x_i) > 0\)，因此\(0 < e^{-y_if_{\rm boost}^{(T)}(x_i)} < 1\)。而\(1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} = 0\)，因此\(1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} < e^{-y_if_{\rm boost}^{(T)}(x_i)}\)
- 如果分类错误，则\(y_if_{\rm boost}^{(T)}(x_i) < 0\)，因此\(e^{-y_if_{\rm boost}^{(T)}(x_i)} > 1\)。而\(1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} = 1\)，因此仍然有\(1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} < e^{-y_if_{\rm boost}^{(T)}(x_i)}\) 即总有 \[ 1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} < e^{-y_if_{\rm boost}^{(T)}(x_i)} = nw_{T+1}(i)\prod_{t=1}^\mathsf{T}Z_t \] 所以 \[ \begin{align*} \frac{1}{n}\sum_{i=1}^n 1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} &\le \frac{1}{n} \sum_{i=1}^n e^{-y_if_{\rm boost}^{(T)}(x_i)} \\ &= \sum_{i=1}^n w_{T+1}(i)\prod_{t=1}^\mathsf{T}Z_t \end{align*} \] 由于所有\(w_{T+1}(i)\)都是被归一化的，因此上式中求和项总和为1，可以忽略掉，所以最后有 \[ \frac{1}{n}\sum_{i=1}^n 1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} \le \prod_{i=1}^\mathsf{T} Z_t \]
第三步，根据定义 \[ \begin{align*} Z_t &= \sum_{i=1}^n w_t(i)e^{-\alpha_ty_if_t(x_i)} \\ &= \sum_{i : y_i = f_t(x_i)}e^{-\alpha_t}w_t(i) + \sum_{i : y_i \not= f_t(x_i)}e^{\alpha_t}w_t(i) \\ &= e^{-\alpha_t}(1-\epsilon_t) + e^{\alpha_t}\epsilon_t \end{align*} \] 其中最后一步是来自于\(\epsilon_t\)的定义
由第二步的结论和上面的推导，如果想让训练误差尽量小，可以让\(Z_t\)以\(\alpha_t\)为变量尽量小。求解得 \[ \alpha_t = \frac{1}{2}\ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right) \] 代回\(Z_t\)的表达式，可知 \[ \begin{align*} Z_t &= 2\sqrt{\epsilon_t(1-\epsilon_t)} \\ &= \sqrt{1-4(\frac{1}{2}-\epsilon_t)^2} \end{align*} \] 由不等式\(1-x\le e^{-x}\)，有 \[ \begin{align*} Z_t &= \left(1-4(\frac{1}{2}-\epsilon_t)^2\right)^{\frac{1}{2}} \\ &\le \left(e^{-4(\frac{1}{2}-\epsilon_t)^2}\right)^{\frac{1}{2}} \\ &= e^{-2(\frac{1}{2}-\epsilon_t)^2} \end{align*} \]
所以有 \[ \prod_{t=1}^\mathsf{T} Z_t \le \prod_{t=1}^\mathsf{T} e^{-2(\frac{1}{2}-\epsilon_t)^2} = e^{-2\sum_{t=1}^\mathsf{T} (\frac{1}{2}-\epsilon_t)^2} \]
综上所述 \[ \frac{1}{n}\sum_{i=1}^n 1\{y_i \not= f_{\rm boost}^{(T)}(x_i)\} \le \prod_{i=1}^\mathsf{T} Z_t \le e^{-2\sum_{t=1}^\mathsf{T} (\frac{1}{2}-\epsilon_t)^2} \] \(\blacksquare\)
注意，Boosting可以把训练误差降到0，但是却很少过拟合
