Adaboost

$\sum_{i=6}^{11} C_i^11(0.25)^i(0.75)^{11-i}$

Adaboost

$C_N^M = \frac{N!}{M!(N-M)!}$

神经网络也在做降维度这件事，自适应提升算法。对于大规模冗余特征是一个比较好的算法。假设数据集，假设为 2 分类问题

数据集 $D =\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(N)},y^{(N)}) \}$
输出 $y^1 = \{-1,+1\}$

接下来介绍基本算法流程

输入数据: $D =\{x^{(i)},y^{(i)}\}_{i = 1 - N}$
输出分类器: $G(X) = \{1,-1\}$

先找一个分类器，只用一个特征来进行分类，要不没有训练，从采样，更多采样那些分错的样本，而且减少对那些分对样本。这样有了两个识别器，对于训练数据集进行有区别采样，两个识别器都对其分错样本给更大权重，在这个训练集上表现更好，把这些弱识别器取加权平均值。
<img src="../basic_machine_learning/images/adaboosting.jpeg">
<img src="./images/adaboosting__002.jpeg">

adaboosting__002.jpeg

推导过程

初始化采样权重 $D_1 = (\omega_{11},\omega_{12},\cdots,\omega_{1N}) \, \omega_{iN} = \frac{1}{N} i \in \{1,N\}$
对 $m = 1,2,\cdots,M$ (M 是弱分类器个数) 用 $D_{M}$ 采样 N 个训练样本，在训练样本上获取弱分类器 $G_m(X) = \pm 1$ 可以选择一个特征或者几个特征来构成分类器，作者是有放回的采样
计算加权错误率
$e_m = P(G_m(x^i) \neq y^i) = \sum_{i=1}^N \omega_{mi} I(G_m(x^i) \neq y^{i})$
$\alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m}$ 识别器 $G_m(X_i)$ 的权重
<img src="./images/log_plot.jpeg">
$e_m$ 越小越大
更新权值分布
$D_{m+1} = (\omega_{m+1,1},\omega_{m+1,2},\cdots,\omega_{m+1,N})$

$\begin{cases} \omega_{m+1,i} = \frac{\omega_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(X_i))\\ Z_m = \sum_{i=1}^N \omega_{mi} \exp(-\alpha_m y_i G_m(X_i)) \end{cases}$

$e_m$ 小于 0.5 $a_m$ > 0
<img src="./images/exp_plot.png">
$Z_m = \sum_{i=1}^N \omega_{mi} \exp(-\alpha_m y_i G_m(X_i))$ 起归一化作用。
回倒第 2 步骤
最终识别器 $G(X)$
- $f(x) = \sum_{m=1}^M \alpha_m G_m(X)$
- $G(X) = sign(f(x)) = sign\left[\sum_{i}^M \alpha_m G(X)\right]$

定理

随着 M 增加，AdaBoost 最终分类器 $G(X)$ 在训练样本上将会越来越小。证明这个定理才能够清楚为什么会在训练集。AdaBoost 不会测试集上发生过拟合的训练器，不是那么容易过拟合，每一个分类器的效果都是若分类器，不能做那么好，对于数据集也不会做的那么差，这些分类器组合，每一个分类器，整个系统会特别稳定，接下来尝试证明一下这个定理。

错误率 $E = \frac{1}{N} \sum_{i=1}^N I(G(X_i)\neq y_i) \le \frac{1}{N} \sum_{i=1}^N \exp(-y_i f(X_i))$ ,
若接下来假设 $G(X_i) = y_i$
$E = \prod_{m=1}^M Z_m$

$E \le \frac{1}{N} \exp \left[ - \sum_{m=1}^M \alpha_m y_i G_m(X_i) \right]$

$E = \sum_{i=1}^N \omega_{1i} \prod_{m=1}^M \exp \left[ - \alpha_m y_i G_m(X_i)\right]$

$E= \sum_{i=1}^M \left[ \omega_{1i} \exp (- \alpha_i y_i G_1(X_i) ) \right] \left[ \prod_{m=2}^M \exp (-\alpha_m y_i G_m(X_i)) \right]$

$= \sum_{i=1}^M \left[ W_{2i} Z_1 \right] \left[ \prod_{m=2}^M \exp (-\alpha_m y_i G_m(X_i)) \right]$

$\omega_{m+1,i} = \frac{\omega_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(X_i))$

$Z_1 \omega_{2,i} = \omega_{1i} \exp(-\alpha_1 y_i G_1(X^i))$

$= Z_1 \sum_{i=1}^M \left[ \omega_{2i} \right] \left[ \prod_{m=2}^M \exp (-\alpha_m y_i G_m(X_i)) \right]$

接下来证明 $Z_m = 2\sqrt{e_m(1 - e_m)}$

$Z_m =\sum_{i=1}^N \omega_{mi} \exp(-\alpha_m y_i G_m(X_i))$

$Z_m = \sum_{i=1}^N \omega_{mi} e^{-\alpha_m} + \sum_{i=1}^N \omega_{mi} e^{\alpha_m} = (1-e_m) e^{-\alpha_m} + e_m e^{\alpha_m}$

$\begin{cases} y^i = G_m(x^i) \\ y^i \neq G_m(x^i) \end{cases}$

$\alpha_m = \frac{1}{2} \log \frac{1 - e_m}{e_m}$

$Z_m \le 2\sqrt{e_m (1-e_m)}$

$e_m < \frac{1}{2} \, Z_m < 1$