Boosting是一类提升算法的总称，包括AdaBoost，提升树，梯度提升等。不同Boosting算法的提升方式不太相同，但主要学习步骤是先从初始训练集中训练出一个基学习器，然后下一个基学习器更多地关注分类错误的样本点，迭代多次，直到误差达到要求以内，最后将每次训练的基学习器组合起来。
AdaBoost
AdaBoost是Freund和Schapire于1995年提出的。每次迭代更改的是样例的权值，不同资料中对于权值更改的方式略有不同，以PRML和The Elements of Statistical Learning为准，即每次只调整错误样例的权值。
AdaBoost算法
$J_m$是目标函数，表示最小加权误差，这里的误差是0-1误差。
$\epsilon_m$是加权的分类错误样本，与$J_m$的区别仅仅是分母归一化，因为在步骤2(c)中，$w_n^{(m+1)}$的更新，并没有归一化。
$\alpha_m$表示此次迭代的基分类器的权重，可以理解为对数几率，即ln{分类正确率/分类错误率}。
该基分类器的$\epsilon_m$误差越小，则$\alpha_m$权重越大，当错误率小于1/2时，$\alpha_m\gt0$；
该基分类器的$\epsilon_m$误差越大，则$\alpha_m$权重越小，当错误率大于1/2时，$\alpha_m\lt0$。
$w_n^{(m+1)}$表示更新样本点$\mathbf{x_n}$更新后的权值。
当基分类器的错误率$\epsilon_m\lt1/2$时，$\alpha_m\gt0$，则错误样本点的权值会变大；
当基分类器的错误率$\epsilon_m\gt1/2$时，$\alpha_m\lt0$，则错误样本点的权值会变小。可以理解为，该基分类器太关注错误的样例，导致大多数都没分对，所以要降低错误样例的权重，更关注大多数的样例
再次强调，只有在初始化时，所有样例的权重等于1/N，且和为1。以后迭代，每次只调整分类错误的样例的权值，分类正确的样例的权值不管，所以权值和基本都不为1。
当加权分类错误率$\epsilon_m\lt1/2$，即$\alpha\gt0$时，那些被分错的样例的权值会变大；
当加权分类错误率$\epsilon_m\gt1/2$，即$\alpha\lt0$时，那些被分错的样例的权值会变小。
AdaBoost的指数函数损失解释
AdaBoost算法可以用另一种方法解释。模型为基学习器的线性组合，损失函数为指数损失，学习算法为前向分步算法的二分类模型。
模型：
$$f_m(x)=\frac{1}{2}\sum_{l=1}^{m}\alpha_ly_l$$
损失函数：
$$E=\sum_{n=1}^{N}exp\{-t_nf_m(\mathbf{x_n})\}$$
将损失函数中的模型拆分为两部分：
$$\begin{align}
E&=\sum_{n=1}^{N}exp\left\{-t_nf_{m-1}(\mathbf{x_n})-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\} \\
&=\sum_{n=1}^{N}w_n^{(m)}exp\left\{-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\}
\end{align}$$
其中，$w_n^{(m)}=exp\left\{-t_nf_{m-1}(\mathbf{x_n})\right\}$
将迭代m次的数据集，分为分类正确的部分$T_m$和分类错误的部分$F_m$，继续拆分$E$
$$\begin{align}
E&=\sum_{n=1}^{N}exp\left\{-t_nf_{m-1}(\mathbf{x_n})-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\} \\
&=\sum_{n=1}^{N}w_n^{(m)}exp\left\{-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\} \\
&=e^{-\alpha_m/2}\sum_{n\in T_m}w_n^{(m)}+e^{\alpha_m/2}\sum_{n\in F_m}w_n^{(m)} \\
&=e^{-\alpha_m/2}\sum_{n\in T_m}w_n^{(m)}+e^{-\alpha_m/2}\sum_{n\in F_m}w_n^{(m)}+e^{\alpha_m/2}\sum_{n\in F_m}w_n^{(m)}-e^{-\alpha_m/2}\sum_{n\in F_m}w_n^{(m)} \\
&=e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)}+(e^{\alpha_m/2}-e^{-\alpha_m/2})\sum_{n\in F_m}w_n^{(m)} \\
&=e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)}+(e^{\alpha_m/2}-e^{-\alpha_m/2})\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n)
\end{align}$$
现在优化参数，一共有两个参数，一个是$y_m(\mathbf{x})$，一个是$\alpha_m$
上式中的第一项相对于$y_m(\mathbf{x})$为常数，所以可以去掉，第二项的系数并不影响$y_m(\mathbf{x})$的优化，因此关于$y_m(\mathbf{x})$的目标函数为：
$$E=\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n)$$
等同于AdaBoost算法中的目标函数(最小加权误差函数)，接下来优化$\alpha_m$，对$E$关于$\alpha_m$求偏导，
$$\begin{align}
\frac{\partial E}{\partial\alpha_m}&=-\frac12e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)}+\frac12(e^{\alpha_m/2}+e^{-\alpha_m/2})\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n) = 0\\
&=-e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)}+(e^{\alpha_m/2}+e^{-\alpha_m/2})\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n) = 0\\
&=-\sum_{n=1}^Nw_n^{(m)}+(e^{\alpha_m}+1)\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n) = 0\\
\end{align}$$
$$\begin{align}
(e^{\alpha_m}+1)\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n)&=\sum_{n=1}^Nw_n^{(m)}\\
(e^{\alpha_m}+1)&=\frac{\sum_{n=1}^Nw_n^{(m)}}{\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n)}\\
e^{\alpha_m}&=\frac{\sum_{n=1}^Nw_n^{(m)}}{\sum_{n=1}^Nw_n^{(m)}I(y_m(\mathbf{x_n})\neq t_n)}-1\\
e^{\alpha_m}&=\frac{1}{\epsilon_m}-1\\
e^{\alpha_m}&=\frac{1-\epsilon_m}{\epsilon_m}\\
\alpha_m&=ln\frac{1-\epsilon_m}{\epsilon_m}
\end{align}$$
可以看出$\alpha_m$也等同于AdaBoost算法的中此次迭代的基分类器的权重。接下来，更新$w_n^{(m+1)}$,
$w_n^{(m)}=exp\left\{-t_nf_{m-1}(\mathbf{x_n})\right\}$
$f_m(x)=\frac{1}{2}\sum_{l=1}^{m}\alpha_ly_l$
$$\begin{align}
w_n^{(m+1)}&=exp\left\{-t_nf_{m}(\mathbf{x_n})\right\} \\
&=exp\left\{-t_nf_{m-1}(\mathbf{x_n})-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\}\\
&=exp\left\{-t_nf_{m-1}(\mathbf{x_n})\right\} exp\left\{-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\}\\
&=w_n^{(m)} exp\left\{-\frac12t_n\alpha_my_m(\mathbf{x_n})\right\}
\end{align}$$
替换 $t_ny_m(\mathbf{x_n})=1-2I(y_m(\mathbf{x_n})\neq t_n)$
所以，$$w_n^{(m+1)}=w_n^{(m)} exp(-\alpha_m/2)exp\left\{\alpha_mI(y_m(\mathbf{x_n})\neq t_n)\right\}$$
对于任何$w_n^{(m+1)}$而言，$exp(-\alpha_m/2)$都对$w_n^{(m+1)}$进行了同样的更新，因此$exp(-\alpha_m/2)$并不影响$w_n^{(m+1)}$的更新，所以可以忽略，因此，得到$w_n^{(m+1)}$最终的更新公式为，
$$w_n^{(m+1)}=w_n^{(m)}exp\left\{\alpha_mI(y_m(\mathbf{x_n})\neq t_n)\right\}$$
等同于AdaBoost算法中的$w_n^{(m+1)}$更新公式。
最后，预测函数为$f_m(x)=\frac{1}{2}\sum_{l=1}^{m}\alpha_ly_l$，因为系数1/2并不影响二分类预测符号的改变，因此去掉后等同于AdaBoost的预测函数。
提升树(Boosting Trees)
Boosting Trees是将Boosting中的基函数换成分类树或回归树，最常用的是GBDT(Gradient Boosting Decision Tree)，需要注意的是，GBDT中的Tree是回归树，不是分类树，因为要求每次迭代要求负梯度。
另外，Boosting Trees相对于AdaBoost也有明显的区别。AdaBoost每次迭代，样例的权值在不断变化，更具体说是错误样例的权值在变化，但GBDT中每次迭代的样本都是不变的，变的是每个样例的回归目标值。
提升分类树
将Adaboost中的基函数换成决策树(ID3,C4.5,CART)，就可以得到最基本的Boosting Decision Tree。
提升回归树
每次迭代，需要拟合一棵回归树，目标值为上次累计预测的残差，最后将所有的树的预测结果加起来。
- 损失函数一般为均方误差
- 最后预测是求和，不是加权求和
算法
- 初始化 $f_0(x)=argmin_\gamma\sum_{i=1}^NL(y_i,\gamma)$
- 对于 m = 1 to M:
(a) 对i=1,2,…,N 计算所有样本点的残差 $$r_i=y_i-f_{m-1}(x_i)$$
(b) 以$r_i$为目标值，拟合一棵回归树，得到叶节点区域$R_{mj}$和每个叶节点的值 $\gamma_{mj}, j=1,2,…,J_m$
(c) 更新$f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J_m}\gamma_{mj}I(x\in R_{jm})$ - 得到最终的提升回归树$\hat f(x)=f_M(x)$
步骤2(b)中，回归树的损失函数为均方误差，梯度恰好为残差的形式，多了一个系数1/2
步骤2(c)中，$x$只能属于一个$R_{mj}$，因此只有一个有效，其他的为0
可以理解为，对于一个值的预测，是每棵树的不同叶节点值的累加
Gradient Boosting Regression Tree
当损失函数不是指数损失和均方误差损失时，常用负梯度来代替残差。GBRT每次迭代的树在生成时，分为两部分，
- 根据回归树生成叶节点
- 并重新评价叶节点的值，使损失函数最小
算法
- 初始化 $f_0(x)=argmin_\gamma\sum_{i=1}^{N}L(y_i,\gamma)$
- 对于m = 1 to M:
(a) 对于i=1,2,…,N 计算每个样本点的近似残差$$r_{mi}=-[\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}]$$
(b) 以上一步计算的$r_{mi}$作为目标值，拟合一棵回归树，得到叶节点区域$R_{mj}, j=1,2,…,J_m$
(c) 对于$j=1,2,…,J_m$ 计算每个叶节点的值$$\gamma_{mj}=argmin_\gamma\sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i)+\gamma)$$
(d) 更新$f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J_m}\gamma_{mj}I(x\in R_{mj})$ - 得到最终的提升回归树$\hat f(x)=f_M(x)$
步骤2(b)中，回归树的损失函数为均方误差，梯度恰好为残差的形式，多了一个系数1/2
不同于Boosting Regression Tree的地方有两个
1.用负梯度近似真正的残差
2.先用回归树拟合出叶节点区域，再重新调整出叶节点的值
Reference
- PRML
- The Elements of Statistical Learning
- https://en.wikipedia.org/wiki/Gradient_boosting
- http://blog.csdn.net/kunlong0909/article/details/17587101
