adaboost提升算法

引言

俗话说得好，三个臭皮匠赛过诸葛亮。更主要的是三个臭皮匠好找，一个诸葛亮太难找了。在机器学习里面也是一样的。我们可以设计出各种分类器，然而分类器的效果确实不一而同的，相对而言，效果较差的分类器比效果很好的分类器更好设计，后者很多时候可遇而不可求。那么是否有什么方法能够将一系列的弱分类器组合，使其能够提示分类效果呢？这就是机器学习里面的提升学习。而且后来Schapire证明强可学习与弱可学习是等价的，这个就很完美了，这样我们就有了理论指导，通过一系列的弱学习算法可以提升为强学习算法，adaboost就是最重要的一个例子。

提升算法的思想

提升算法通过提高前面分类错误的样本的权重，是后面的分类器更加关注这些错误样本的分类，进而能够分而治之，使分类器重点关注不同的样本。

adaboost算法

下面我们先来介绍adaboost算法，后面再对算法做推导解释。（猜想adaboost算法应该是先提出的算法，后续才找个合理的解释。）

输入

• 训练数据集 D={(x1,y1),...,(xN,yN)} D = { ( x 1 , y 1 ) , . . . , ( x N , y N ) } $D = \left \{ (x_1,y_1),...,(x_N,y_N) \right \}$
• 弱学习算法

算法过程

• 
  
• 初始化训练数据的权值分布为 W1=(w11,...,w1N) W 1 = ( w 11 , . . . , w 1 N ) $W_1 = (w_{11},...,w_{1N})$其中 W1i=1N W 1 i = 1 N $W_{1i} = \frac{1}{N}$
• 进行迭代训练，即对 m=1,2,...,M m = 1 , 2 , . . . , M $m = 1,2,...,M$
  

• 使用权重为 Wm W m $W_m$的训练数据训练学习器 Gm(x) G m ( x ) $G_m(x)$
  
• 计算 Gm(x) G m ( x ) $G_m(x)$上的训练误差率 em=P(Gm(xi)≠yi)=∑Ni=1wmiI(Gm(xi)≠yi) e m = P ( G m ( x i ) ≠ y i ) = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) $e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i)$
  
• 计算 Gm(x) G m ( x ) $G_m(x)$的系数 αm=12log1−emem α m = 1 2 l o g 1 − e m e m $\alpha_m = \frac{1}{2} log \frac{1-e_m}{e_m}$
  
• 更新训练集的权重 Wm+1=(wm+1,1,...,wm+1,N) W m + 1 = ( w m + 1 , 1 , . . . , w m + 1 , N ) $W_{m+1} = (w_{m+1,1},...,w_{m+1,N})$ 其中 wm+1,1=xmiZmexp(−αmyiGm(xi)) w m + 1 , 1 = x m i Z m e x p ( − α m y i G m ( x i ) ) $w_{m+1,1} = \frac{x_{mi}}{Z_m} exp(- \alpha_my_iG_m(x_i))$,其中 Zm Z m $Z_m$ 是规范化因子，即 Zm=∑Ni=1wmiexp(−αmyiGm(xi)) Z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) $Z_m = \sum^N_{i=1} w_{mi}exp(- \alpha_my_iG_m(x_i))$
• 构建分类器的线性组合 f(x)=∑Mm=1αmGm(x) f ( x ) = ∑ m = 1 M α m G m ( x ) $f(x) = \sum^{M}_{m=1} \alpha_mG_m(x)$
• 得到最终的分类器为 G(x)=sign(f(x))=sign(∑Mm=1αmGm(x)) G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) $G(x) =sign(f(x)) = sign( \sum^{M}_{m=1} \alpha_mG_m(x) )$

输出

• 最终的分类器 G(x) G ( x ) $G(x)$

算法很简单也很好理解，同时很好用，而且效果确实很好，这就够了。

本质上讲权重在 em e m $e_m$出影响了分类器的选择，进而影响了数据分布，在这里将去权重间接的引入到了数据集中，影响了训练数据的分布。在一些书中说通过改变权重影响训练数据集的分布，其实就是这个意思，并不是真的修改了数据集的分布，而是通过误差率选择了分类效果最好的学习器，使分类器能够偏向去正确分类之前错误分类的数据。

过拟合

有了算法，那么还有一个问题，就是算法的过拟合问题。adaboost有很强的抗过拟合能力，然而很遗憾的是，针对adaboost问题的抗过拟合原因，至今没有一个比较完美的解释，虽然大牛们做了很多工作，但是依旧还是有很大的困难。一种猜想是通过多种分类器的组合，天然的引入了多样性，使算法不易过拟合。

算法解释

上面我们提出了算法，这里我们尝试利用数学推导来解释一下为什么adaboost这样设计是合理的。

对于adaboost可以理解为算法模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的二分类学习算法

给定加法模型 f(x)=∑Mm=1βmb(xi,γm) f ( x ) = ∑ m = 1 M β m b ( x i , γ m ) $f(x) = \sum^{M}_{m=1} \beta_mb(x_i,\gamma_m)$,损失函数为 L(x,f(x)) L ( x , f ( x ) ) $L(x,f(x))$,则问题转化为最小化损失函数，即 minβm,γm∑Ni=1L(yi,∑Mm=1βmb(xi,γm)) m i n β m , γ m ∑ i = 1 N L ( y i , ∑ m = 1 M β m b ( x i , γ m ) ) $min_{\beta_m,\gamma_m}{\sum_{i=1}^N L(y_i,\sum^{M}_{m=1} \beta_mb(x_i,\gamma_m))}$

对于这个公式，基本上没有办法直接求得解析解，因此我们可以利用前向分步算法来近似求解。

前向分步算法

前向分步算法的思想就是每次只优化一个基函数机器系数，逐步逼近目标，最后得到目标的近似值。

• 
  
• 初始化 f(x)=0 f ( x ) = 0 $f(x) = 0$
• 对 m=1,2,...,M m = 1 , 2 , . . . , M $m = 1,2,...,M$
  

• 极小化损失函数 (βm,γm)=argminβ,γ(∑Ni=1L(yi,fm−1(xi)+βb(xi,γ))) ( β m , γ m ) = a r g m i n β , γ ( ∑ i = 1 N L ( y i , f m − 1 ( x i ) + β b ( x i , γ ) ) ) $(\beta_m,\gamma_m) = arg min_{\beta,\gamma} (\sum_{i=1}^{N} L (y_i,f_{m-1}(x_i) + \beta b(x_i,\gamma)))$
  
• 更新 fm(x)=fm−1+βmb(x,γm) f m ( x ) = f m − 1 + β m b ( x , γ m ) $f_m(x) = f_{m-1} + \beta_mb(x,\gamma_m)$
• 得到加法模型 f(x)=∑Mm=1βmb(x,γm) f ( x ) = ∑ m = 1 M β m b ( x , γ m ) $f(x) = \sum_{m=1}^M \beta_mb(x,\gamma_m)$

adaboost算法解释

由前文，adaboost算法的分类器如下：

f(x)=∑Mm=1αmGm(x) f ( x ) = ∑ m = 1 M α m G m ( x ) $f(x) = \sum^{M}_{m=1} \alpha_mG_m(x)$

根据数学归纳法，假设 m−1 m − 1 $m-1$轮，根据前向分步算法，已经得到：

fm−1(x)=fm−2(x)+αm−1Gm−1(x) f m − 1 ( x ) = f m − 2 ( x ) + α m − 1 G m − 1 ( x ) $f_{m-1}(x) = f_{m-2}(x) + \alpha_{m-1}G_{m-1}(x)$，

则在第 m m $m$轮有：

fm(x)=fm−1(x)+αmGm(x) f m ( x ) = f m − 1 ( x ) + α m G m ( x ) $f_{m}(x) = f_{m-1}(x) + \alpha_{m}G_{m}(x)$

目标：得到 αm,Gm(x) α m , G m ( x ) $\alpha_m,G_m(x)$使得 fm(x) f m ( x ) $f_{m}(x)$在训练集上的指数损失 L(y,f(x))=exp[−yf(x)] L ( y , f ( x ) ) = e x p [ − y f ( x ) ] $L(y,f(x)) = exp[-yf(x)]$最小。

即 (αm,Gm(x))=argminα,G∑Ni=1exp(−yi(fm−1(xi)+αmGm(x))) ( α m , G m ( x ) ) = a r g m i n α , G ∑ i = 1 N e x p ( − y i ( f m − 1 ( x i ) + α m G m ( x ) ) ) $(\alpha_{m},G_m(x)) = arg min_{\alpha,G} \sum_{i=1}^{N} exp( - y_i (f_{m-1}(x_i)+\alpha_mG_m(x)))$

前一项 w¯mi=exp(−yifm−1(xi)) w ¯ m i = e x p ( − y i f m − 1 ( x i ) ) $\bar{w}_{mi} = exp( - y_i f_{m-1}(x_i))$跟最小化 (αm,Gm(x)) ( α m , G m ( x ) ) $(\alpha_{m},G_m(x))$无关，

因此
(αm,Gm(x))=argminα,G∑Ni=1w¯miexp(−yiαmGm(x)) ( α m , G m ( x ) ) = a r g m i n α , G ∑ i = 1 N w ¯ m i e x p ( − y i α m G m ( x ) ) $(\alpha_{m},G_m(x)) = arg min_{\alpha,G} \sum_{i=1}^{N} \bar{w}_{mi} exp( - y_i \alpha_mG_m(x))$

则最小的 Gm(x) G m ( x ) $G_m(x)$为：

G∗m(x)=argminG∑Ni=1w¯miI(yi≠G(xi)) G m ∗ ( x ) = a r g m i n G ∑ i = 1 N w ¯ m i I ( y i ≠ G ( x i ) ) $G_m^*(x) = arg min_{G} \sum_{i=1}^{N} \bar{w}_{mi} I( y_i \neq G(x_i))$

对于 α∗m α m ∗ $\alpha^*_m$，有：

∑Ni=1w¯miexp(−yiαmGm(x))=∑yi∈Gm(xi)w¯mie−α+∑yi∉Gm(xi)w¯mieα ∑ i = 1 N w ¯ m i e x p ( − y i α m G m ( x ) ) = ∑ y i ∈ G m ( x i ) w ¯ m i e − α + ∑ y i ∉ G m ( x i ) w ¯ m i e α $\sum_{i=1}^{N} \bar{w}_{mi} exp( - y_i \alpha_mG_m(x)) = \sum_{y_i \in G_m(x_i)} \bar{w}_{mi} e^{-\alpha} + \sum_{y_i \notin G_m(x_i)} \bar{w}_{mi} e^{\alpha}$

=(eα−e−α)∑Ni=1w¯miI(yi≠G(xi))+e−α∑Ni=1w¯mi = ( e α − e − α ) ∑ i = 1 N w ¯ m i I ( y i ≠ G ( x i ) ) + e − α ∑ i = 1 N w ¯ m i $= (e^{\alpha} - e^{-\alpha})\sum_{i=1}^N \bar{w}_{mi} I(y_i \neq G(x_i)) +e^{-\alpha} \sum_{i=1}^N \bar{w}_{mi}$

对 α α $\alpha$进行求导,有:

(eα+e−α)∑Ni=1w¯miI(yi≠G(xi))−e−α∑Ni=1w¯mi=0 ( e α + e − α ) ∑ i = 1 N w ¯ m i I ( y i ≠ G ( x i ) ) − e − α ∑ i = 1 N w ¯ m i = 0 $(e^{\alpha} + e^{-\alpha})\sum_{i=1}^N \bar{w}_{mi} I(y_i \neq G(x_i)) -e^{-\alpha} \sum_{i=1}^N \bar{w}_{mi} = 0$

可以得到 α∗m=12log(∑w¯mi∑w¯miI(yi≠G(xi))−1) α m ∗ = 1 2 l o g ( ∑ w ¯ m i ∑ w ¯ m i I ( y i ≠ G ( x i ) ) − 1 ) $\alpha_m^* = \frac{1}{2} log(\frac{\sum \bar{w}_{mi}}{\sum \bar{w}_{mi}I(y_i \neq G(x_i)) } - 1)$

令 em=∑w¯miI(yi≠G(xi))∑w¯mi=wmiI(yi≠G(xi)) e m = ∑ w ¯ m i I ( y i ≠ G ( x i ) ) ∑ w ¯ m i = w m i I ( y i ≠ G ( x i ) ) $e_m = \frac{\sum \bar{w}_{mi}I(y_i \neq G(x_i))}{\sum \bar{w}_{mi} } = w_{mi}I(y_i \neq G(x_i))$

有： α∗m=12log1−emem α m ∗ = 1 2 l o g 1 − e m e m $\alpha_m^* = \frac{1}{2} log \frac{1-e_m}{e_m}$

αm α m ${\alpha_m}$ 的更新与adaboost算法的 αm α m ${\alpha_m}$的更新形式一致，因此adaboost可以看做是算法模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的二分类学习算法