集成学习之Adaboost 算法及相关参数公式推导

算法及相关参数公式推导"/>

集成学习之Adaboost 算法及相关参数公式推导

集成学习

什么是集成学习？
集成学习就是将多个学习器通过各类方法集成起来，从而获得更好的学习效果的一种学习方式。

一般来说，集成学习分为两种

• 同质集成
      该集成中仅仅包含同种类型的学习器
• 异质继承
      该集成中包含不同类型的学习器

现在一般都使用同质集成的方式，常用的方法又可以分为两类

• 序列化方法
      个体学习器之间存在强依赖关系，必须串行生成，代表算法有Boosting
• 并行化方法
      个体学习器之间不存在强依赖关系，可以同时生成，代表算法有Bagging和Random Forest

Boosting

这里主要讲Adaboost，所以先简单说一下Boosting

在前文中提过，boosting属于序列化方法，及各个学习器之间存在强依赖关系，需要串行生成。具体的生成流程可以看下图

• D ( i ) D(i) D(i) 是为了让之前普通学习器中分类错误的样本在下一个学习器中多受重视
• m m m 为样本数量
• T T T 为提前设定的普通学习器数量，当训练到第 T T T 个学习器时就停止训练

那么从图中可以看出，一个完整的Boosting学习过程需要解决4个问题

• l o s s loss loss 的计算方式
• α \alpha α 的获取方式
• D D D 的更新方式
• 合并策略的选择

接下来将详细讲述Adaboost针对以上四个问题的解决方法。

Adaboost

符号&参数&其他需要提前说明的东西

Adaboost解决分类问题

这里以二分类为例，那我们需要的输出就是 { − 1 , 1 } \{-1, 1\} {−1,1}
先把最后的参数结果列出来

对于第 k k k 个分类器 G k ( x ) G_k(x) Gk​(x) 在训练集 T T T 上的参数

• 加权误差 l o s s ( k ) loss(k) loss(k)
  l o s s ( k ) = P ( G k ( x i ) ≠ y i ) = ∑ i = 1 m w k , i I ( G k ( x i ) ≠ y i ) \begin {aligned} loss(k) &= P(G_k(x_i)≠y_i) \\ &=\sum_{i=1}^m{w_{k, i}I(G_k(x_i)≠y_i)} \end {aligned} loss(k)​=P(Gk​(xi​)​=yi​)=i=1∑m​wk,i​I(Gk​(xi​)​=yi​)​
      其中 I I I 是单位矩阵
• 权重系数 α k \alpha_k αk​
  α k = 1 2 log ⁡ 1 − l o s s ( k ) l o s s ( k ) \alpha_k = \frac{1}{2}\log{\frac{1-loss(k)}{loss(k)}} αk​=21​logloss(k)1−loss(k)​
       l o s s ( k ) loss(k) loss(k) 越大，该分类器 G k ( x ) G_k(x) Gk​(x) 的权重系数越小
• 样本权重 w k + 1 , i w_{k+1, i} wk+1,i​
  w k + 1 , i = w k , i Z k exp ⁡ ( − α k y i G k ( x i ) ) Z k = ∑ i = 1 m w k , i exp ⁡ ( − α k y i G k ( x i ) ) \begin {aligned} w_{k+1, i} &= \frac{w_{k, i}}{Z_k}\exp(-\alpha_ky_iG_k(x_i)) \\ Z_k&=\sum_{i=1}^m{w_{k, i}\exp(-\alpha_ky_iG_k(x_i))} \end {aligned} wk+1,i​Zk​​=Zk​wk,i​​exp(−αk​yi​Gk​(xi​))=i=1∑m​wk,i​exp(−αk​yi​Gk​(xi​))​
       当第 i i i 个样本分类错误，有 y i G k ( x i ) < 0 y_iG_k(x_i) < 0 yi​Gk​(xi​)<0，这会导致 w k + 1 , i w_{k+1, i} wk+1,i​ 变大，符合之前的要求
• 合并策略 f ( x ) f(x) f(x)
  f ( x ) = s i g n ( ∑ k = 1 K α k G k ( x ) ) f(x) = sign(\sum_{k=1}^K\alpha_kG_k(x)) f(x)=sign(k=1∑K​αk​Gk​(x))
       是一种加权表决法，最后取输出符号作为prediction

接下来是对各个参数的推导

首先明确，可以从参数中看出，Adaboost分类问题是一个模型为加法模型；学习算法为前向分步学习算法；损失函数为指数函数的分类问题

其中

• 加法模型体现在合并策略
• 前向分步学习体现在 f k ( x ) = f k − 1 ( x ) + α k G k ( x ) f_k(x) = f_{k - 1}(x) + \alpha_kG_k(x) fk​(x)=fk−1​(x)+αk​Gk​(x)
• 而指数函数体现在 ( α , G k ( x ) ) = arg min ⁡ α , G ∑ i = 1 m exp ⁡ ( − y i f k ( x i ) ) (\alpha_, G_k(x)) = {\underset {\alpha, G}{\operatorname {arg\,min} }} \sum_{i=1}^m\exp(-y_if_k(x_i)) (α,​Gk​(x))=α,Gargmin​i=1∑m​exp(−yi​fk​(xi​))

那公式推导就从指数函数形式的损失函数开始

为了得到第 k k k 个分类器的 G k G_k Gk​ 和 α k \alpha_k αk​，我们需要最小化 l o s s loss loss，也就是计算上式

当我们把前向分步学习算法的公式融入 l o s s loss loss 中可以发现
( α , G k ( x ) ) = arg min ⁡ α , G ∑ i = 1 m exp ⁡ [ − y i ( f k − 1 ( x ) + α k G k ( x ) ) ] (\alpha_, G_k(x)) = {\underset {\alpha, G}{\operatorname {arg\,min} }} \sum_{i=1}^m\exp[-y_i(f_{k - 1}(x) + \alpha_kG_k(x))] (α,​Gk​(x))=α,Gargmin​i=1∑m​exp[−yi​(fk−1​(x)+αk​Gk​(x))]
不难发现，对于 exp ⁡ ( − y i ( f k − 1 ( x ) ) \exp(-y_i(f_{k - 1}(x)) exp(−yi​(fk−1​(x)) 来说，这个式子不依赖于 α \alpha α 或 G G G，因此可以单独拎出来，有
w k , i ′ = exp ⁡ ( − y i ( f k − 1 ( x ) ) w'_{k, i} = \exp(-y_i(f_{k - 1}(x)) wk,i′​=exp(−yi​(fk−1​(x))

将其带入，则有
( α , G k ( x ) ) = arg min ⁡ α , G ∑ i = 1 m w k , i ′ exp ⁡ ( − y i α G ( x ) ) (\alpha_, G_k(x)) = {\underset {\alpha, G}{\operatorname {arg\,min} }} \sum_{i=1}^m{w'_{k, i}\exp(-y_i\alpha G(x))} (α,​Gk​(x))=α,Gargmin​i=1∑m​wk,i′​exp(−yi​αG(x))
接下来就可以开始推导了
∑ i = 1 m w k , i ′ exp ⁡ ( − y i α G ( x ) ) = ∑ y i = G k ( x i ) exp ⁡ ( w k , i ′ e − α ) + ∑ y i ≠ G k ( x i ) exp ⁡ ( w k , i ′ e α ) = e − α ∑ i = 1 m w k , i ′ I ( y i = G k ( x i ) ) + e α ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) = e − α ∑ i = 1 m w k , i ′ [ I − I ( y i ≠ G k ( x i ) ) ] + e α ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) = e − α ∑ i = 1 m w k , i ′ − e − α ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) + e α ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) = e − α ∑ i = 1 m w k , i ′ + ( e α − e − α ) ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) \begin {aligned} &\sum_{i=1}^m{w'_{k, i}\exp(-y_i\alpha G(x))} \\ = &\sum_{y_i=G_k(x_i)}{\exp(w'_{k, i}e^{-\alpha})} + \sum_{y_i≠G_k(x_i)}{\exp(w'_{k, i}e^{\alpha})} \\ =&e^{-\alpha}\sum_{i=1}^{m}w'_{k, i}I(y_i=G_k(x_i))+e^{\alpha}\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i)) \\ =&e^{-\alpha}\sum_{i=1}^{m}w'_{k, i}[I - I(y_i≠G_k(x_i))]+e^{\alpha}\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i)) \\ =&e^{-\alpha}\sum_{i=1}^{m}w'_{k, i} - e^{-\alpha}\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i)) + e^{\alpha}\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i))\\ =&e^{-\alpha}\sum_{i=1}^{m}w'_{k, i} + (e^{\alpha} - e^{-\alpha})\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i)) \end{aligned} =====​i=1∑m​wk,i′​exp(−yi​αG(x))yi​=Gk​(xi​)∑​exp(wk,i′​e−α)+yi​​=Gk​(xi​)∑​exp(wk,i′​eα)e−αi=1∑m​wk,i′​I(yi​=Gk​(xi​))+eαi=1∑m​wk,i′​I(yi​​=Gk​(xi​))e−αi=1∑m​wk,i′​[I−I(yi​​=Gk​(xi​))]+eαi=1∑m​wk,i′​I(yi​​=Gk​(xi​))e−αi=1∑m​wk,i′​−e−αi=1∑m​wk,i′​I(yi​​=Gk​(xi​))+eαi=1∑m​wk,i′​I(yi​​=Gk​(xi​))e−αi=1∑m​wk,i′​+(eα−e−α)i=1∑m​wk,i′​I(yi​​=Gk​(xi​))​
在得到了这个式子之后，想要得到 a r g m i n argmin argmin，就把他对 α \alpha α 求偏导，令其 = 0 = 0 =0 即可，所以有
− e − α ∑ i = 1 m w k , i ′ + ( e α + e − α ) ∑ i = 1 m w k , i ′ I ( y i ≠ G k ( x i ) ) = 0 ∵ w k , i ′ = exp ⁡ ( − y i ( f k − 1 ( x ) ) ∴ ∑ i = 1 m w k , i ′ = 1 ∵ l o s s ( k ) = ∑ i = 1 m w k , i I ( G k ( x i ) ≠ y i ) ∴ ( e α + e − α ) l o s s ( k ) = e − α ( e 2 α + 1 ) l o s s ( k ) = 1 e 2 α = 1 l o s s ( k ) − 1 e 2 α = 1 − l o s s ( k ) l o s s ( k ) α = 1 2 ln ⁡ 1 − l o s s ( k ) l o s s ( k ) \begin {aligned} -e^{-\alpha}\sum_{i=1}^{m}w'_{k, i} + (e^{\alpha} + e^{-\alpha})\sum_{i=1}^{m}w'_{k, i}I(y_i≠G_k(x_i)) &= 0 \\ \\ ∵ w'_{k, i} = \exp(-y_i(f_{k - 1}(x))&\space \\ ∴\sum_{i=1}^{m}w'_{k, i}=1&\space \\ ∵loss(k)&=\sum_{i=1}^m{w_{k, i}I(G_k(x_i)≠y_i)}\\ ∴(e^{\alpha} + e^{-\alpha}) loss(k) &= e^{-\alpha} \\ (e^{2\alpha} + 1)loss(k) &= 1 e^{2\alpha} &= \frac{1}{loss(k)} - 1 \\ e^{2\alpha} &= \frac{1-loss(k)}{loss(k)} \\ \alpha &= \frac{1}{2}\ln\frac{1-loss(k)}{loss(k)} \end{aligned} −e−αi=1∑m​wk,i′​+(eα+e−α)i=1∑m​wk,i′​I(yi​​=Gk​(xi​))∵wk,i′​=exp(−yi​(fk−1​(x))∴i=1∑m​wk,i′​=1∵loss(k)∴(eα+e−α)loss(k)(e2α+1)loss(k)e2αα​=0  =i=1∑m​wk,i​I(Gk​(xi​)​=yi​)=e−α=1e2α=loss(k)1−loss(k)​=21​lnloss(k)1−loss(k)​​=loss(k)1​−1​

由此就推出了权重系数 α k \alpha_k αk​
又因为 w k , i ′ = exp ⁡ ( − y i ( f k − 1 ( x ) ) w'_{k, i} = \exp(-y_i(f_{k - 1}(x)) wk,i′​=exp(−yi​(fk−1​(x))
可以更新用于训练第 k + 1 k +1 k+1 个分类器的新的样本权重
w k + 1 , i ′ = exp ⁡ ( − y i f k ( x ) ) = exp ⁡ ( − y i ( f k − 1 ( x ) + α k G k ( x ) ) ) = w k , i ′ exp ⁡ ( − y i α k G k ( x ) ) \begin{aligned} w'_{k+1, i} &= \exp(-y_if_k(x)) \\ &=\exp(-y_i(f_{k-1}(x)+\alpha_kG_k(x)))\\ &=w'_{k, i}\exp(-y_i\alpha_kG_k(x)) \end{aligned} wk+1,i′​​=exp(−yi​fk​(x))=exp(−yi​(fk−1​(x)+αk​Gk​(x)))=wk,i′​exp(−yi​αk​Gk​(x))​
再通过规范化因子 Z k Z_k Zk​ 对 w k + 1 , i ′ w'_{k+1, i} wk+1,i′​进行规范化，就有
w k + 1 , i = w k , i Z k exp ⁡ ( − α k y i G k ( x i ) ) w_{k+1, i} = \frac{w_{k, i}}{Z_k}\exp(-\alpha_ky_iG_k(x_i)) wk+1,i​=Zk​wk,i​​exp(−αk​yi​Gk​(xi​))

完成了公式推导

Adaboost解决回归问题

以Adaboost_R2为例，这里就仅仅把参数列出来，不进行推导了

• 加权误差 l o s s ( k ) loss(k) loss(k)
  • 计算在训练集 T T T上的最大误差 L ( k ) = m a x ∣ y i − G k ( x i ) ∣ L(k) = max|y_i - G_k(x_i)| L(k)=max∣yi​−Gk​(xi​)∣
  • 计算每个样本的相对误差（有三种方式）
    • 线性误差： l k , i = ∣ y i − G k ( x i ) ∣ L k l_{k, i} = \frac{|y_i-G_k(x_i)|}{L_k} lk,i​=Lk​∣yi​−Gk​(xi​)∣​
    • 平方误差： l k , i = ( y i − G k ( x i ) ) 2 L k 2 l_{k, i} = \frac{(y_i-G_k(x_i))^2}{L_k^2} lk,i​=Lk2​(yi​−Gk​(xi​))2​
    • 指数误差： l k , i = 1 − exp ⁡ ( y i − G k ( x i ) L k ) l_{k, i} = 1 - \exp(\frac{y_i-G_k(x_i)}{L_k}) lk,i​=1−exp(Lk​yi​−Gk​(xi​)​)
  • 计算加权误差
    l o s s ( k ) = ∑ i = 1 m w k , i l k , i loss(k) = \sum_{i=1}^{m}{w_{k, i}l_{k, i}} loss(k)=i=1∑m​wk,i​lk,i​
• 权重系数 α k \alpha_k αk​
  α k = l o s s ( k ) 1 − l o s s ( k ) \alpha_k = \frac{loss(k)}{1-loss(k)} αk​=1−loss(k)loss(k)​
• 样本权重 w k + 1 , i w_{k+1, i} wk+1,i​
  w k + 1 , i = w k , i Z k α k 1 − l k , i Z k = ∑ i = 1 m w k , i α k 1 − l k , i \begin {aligned} w_{k+1, i} &= \frac{w_{k, i}}{Z_k}\alpha_k^{1-l_k, i} \\ Z_k&=\sum_{i=1}^m{w_{k, i}\alpha_k^{1-l_k, i}} \end {aligned} wk+1,i​Zk​​=Zk​wk,i​​αk1−lk​,i​=i=1∑m​wk,i​αk1−lk​,i​​
• 合并策略 f ( x ) f(x) f(x)
  f ( x ) = G k ∗ ( x ) f(x) = G_k^*(x) f(x)=Gk∗​(x)
       与分类问题的加权表决法不同，这里是对学习其中取权重中位数对应的学习器，只取一个

Adaboost可能存在的问题

• 对异常样本敏感