本文将记录《统计学习方法》中有关提升学习Adaboost的内容。
Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

提升算法需要解决的问题：
1）如何计算弱分类器学习误差率e?
2) 如何得到弱学习器权重系数α?
3）如何更新样本权重D?
4) 使用何种结合策略结合得到强学习算法？

Adaboost分类算法

输入：数据集 T = { ( x 1 , y 1 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),...,(x_N,y_N)\} T={(x1​,y1​),...,(xN​,yN​)}
输出：最终的强分类器

1. 初始化了全部样本的权重：
   W 0 = { w 1 0 , . . . w N 0 } ,    w i 0 = 1 N W^0=\{w_1^0,...w_N^0\},\;w_i^0=\frac{1}{N} W0={w10​,...wN0​},wi0​=N1​
2. 对于m=1,2…,M次迭代的弱分类器：
   1. 对上次的样本权重构建弱分类器:$G_m$
   2. 计算在弱分类器上的分类误差：
      $$E_m=\sum _i^N{w}_i^{m}I(G_m(x_i̸=y_i))$$
   3. 计算该弱分类器的结合权重：
      $${\alpha }_m=\frac{1}{2}log\frac{E_m}{1-E_m}$$
   4. 调整样本权重：
      W m + 1 = { w i m + 1 , . . . , w N m + 1 } w i m + 1 = w i m Z e − α i y i G m ( x i ) Z = ∑ i N w i m + 1 W^{m+1} = \{w^{m+1}_i,...,w^{m+1}_N\}\\ w^{m+1}_i= {w^m_i\over Z }e^{-\alpha_iy_iG_m(x_i)}\\ Z=\sum_i^N w^{m+1}_i Wm+1={wim+1​,...,wNm+1​}wim+1​=Zwim​​e−αi​yi​Gm​(xi​)Z=i∑N​wim+1​

3.构建强分类器的集合策略采用的加权：
$$\begin{gathered} f(x)=\sum _m^M{\alpha }_m{G}_m \\ G(x)=sign(f(x))=sign(\sum _m^M{\alpha }_m{G}_m) \end{gathered}$$

Adaboost回归算法

输入： T = { ( x 1 , y 1 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),...,(x_N,y_N)\} T={(x1​,y1​),...,(xN​,yN​)}
输出：最终的强回归算法

1. 初始化了全部样本的权重：
   W 0 = { w 1 0 , . . . w N 0 } ,    w i 0 = 1 N W^0=\{w_1^0,...w_N^0\},\;w_i^0=\frac{1}{N} W0={w10​,...wN0​},wi0​=N1​

2. 对于m=1,2…M的弱回归算法：

   1. 构建弱回归算法$G_m$

   2. 计算在该弱学习算法上的最大误差，得到每个样本的相对误差：
      $$\begin{gathered} E_m=\max |y_i-G_m(x_i)| \\ {e}_i^m=\frac{|y_i-G_m(x_i)|}{E_m} \end{gathered}$$

      如果采用平方误差,$e_i^m=\frac{(y_i-G_m(x_i){)}^2}{E_m^2}$;
      如果采用指数误差$e_i^m=1-exp(\frac{-y_i+G_m(x_i)}{E_m})$

      得到该弱回归算法的误差率：
      $$e^m=\sum _i^N{w}_i^m{e}_i^m$$

   3. 计算该弱回归算法的结合权重：
      $${\alpha }_m=\frac{e^m}{1-e^m}$$

   4. 更新样本权重：
      W m + 1 = { w i m + 1 , . . . , w N m + 1 } w i m + 1 = w i m Z α m 1 − e i m Z = ∑ i N w i m + 1 W^{m+1} = \{w^{m+1}_i,...,w^{m+1}_N\}\\ w^{m+1}_i= {w^m_i\over Z }\alpha^{1-e^m_i}_m\\ Z=\sum_i^N w^{m+1}_i Wm+1={wim+1​,...,wNm+1​}wim+1​=Zwim​​αm1−eim​​Z=i∑N​wim+1​

3. 弱回归算法结合策略：
   $$f(x)=\sum _k(ln\frac{1}{a_k})g(x)$$

前向分步算法

前向分布算法是一个加法算法，将前面的弱学习算法通过对之前的算法一步一步的求和，强算法由弱算法加权得到，利用前一个弱学习来更新后一个弱学习的权重。
那么对于第K-1轮强学习算法：
$$f_{k-1}=\sum _i^{k-1}{\alpha }_i{G}_i(x)$$
对于第K轮强学习算法
$$f_k=\sum _i^k{\alpha }_i{G}_i(x)$$
对比可知：
$$f_{k-1}=f_{k-1}(x)+\sum _i^{k-1}{\alpha }_i{G}_i(x)$$
定义损失函数：
$$\sum L(y_i,f_{k-1}(x)+\alpha G(x;\gamma )$$
最小化损失函数:
$$({\alpha }^{\ast },{\gamma }^{\ast })=\arg \min \sum L(y_i,f_{m-1}(x)+\alpha G(x,\gamma ))$$
更新强学习算法：
$$f_m(x)=f_{m-1}(x)+{\alpha }_m^{\ast }G(x,{\gamma }^{\ast })$$