AdaBoost 的思想是基于弱分类器得到强分类器的一种boosting算法。主要的思想是每次迭代训练一棵决策树，每棵决策树都有一个权重，该权重和当前决策树的误分类率有关。基于当前决策树的权重，每个样本也会计算一个权重。基本思想是提高被误分类的样本的权重，降低分类正确的样本权重。这样，每次迭代时会更关注错误分类的样本。最终，所有决策树的加权和就是最终的分类模型。
Adaboost算法如下：
其中， \(G(x)\)是输出值为{+1,-1}的二分类决策树。 AdaBoost 也是前向分布加法模型框架下的模型。
下面证明AdaBoost 等价于使用指数损失函数的前向分步加法模型。
\[L(y,f(x))=exp(-yf(x))\]AdaBoost的基分类器是\(G_m(x)\in {-1,1}\)，
采用指数损失函数，每次需要求解如下优化问题，从而得到分类器\(G_m\)和对应的权重\(\beta_m\)
\[(\beta_m,G_m)=\mathrm{arg};\underset{\beta,G}{\mathrm {min}}\sum\limits_{i=1}^N\exp[-y_i(f_{m-1}(x_i)+\beta G(x_i))]\]上式可以写成
\[(\beta_m,G_m)=\mathrm{arg}\ \underset{\beta, G}{\mathrm{min}}\sum\limits_{i=1}^N\omega_i^{(m)}\exp(-\beta y_iG(x_i))\tag{10.9}\label{10.9}\]其中,
\[w^{(m)}_i=\exp(-y_if_{m-1}(x))\]这是一个常数。
10.9可以通过两步来求解，先求\(G_m(x)\)，再求解\(\beta_m\)
\(G_m(x)\)的解为
\[G_m=\mathrm{arg};\underset{G}{\mathrm{min}}\sum\limits_{i=1}^N\omega_i^{(m)}I(y_i\neq G(x_i))\tag{10.10}\label{10.10}\]这是加权误分类率最低的分类器。
这个可以推导如下:
将10.9展开:
\[e^{-\beta}\sum\limits_{y_i=G(x_i)}\omega_i^{(m)}+e^\beta\sum\limits_{y_i\neq G(x_i)}\omega_i^{(m)}\] \[(e^{\beta}-e^{-\beta})\sum\limits_{i=1}^N\omega_i^{(m)}I(y_i\neq G(x_i)) + e^{-\beta}\sum\limits_{i=1}^N\omega_i^{(m)}\tag{10.11}\label{10.11}\]在该式中，和\(G_m(x)\)相关的就只有
\[\sum\limits_{i=1}^N\omega_i^{(m)}I(y_i\neq G(x_i))\]所以，从该式可以看出来，10.10是10.9的解。
然后是第二步，求解\(\beta_m\)
将\(G_m(x)\)的解10.10代入到10.9，也就是10.11
\[(e^{\beta}-e^{-\beta} ) G_m(x) +e^{-\beta}\sum\limits_{i=1}^N\omega_i^{(m)}\]对\(\beta\) 求导并令导数为0
\[(e^{\beta}+e^{-\beta} ) G_m(x) -e^{-\beta}\sum\limits_{i=1}^N\omega_i^{(m)} = 0\] \[e^{\beta} G_m(x)= e^{-\beta}(\sum\limits_{i=1}^N\omega_i^{(m)} -G_m(x))\] \[2\beta = log\frac{\sum\limits_{i=1}^N\omega_i^{(m)} -G_m(x)}{G_m(x)}\] \[\beta = \frac{1}{2}log\frac{\sum\limits_{i=1}^N\omega_i^{(m)} -G_m(x)}{G_m(x)}\]右侧分子分母同时除以 \(\sum\limits_{i=1}^N\omega_i^{(m)}\)
同时，定义:
\[err_m=\frac{\sum_{i=1}^N \omega_i^{(m)}I(y_i\neq G_m(x_i))}{\sum_{i=1}^N\omega_i^{(m)}}\tag{10.13}\]得到:
\[\beta_m=\frac{1}{2}\log\frac{1-err_m}{err_m}\qquad \tag{10.12}\]下面看下样本的权重是怎么更新的
根据更新公式:
\[f_m(x)=f_{m-1}(x)+\beta_mG_m(x)\]\(w_m\)的更新如下：
\[w^{(m+1)}_i=\exp(-y_i f_{m}(x))\] \[w^{(m+1)}_i=\exp(-y_i (f_{m-1}(x)+\beta_mG_m(x)) )\] \[w^{(m+1)}_i=\exp(-y_i f_{m-1}(x)) exp(-y_i \beta_m G_m(x))\] \[\omega_i^{(m+1)}=\omega_i^{(m)}\cdot e^{-\beta_my_iG_m(x_i)}\tag{10.14}\label{10.14}\]根据
\[-y_iG_m(x_i)=2\cdot I(y_i\neq G_m(x_i))-1\]得到
\[\omega_i^{(m+1)}=\omega_i^{(m)}\cdot e^{\alpha_mI(y_i\neq G_m(x_i))}\cdot e^{-\beta_m}\tag{10.15}\label{10.15}\]其中: \(\alpha_m=2\beta_m\) 这就是开头Adaboost算法中的第2(c)步， 其中,10.15和第2(d)步就相差了一个\(e^{-\beta_m}\),因为对所以样本该值都相同，所以可以去掉。这样就等价于第2(d)步了。