您的位置: 首页  >  文章  >  周志华西瓜书-AdaBoost算法证明解析

周志华西瓜书-AdaBoost算法证明解析

分类: 文章 • 2024-11-12 19:50:40

  本节证明并未从集成学习源头开始，如若对集成学习还不是很清楚的同学，参考文章：

AdaBoost算法证明

  本文以周志华西瓜书推导过程为例，以“加性模型”（additive model）进行解析：

  将基学习器ht(x)h_{t}(\boldsymbol{x})线性组合，则基学习器的线性组合表示为如下H(x)H(\boldsymbol{x})形式：

H(x)=∑t=1Tαtht(x) H(\boldsymbol{x})=\sum_{t=1}^{T}\alpha_{t}h_{t}(\boldsymbol{x})

  定义整个学习器的损失函数为指数损失函数(exponential loss function)，期望指数损失函数最小化：

ℓexp⁡(H∣D)=Ex∼D[e−f(x)H(x)] \ell_{\exp }(H | \mathcal{D})=\mathbf{E}_{x \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right]

  其中ff是真实函数，yi∈{−1,+1}y_{i} \in \{-1,+1\}，D\mathcal{D}表示样本的权值分布(对于错误的样本权重要高一点，正确的样本权重要低一点，所有的样本组合起来就相当于有一个分布)。

  若基学习器的线性组合H(x)H(\boldsymbol{x})能够使得指数损失函数最小化，一般的做法就是求偏导数，令其等于零，求解。由于f(x)f(\boldsymbol{x})取值只有两种，所以其求偏导数之后的结果如下所示：

∂ℓexp⁡(H∣D)∂H(x)=−e−H(x)P(f(x)=1∣x)+eH(x)P(f(x)=−1∣x) \frac{\partial \ell_{\exp }(H | \mathcal{D})}{\partial H(\boldsymbol{x})}=-e^{-H(\boldsymbol{x})} P(f(\boldsymbol{x})=1 | \boldsymbol{x})+e^{H(\boldsymbol{x})} P(f(\boldsymbol{x})=-1 | \boldsymbol{x})

  令其偏导数为0，解得：

H(x)=12lnP(f(x)=1∣x)P(f(x)=−1∣x) H(\boldsymbol{x}) = \frac{1}{2}ln\frac{P(f(x)=1|\boldsymbol{x})}{P(f(x)=-1|\boldsymbol{x})}

  有：

sign⁡(H(x))=sign⁡(12ln⁡P(f(x)=1∣x)P(f(x)=−1∣x))={1,P(f(x)=1∣x)>P(f(x)=−1∣x)−1,P(f(x)=1∣x)<P(f(x)=−1∣x)=arg⁡max⁡y∈{−1,1}P(f(x)=y∣x) \begin{aligned} \operatorname{sign}(H(\boldsymbol{x})) &=\operatorname{sign}\left(\frac{1}{2} \ln \frac{P(f(x)=1 | \boldsymbol{x})}{P(f(x)=-1 | \boldsymbol{x})}\right) \\ &=\left\{\begin{array}{ll} {1,} & {P(f(x)=1 | \boldsymbol{x}) > P(f(x)=-1 | \boldsymbol{x})} \\ {-1,} & {P(f(x)=1 | \boldsymbol{x}) < P(f(x)=-1 | \boldsymbol{x})} \\ \end{array}\right.\\ & {=\underset{y \in\{-1,1\}}{\arg \max } P(f(x)=y | \boldsymbol{x})} \end{aligned}

  这意味着若指数损失函数最小化，则分类错误率也将最小化。说明指数损失函数是原任务的替代函数，但由于其连续可微，所以用它替代0/1损失函数作为优化目标。上面这么多就是说接下来用这个连续的指数损失函数做进一步的处理。

  在AdaBoost算法中，第一个基分类器h1h_{1}通过直接将基学习算法用于初始数据分布而得到；之后的hth_{t}和αt\alpha_{t}是通过迭代生成得到的。当基分类器hth_{t}基于分布Dt\mathcal{D}_{t}产生之后，基分类器的权重αt\alpha_{t}应该使得αtht\alpha_{t}h_{t}最小化指数损失函数，只有αt\alpha_{t}在判断错误的基分类器给予较小权值，判断正确的基分类器给予较大权值，才能使得H(x)H(\boldsymbol{x})具有较准确的判断，从而最小化指数损失函数

ℓexp⁡(αtht∣Dt)=Ex∼Dt[e−f(x)αtht(x)]=Ex∼Dt[e−αtI(f(x)=ht(x))+eαtI(f(x)≠ht(x))]=e−αtPx∼Dt(f(x)=ht(x))+eαtPx∼Dt(f(x)≠ht(x))=e−αt(1−ϵt)+eαtϵt \begin{aligned} \ell_{\exp }\left(\alpha_{t} h_{t} | \mathcal{D}_{t}\right) &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left[ e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x}) } \right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left[e^{-\alpha_{t}} \mathbb{I}\left(f(\boldsymbol{x})=h_{t}(\boldsymbol{x})\right)+e^{\alpha_{t}} \mathbb{I}\left(f(\boldsymbol{x}) \neq h_{t}(\boldsymbol{x})\right)\right] \\ &=e^{-\alpha_{t}} P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(f(\boldsymbol{x})=h_{t}(\boldsymbol{x})\right)+e^{\alpha_{t}} P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(f(\boldsymbol{x}) \neq h_{t}(\boldsymbol{x})\right) \\ &=e^{-\alpha_{t}}\left(1-\epsilon_{t}\right)+e^{\alpha_{t}} \epsilon_{t} \end{aligned}

  其中ϵt=Px∼Dt(f(x)≠ht(x))\epsilon_{t}=P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(f(\boldsymbol{x}) \neq h_{t}(\boldsymbol{x})\right)，其实就是误判率。为了求得基分类器的权重，对其求导：

∂ℓexp⁡(αtht∣Dt)∂αt=−e−αt(1−ϵt)+eαtϵt \frac{\partial \ell_{\exp }\left(\alpha_{t} h_{t} | \mathcal{D}_{t}\right)}{\partial \alpha_{t}}=-e^{-\alpha_{t}}\left(1-\epsilon_{t}\right)+e^{\alpha_{t}} \epsilon_{t}

  再令导数为0，可得：

αt=12ln⁡(1−ϵtϵt) \alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)

  到这里相当于自适应做完了，在这里，AdaBoost自适应的思想采取的是加权多数表决的方法，上述公式体现出来的就是加大分类器误差率小的弱分类器的权值，使其在表决中起较大作用。误差率较大的则相反。

  现在要回到Boost的原理中对样本的处理，在改变这个样本的权值，或者说概率分布的时候，我们要实现的直观想法是：提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。接下来我们去把这个公式证出来：

   这里通过基学习器开始证明，看基学习器在什么样本分布下能够学出来最小化分类误差。

  AdaBoost在得到Ht−1H_{t-1}之后，调整样本分布，使得hth_{t}能学出来之前的基学习器无法学习到的东西，能纠正Ht−1H_{t-1}的一些错误，那这个hth_{t}就能够最小化：

ℓexp⁡(Ht−1+ht∣D)=Ex∼D[e−f(x)(Ht−1(x)+ht(x))]=Ex∼D[e−f(x)Ht−1(x)e−f(x)ht(x)] \begin{aligned} \ell_{\exp }\left(H_{t-1}+h_{t} | \mathcal{D}\right)& = \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x})(H_{t-1}(\boldsymbol{x})+h_{t}(\boldsymbol{x}))} \right]\\ &= \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[ e^{-f(\boldsymbol{x})H_{t-1}(\boldsymbol{x})}e^{-f(\boldsymbol{x})h_{t}(\boldsymbol{x})} \right] \end{aligned}

  注意到f2(x)=ht2(x)=1f^{2}(x)=h_{t}^{2}(x)=1，上式可使用e−f(x)ht(x)e^{-f(\boldsymbol{x})h_{t}(\boldsymbol{x})}的泰勒展开式近似为如下公式：

ℓexp⁡(Ht−1+ht∣D)≃Ex∼D[e−f(x)Ht−1(x)(1−f(x)ht(x)+f2(x)ht2(x)2)]=Ex∼D[e−f(x)Ht−1(x)(1−f(x)ht(x)+12)] \begin{aligned} \ell_{\exp }\left(H_{t-1}+h_{t} | \mathcal{D}\right) & \simeq \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h_{t}(\boldsymbol{x})+\frac{f^{2}(\boldsymbol{x}) h_{t}^{2}(\boldsymbol{x})}{2}\right)\right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h_{t}(\boldsymbol{x})+\frac{1}{2}\right)\right] \end{aligned}

   于是理想的基学习器：

ht(x)=arg⁡min⁡hℓexp⁡(Ht−1+h∣D)=arg⁡min⁡hEx∼D[e−f(x)Ht−1(x)(1−f(x)h(x)+12)]=arg⁡max⁡hEx∼D[e−f(x)Ht−1(x)f(x)h(x)]=arg⁡max⁡hEx∼D[e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)]f(x)h(x)] \begin{aligned} h_{t}(x)&=\underset{h}{\arg \min } \ell_{\exp }\left(H_{t-1}+h | \mathcal{D}\right)\\ &=\underset{h}{\arg \min } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h(\boldsymbol{x})+\frac{1}{2}\right)\right]\\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} f(\boldsymbol{x}) h(\boldsymbol{x})\right]\\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \end{aligned}

   注意到Ex∼D[e−f(x)Ht−1(x)]\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]是一个常数。令Dt\mathcal{D}_{t}表示一个分布：

Dt(x)=D(x)e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)] \mathcal{D}_{t}(\boldsymbol{x})=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]}

   依据数学期望的定义，等价于令:

ht(x)=arg⁡max⁡hEx∼D[e−f(x)Ht−1(x)Ex∼D[e−f(x)Ht−1(x)]f(x)h(x)]=arg⁡max⁡hEx∼Dt[f(x)h(x)] \begin{aligned} h_{t}(\boldsymbol{x}) &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \end{aligned}

   由f(x)f(\boldsymbol{x})，h(x)h(\boldsymbol{x}) ，∈{−1,+1}\in \{-1,+1\}，有：

f(x)h(x)=1−2I(f(x)≠h(x)) f(\boldsymbol{x}) h(\boldsymbol{x})=1-2 \mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x}))

   则理想的基学习器：

ht(x)=arg⁡min⁡hEx∼Dt[I(f(x)≠h(x))] h_{t}(\boldsymbol{x})=\underset{h}{\arg \min } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[\mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x}))]

  由此可见，理想的hth_{t}将在分布Dt\mathcal{D}_{t}下最小化分类误差。Dt\mathcal{D}_{t}和Dt+1\mathcal{D}_{t+1}的关系有：

Dt+1(x)=D(x)e−f(x)Ht(x)Ex∼D[e−f(x)Ht(x)]=D(x)e−f(x)Ht−1(x)e−f(x)αtht(x)Ex∼D[e−f(x)Ht(x)]=Dt(x)⋅e−f(x)αtht(x)Ex∼D[e−f(x)Ht−1(x)]Ex∼D[e−f(x)Ht(x)] \begin{aligned} \mathcal{D}_{t+1}(\boldsymbol{x}) &=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \\ &=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \\ &= \mathcal{D}_{t}(\boldsymbol{x}) \cdot e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x}) }\frac{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \end{aligned}

  上述公式就是下图AdaBoost的第7步更新公式，整个的AdaBoost算法如下图所示：
周志华西瓜书-AdaBoost算法证明解析

  AdaBoost 算法第五行检查当前基分类器是否比随机猜测好，一旦不满足条件，当前基学习器即被抛弃，且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少，导致整体性能不佳。采用“重采样法”（re-sampling）来处理，即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样而得到的样本集对基学习器进行训练，则可获得重启动。

我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究强化学习、计算机视觉、深度学习、机器学习等相关内容，分享学习过程中的学习笔记和心得！期待您的关注，欢迎一起学习交流进步！

相关推荐