（《机器学习》完整版系列）第8章集成学习——8.2 AdaBoost算法（三合一：分布演进、集成投票、权重优选）

编程入门行业动态更新时间:2024-10-23 18:29:42

（《机器学习》完整版系列）第8章集成学习——8.2 AdaBoost算法（三合一：分布演进、集成投票、<a href=https://www.elefans.com/category/jswz/34/1758801.html style= 权重优选）"/>

（《机器学习》完整版系列）第8章集成学习——8.2 AdaBoost算法（三合一：分布演进、集成投票、权重优选）

AdaBoost算法实现了“三合一”：
1、不同的分布则可得到不同的学习器，利用这些不同的学习器，进行投票可得到一个集成学习器；
2、这些分布是一系列演进的，即通过先前的学习器的效果（损失情况）对分布进行调整。
3、算法优化是动态过程，即逐步累加且权重是经过优选的。

AdaBoost算法

基于概率论知识的学习算法（如，贝叶斯分类器）往往建立在训练集 D D D以及样本分布 D \mathcal{D} D的基础上，该类学习器表示为 L ( D , D ) \mathcal{L} (D,\mathcal{D} ) L(D,D)。

不同的分布则可得到不同的学习器，利用这些不同的学习器，进行投票可得到一个集成学习器，这是一个想法。另一个想法是：这些分布是一系列演进的，即通过先前的学习器的效果（损失情况）对分布进行调整。再一个想法就是算法是动态过程，即逐步累加且权重是经过优选的。 AdaBoost算法实现了这三个想法。

对AadBoost算法【西瓜书图8.3】的理解：

（1）已知训练集 D D D，选择一个合适的学习算法 L \mathcal{L} L。

（2） T T T轮训练后，得到的集成学习器为 H ( x ) = ∑ t = 1 T α t h t ( x ) H(\boldsymbol{x})=\sum_{t=1}^T{\alpha }_th_t(\boldsymbol{x}) H(x)=∑t=1Tαtht(x)（当然，对应的分类器为 s g n H ( x ) \mathrm{sgn}H(\boldsymbol{x}) sgnH(x)）。

（3）学习器序列为 h t ( x ) = L ( D , D t ) h_t(\boldsymbol{x})=\mathcal{L} (D,\mathcal{D}_t ) ht(x)=L(D,Dt)，即它由序列 D t \mathcal{D}_t Dt决定。将该序列的起点初始化为均匀分布，即 D 1 = 1 m \mathcal{D}_1=\frac{1}{m} D1=m1，之后，按某种更新公式生成序列，如【西瓜书式(8.19)】。

（4）在集成式中， h t h_t ht有一个权重 α t {\alpha }_t αt，希望它是选优得到的。即在 D t {\mathcal{D}_t } Dt和 h t h_t ht已定的情况下，确定未知的 α t {\alpha }_t αt使得 α t h t {\alpha }_th_t αtht损失最小，即： min ⁡ ℓ exp ⁡ ( α t h t ∣ D t ) \min {\ell }_{\exp}({\alpha }_th_t\,|\,\mathcal{D}_t) minℓexp(αtht∣Dt)，这个最优 α t {\alpha }_t αt由【西瓜书式(8.11)】给出。

【西瓜书式(8.7)(8.8)】说明了算法中分类器为最优贝叶斯分类器，下面进行推导。

优化目标为最小化【西瓜书式(8.5)】，即（以样本空间有限为例）：
ℓ exp ⁡ ( H ∣ D ) = E x ∼ D e − f ( x ) H ( x ) = 1 ∣ X ∣ ∑ x ∈ X e − f ( x ) H ( x ) = 1 ∣ X ∣ ∑ f ( x ) = 1 e − f ( x ) H ( x ) + 1 ∣ X ∣ ∑ f ( x ) = − 1 e − f ( x ) H ( x ) = ∣ X + ∣ ∣ X ∣ e − H ( x ) + ∣ X − ∣ ∣ X ∣ e H ( x ) = e − H ( x ) P ( y = 1 ∣ x ) + e H ( x ) P ( y = − 1 ∣ x ) = e − H ( x ) η ( x ) + e H ( x ) ( 1 − η ( x ) ) \begin{align} {\ell }_{\exp}(H\,|\,\mathcal{D}) & =\mathop{\mathbb{E} }\limits_{\boldsymbol{x}\thicksim \mathcal{D} }\,\mathrm{e}^{-f(\boldsymbol{x})H(\boldsymbol{x})}\notag \\ & =\frac{1}{|\mathcal{X} |}\sum_{\boldsymbol{x}\in \mathcal{X} }\,\mathrm{e}^{-f(\boldsymbol{x})H(\boldsymbol{x})}\notag \\ & =\frac{1}{|\mathcal{X} |}\sum_{f(\boldsymbol{x})=1 }\,\mathrm{e}^{-f(\boldsymbol{x})H(\boldsymbol{x})}+\frac{1}{|\mathcal{X} |}\sum_{f(\boldsymbol{x})=-1 }\,\mathrm{e}^{-f(\boldsymbol{x})H(\boldsymbol{x})}\notag \\ & =\frac{|\mathcal{X}^+ |}{|\mathcal{X} |}\,\mathrm{e}^{-H(\boldsymbol{x})}+\frac{|\mathcal{X}^- |}{|\mathcal{X} |}\,\mathrm{e}^{H(\boldsymbol{x})}\notag \\ & =\mathrm{e}^{-H(\boldsymbol{x})}P(y=1\,|\,\boldsymbol{x})+\mathrm{e}^{H(\boldsymbol{x})}P(y=-1\,|\,\boldsymbol{x})\notag \\ & =\mathrm{e}^{-H(\boldsymbol{x})}{\eta} (\boldsymbol{x})+\mathrm{e}^{H(\boldsymbol{x})}(1-{\eta} (\boldsymbol{x})) \tag{8.10} \end{align} ℓexp(H∣D)=x∼DEe−f(x)H(x)=∣X∣1x∈X∑e−f(x)H(x)=∣X∣1f(x)=1∑e−f(x)H(x)+∣X∣1f(x)=−1∑e−f(x)H(x)=∣X∣∣X+∣e−H(x)+∣X∣∣X−∣eH(x)=e−H(x)P(y=1∣x)+eH(x)P(y=−1∣x)=e−H(x)η(x)+eH(x)(1−η(x))(8.10)
记
L [ H ] = e − H η + e H ( 1 − η ) \begin{align} L[H]=\mathrm{e}^{-H}{\eta}+\mathrm{e}^{H}(1-{\eta} ) \tag{8.11} \end{align} L[H]=e−Hη+eH(1−η)(8.11)
令 ∂ L [ H ] ∂ H = 0 \frac{\partial L[H]}{\partial H }=0 ∂H∂L[H]=0，则
− e − H η + e H ( 1 − η ) = 0 \begin{align} -\mathrm{e}^{-H}{\eta}+\mathrm{e}^{H}(1-{\eta} )=0 \tag{8.12} \end{align} −e−Hη+eH(1−η)=0(8.12)
解得
H ∗ = 1 2 ln ⁡ η 1 − η \begin{align} H^*=\frac{1}{2}\ln\frac{\eta}{1-\eta} \tag{8.13} \end{align} H∗=21ln1−ηη(8.13)
令 H ( x ) = H ∗ ( η ( x ) ) H(\boldsymbol{x})=H^*({\eta} (\boldsymbol{x})) H(x)=H∗(η(x))即得到【西瓜书式(8.7)】。由预测器 H ( x ) H(\boldsymbol{x}) H(x)即可得分类器 h ( x ) = s g n ( H ( x ) ) h(\boldsymbol{x})=\mathrm{sgn}(H(\boldsymbol{x})) h(x)=sgn(H(x))即【西瓜书式(8.8)】，与【西瓜书式(7.6)】比较，知其为贝叶斯最优分类器。

注：基于一般情况的推导即为【西瓜书式(8.9)】的推导。

本文为原创，您可以：