集成学习（面试准备）

作者: 单调不减 | 来源:发表于2020-03-02 16:22 被阅读0次

1、什么是集成学习

根据维基百科的说法：在统计学和机器学习中，集成学习方法使用多种学习算法来获得比单独使用任何单独的学习算法更好的预测性能。

具体说来，就是对于训练集数据，我们通过训练若干个个体学习器（弱学习器），通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。

不难看出，对集成学习来说，最重要的部分有两个：

以何种方式训练多个个体学习器
以何种方式将训练好的学习器结合起来

2、集成学习的算法有哪几类，简述其主要思想

集成学习的主要方法可以分为以下四类：

Bagging 的全称是 Bootstrap Aggregating，Bagging 采用自助采样法，也就是有放回的采样。通过采样得到多个数据集，并在每个数据集上训练一个基分类器，然后将各分类器的结果结合起来得到最终预测结果（一般分类采取简单投票，回归采取简单平均）。

Boosting 也就是所谓的提升方法，多数提升方法是首先改变训练数据的概率分布（或者权值），针对不同的训练数据分布调用弱学习算法学习多个弱分类器，然后采用加权多数表决（即加大误差小的弱分类器的权值，减小误差大的弱分类器的权值）的方法将各弱学习器结合在一起。

Stacking 和 Blending 类似，都是将不同模型的训练结果作为另一个模型的输入，然后得到最终的结果。也就是说，在此类算法中的学习算法可以分为两类，一类是以原数据为输入训练弱学习器的算法，另一类学习算法是以弱学习的输出为输入训练元学习器的算法，元学习器学习的其实是各个弱学习器的结合策略。

3、集成学习可能带来哪些好处

4、Bagging 和 Boosting 优缺点及两者比较

Bagging

优点

(1) 由于每个基学习器只用初始训练集中约 63.2% 的样本来训练，剩下的约 36.8% 的样本可用作验证集来对泛化性能进行包外 (Out-Of-Bag) 估计。

(2) 有放回采样得到的训练集之间是相互独立的，这就使得个体学习器尽可能相互独立。

(3) 各个基学习器的训练过程独立，因此可以并行化。

Boosting

(1) 由于各个基学习器的训练是序列化进行的，且后一个基学习器重点关注前一个基学习器上表现不好的样本，因此产生的各个基学习器相对互补，因此可以减少偏差。

两者比较

1）样本选择：

Bagging：训练集是有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大

3）预测函数：

Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重

4）并行计算：

Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果

5）优化部分：

Bagging：主要减小模型的方差（Variance）
Boosting：主要减小模型的偏差（Bias）

5、为什么 Bagging 减小方差，Boosting 减小偏差

假设各基分类器在集成分类器中所占的权重 $\gamma_i$ ，各基分类器的方差为 $\sigma_i^2$ ，均值为 $\mu_i$ ，基分类器两两之间的相关性为 $\rho_{ij}$ 。基分类器个数为 $m$ 。

对于 Bagging 来说， $\gamma_1=\gamma_2=\dots=\gamma_n=\frac{1}{m}$ ，由于各基分类器使用相同算法在独立的数据集上进行训练得到，因此可以近似认为 $\sigma_i=\sigma$ 且 $\mu_i=\mu$ ， $i=1,2,\dots,m$ ，且基分类器两两之间相关系数近似相等： $\rho_{ij}=\rho\ for\ all\ i\neq j$ 。

从而：

$\begin{aligned} E(F)&= \gamma * \sum_{i}^{m} E\left(f_{i}\right) \\ &=\frac{1}{m} * m * \mu \\ &=\mu \\ \\ \operatorname{Var}(F) &=\gamma^2[\sum_i^m Var(f_i) + 2 \sum_i^m\sum_{j\neq i} Cov(f_i,f_j)]\\ &=\frac{1}{m^2 } (m\sigma^2+2 \frac{m(m-1)}{2}\rho\sigma^2) \\ &=\frac{\sigma^2}{m}+\frac{m-1}{m}\rho\sigma^2 \\ &=\frac{1-\rho}{m}\sigma^2+\rho\sigma^2 \\ \end{aligned}$

根据上式我们可以看到，整体模型的期望近似于基模型的期望，这也就意味着整体模型的偏差和基模型的偏差近似。同时，整体模型的方差小于等于基模型的方差（当相关性为1时取等号），随着基模型数 $m$ 的增多，上式中第一项减小，从而整体模型的方差减少，从而防止过拟合的能力增强，模型的准确度得到提高。

因此 Bagging 就是在几乎不改变模型准确性的前提下尽可能减小模型的方差。因此 Bagging 中的基模型一定要为强模型，否则就会导致整体模型的偏差大，即准确度低。

Random Forest 是典型的基于 Bagging 框架的模型，其基模型是拟合能力很强的决策树。Random Fores 在树的内部节点分裂过程中，不是将所有特征，而是随机抽样一部分特征纳入分裂的候选项。这样一来，基模型之间的相关性 $\rho$ 降低，从而在方差公式中，第一项增加 $\frac{\triangle \rho}{m}\sigma^2$ ，第二项减小 $\triangle \rho \sigma^2$ ，整体方差进一步减小。

对于 Boosting 来说，基模型的训练集抽样是强相关的，那么模型的相关系数近似等于1，即 $\rho_i=1$ ，从而：

$\begin{aligned} E(F)&= \sum_i^m \gamma_i\mu_i \\ \\ \operatorname{Var}(F) &=\sigma^2 \\ \end{aligned}$

根据上式我们可以看到，整体模型的方差近似于基模型的方差，而期望则可以根据各基学习器权重的分配进行优化（误分率低的权重大）。

因此 Boosting 就是在几乎不改变模型方差的前提下减小模型的偏差。故 Boosting 中的基模型一定要为弱模型，否则就会导致整体模型的方差大（强模型容易过拟合，导致方差过大）。

6、AdaBoost 原理及推导

AdaBoost，即 Adaptive Boosting （自适应提升）的简称，它的思想是通过序列化地训练多个弱分类器并将它们进行线性组合得到一个强分类器。具体来说，每次训练一个弱分类时都根据前一个分类器的结果来对样本权值进行更新，增加误分类样本的权值，降低正确分类样本的权值；将各分类器进行线性组合的时候，其权重与其误分类率成反比，误分类率越小的弱分类器其权重越大。

AdaBoost 本质上是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的二分类学习方法。

首先，加法模型就是指最终的集成分类器由各个基分类器线性组合构成：

$f(x)=\sum_{m=1}^M \beta_m b(x;\gamma_m)$

$b(x;\gamma_m)$ 是基函数， $\gamma_m$ 是基函数的参数， $\beta_m$ 为基函数的系数。

给定训练数据及损失函数 $L(y,f(x))$ 的条件下，学习加法模型 $f(x)$ 成为经验风险最小化问题：

$\min_{\beta_m,\gamma_m}\sum_{i=1}^N L(y_i,\sum_{m=1}^M \beta_m b(x_i;\gamma_m))$

这是一个复杂的优化问题。前向分步算法的想法是，每一步只学习一个基函数及其系数，逐步逼近优化目标，就可以简化复杂度，即极小化损失函数：

$(\beta_m,\gamma_m)=\arg\min_{\beta,\gamma}\sum_{i=1}^N L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma))$

现假设损失函数为指数函数：

$L(y,f(x))=\exp[-yf(x)]$

并假设经过 $m-1$ 轮已经得到 $f_{m-1}(x)$ ，则现在的优化目标是：

$\begin{aligned} (\alpha_m,G_{m}(x))&=\arg\min_{\alpha,G}\sum_{i=1}^N \exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))] \\ &= \arg\min_{\alpha,G}\sum_{i=1}^N \exp(-y_if_{m-1}(x_i))\exp(-y_i\alpha G(x_i))\\ \end{aligned}$

记 $w_{mi}=\exp(-y_if_{m-1}(x_i))$ ，此项与 $\alpha,G$ 无关。而 $\exp(-y_i\alpha G(x_i))$ 在 $y_i=G(x_i)$ 时为 $e^{-\alpha}$ ，在在 $y_i \neq G(x_i)$ 时为 $e^{\alpha}$ ，因此 $G^*_m(x)$ 可以写成：

$\begin{aligned} G^*_m(x)&=\arg\min_{G}[e^{-\alpha}\sum_{ i=1}^N w_{mi}+(e^{ \alpha}-e^{-\alpha})\sum_{ i=1}^N w_{mi}I(y_i\neq G(x_i))] \\ & = \arg\min_{G}\sum_{ i=1}^N w_{mi}I(y_i\neq G(x_i)) \end{aligned}$

将 $G^*_m(x)$ 带入上式后求解 $\alpha_m^*$ ：

$\alpha_m^*=\arg\min_{G}[e^{-\alpha}\sum_{ i=1}^N w_{mi}+(e^{ \alpha}-e^{-\alpha})\sum_{ i=1}^N w_{mi}I(y_i\neq G^*_m(x_i))]$

求导令其为 0 解得：

$\alpha_m^*=\frac{1-\sum_{ i=1}^N w_{mi}I(y_i\neq G^*_m(x_i))}{\sum_{ i=1}^N w_{mi}I(y_i\neq G^*_m(x_i))}=\frac{1-e_m}{e_m}$

这里 $e_m=\sum_{ i=1}^N w_{mi}I(y_i\neq G^*_m(x_i))$ 即为分类误差率。

这样我们就得到了 AdaBoost 的基函数系数计算公式。

下面我们来看权值的更新：

由：

$f_m(x)=f_{m-1}(x)+\alpha_m G_m(x)$

$w_{mi}=\exp(-y_if_{m-1}(x_i))$

$w_{m+1,i}=\exp(-y_if_{m}(x_i))$

得到：

$\begin{aligned} w_{m+1,i}&=\exp(-y_if_{m}(x_i)) \\ &=\exp(-y_i[f_{m-1}(x)+\alpha_m G_m(x)]) \\ &=\exp(-y_if_{m-1}(x_i))\exp(-y_i\alpha_m G_m(x)) \\ &=w_{mi} \exp(-y_i\alpha_m G_m(x)) \end{aligned}$

添加一个规范化因子即得到 AdaBoost 的权值更新过程。

7、简述 GBDT 算法

GBDT 利用加法模型和前向分步算法实现学习的优化过程。并在优化损失函数时利用损失函数对当前模型的负梯度作为残差的估计，通过不断拟合负梯度的值依次得到各个基分类器。

8、GBDT 如何选择特征

因为 GBDT 中的基分类器是 CART 模型，因此各结点选择划分特征的方法与 CART 相同，即遍历所有可能特征 $j$ 及对应的划分点 $s$ ，选择使得下式最小的：

$\min_{j,s}[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)} \left(y_{i}-c_{1}\right)^{2} + \min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)} \left(y_{i}-c_{2}\right)^{2}]$

9、GBDT 如何构建（组合）特征

GBDT 本身是不能产生特征的，但是我们可以利用 GBDT 去产生特征的组合。

Facebook 在 2014 年发表的一篇论文利用 GBDT 去产生有效的特征组合，以便用于逻辑回归的训练，提升模型最终的效果。

如图所示，我们使用 GBDT 生成了两棵树，两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去，样本 X 落在了第一棵树的第二个叶子节点，第二颗树的第一个叶子节点，于是我们便可以依次构建一个五纬的特征向量，每一个纬度代表了一个叶子节点，样本落在这个叶子节点上面的话那么值为 1，没有落在该叶子节点的话，那么值为 0。于是对于该样本，我们可以得到一个向量 [0,1,0,1,0] 作为该样本的组合特征，和原来的特征一起输入到逻辑回归当中进行训练。实验证明这样会得到比较显著的效果提升。

10、GBDT 如何用于分类

首先需要明确的是，GBDT 无论用于分类还是回归一直都是使用的 CART 回归树。

假设有训练样本 $\{x_i,y_i\},i=1,2,\dots,n$ ，第 $m-1$ 步获得的集成学习器为 $F_{m-1}(x)$ ，那么 GBDT 通过下面的递推式，获得一个新的弱学习器 $h(x)$ ：

$F_{m}(x)=F_{m-1}(x)+\underset{h \in H}{\operatorname{argmin}} \sum_{i=1}^{n} \operatorname{Loss}\left(y_{i}, F_{m-1}\left(x_{i}\right)+h\left(x_{i}\right)\right)$

将损失函数 $\operatorname{Loss}\left(y_{i}, F_{m-1}\left(x_{i}\right)+h\left(x_{ i} \right)\right)$ 看作向量 $\left(F\left(x_{1}\right), F\left(x_{2}\right), \ldots, F\left(x_{n}\right)\right)$ 上的函数，在第 $m-1$ 轮迭代之后，向量位于 $\left(F_{m-1}\left(x_{1}\right), F_{m-1}\left(x_{2}\right), \ldots, F_{m-1}\left(x_{n}\right)\right)$ ,如果我们想进一步减小损失函数，则根据梯度下降法，向量移动的方向应为损失函数的负梯度方向，即：

$\mathbf{v}=-\left(\frac{\partial \operatorname{loss}\left(y_{1}, F_{m-1}\left(x_{1}\right)\right)}{\partial F_{m-1}\left(x_{1}\right)}, \frac{\partial \operatorname{loss}\left(y_{2}, F_{m-1}\left(x_{2}\right)\right)}{\partial F_{m-1}\left(x_{2}\right)}, \ldots, \frac{\partial \operatorname{loss}\left(y_{n}, F_{m-1}\left(x_{n}\right)\right)}{\partial F_{m-1}\left(x_{n}\right)}\right)$

这样如果使用训练集： $\left\{x_{i},-\frac{\partial \operatorname{loss}\left(y_{i}, F_{m-1}\left(x_{i}\right)\right)}{\partial F_{m-1}\left(x_{i}\right)}\right\}_{i=1}^{n}$ 去训练一棵树的话，就相当于朝着损失函数减小的方向又走了一步。

将 GBDT 应用于回归问题，相对来说比较容易理解。因为回归问题的损失函数一般为平方差损失函数，这时的残差，恰好等于预测值与实际值之间的差值。

而将 GBDT 用于分类问题，则不那么显而易见。这里我们回顾一下逻辑回归是怎么做的：

$P(y=1|x)=\frac{1}{1+e^{-w\cdot x}}$

在 LR 中实际上我们所做的是用线性模型去拟合对数几率 $\log\frac{p}{1-p}$ ，现在我们把这里的线性模型 $w\cdot x$ 替换成经 $k$ 步学习后的集成学习器 $F(x)=\sum_{m=1}^k h_{m}(x)$ 即可实现用非线性模型去拟合对数几率的目标。

分类模型可以表达为：

$P(y=1|x)=\frac{1}{ 1+e^{-\sum_{m=1}^k h_{m}(x)}}=\pi(x)$

则样本 $(x_i,y_i)$ 的损失函数为：

$\begin{aligned} loss(x_i,y_i)&=-[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))] \\ &= y_{i} \log \left(1+e^{-F\left(x_{i}\right)}\right)+\left(1-y_{i}\right)\left[F\left(x_{i}\right)+\log \left(1+e^{-F\left(x_{i}\right)}\right)\right] \\ \end{aligned}$

从而：

$-\left.\frac{\partial \operatorname{loss} }{\partial F(x)}\right|_{x_{i}, y_{i}}=y_{i}-\frac{1}{1+e^{-F\left(x_{i}\right)}}=y_{i}-\pi({x}_{ I})$

可以看到，需要拟合的近似残差为真实概率与预测概率之差。

于是 GBDT 应用于二分类的算法如下：

$F_0(x)=h_0(x)=\log\frac{p_1}{1-p_1}$ ，其中 $p_1$ 是训练样本中 $y=1$ 的比例，以此作为先验信息。
对 $m=1,2,\dots,M$ ：

(1) 计算 $g_i=\pi(x_i)-y_i$ ，并使用训练集 $\{x_i,-g_i \}_{ i=1}^n$ 训练一棵回归树 $h_m(x)$ ，其中 $\pi(x_i)=\frac{1}{1+e^{-F(x_i)}}$ 。

(2) 考虑 shrinkage，可得这一轮迭代之后的学习器 $F_m(x)=F_{m-1}(x)+\alpha h_m(x)$ ， $\alpha$ 为学习率。

将以上得到的学习器累加，得到最终的学习器 $F_M(x)=\sum_{ i=1}^{M}h_i(x)$ 。

类似地，对于多分类问题，则需要考虑以下 softmax 模型：

$\begin{aligned} &P(y=1 | x)=\frac{e^{F_{1}(x)}}{\sum_{i=1}^{k} e^{F_{i}(x)}}\\ &P(y=2 | x)=\frac{e^{F_{2}(x)}}{\sum_{i=1}^{k} e^{F_{i}(x)}}\\ &P(y=k | x)=\frac{e^{F_{k}(x)}}{\sum_{i=1}^{k} e^{F_{i}(x)}} \end{aligned}$

这里 $F_1$ 到 $F_k$ 是 $k$ 个不同的 ensemble tree，每一轮的训练实际上是训练了 $k$ 棵树去拟合 softmax 的每一个分支模型的负梯度。softmax 模型的单样本损失函数为：

$\operatorname{loss}=-\sum_{i=1}^{k} y_{i} \log P\left(y_{i} | x\right)=-\sum_{i=1}^{k} y_{i} \log \frac{e^{F_{i}(x)}}{\sum_{j=1}^{k} e^{F_{j}(x)}}$

这里的 $y_i$ 是样本 label 在 $k$ 个类别上作 one-hot 编码之后的取值，只有一维为1，其余都是 0。由以上表达式不难推导：

$-\frac{\partial \operatorname{los} s}{\partial F_{q}}=y_{q}-\frac{e^{F_{q}(x)}}{\sum_{j=1}^{k} e^{F_{j}(x)}}=y_{q}-\hat{y}_{q}$

可见，这 $k$ 棵树同样是拟合了样本的真实概率与预测概率之差，与二分类类似。

11、GBDT 和 RF 的比较

相同点：

都是由多棵树组成；最终的结果都由多棵树共同决定。

不同点：

组成随机森林的可以是分类树、回归树；组成 GBDT 只能是回归树
组成随机森林的树可以并行生成（Bagging）；GBDT 只能串行生成（Boosting）
对于最终的输出结果而言，随机森林使用多数投票或者简单平均；而 GBDT 则是将所有结果累加起来，或者加权累加起来
随机森林对异常值不敏感，GBDT 对异常值非常敏感
随机森林对训练集一视同仁权值一样，GBDT 是基于权值的弱分类器的集成
随机森林通过减小模型的方差提高性能，GBDT 通过减少模型偏差提高性能

12、简要介绍 Stacking 算法

Stacking 算法指训练一个元模型用于组合各个基模型。具体来说就是将训练好的各个基模型的输出作为元模型的输入来训练一个元模型，这样就能得到一个最终的输出。如果可以选用任意一个组合算法，那么理论上，Stacking可以表示任意一种 Ensemble 算法。实际中，我们通常使用单层 logistic(softmax) 回归作为元模型。

具体流程如上图所示，首先我们记第一个基模型为 Model 1，然后我们把训练集（假设大小为 $N$ ）等分成 5 份，在其中 4 份上训练模型，在剩下 1 份上输出预测结果，这样 5 个模型各得到 $\frac{N}{5}$ 维的输出，组合在一起即为 $N$ 维的输出，以此作为 Model 1 在训练集上的输出，同样也是元模型的第一列输入。假设有 $M$ 个基模型，则最终会产生第二层的训练集维数为 $N\times M$ 。以此作为第二层的特征，并把训练集标签作为第二层的标签训练元模型，即得到最后的集成模型。

这里有一个问题，就是我们学习好的集成模型如何用于测试集的预测呢，测试集的标签我们是不知道的，因此不能像在训练集上一样通过 k-fold 的方式来产生第二层的输入。这里采用的方案（以 Model 1 为例）是以 Model 1 在训练集上训练的 5 个模型在测试集上的预测结果的均值作为第二层的输入，从而得到最终结果。

Stacking 的好处直观来看就是让各个基模型之间取长补短：

如图所示，model 1 在红框范围内表现由于 model 2，model 2 在篮框范围内表现优于 model 1，因此 Stacking 做的事就是让两个模型在各自擅长的数据点上权重大一些，以达到各取所长的效果。

Reference

https://zhuanlan.zhihu.com/p/26890738
https://www.cnblogs.com/liuwu265/p/4690486.html
https://zhuanlan.zhihu.com/p/36822575
https://www.cnblogs.com/ModifyRong/p/7744987.html#FeedBack
https://zhuanlan.zhihu.com/p/46445201
https://www.datasciencecentral.com/profiles/blogs/stacking-models-for-improved-predictions-a-case-study-for-housing