引言

上一节介绍了$\text{Bagging}$集成学习思想。本节将介绍集成学习思想——$\text{Boosting}$，并介绍经典模型$\text{AdaBoost}$。

回顾：$\text{Bagging}$过程

关于$\text{Bagging}$过程主要有两个特点：

• 针对某一具体学习任务(回归、分类等)，独立地训练若干个基学习器($\text{Base Learner}$)；每个基学习器得到的预测结果基于不同任务进行融合，从而得到最终预测结果。
• 每个基学习器训练使用的数据集是基于原始数据集通过自助采样($\text{Bootstrap Sampling}$)的方式生成的结果。

$\text{Bagging}$过程优化的是预测模型泛化误差中的方差($\text{Variance}$)部分，与泛化误差中的偏差($\text{Bias}$)部分无关。并且泛化误差中方差的大小仅与预测过程中，预测模型的自身性质相关。

通常称方差较大的预测模型为不稳定学习器($\text{Unstable Learner}$)。该类学习器的特点在于：不同的基学习器随着样本的扰动会得到差异度较高的学习结果。最终通过$\text{Bagging}$集成后的泛化性能可通过差异度的增加而进一步提升。

• 例如决策树($\text{Decision Tree}$)就是一种典型的不稳定学习器。随着样本的扰动，样本内的特征分布(假设是经验分布)随着样本的变化而发生变化。这种情况下决策树可能根据不同的样本集合得到不同的划分顺序，从而得到有差异的预测模型。

这种基于样本扰动带来的差异性恰恰是$\text{Bagging}$集成思想的要求。甚至我们可以 人为设置 各基学习器之间的差异程度。如随机森林($\text{Random Forest,RF}$)。该算法就是将样本扰动、属性扰动相结合，从而控制学习器之间的差异性：

• 样本扰动：各基学习器(决策树)的训练样本来自自助采样法；
• 属性扰动：各基学习器(决策树)每次结点划分时，先随机划分一个属性子集，再从属性子集内部选择最优属性，以此来代替决策树原始的从全局属性中选择最优属性的方式。
  而划分属性子集的大小，就是人为控制的参数。这种方式是通过‘人工干扰’，故意让模型学的不够准确，使得各学习器之间的差异性明显显现出来，从而更加符合$\text{Bagging}$算法的条件。

$\text{Boosting}$过程介绍

$\text{Boosting}$算法的核心思路是将一组弱学习器($\text{Weak Learners}$)提升为强学习器($\text{Strong Learners}$)的算法。相比于$\text{Bagging}$算法的思想，它有如下几点不同之处：

• $\text{Bagging}$针对预测模型泛化误差中的方差；而$\text{Boosting}$针对预测模型泛化误差中的偏差。
  • $\text{Bagging}$主要将若干个‘不稳定学习器’，也就是预测方差较大的学习器组合成一个‘稳定的学习器’($\text{Stable Learner}$)；
  • $\text{Boosting}$主要将若干个‘弱学习器’，也就是预测偏差较大的学习器组合成一个‘强学习器’。这个强学习器对于样本分布的位置更加准确(偏差较小).
• $\text{Bagging}$中的若干个学习器在训练过程中相互独立。也就是说，学习过程中各基学习器之间互不干扰；而$\text{Boosting}$需要按顺序的学习若干个模型。也就是说，当前时刻学习的模型与前面时刻学习的模型之间存在关联关系。

关于$\text{Boosting}$算法思想可描述为如下步骤：

• 基于数据集合$\mathcal{D}$，以及一个初始状态下的基学习器$h_{init}$，并设计迭代次数$\mathcal{T}$；
• 使用数据集合$\mathcal{D}$训练基学习器$h_{init}$，并评估$h_{init}$对于$\mathcal{D}$的误差${ϵ}_{init}$；
• 将数据变换/重新采样，产生一个新数据集，记作${\mathcal{D}}_1$；根据误差${ϵ}_{init}$，继续训练下一个基学习器$h_1$，使得$h_1$会关注$h_{init}$预测误差更大的那些样本。
  可以看作${\mathcal{D}}_1$是$\mathcal{D}$的一个子集， 而${\mathcal{D}}_1$内主要包含$h_{init}$预测误差更大样本，而$h_{init}$预测误差小/准确的样本并不做过多关注。
• 重复执行$\text{2-3}$步骤，直到训练至基学习器$h_{\mathcal{T}}$，最终将$\mathcal{T}$个学习器 h = { h 1 , h 2 , ⋯   , h T } h = \{h_1,h_2,\cdots,h_{\mathcal T}\} h={h1​,h2​,⋯,hT​}进行加权结合，得到最终的预测模型。

$\text{Boosting}$算法系列里面有一些著名样例。如$\text{AdaBoost,Gradient Boosting}$等。本节对$\text{AdaBoost}$算法进行介绍。

基于加性模型融合方式的$\text{AdaBoost}$

场景构建

$\text{AdaBoost}$有多种推导方式，这里以加性模型($\text{Additive Model}$)作为基学习器的融合方式进行描述。而加性模型本质上就是各基学习器的线性组合：
$$\mathcal{H}(x)=\sum _{t=1}^{\mathcal{T}}{\alpha }_t\cdot h_t(x)$$
其中$x$表示具体样本；$\mathcal{H}(x)$表示融合后的预测模型；$h_t(x)$表示$t$时刻训练出的基学习器；${\alpha }_t$表示基学习器$h_t(x)$对应的权重信息；

已知数据集合$\mathcal{D}=\{(x^{(i)},y^{(i)}){\}}_{i=1}^N$，其中样本标签 y ( i ) ( i = 1 , 2 , ⋯   , N ) ∈ { + 1 , − 1 } y^{(i)}(i=1,2,\cdots,N) \in \{+1,-1\} y(i)(i=1,2,⋯,N)∈{+1,−1}。
这明显是一个关于‘二分类问题’的数据集合。

指数损失函数的理论意义

关于模型$\mathcal{H}(x)$的优化过程，使用的策略是 指数损失函数($\text{Exponential Loss Function}$)：
$$\begin{array}{rl}{\mathcal{L}}_{exp}(\mathcal{H}\mid \mathcal{D})& =\frac{1}{N}\sum _{i=1}^N\exp \left[-f(x^{(i)})\cdot \mathcal{H}(x^{(i)})\right]\\ & ={\mathbb{E}}_{x^{(i)}\sim \mathcal{D}}\left\{\exp \left[-f(x^{(i)})\cdot \mathcal{H}(x^{(i)})\right]\right\}\end{array}$$
其中$f(x)$表示真实函数/真实模型。最终目标是通过调整$\mathcal{H}(x)$中的权重信息$({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_{\mathcal{T}})$，使得损失函数${\mathcal{L}}_{exp}(\mathcal{H}\mid \mathcal{D})$达到最小：
$$\underset{{\alpha }_1,\cdots ,{\alpha }_t}{\mathrm{argmax}}{\mathcal{L}}_{exp}(\mathcal{H}\mid \mathcal{D})$$

由于${\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_{\mathcal{T}}$均是$\mathcal{H}(x)$中的项，首先基于损失函数对$\mathcal{H}(x)$求解偏导：
∂ ∂ H ( x ) [ L e x p ( H ∣ D ) ] = − f ( x ) ⋅ exp ⁡ { − f ( x ) ⋅ H ( x ) } \frac{\partial}{\partial \mathcal H(x)} \left[\mathcal L_{exp}(\mathcal H \mid \mathcal D)\right] = -f(x) \cdot \exp\{-f(x) \cdot \mathcal H(x)\} ∂H(x)∂​[Lexp​(H∣D)]=−f(x)⋅exp{−f(x)⋅H(x)}

• 由于$f(x)$是真实模型，根据样本标签的描述，$f(x)$只可能返回两个结果： { − 1 , 1 } \{-1,1\} {−1,1}。从概率分布的角度观察，$f(x)$表示如下：
  $$f(x)=\{\begin{array}{l}\mathcal{P}(f(x)=1\mid x)\\ \mathcal{P}(f(x)=-1\mid x)\end{array}$$
• 至此，可以将$f(x)$的概率分布表示代入到上述公式中，最终可得到如下形式：
  ∂ ∂ H ( x ) [ L e x p ( H ∣ D ) ] = − exp ⁡ { − H ( x ) } ⋅ P ( f ( x ) = 1 ∣ x ) + exp ⁡ { H ( x ) } ⋅ P ( f ( x ) = − 1 ∣ x ) \begin{aligned} \frac{\partial}{\partial \mathcal H(x)} \left[\mathcal L_{exp}(\mathcal H \mid \mathcal D)\right] & = - \exp \{-\mathcal H(x)\} \cdot \mathcal P(f(x) = 1 \mid x) + \exp\{\mathcal H(x)\} \cdot \mathcal P(f(x) = -1 \mid x) \end{aligned} ∂H(x)∂​[Lexp​(H∣D)]​=−exp{−H(x)}⋅P(f(x)=1∣x)+exp{H(x)}⋅P(f(x)=−1∣x)​

令偏导$\frac{\partial }{\partial \mathcal{H}(x)}\left[{\mathcal{L}}_{exp}(\mathcal{H}\mid \mathcal{D})\right]\triangleq 0$，求得$\mathcal{H}(x)$可表示为如下形式：
exp ⁡ { − H ( x ) } ⋅ P ( f ( x ) = 1 ∣ x ) + exp ⁡ { H ( x ) } ⋅ P ( f ( x ) = − 1 ∣ x ) ≜ 0 ⇒ [ exp ⁡ { H ( x ) } ] 2 ⋅ P [ f ( x ) = − 1 ∣ x ] = P [ f ( x ) = 1 ∣ x ] ⇒ H ( x ) = 1 2 ln ⁡ [ P ( f ( x ) = 1 ∣ x ) P ( f ( x ) = − 1 ∣ x ) ] \begin{aligned} & \exp \{-\mathcal H(x)\} \cdot \mathcal P(f(x) = 1 \mid x) + \exp\{\mathcal H(x)\} \cdot \mathcal P(f(x) = -1 \mid x) \triangleq 0 \\ & \Rightarrow \left[\exp\{\mathcal H(x)\}\right]^2 \cdot \mathcal P \left[f(x) = -1 \mid x\right] = \mathcal P [f(x) = 1 \mid x] \\ & \Rightarrow \mathcal H(x) = \frac{1}{2} \ln \left[\frac{\mathcal P(f(x) = 1 \mid x)}{\mathcal P(f(x) = -1 \mid x)}\right] \end{aligned} ​exp{−H(x)}⋅P(f(x)=1∣x)+exp{H(x)}⋅P(f(x)=−1∣x)≜0⇒[exp{H(x)}]2⋅P[f(x)=−1∣x]=P[f(x)=1∣x]⇒H(x)=21​ln[P(f(x)=−1∣x)P(f(x)=1∣x)​]​
由于在该任务中，预测模型$\mathcal{H}(x)$同样也是判别模型。令$\text{Sign}$为指示函数，关于$\mathcal{H}(x)$的指示函数$\text{Sign}[\mathcal{H}(x)]$可表示为：
这里没有考虑$\mathcal{P}(f(x)=1\mid x)=\mathcal{P}(f(x)=-1\mid x)$的情况。这种情况$\mathcal{H}(x)=0$,随机选择一项即可。
Sign [ H ( x ) ] = { 1 H ( x ) > 0 ⇔ P ( f ( x ) = 1 ∣ x ) > P ( f ( x ) = − 1 ∣ x ) − 1 H ( x ) < 0 ⇔ P ( f ( x ) = 1 ∣ x ) < P ( f ( x ) = − 1 ∣ x ) = arg ⁡ max ⁡ y ∈ { − 1 , 1 } P ( f ( x ) = y ∣ x ) \begin{aligned} \text{Sign} \left[\mathcal H(x)\right] & = \begin{cases} 1 \quad \mathcal H(x) > 0 \Leftrightarrow \mathcal P(f(x) = 1 \mid x) > \mathcal P(f(x) = -1 \mid x) \\ -1 \quad \mathcal H(x) < 0 \Leftrightarrow \mathcal P(f(x) = 1 \mid x) < \mathcal P(f(x) = -1 \mid x) \end{cases} \\ & = \mathop{\arg\max}\limits_{y \in \{-1,1\}} \mathcal P(f(x) = y \mid x) \end{aligned} Sign[H(x)]​={1H(x)>0⇔P(f(x)=1∣x)>P(f(x)=−1∣x)−1H(x)<0⇔P(f(x)=1∣x)<P(f(x)=−1∣x)​=y∈{−1,1}argmax​P(f(x)=y∣x)​
由于原本的任务是二分类任务，因而在定义域中它并不是连续的。但如果使用指数损失函数来替代这个分段函数，能够得到相同的效果。这也是指数损失函数的理论意义。
指数损失函数的最大特点就是该函数连续、可微。该函数在迭代获取最优参数起到关键作用。

$t$时刻权重参数${\alpha }_t$的求解过程

由于第一个基学习器$h_1$是由原始数据$\mathcal{D}$以及初始数据分布${\mathcal{D}}_1(x)$学习得到。以此类推；如果第$t$次迭代得到基学习器$h_t(x)$以及对应的权重参数${\alpha }_t$，那么仅仅该学习器也同样满足指数损失函数最小：
$$\text{Select }{\alpha }_t\Rightarrow \min {\mathcal{L}}_{exp}\left[{\alpha }_t{h}_t(x)\mid {\mathcal{D}}_t\right]$$
将${\mathcal{L}}_{exp}\left[{\alpha }_t{h}_t(x)\mid {\mathcal{D}}_t\right]$展开，可表示为如下形式：
L e x p [ α t h t ( x ) ∣ D t ] = E x ∼ D t { exp ⁡ [ − f ( x ) ⋅ α t h t ( x ) ] } \mathcal L_{exp} \left[\alpha_th_t(x) \mid \mathcal D_t\right] = \mathbb E_{x \sim \mathcal D_t} \left\{\exp[-f(x) \cdot \alpha_th_t(x)]\right\} Lexp​[αt​ht​(x)∣Dt​]=Ex∼Dt​​{exp[−f(x)⋅αt​ht​(x)]}
观察$\exp$内的项：$-f(x)\cdot {\alpha }_t{h}_t(x)=-{\alpha }_t\cdot f(x)h_t(x)$，其中$f(x)h_t(x)$表示结果如下：
无论是$f(x)$还是$t$时刻的$h_t(x)$,它们都描述二分类任务的函数结果： { − 1 , + 1 } \{-1,+1\} {−1,+1},因而存在如下两种匹配情况：
$$f(x)h_t(x)=\{\begin{array}{l}1f(x)=h_t(x)\\ -1f(x)\ne h_t(x)\end{array}$$
至此，可以通过指示函数$\mathbb{I}(\cdot )$对${\mathcal{L}}_{exp}\left[{\alpha }_t{h}_t(x)\mid {\mathcal{D}}_t\right]$进行表示：
L e x p [ α t h t ( x ) ∣ D t ] = E x ∼ D t { exp ⁡ [ − α t ⋅ f ( x ) h t ( x ) ] } = E x ∼ D t { exp ⁡ { − α t } ⋅ I [ f ( x ) = h t ( x ) ] + exp ⁡ { − α t } ⋅ I [ f ( x ) ≠ h t ( x ) ] } = 1 N ∑ x ∼ D t { exp ⁡ { − α t } ⋅ I [ f ( x ) = h t ( x ) ] + exp ⁡ { − α t } ⋅ I [ f ( x ) ≠ h t ( x ) ] } = exp ⁡ { − α t } ⋅ P x ∼ D t [ f ( x ) = h t ( x ) ] + exp ⁡ { α t } ⋅ P x ∼ D t [ f ( x ) ≠ h t ( x ) ] = exp ⁡ { − α t } ⋅ ( 1 − ϵ t ) + exp ⁡ { α t } ⋅ ϵ t \begin{aligned} \mathcal L_{exp} \left[\alpha_th_t(x) \mid \mathcal D_t\right] & = \mathbb E_{x \sim \mathcal D_t} \left\{\exp[-\alpha_t \cdot f(x)h_t(x)]\right\} \\ & = \mathbb E_{x \sim \mathcal D_t}\{\exp\{-\alpha_t\} \cdot \mathbb I[f(x) = h_t(x)] + \exp\{-\alpha_t\} \cdot \mathbb I[f(x) \neq h_t(x)]\} \\ & = \frac{1}{N}\sum_{x \sim \mathcal D_t} \{\exp\{-\alpha_t\} \cdot \mathbb I[f(x) = h_t(x)] + \exp\{-\alpha_t\} \cdot \mathbb I[f(x) \neq h_t(x)]\} \\ & = \exp\{-\alpha_t\} \cdot \mathcal P_{x \sim \mathcal D_t} \left[f(x) = h_t(x)\right] + \exp\{\alpha_t\} \cdot P_{x \sim \mathcal D_t} \left[f(x) \neq h_t(x)\right] \\ & = \exp\{-\alpha_t\} \cdot (1 - \epsilon_t) + \exp\{\alpha_t\} \cdot \epsilon_t \end{aligned} Lexp​[αt​ht​(x)∣Dt​]​=Ex∼Dt​​{exp[−αt​⋅f(x)ht​(x)]}=Ex∼Dt​​{exp{−αt​}⋅I[f(x)=ht​(x)]+exp{−αt​}⋅I[f(x)=ht​(x)]}=N1​x∼Dt​∑​{exp{−αt​}⋅I[f(x)=ht​(x)]+exp{−αt​}⋅I[f(x)=ht​(x)]}=exp{−αt​}⋅Px∼Dt​​[f(x)=ht​(x)]+exp{αt​}⋅Px∼Dt​​[f(x)=ht​(x)]=exp{−αt​}⋅(1−ϵt​)+exp{αt​}⋅ϵt​​

其中${ϵ}_t(t=1,2,\cdots ,\mathcal{T})$描述为：
${ϵ}_t$是一个值域是$[0,1]$的值，它表示属于数据集${\mathcal{D}}_t$满足$f(x)\ne h_t(x)$的样本$x$的数量占据数据集${\mathcal{D}}_t$总体数量的比例。
$$\begin{array}{rl}{ϵ}_t& ={\mathcal{P}}_{x\sim {\mathcal{D}}_t}[f(x)\ne h_t(x)]\\ & =\frac{\sum [f(x)\ne h_t(x){]}_{x\sim {\mathcal{D}}_t}}{N}\end{array}$$
基于化简后的${\mathcal{L}}_{exp}\left[{\alpha }_t{h}_t(x)\mid {\mathcal{D}}_t\right]$，对权重参数${\alpha }_t$求解偏导：
∂ ∂ α t L e x p [ α t h t ( x ) ∣ D t ] = − exp ⁡ { − α t } ⋅ ( 1 − ϵ t ) + exp ⁡ { α t } ⋅ ϵ t \frac{\partial}{\partial \alpha_t}\mathcal L_{exp} \left[\alpha_th_t(x) \mid \mathcal D_t\right] = -\exp\{-\alpha_t\} \cdot (1 - \epsilon_t) + \exp\{\alpha_t\} \cdot \epsilon_t ∂αt​∂​Lexp​[αt​ht​(x)∣Dt​]=−exp{−αt​}⋅(1−ϵt​)+exp{αt​}⋅ϵt​
令$\frac{\partial }{\partial {\alpha }_t}{\mathcal{L}}_{exp}\left[{\alpha }_t{h}_t(x)\mid {\mathcal{D}}_t\right]\triangleq 0$，求出${\alpha }_t$的最优解：
$${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$$

关于$t$时刻对于过去时刻错误的纠正过程

我们仅仅求解出$t$时刻的最优解是不够的，我们更希望新一轮产生的基学习器$h_t(x)$能够纠正前一轮预测模型${\mathcal{H}}_{t-1}(x)$中的错误。

通过数学语言表达则是：新一轮产生的预测模型${\mathcal{H}}_t(x)={\mathcal{H}}_{t-1}(x)+{\alpha }_t{h}_t$能够使损失函数${\mathcal{L}}_{exp}[{\mathcal{H}}_t(x)\mid \mathcal{D}]$达到最小。
需要注意的点：此时的预测模型${\mathcal{H}}_t(x)$是从初始时刻开始到$t$时刻的‘加权模型’结果。它并非仅仅针对于$t$时刻采样数据集${\mathcal{D}}_t$,而是完整数据集$\mathcal{D}$.
L e x p [ H t ( x ) ∣ D ] = E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] = E x ∼ D [ exp ⁡ { − f ( x ) ⋅ ( H t − 1 ( x ) + h t ( x ) ) } ] = E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ exp ⁡ { − f ( x ) ⋅ h t ( x ) } ] \begin{aligned} \mathcal L_{exp}[\mathcal H_t(x) \mid \mathcal D] & = \mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x) \cdot \mathcal H_t(x)\}\right] \\ & = \mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x) \cdot (\mathcal H_{t-1}(x) + h_t(x))\}\right] \\ & = \mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot \exp\{-f(x) \cdot h_t(x)\}\right] \end{aligned} Lexp​[Ht​(x)∣D]​=Ex∼D​[exp{−f(x)⋅Ht​(x)}]=Ex∼D​[exp{−f(x)⋅(Ht−1​(x)+ht​(x))}]=Ex∼D​[exp{−f(x)⋅Ht−1​(x)}⋅exp{−f(x)⋅ht​(x)}]​
观察项 exp ⁡ { − f ( x ) ⋅ h t ( x ) } \exp\{-f(x)\cdot h_t(x)\} exp{−f(x)⋅ht​(x)}，可以使用泰勒公式将其展开成如下形式：
由于‘真实函数’$f(x)$,基学习器$h_t(x)$的值域均是 { − 1 , + 1 } \{-1,+1\} {−1,+1}，因而有$f^2(x)=h_t^2(x)=1$
exp ⁡ { − f ( x ) ⋅ h t ( x ) } = 1 − f ( x ) ⋅ h t ( x ) + f 2 ( x ) ⋅ h t 2 ( x ) 2 = 1 − f ( x ) ⋅ h t ( x ) + 1 2 \begin{aligned} \exp\{-f(x)\cdot h_t(x)\} & = 1 - f(x) \cdot h_t(x) + \frac{f^2(x) \cdot h_t^2(x)}{2} \\ & = 1 - f(x) \cdot h_t(x) + \frac{1}{2} \end{aligned} exp{−f(x)⋅ht​(x)}​=1−f(x)⋅ht​(x)+2f2(x)⋅ht2​(x)​=1−f(x)⋅ht​(x)+21​​
从而${\mathcal{L}}_{exp}[{\mathcal{H}}_t(x)\mid \mathcal{D}]$可表示为如下形式：
L e x p [ H t ( x ) ∣ D ] = E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ ( 1 − f ( x ) ⋅ h t ( x ) + 1 2 ) ] \mathcal L_{exp}[\mathcal H_t(x) \mid \mathcal D] = \mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot \left(1 - f(x) \cdot h_t(x) + \frac{1}{2}\right)\right] Lexp​[Ht​(x)∣D]=Ex∼D​[exp{−f(x)⋅Ht−1​(x)}⋅(1−f(x)⋅ht​(x)+21​)]
因而，基于纠错后$t$时刻最优基学习器可表示为：

• 将上面式子代入~
• 其中常数$1,\frac{1}{2}$均不影响最值的取值，消掉;
• 将$-f(x)\cdot h_t(x)$中的负号提到前面，将$\underset{h_t(x)}{\mathrm{argmin}}$改成$\underset{h_t(x)}{\mathrm{argmax}}$
  h ^ t ( x ) = arg ⁡ min ⁡ h t ( x ) L e x p [ H t ( x ) ∣ D ] = arg ⁡ min ⁡ h t ( x ) L e x p [ H t − 1 ( x ) + h t ( x ) ∣ D ] = arg ⁡ min ⁡ h t ( x ) { E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ ( 1 − f ( x ) ⋅ h t ( x ) + 1 2 ) ] } = arg ⁡ max ⁡ h t ( x ) { E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ f ( x ) ⋅ h t ( x ) ] } \begin{aligned} \hat h_t(x) & = \mathop{\arg\min}\limits_{h_t(x)} \mathcal L_{exp} [\mathcal H_t(x) \mid \mathcal D] \\ & = \mathop{\arg\min}\limits_{h_t(x)} \mathcal L_{exp} \left[\mathcal H_{t-1}(x) + h_t(x) \mid \mathcal D\right] \\ & = \mathop{\arg\min}\limits_{h_t(x)} \left\{\mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot \left(1 - f(x) \cdot h_t(x) + \frac{1}{2}\right)\right]\right\} \\ & = \mathop{\arg\max}\limits_{h_t(x)} \left\{\mathbb E_{x \sim \mathcal D} \left[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot f(x) \cdot h_t(x)\right]\right\} \end{aligned} h^t​(x)​=ht​(x)argmin​Lexp​[Ht​(x)∣D]=ht​(x)argmin​Lexp​[Ht−1​(x)+ht​(x)∣D]=ht​(x)argmin​{Ex∼D​[exp{−f(x)⋅Ht−1​(x)}⋅(1−f(x)⋅ht​(x)+21​)]}=ht​(x)argmax​{Ex∼D​[exp{−f(x)⋅Ht−1​(x)}⋅f(x)⋅ht​(x)]}​

这里添加一个技巧：将上述结果乘以一个常数： 1 E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] \frac{1}{\mathbb E_{x \sim \mathcal D} \left[\exp \{-f(x) \cdot \mathcal H_{t-1}(x)\}\right]} Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]1​

• 首先，乘以一个常数并不影响上述公式最值的取值;
• 其次，由于${\mathcal{H}}_{t-1}(x)$是上一次迭代产生的预测模型，是已知项;因而 E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] \mathbb E_{x \sim \mathcal D} \left[\exp \{-f(x) \cdot \mathcal H_{t-1}(x)\}\right] Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]是一个已知项，是一个常数。
  h ^ t ( x ) = arg ⁡ max ⁡ h t ( x ) { E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] ⋅ f ( x ) ⋅ h t ( x ) ] } \hat h_t(x) = \mathop{\arg\max}\limits_{h_t(x)} \left\{\mathbb E_{x \sim \mathcal D} \left[\frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]} \cdot f(x) \cdot h_t(x)\right]\right\} h^t​(x)=ht​(x)argmax​{Ex∼D​[Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]exp{−f(x)⋅Ht−1​(x)}​⋅f(x)⋅ht​(x)]}

此时，第一项 exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] \begin{aligned}\frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]}\end{aligned} Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]exp{−f(x)⋅Ht−1​(x)}​​整个就是一个常数项，并且分子是分母的一部分。由于期望自身就是积分，可以直接将这个常数项提出去：
h ^ t ( x ) = arg ⁡ max ⁡ h t ( x ) { exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] ⋅ E x ∼ D [ f ( x ) ⋅ h t ( x ) ] } \hat h_t(x) = \mathop{\arg\max}\limits_{h_t(x)} \left\{\frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]} \cdot \mathbb E_{x \sim \mathcal D} \left[f(x) \cdot h_t(x)\right]\right\} h^t​(x)=ht​(x)argmax​{Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]exp{−f(x)⋅Ht−1​(x)}​⋅Ex∼D​[f(x)⋅ht​(x)]}
核心思路：将这个常数项直接映射到数据基$\mathcal{D}$的特征空间中，相当于数据集合$\mathcal{D}$中的所有样本乘了一个常数项；并从这个集合中重新采样：

• 令 D t = exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] ⋅ D \begin{aligned}\mathcal D_t = \frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]} \cdot \mathcal D\end{aligned} Dt​=Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]exp{−f(x)⋅Ht−1​(x)}​⋅D​，此时将采样分布从$\mathcal{D}$映射到了${\mathcal{D}}_t$
  h ^ t ( x ) = arg ⁡ max ⁡ h t ( x ) { E x ∼ D t [ f ( x ) ⋅ h t ( x ) ] } D t = exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] ⋅ D \hat h_t(x) = \mathop{\arg\max}\limits_{h_t(x)} \left\{ \mathbb E_{x \sim \mathcal D_t} \left[f(x) \cdot h_t(x)\right]\right\} \quad \mathcal D_t = \frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]} \cdot \mathcal D h^t​(x)=ht​(x)argmax​{Ex∼Dt​​[f(x)⋅ht​(x)]}Dt​=Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]exp{−f(x)⋅Ht−1​(x)}​⋅D

又因为$f(x),h(x)$的值域均为 { − 1 , + 1 } \{-1,+1\} {−1,+1}，那么$f(x)\cdot h(x)$结果可表示为如下形式：
$$f(x)\cdot h(x)=\{\begin{array}{l}1h(x)=f(x)\\ -1h(x)\ne f(x)\end{array}$$
使用一个式子表示，有：
$\mathbb{I}$表示指示函数。
$$f(x)\cdot h(x)=1-2\cdot \mathbb{I}[f(x)\ne h(x)]$$
将该式子带回上式，有：

• 下式中的常数(系数)$1,2$都可以消掉，将负号与$\underset{h_t(x)}{\mathrm{argmax}}$合并成$\underset{h_t(x)}{\mathrm{argmin}}$.
• 机器学习(西瓜书)P176.
  h ^ t ( x ) = arg ⁡ max ⁡ h t ( x ) { E x ∼ D t [ f ( x ) ⋅ h t ( x ) ] } = arg ⁡ max ⁡ h t ( x ) { E x ∼ D t [ 1 − 2 ⋅ I [ f ( x ) ≠ h t ( x ) ] ] } = arg ⁡ min ⁡ h t ( x ) { E x ∼ D t [ I [ f ( x ) ≠ h t ( x ) ] ] } \begin{aligned} \hat h_t(x) & = \mathop{\arg\max}\limits_{h_t(x)} \left\{ \mathbb E_{x \sim \mathcal D_t} \left[f(x) \cdot h_t(x)\right]\right\} \\ & = \mathop{\arg\max}\limits_{h_t(x)} \left\{ \mathbb E_{x \sim \mathcal D_t} \left[1 - 2 \cdot \mathbb I[f(x) \neq h_t(x)]\right]\right\} \\ & = \mathop{\arg\min}\limits_{h_t(x)} \{\mathbb E_{x \sim \mathcal D_t} [\mathbb I[f(x) \neq h_t(x)]]\} \end{aligned} h^t​(x)​=ht​(x)argmax​{Ex∼Dt​​[f(x)⋅ht​(x)]}=ht​(x)argmax​{Ex∼Dt​​[1−2⋅I[f(x)=ht​(x)]]}=ht​(x)argmin​{Ex∼Dt​​[I[f(x)=ht​(x)]]}​

至此，可以发现，$t$时刻我们的最优基学习器${\hat{h}}_t(x)$是可以直接从分布${\mathcal{D}}_t$中进行学习的，而不是仅被局限于原始数据集$\mathcal{D}$。继续观察上述最优化的项：
$${\mathbb{E}}_{x\sim {\mathcal{D}}_t}[\mathbb{I}[f(x)\ne h(x)]]=\frac{1}{N}\sum _{i=1}^N\mathbb{I}\left[f(x^{(i)})\ne h(x^{(i)})\right]$$
该一共$N$个项，并且每一项的值域为 { 0 , 1 } \{0,1\} {0,1}，那么这个期望结果必然是一个$[0,1]$之间的值：

• 如果${\mathbb{E}}_{x\sim {\mathcal{D}}_t}[\mathbb{I}[f(x)\ne h(x)]]=1$，那意味着第$t$次迭代产生的$h_t(x)$的学习结果与真实模型的结果一个都对不上，全错；
• 相反，${\mathbb{E}}_{x\sim {\mathcal{D}}_t}[\mathbb{I}[f(x)\ne h(x)]]=0$，那么所有样本全部学对了。

当然，上述是极端情况。一般情况下，我们希望这个误差$<0.5$，意味着第$t$次迭代对于样本的学习结果如果有一半以上没有学习正确，那就没有学习的必要了。

与此同时，${\mathcal{D}}_t$不是凭空生成的，也是经过一次又一次的迭代产生的。关于${\mathcal{D}}_{t+1}$和${\mathcal{D}}_t$之间的关系表示如下：

• 将${\mathcal{H}}_t(x)={\mathcal{H}}_{t-1}(x)+{\alpha }_t{h}_t(x)$代入。
• 将上面的${\mathcal{D}}_t$与$\mathcal{D}$之间的关系代入。 D = D t ⋅ E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } \begin{aligned}\mathcal D = \frac{\mathcal D_t \cdot \mathbb E_{x \sim \mathcal D}[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]}{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}\end{aligned} D=exp{−f(x)⋅Ht−1​(x)}Dt​⋅Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]​​
  D t + 1 = exp ⁡ { − f ( x ) ⋅ H t ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] ⋅ D = exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ exp ⁡ { − f ( x ) ⋅ α t h t ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] ⋅ D = exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ⋅ exp ⁡ { − f ( x ) ⋅ α t h t ( x ) } E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] ⋅ D t ⋅ E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } = D t ⋅ exp ⁡ { − f ( x ) ⋅ α t h t ( x ) } ⋅ E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] \begin{aligned} \mathcal D_{t+1} & = \frac{\exp\{-f(x)\cdot \mathcal H_{t}(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t}(x)\}]} \cdot \mathcal D \\ & = \frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot \exp\{-f(x) \cdot \alpha_th_t(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t}(x)\}]} \cdot \mathcal D \\ & = \frac{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\} \cdot \exp\{-f(x) \cdot \alpha_th_t(x)\}}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x)\cdot \mathcal H_{t}(x)\}]} \cdot \frac{\mathcal D_t \cdot \mathbb E_{x \sim \mathcal D}[\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}]}{\exp\{-f(x)\cdot \mathcal H_{t-1}(x)\}}\\ & = \mathcal D_t \cdot \exp\{-f(x) \cdot \alpha_th_t(x)\} \cdot \frac{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x) \cdot \mathcal H_{t-1}(x)\}]}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x) \cdot \mathcal H_t(x)\}]} \end{aligned} Dt+1​​=Ex∼D​[exp{−f(x)⋅Ht​(x)}]exp{−f(x)⋅Ht​(x)}​⋅D=Ex∼D​[exp{−f(x)⋅Ht​(x)}]exp{−f(x)⋅Ht−1​(x)}⋅exp{−f(x)⋅αt​ht​(x)}​⋅D=Ex∼D​[exp{−f(x)⋅Ht​(x)}]exp{−f(x)⋅Ht−1​(x)}⋅exp{−f(x)⋅αt​ht​(x)}​⋅exp{−f(x)⋅Ht−1​(x)}Dt​⋅Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]​=Dt​⋅exp{−f(x)⋅αt​ht​(x)}⋅Ex∼D​[exp{−f(x)⋅Ht​(x)}]Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]​​

$\text{AdaBoost}$算法流程

至此，关于加性模型的推导过程全部结束。可以观察一下基于加性模型下$\text{AdaBoost}$的算法流程：

• 给定训练数据集 D = { x ( i ) , y ( i ) } i = 1 N \mathcal D =\{x^{(i)},y^{(i)}\}_{i=1}^N D={x(i),y(i)}i=1N​；基学习算法$\mathcal{K}$，迭代次数$\mathcal{T}$；
  基学习算法$\mathcal{K}$就是产生基学习器算法方式。它通过已知数据集$\mathcal{D}$和作用于数据集的分布参数${\mathcal{D}}_t$共同实现。
• 初始化分布参数为均匀分布，对任意样本的采样概率均相同。${\mathcal{D}}_{init}=\frac{1}{N}$
• 迭代过程：首先通过$\mathcal{K}$得到当前迭代步骤的基学习器$h_t(x)$；
• 统计$h_t(x)$预测结果与真实函数(真实标签)之间的差异${ϵ}_t$:
  $${ϵ}_t={\mathcal{P}}_{x\sim {\mathcal{D}}_t}(h(x)\ne f(x))$$
• 如果该值大于$0.5$，意味着至少一半的样本均学习错误，停止迭代；
• 否则，计算该时刻的权重参数${\alpha }_t$:
  $${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$$
• 最终更新下一时刻的分布参数${\mathcal{D}}_{t+1}$：
  其中配分项$\frac{1}{{\mathcal{Z}}_t}$是关于$t$时刻的项。并且 1 Z t = E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t − 1 ( x ) } ] E x ∼ D [ exp ⁡ { − f ( x ) ⋅ H t ( x ) } ] \begin{aligned}\frac{1}{\mathcal Z_t} = \frac{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x) \cdot \mathcal H_{t-1}(x)\}]}{\mathbb E_{x \sim \mathcal D} [\exp\{-f(x) \cdot \mathcal H_t(x)\}]}\end{aligned} Zt​1​=Ex∼D​[exp{−f(x)⋅Ht​(x)}]Ex∼D​[exp{−f(x)⋅Ht−1​(x)}]​​
  D t + 1 ⇐ 1 Z t ⋅ D t ⋅ exp ⁡ { − f ( x ) ⋅ α t h t ( x ) } \mathcal D_{t+1} \Leftarrow \frac{1}{\mathcal Z_t} \cdot \mathcal D_t \cdot \exp\{-f(x) \cdot \alpha_th_t(x)\} Dt+1​⇐Zt​1​⋅Dt​⋅exp{−f(x)⋅αt​ht​(x)}
• 直到$\mathcal{T}$次迭代结束，得到最终结果。

最终输出：

• 每次迭代产生的基学习器$h_t(x)(t=1,2,\cdots ,\mathcal{T})$；
• 每次迭代更新的权重参数${\alpha }_t(t=1,2,\cdots ,\mathcal{T})$

至此，$\text{AdaBoost}$的推导过程结束。下一节将介绍$\text{Gradient Boosting}$。

相关参考：
机器学习(周志华著)