集成学习

1. 集成学习(ensemble learning)是通过构建并结合多个学习器来完成学习任务。其一般结构为：

• 先产生一组个体学习器(individual learner) 。个体学习器通常由一种或者多种现有的学习算法从训练数据中产生。

  • 如果个体学习器都是从某一种学习算法从训练数据中产生，则称这样的集成学习是同质的(homogenerous)。

    此时的个体学习器也称作基学习器(base learner)，相应的学习算法称作基学习算法(base learning algoruthm)。

  • 如果个体学习器是从某几种学习算法从训练数据中产生，则称这样的集成学习是异质的(heterogenous)。

    异质集成中的个体学习器由不同的学习算法组成，这时就不再有基学习算法；相应的，个体学习器一般不称为基学习器，常称为组件学习器(component learner)或直接称为个体学习器。

• 再使用某种策略将它们结合起来。集成学习通过将多个学习器进行组合，通常可以获得比单一学习器显著优越的泛化性能。

2. 通常选取个体学习器的准则是：

• 个体学习器要有一定的准确性，预测能力不能太差。
• 个体学习器之间要有多样性，即学习器之间要有差异。

3. 通常基于实际考虑，往往使用预测能力较强的个体学习器（即强学习器，与之对应的为弱学习器）。

   强学习器的一个显著的好处就是可以使用较少数量的个体学习器来集成就可以获得很好的效果。

4. 根据个体学习器的生成方式，目前的集成学习方法大概可以分作两类：

• 个体学习器之间存在强依赖关系、必须串行生成的序列化方法，每一轮迭代产生一个个体学习器。其中以Boosting为代表。
• 个体学习器之间不存在强依赖关系、可同时生成的并行化方法。其中以Bagging和随机森林Random Forest为代表。

一、集成学习误差

1. 考虑一个二分类问题$y\in\left \{-1,+1 \right \}$y∈{−1,+1}和真实函数$f$f，假定基分类器的错误率为$\varepsilon$ε，即对每个基分类器$h_i$hi​有
   $P(h_i(\mathbf x)\neq f(\mathbf x))=\varepsilon\tag{1}$P(hi​(x)̸​=f(x))=ε(1)

   • 假设集成学习通过简单投票法结合$T$T个基分类器，若有超过半数的基分类器正确，则集成分类就正确。根据描述，给出集成学习器为：
     $H(\mathbf x)=sign\left (\sum_{i=1}^{T}h_i(\mathbf x) \right )\tag{2}$H(x)=sign(i=1∑T​hi​(x))(2)

   • 假设基分类器的错误率相互独立，则由Hoeffding不等式可知，集成的错误率为：
     $P(H(\mathbf x)\neq f(\mathbf x))=\sum_{k=0}^{\left \lfloor T/2 \right \rfloor} {^{T}\textrm{C}_k}(1-\varepsilon)^k\varepsilon^{T-k}\\ \leqslant exp(-\frac{1}{2}T(1-2\varepsilon)^2)\tag{3}$P(H(x)̸​=f(x))=k=0∑⌊T/2⌋​TCk​(1−ε)kεT−k⩽exp(−21​T(1−2ε)2)(3)
     上式显示出，随着继承中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。

     $\left \lfloor\ \ \right \rfloor$⌊  ⌋：floor函数，向下取整。

2. 上面的分析有一个关键假设：基学习器的误差相互独立。

   • 实际上个体学习器是为了解决同一个问题训练出来的，而且可能是同一类算法从同一个训练集中产生。

     这样个体学习器的错误率显然不能相互独立。

   • 实际上个体学习器的准确性和多样性本身就存在冲突。

     • 通常个体学习器的准确性很高之后，要增加多样性就需要牺牲准确性。
     • 实际上如何产生并结合”好而不同“的个体学习器就是集成学习研究的核心。

3. 根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类。

   • 个体学习器间存在强依赖关系，必须串行生成的序列化方法，代表是Boosting。
   • 个体学习器间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和随机森林(Random Forest)。

假设硬币正面朝上的概率为$p$p，反面朝上的概率为$1-p$1−p。令$H(n)$H(n)代表抛$n$n次硬币所得正面朝上的次数，则最多$k$k次正面朝上的概率为（二项分布）：
$P(H(n)\leqslant k)=\sum_{i=1}^{k}{^{n}\textrm{C}_i}p^i(1-p)^{1-i}$P(H(n)⩽k)=i=1∑k​nCi​pi(1−p)1−i
对$\delta>0$δ>0，$k=(p-\delta)n$k=(p−δ)n有Hoeffding不等式：
$P(H(n)\leqslant (p-\delta)n)\leqslant e^{-2\delta^2n}$P(H(n)⩽(p−δ)n)⩽e−2δ2n
式(3)推导过程：由基分类器相互独立，设$X$X为$T$T个基分类器分类正确的次数，则该实验服从二项分布$X\sim B(T,1-\epsilon)→(n,p)$X∼B(T,1−ϵ)→(n,p)
$P(H(\mathbf x)\neq f(\mathbf x))=P(X\leqslant\left \lfloor T/2 \right \rfloor) \leqslant P(X\leqslant \frac{1}{2})$P(H(x)̸​=f(x))=P(X⩽⌊T/2⌋)⩽P(X⩽21​)
此处与Hoeffding不等时中对应关系为：$X→H(n)$X→H(n)，$\frac{T}{2}→k$2T​→k，$1-\epsilon→p$1−ϵ→p，$T→n$T→n

带入$k=(p-\delta)n)$k=(p−δ)n)，有$\frac{T}{2}=(1-\epsilon-\delta)T$2T​=(1−ϵ−δ)T，得到$\delta=\frac{1-2\epsilon}{2}$δ=21−2ϵ​，由此得到式(8.3)。

二、Boosting

1. 提升方法(boosting) 是一种常用的统计学习方法。在分类问题中，它通过改变训练样本的权重学习多个分类器，并将这些分类器们进行线性组合来提高分类的能力。

2. 提升方法的基本思想是：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断要好。类似于”三个臭皮匠顶一个诸葛亮“。

3. 提升方法的理论基础是：强可学习与弱可学习是等价的。

   在概率近似正确(probably approximately correct,PAC)学习的框架下：

   • 强可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它并且正确率很高，那么称这个概念是强可学习的。
   • 弱可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么称这个概念是弱可学习的。

   可以证明：强可学习与弱可学习是等价的。

   即：若在学习中发现了 ”弱学习算法“ ，则可以通过某些办法将它提升为 ”强学习算法“。

4. 对于分类问题而言，求一个比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）要容易得多。

5. Boosting就是一族可以将弱学习器提升为强学习器的算法。

   这族算法的工作原理类似：

   • 先从初始训练集训练出一个基学习器。
   • 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注。
   • 然后基于调整后的样本分布来训练下一个基学习器。
   • 如此重复，直到基学习器数量达到事先指定的值T。
   • 最终将这T个基学习器进行加权组合。

2.1 AdaBoost算法

1. Boosting族算法最著名的代表是AdaBoost算法。

2. AdaBoot算法两个核心步骤：

   • 每一轮中如何改变训练数据的权值？

     AdaBoost算法提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

     于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。

   • 最后如何将一系列弱分类器组合成一个强分类器？

     AdaBoost采用加权多数表决的方法：

     • 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
     • 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

3. AdaBoost算法有两个特点：

   • 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用。

     • 因此AdaBoost要求基本学习器能够对特定的数据分布进行学习，这可通过重赋权法(re-weighting)实施，即在训练的 每一轮中，根据样本分布为每个训练样本重新赋予一个权重。
     • 对于无法接受带权样本的基本学习算法，则可以通过重采样法(re-sampling)来处理：即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样的样本集对基本学习器进行训练。
     • 一般而言这两者没有显著的优劣差别。

   • 利用基本分类器的线性组合$f(\mathbf x)=\sum_{t=1}^{T}\alpha_th_t(\mathbf x)$f(x)=∑t=1T​αt​ht​(x)构成最终分类器：
     $H(\mathbf x)=sign(f(\mathbf x))=sign \left (\sum_{t=1}^{T}\alpha_th_t(\mathbf x)\right)$H(x)=sign(f(x))=sign(t=1∑T​αt​ht​(x))
     其中：

     • $f(\mathbf x)$f(x)的符号决定实例$\mathbf x$x的分类。
     • $f(\mathbf x)$f(x)的绝对值表示分类的确信度。

4. 从偏差-方差角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

5. AdaBoost算法具有自适应性，即它能够自动适应弱分类器各自的训练误差率，这也是它的名字（适应的提升）的由来。

6. AdaBoost算法的描述如图，其中$y_i\in\left \{-1,+1 \right \}$yi​∈{−1,+1}，$f$f是真实函数。

2.2 AdaBoost算法

1. AdaBoost算法有多重推导方式，比较容易理解的是基于加性模型(additive model)，即基学习器的线性组合：
   $H(\mathbf x)=\sum_{t=1}^{T}\alpha_th_t(\mathbf x) \tag{4}$H(x)=t=1∑T​αt​ht​(x)(4)
   来最小化指数损失函数(exponential loss function)：
   $l_{exp}(H|\mathcal D)=\mathbb E_{\mathbf x\sim\mathcal D}\left [e^{-f(\mathbf x)H(\mathbf x)}\right ]\tag{5}$lexp​(H∣D)=Ex∼D​[e−f(x)H(x)](5)

2. 若$H(\mathbf x)$H(x)能令指数损失函数最小化，则考虑式(5)对$H(\mathbf x)$H(x)的偏导：
   $\frac{\partial l_{exp}(H|\mathcal D)}{\partial H(\mathcal D)}=-e^{-H(\mathbf x)}P(f(\mathbf x)=1|\mathbf x)+e^{H(\mathbf x)}P(f(\mathbf x)=-1|\mathbf x)\tag{6}$∂H(D)∂lexp​(H∣D)​=−e−H(x)P(f(x)=1∣x)+eH(x)P(f(x)=−1∣x)(6)
   令式(6)为零可解得：
   $H(\mathbf x)=\frac{1}{2}ln\frac{P(f(\mathbf x)=1|\mathbf x)}{P(f(\mathbf x)=-1|\mathbf x)}\tag{7}$H(x)=21​lnP(f(x)=−1∣x)P(f(x)=1∣x)​(7)
   因此，有：
   $sign(H(\mathbf x))=sign(\frac{1}{2}ln\frac{P(f(\mathbf x)=1|\mathbf x)}{P(f(\mathbf x)=-1|\mathbf x)})\\ =\left\{\begin{matrix} 1,\ \ \ \ P(f(\mathbf x)=1|\mathbf x)&gt;P(f(\mathbf x)=-1|\mathbf x)\\ -1,\ \ \ \ P(f(\mathbf x)=1|\mathbf x)&lt;P(f(\mathbf x)=-1|\mathbf x) \end{matrix}\right.\\ =\underset{y_\in\left \{-1,+1 \right \}}{arg\ max}P(f(\mathbf x)=y|\mathbf x)\tag{8}$sign(H(x))=sign(21​lnP(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)​=y∈​{−1,+1}arg max​P(f(x)=y∣x)(8)
   这意味着$sign(H(\mathbf x))$sign(H(x))达到了贝叶斯最优错误率。换言之，若指数损失函数最小化，则分类错误率也将最小化；这说明指数损失函数是分类任务元贝$0/1$0/1损失函数的一致的(consistent)替代损失函数。由于这个函数有更好的数学性质，例如它是连续可微函数，因此我们用它代替$0/1$0/1损失函数作为优化目标。

   式(5)-(8)推导：

   损失函数$e^{f(\mathbf x)H(\mathbf x)}$ef(x)H(x)，$f(\mathbf x)$f(x)为真实函数，$f(\mathbf x)\in\left \{-1,+1 \right \}$f(x)∈{−1,+1}

   当$f(\mathbf x)=+1$f(x)=+1时，$e^{f(\mathbf x)H(\mathbf x)}=e^{H(\mathbf x)}$ef(x)H(x)=eH(x)，于是式(5)：
   $l_{exp}(H|\mathcal D)=\mathbb E_{\mathbf x\sim\mathcal D}\left [e^{-f(\mathbf x)H(\mathbf x)}\right ]\\ =e^{-H(\mathbf x)}P(f(\mathbf x)=1|\mathbf x)+e^{H(\mathbf x)}P(f(\mathbf x)=-1|\mathbf x)$lexp​(H∣D)=Ex∼D​[e−f(x)H(x)]=e−H(x)P(f(x)=1∣x)+eH(x)P(f(x)=−1∣x)
   可得式(6)：
   $\frac{\partial l_{exp}(H|\mathcal D)}{\partial H(\mathcal D)}=-e^{-H(\mathbf x)}P(f(\mathbf x)=1|\mathbf x)+e^{H(\mathbf x)}P(f(\mathbf x)=-1|\mathbf x)$∂H(D)∂lexp​(H∣D)​=−e−H(x)P(f(x)=1∣x)+eH(x)P(f(x)=−1∣x)
   令式(6)为零，可得式(7)：
   $H(\mathbf x)=\frac{1}{2}ln\frac{P(f(\mathbf x)=1|\mathbf x)}{P(f(\mathbf x)=-1|\mathbf x)}$H(x)=21​lnP(f(x)=−1∣x)P(f(x)=1∣x)​
   显然有式(8)。

3. 在AdaBoost算法中，第一个基分类器$h_1$h1​是通过直接将基学习算法用于初始数据分布而得；此后迭代生成$h_t$ht​和$\alpha_t$αt​，当基分类器$h_t$ht​基于分布$D_t$Dt​产生后，该基分类器的权重$\alpha_t$αt​应使得$\alpha_{t}h_{t}$αt​ht​最小化指数损失函数：
   $l_{exp}(\alpha_th_t|\mathcal D_t)=\mathbb E_{\mathbf x\sim\mathcal D_t}\left [e^{-f(\mathbf x)\alpha_th_t(\mathbf x)}\right ]\\ =\mathbb E_{\mathbf x\sim\mathcal D_t}\left [e^{-\alpha_t}\mathbb I(f(\mathbf x)=h_t(\mathbf x))+e^{\alpha_t}\mathbb I(f(\mathbf x)\neq h_t(\mathbf x))\right ]\\ =e^{-\alpha_t}P_{\mathbf x\sim D_t}(f(\mathbf x)=h_t(\mathbf x))+e^{\alpha_t}P_{\mathbf x\sim D_t}(f(\mathbf x)\neq h_t(\mathbf x))\\ =e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t)\tag{9}$lexp​(αt​ht​∣Dt​)=Ex∼Dt​​[e−f(x)αt​ht​(x)]=Ex∼Dt​​[e−αt​I(f(x)=ht​(x))+eαt​I(f(x)̸​=ht​(x))]=e−αt​Px∼Dt​​(f(x)=ht​(x))+eαt​Px∼Dt​​(f(x)̸​=ht​(x))=e−αt​(1−ϵt​)+eαt​ϵt​)(9)
   其中$\epsilon_t=P_{\mathbf x\sim D_t}(f(\mathbf x)\neq h_t(\mathbf x))$ϵt​=Px∼Dt​​(f(x)̸​=ht​(x))。考虑指数损失函数的导数：
   $\frac{\partial l_{exp}(\alpha_th_t|\mathcal D_t)}{\partial \alpha_t}=-e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t)\tag{10}$∂αt​∂lexp​(αt​ht​∣Dt​)​=−e−αt​(1−ϵt​)+eαt​ϵt​)(10)
   令式(10)为零可解得：
   $\alpha_t=\frac{1}{2}ln\left (\frac{1-\epsilon_t}{\epsilon_t} \right )\tag{11}$αt​=21​ln(ϵt​1−ϵt​​)(11)
   这恰是AdaBoost算法第6行的分类器权重更新公式。

   式(9)第二行推导：

   $h_t(\mathbf x)\in\left \{-1,+1 \right \}$ht​(x)∈{−1,+1}，当$f(\mathbf x)=h_t(\mathbf x)$f(x)=ht​(x)时，$f(\mathbf x)h_t(\mathbf x)=1$f(x)ht​(x)=1，当$f(\mathbf x)\neq h_t(\mathbf x)$f(x)̸​=ht​(x)时，$f(\mathbf x)h_t(\mathbf x)=-1$f(x)ht​(x)=−1，于是有：
   $e^{-f(\mathbf x)\alpha_th_t(\mathbf x)}=\left\{\begin{matrix} e^{-\alpha_t},\ \ \ f(\mathbf x)=h(\mathbf x)\\ e^{\alpha_t},\ \ \ f(\mathbf x)\neq h(\mathbf x) \end{matrix}\right.$e−f(x)αt​ht​(x)={e−αt​,   f(x)=h(x)eαt​,   f(x)̸​=h(x)​
   也就是$e^{-\alpha_t}\mathbb I(f(\mathbf x)=h_t(\mathbf x))+e^{\alpha_t}\mathbb I(f(\mathbf x)\neq h_t(\mathbf x))$e−αt​I(f(x)=ht​(x))+eαt​I(f(x)̸​=ht​(x))。

4. AdaBoost算法在获得$H_{t-1}$Ht−1​之后样本分布进行调整，使下一轮的基学习器$h_t$ht​能纠正$H_{t-1}$Ht−1​的一些错误。理想的$h_t$ht​能纠正$H_{t-1}$Ht−1​的全部错误，即最小化：
   $l_{exp}(H_{t-1}+h_t|\mathcal D)=\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)(H_{t-1}(\mathbf x)+h_t(\mathbf x))}\right ]\\ =\mathbb E_{\mathbf x\sim\mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}e^{-f(\mathbf x)h_t(\mathbf x)}\right ]\tag{12}$lexp​(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)](12)
   注意到$f^2(\mathbf x)=h_t^2(\mathbf x)=1$f2(x)=ht2​(x)=1，式(12)可使用$e^{-f(\mathbf x)h_t(\mathbf x)}$e−f(x)ht​(x)的泰勒展式近似为：
   $l_{exp}(H_{t-1}+h_t|\mathcal D)\simeq \mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\left (1-f(\mathbf x)h_t(\mathbf x)+\frac{f^2(\mathbf x)h_t^2(\mathbf x)}{2} \right )\right ]\\ =\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\left (1-f(\mathbf x)h_t(\mathbf x)+\frac{1)}{2} \right )\right ]\tag{13}$lexp​(Ht−1​+ht​∣D)≃Ex∼D​[e−f(x)Ht−1​(x)(1−f(x)ht​(x)+2f2(x)ht2​(x)​)]=Ex∼D​[e−f(x)Ht−1​(x)(1−f(x)ht​(x)+21)​)](13)
   于是，理想的基学习器：
   $h_t(\mathbf x)=\underset{h}{arg\ min}\ l_{exp}(H_{t-1}+h_t|\mathcal D)\\ =\underset{h}{arg\ min}\ \mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\left (1-f(\mathbf x)h_t(\mathbf x)+\frac{1)}{2} \right )\right ]\\ =\underset{h}{arg\ min}\ \mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\left (-f(\mathbf x)h_t(\mathbf x)\right )\right ]\\ =\underset{h}{arg\ max}\ \mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}f(\mathbf x)h_t(\mathbf x)\right ]\\ =\underset{h}{arg\ max}\ \mathbb E_{\mathbf x\sim \mathcal D}\left [\frac{e^{-f(\mathbf x)H_{t-1}(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}f(\mathbf x)h_t(\mathbf x)\right ]\tag{14}$ht​(x)=harg min​ lexp​(Ht−1​+ht​∣D)=harg min​ Ex∼D​[e−f(x)Ht−1​(x)(1−f(x)ht​(x)+21)​)]=harg min​ Ex∼D​[e−f(x)Ht−1​(x)(−f(x)ht​(x))]=harg max​ Ex∼D​[e−f(x)Ht−1​(x)f(x)ht​(x)]=harg max​ Ex∼D​[Ex∼D​[e−f(x)Ht−1​(x)]e−f(x)Ht−1​(x)​f(x)ht​(x)](14)
   注意到$\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]$Ex∼D​[e−f(x)Ht−1​(x)]是一个常数。令$\mathcal D_t$Dt​表示一个分布：
   $\mathcal D_t(\mathbf x)=\frac{\mathcal D(\mathbf x)e^{-f(\mathbf x)H_{t-1}(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}\tag{15}$Dt​(x)=Ex∼D​[e−f(x)Ht−1​(x)]D(x)e−f(x)Ht−1​(x)​(15)
   则根据数学期望的定义，这等价于令：
   $h_t(\mathbf x)=\underset{h}{arg\ max}\ \mathbb E_{\mathbf x\sim \mathcal D}\left [\frac{e^{-f(\mathbf x)H_{t-1}(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}f(\mathbf x)h_t(\mathbf x)\right ]\\ =\underset{h}{arg\ max}\ \mathbb E_{\mathbf x\sim \mathcal D_t}\left [f(\mathbf x)h(\mathbf x) \right ]\tag{16}$ht​(x)=harg max​ Ex∼D​[Ex∼D​[e−f(x)Ht−1​(x)]e−f(x)Ht−1​(x)​f(x)ht​(x)]=harg max​ Ex∼Dt​​[f(x)h(x)](16)
   由$f(\mathbf x),h(\mathbf x)\in\left \{-1,+1 \right \}$f(x),h(x)∈{−1,+1}，有：
   $f(\mathbf x)h(\mathbf x)=1-2\mathbb I(f(\mathbf x)\neq h(\mathbf x))\tag{17}$f(x)h(x)=1−2I(f(x)̸​=h(x))(17)
   则理想的基学习器：
   $h_t(\mathbf x)=\underset{h}{arg\ max}\ \mathbb E_{\mathbf x\sim \mathcal D_t}\left [\mathbb I(f(\mathbf x)\neq h(\mathbf x)\right]\tag{18}$ht​(x)=harg max​ Ex∼Dt​​[I(f(x)̸​=h(x)](18)
   由此可见，理想的$h_t$ht​将在分布$\mathcal D_t$Dt​下最小化分类误差。因此，弱分类器将基于分布$\mathcal D_t$Dt​来训练，且针对$\mathcal D_t$Dt​的分类误差应小于0.5.这在一定程度上类似’‘残差逼近’'的思想。考虑到$\mathcal D_t$Dt​和$\mathcal D_{t+1}$Dt+1​的关系，有：
   $\mathcal D_{t+1}(\mathbf x)=\frac{\mathcal D(\mathbf x)e^{-f(\mathbf x)H_{t}(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t}(\mathbf x)}\right ]}\\ =\frac{\mathcal D(\mathbf x)e^{-f(\mathbf x)H_{t-1}(\mathbf x)}e^{-f(\mathbf x)\alpha_th_t(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t}(\mathbf x)}\right ]}\\ =\mathcal D_t(\mathbf x)·e^{-f(\mathbf x)\alpha_th_t(\mathbf x)}\frac{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t}(\mathbf x)}\right ]}\tag{19}$Dt+1​(x)=Ex∼D​[e−f(x)Ht​(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)αt​ht​(x)​=Dt​(x)⋅e−f(x)αt​ht​(x)Ex∼D​[e−f(x)Ht​(x)]Ex∼D​[e−f(x)Ht−1​(x)]​(19)
   这恰是AdaBoost算法第7行的样本分布更新公式。

   式(12)-(13)推导：

   泰勒公式：

   $f(x)=\frac{f(x_0)}{0!}+\frac{f&#x27;(x)}{1!}(x-x_0)+\frac{f&#x27;&#x27;(x)}{2!}(x-x_0)^2+...+\frac{f^n(x)}{n!}(x-x_0)^n+Rn(x)$f(x)=0!f(x0​)​+1!f′(x)​(x−x0​)+2!f′′(x)​(x−x0​)2+...+n!fn(x)​(x−x0​)n+Rn(x)

   剩余的$Rn(x)$Rn(x)是泰勒公式的余项，是$(x-x_0)^n$(x−x0​)n的高阶无穷小。

   $e^x$ex的泰勒公式：

   $e^x=1+\frac{1}{1!}x+\frac{1}{2!}x^2+\frac{1}{3!}x^3+o(x^3)$ex=1+1!1​x+2!1​x2+3!1​x3+o(x3)

   于是有：
   $e^{-f(\mathbf x)H(\mathbf x)}=1+(-f(\mathbf x)H(\mathbf x))+\frac{1}{2}(-f(\mathbf x)H(\mathbf x))^2\\ =1+f(\mathbf x)H(\mathbf x)+\frac{f^2(\mathbf x)H^2(\mathbf x)}{2}\\ =1+f(\mathbf x)H(\mathbf x)+\frac{1}{2}$e−f(x)H(x)=1+(−f(x)H(x))+21​(−f(x)H(x))2=1+f(x)H(x)+2f2(x)H2(x)​=1+f(x)H(x)+21​

   式(16)推导：

   假设$x$x的概率分布是$\mathcal D(x)$D(x)，则$\mathbb E(f(x))=\sum_{i=1}^{|\mathcal D|}\mathcal D(x_i)f(x_i)$E(f(x))=∑i=1∣D∣​D(xi​)f(xi​)，故可得：
   $\mathbb E_{\mathbf x\sim \mathcal D}\left[e^{-f(\mathbf x)H(\mathbf x)} \right]=\sum_{i=1}^{|\mathcal D|}\mathcal D(x_i)e^{-f(\mathbf x_i)H(\mathbf x_i)}$Ex∼D​[e−f(x)H(x)]=i=1∑∣D∣​D(xi​)e−f(xi​)H(xi​)
   由式(15)可知：
   $\mathcal D_t(\mathbf x_i)=\frac{\mathcal D(\mathbf x_i)e^{-f(\mathbf x_i)H_{t-1}(\mathbf x_i)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}$Dt​(xi​)=Ex∼D​[e−f(x)Ht−1​(x)]D(xi​)e−f(xi​)Ht−1​(xi​)​
   所以式(16)可表示为：
   $\mathbb E_{\mathbf x\sim \mathcal D}\left [\frac{e^{-f(\mathbf x)H_{t-1}(\mathbf x)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}f(\mathbf x)h_t(\mathbf x)\right ]\\ =\sum_{i=1}^{|\mathcal D|}\mathcal D(x_i)\frac{e^{-f(\mathbf x_i)H_{t-1}(\mathbf x_i)}}{\mathbb E_{\mathbf x\sim \mathcal D}\left [e^{-f(\mathbf x)H_{t-1}(\mathbf x)}\right ]}f(\mathbf x_i)h_t(\mathbf x_i)\\ =\sum_{i=1}^{|\mathcal D|}\mathcal D(x_i)f(\mathbf x_i)h_t(\mathbf x_i)\\ =\mathbb E_{\mathbf x\sim \mathcal D_t}\left [f(\mathbf x)h(\mathbf x) \right ]$Ex∼D​[Ex∼D​[e−f(x)Ht−1​(x)]e−f(x)Ht−1​(x)​f(x)ht​(x)]=i=1∑∣D∣​D(xi​)Ex∼D​[e−f(x)Ht−1​(x)]e−f(xi​)Ht−1​(xi​)​f(xi​)ht​(xi​)=i=1∑∣D∣​D(xi​)f(xi​)ht​(xi​)=Ex∼Dt​​[f(x)h(x)]

三、Bagging与随机森林

3.1 Bagging

1. Bagging是并行式集成学习方法最著名的代表，直接基于自助采样法(bootstrap sampling)。

   自助采样法的步骤是：给定包含m个样本的数据集：

   • 先随机取出一个样本放入采样集中，再把该样本放回原始数据集。
   • 这样经过m次随机采样操作，得到包含m个样本的采样集。

   初始训练集中有的样本在采样集中多次出现，有的则从未出现。一个样本始终不在采样集中出现的概率是$(1-\frac{1}{m})^m$(1−m1​)m。

   根据$lim_{m→\infty}=(1-\frac{1}{m})^m= \frac{1}{e}\simeq0.368$limm→∞​=(1−m1​)m=e1​≃0.368，因此初始训练集中约有63.2%的样本出现在了采样集中。

2. 自助采样法给Bagging算法带来了额外的优点：由于每个基学习器只用初始训练集中约 63.2% 的样本来训练，剩下的约36.8%的样本可用作验证集来对泛化性能进行包外估计。

3. Bagging的基本流程：

   • 经过T轮自助采样，可以得到T个包含m个训练样本的采样集。

   • 然后基于每个采样集训练出一个基学习器。

   • 最后将这T个基学习器进行组合，得到集成模型。

     Bagging算法的描述如图：

   

4. 在使用 Bagging学习器进行预测时：

   • 分类任务采取简单投票法，取每个基学习器的预测类别的众数。
   • 回归任务使用简单平均法，取每个基学习器的预测值的平均。

5. 假定基学习器计算复杂度为$O(m)$O(m)，则Bagging的复杂度大致为$T(O(m)+O(s))$T(O(m)+O(s))，考虑到采样与投票/平均过程的复杂度$O(s)$O(s)很小，而$T$T通常是一个不太大的常数，因此，训练一个Bagging集成与直接使用基学习器算法训练一个学习器的复杂度同阶，这说明Bagging是一个很高效的集成学习算法。

6. 与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改地用于多分类、回归等任务。

7. 从偏差-方差分解的角度来看：

   • Bagging主要关注降低方差，它能平滑强学习器的方差。

     因此它在非剪枝决策树、神经网络等容易受到样本扰动的学习器上效果更为明显。

   • Boosting主要关注降低偏差，它能将一些弱学习器提升为强学习器。

     因此它在SVM 、knn 等不容易受到样本扰动的学习器上效果更为明显。

3.2 随机森林

1. 随机森林(Random Forest，简称RF) 是Bagging的一个扩展变体。

2. 随机森林对Bagging做了小改动：

   • Bagging中基学习器的“多样性”来自于样本扰动。样本扰动来自于对初始训练集的随机采样。

   • 随机森林中的基学习器的多样性不仅来自样本扰动，还来自属性扰动。

     这就是使得最终集成的泛化性能可以通过个体学习器之间差异度的增加而进一步提升。

3. 随机森林在以决策树为基学习器构建Bagging集成模型的基础上，进一步在决策树的训练过程中引入了随机属性选择。

   • 传统决策树在选择划分属性时，是在当前结点的属性集合(假定有$d$d个属性)中选择一个最优属性。
   • 随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含$k$k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。
     • 如果$k=d$k=d，则基决策树的构建与传统决策树相同。
     • 如果$k=1$k=1，则随机选择一个属性用于划分。
     • 通常建议$k=log_2d$k=log2​d。

4. 随机森林的优点：

   • 训练效率较高。因为随机森林使用的决策树只需要考虑所有属性的一个子集。
   • 随机森林简单、容易实现、计算开销小。
   • 随机森林在很多现实任务中展现出强大的性能，被称作 “代表集成学习技术水平的方法”。

5. 随着树的数量的增加，随机森林可以有效缓解过拟合。因为随着树的数量增加，模型的方差会显著降低。

   但是树的数量增加并不会纠正偏差，因此随机森林还是会有过拟合。

四、结合策略

1. 学习器组合可以能带来好处：

   • 由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能。

     此时如果使用单学习器可能因为造成误选而导致泛化性能不佳，通过学习器组合之后会减小这一风险。

   • 学习算法往往会陷入局部极小。有的局部极小点所对应的泛化性能可能很差，而通过学习器组合之后可降低陷入糟糕局部极小的风险。

   • 某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时使用单学习器肯定无效。

     通过学习器组合之后，由于相应的假设空间有所扩大，有可能学得更好的近似。

   

2. 假定集成包含$T$T个基学习器$\left \{h_1,h_2,…,h_T \right \}${h1​,h2​,…,hT​}。一共有三种集成策略：

   • 平均法。
   • 投票法。
   • 学习法。

4.1 平均法

1. 平均法通常用于回归任务中。

   对数值型输出$h_i(\mathbf x)\in \mathbb R$hi​(x)∈R，最常见的结合策略是使用平均法(averaging)。

   • 简单平均法(simple averaging)：
     $H(\mathbf x)=\frac{1}{T}\sum_{i=1}^{T}h_i(\mathbf x)\tag{20}$H(x)=T1​i=1∑T​hi​(x)(20)

   • 加权平均法(weighted averaging)：
     $H(\mathbf x)=\sum_{i=1}^{T}\omega_ih_i(\mathbf x)\tag{21}$H(x)=i=1∑T​ωi​hi​(x)(21)
     其中学习器$h_i$hi​的权重$\omega_i$ωi​是从训练数据中学得，通常要求$\omega_i\geqslant0,\sum_{i=1}^{T}\omega_i=1$ωi​⩾0,∑i=1T​ωi​=1

2. 现实任务中训练样本通常不充分或者存在噪声，这就使得学得的权重不完全可靠。尤其是对于规模比较大的集成学习，要学习的权重比较多，很容易出现过拟合。

   因此实验和应用均显示出，加权平均法不一定优于简单平均法。

3. 通常如果个体学习器性能相差较大时，适合使用加权平均法；个体学习器性能相差较近时，适合使用简单平均法。

4.2 投票法

对于分类任务来说，学习器$h_i$hi​将从类别标记集合$\left \{c_1,c_2,…,c_N \right \}${c1​,c2​,…,cN​}中预测出一个标记，最常见的结合策略是使用投票法(voting)。为便于讨论，我们将$h_i$hi​在样本$\mathbf x$x上的预测输出表示为一个$N$N维向量$(h^1_i(\mathbf x);h^2_i(\mathbf x);…;h^N_i(\mathbf x))$(hi1​(x);hi2​(x);…;hiN​(x))，其中$h^j_i(\mathbf x)$hij​(x)是$h_i$hi​在类别$c_j$cj​上的输出。

• 绝大多数投票法(majority voting)：
  $H(\mathbf x)=\left\{\begin{matrix} c_j,\ \ \ if\ \sum_{i=1}^{T}h_i^j(\mathbf x)&gt;0.5\sum_{k=1}^{N}\sum_{i=1}^{T}h_i^k(\mathbf x)\\ reject,\ \ \ otherwise \end{matrix}\right. \tag{22}$H(x)={cj​,   if ∑i=1T​hij​(x)>0.5∑k=1N​∑i=1T​hik​(x)reject,   otherwise​(22)
  若某个标记得票数过半，则预测为该标记；否则拒绝预测。

  此时很有可能所有标记都未过半，则预测失败。因此这种方法比较少用。

• 相对多数投票法：
  $H(\mathbf x)=c_{\underset{j}{arg\ max}\ \sum_{i=1}^{T}h_i^j(\mathbf x)}\tag{23}$H(x)=cjarg max​ ∑i=1T​hij​(x)​(23)

  即预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个 。

• 加权投票法(weighted voting)：
  $H(\mathbf x)=c_{\underset{j}{arg\ max}\ \sum_{i=1}^{T}\omega_ih_i^j(\mathbf x)}\tag{24}$H(x)=cjarg max​ ∑i=1T​ωi​hij​(x)​(24)
  与加权平均法类似，$\omega_i$ωi​是$h_i$hi​的权重，通常$\omega_i\geqslant0,\sum_{i=1}^{T}\omega_i=1$ωi​⩾0,∑i=1T​ωi​=1 。

4.3 学习法

1. 学习法中，个体学习器的分类结果通过与另一个学习器来组合。

   此时称个体学习器为初级学习器，用于组合的学习器称作次级学习器或者元学习器(meta_learner)。

2. 学习法的典型代表就是stacking集成算法。stacking 集成算法中：

   • 首先从初始数据集训练出初级学习器。

   • 然后将初级学习器的预测结果作为一个新的数据集用于训练次级学习器。

     在这个新数据集中，初级学习器的输出被当作样本输入特征；初始样本的标记仍被视作标记。

   

3. 若直接使用初级学习器的输出来产生次级训练集，则容易发生过拟合。

   一般是通过使用交叉验证，使用训练初级学习器时未使用的样本来产生次级学习器的训练样本。

4. 次级学习器的输入属性表示和次级学习算法对stacking集成算法的泛化性能有很大影响。通常推荐：

   • 次级学习器的输入特征是以初级学习器的输出类概率为特征。
   • 次级学习算法采用多响应线性回归(Multi-response Linear Regression，简称MLR) 。

参考

• 《机器学习》
• AI算法工程师手册
• 南瓜书PumpkinBook