集成学习(面试准备)

1、什么是集成学习

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

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

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

  • 以何种方式训练多个个体学习器

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

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

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

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

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

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

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

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

  1. Bagging
  • 优点

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

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

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

  1. Boosting

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

  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=\mui=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 应用于二分类的算法如下:

  1. F_0(x)=h_0(x)=\log\frac{p_1}{1-p_1},其中p_1是训练样本中y=1的比例,以此作为先验信息。

  2. 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为学习率。

  1. 将以上得到的学习器累加,得到最终的学习器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_1F_kk个不同的 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 的比较

  • 相同点:
  1. 都是由多棵树组成;最终的结果都由多棵树共同决定。
  • 不同点:
  1. 组成随机森林的可以是分类树、回归树;组成 GBDT 只能是回归树
  2. 组成随机森林的树可以并行生成(Bagging);GBDT 只能串行生成(Boosting)
  3. 对于最终的输出结果而言,随机森林使用多数投票或者简单平均;而 GBDT 则是将所有结果累加起来,或者加权累加起来
  4. 随机森林对异常值不敏感,GBDT 对异常值非常敏感
  5. 随机森林对训练集一视同仁权值一样,GBDT 是基于权值的弱分类器的集成
  6. 随机森林通过减小模型的方差提高性能,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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,542评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,596评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,021评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,682评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,792评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,985评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,107评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,845评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,299评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,612评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,747评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,441评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,072评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,828评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,069评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,545评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,658评论 2 350

推荐阅读更多精彩内容