跳转至

集成学习

信息
  • 这里的"基分类器"/"分类器"指的就是参与集成学习中使用的单个分类器. 事实上, "分类器"这个术语并不准确, 因为有一些问题不是分类问题, 而是回归问题, 我们可以使用更加通用的术语"基学习器"或者"基模型"来代替基分类器. 这里, 为了和网上广大的教程(包括悉大的课件)保持统一, 就称其为"基分类器".

传统的机器学习算法(如决策树, 人工神经网络, 支持向量机, 朴素贝叶斯等)的目标都是寻找一个最优分类器尽可能将训练数据分开. 集成学习, Ensemble Learning算法的基本思想就是将多个分类器组合, 从而实现一个预测效果更好的集成分类器. 集成算法可以描述为: "三个臭皮匠, 赛过诸葛亮".

集成算法大致上可以分为: Bagging, Boosting和Stacking等类型.

为何要集成学习

使用集成学习具有很多优势:

  • 统计上的优势: 一个学习算法可以理解为在一个假设空间中找到一个最好的假设(假设空间是指所有可能的模型或者假设的集合). 但是, 当训练样本的数据量小到不够用来准确的学习到目标假设的时候, 学习算法可以找到很多满足训练样本的分类器. 所以, 学习算法选择任何一个分类器都会面临一定错误预测的风险, 因此将多个假设集成起来可以降低错误分类器的风险
  • 计算上的优势: 很多学习算法在进行最优化搜索的时候很可能陷入局部最优的错误中, 因此对于学习算法而言很难得到一个全局最优的假设. 事实上人工神经网络和决策树已经被证明是一个NP问题. 集成算法可以从多个起始点进行局部搜索, 从而分散陷入局部最优的风险
  • 表示上的优势: 在现实中, 假设空间中的任意一个单一模型(假设)通常难以完美的表示(或者近似的表示)数据的真实分类函数. 换句话说, 一个单一的模型不足以捕捉数据的复杂性, 无法做出准确的预测. 集成学习算法, 如Boosting, 通过组合多个不同的基分类器来形成一个更强的模型. 这些基分类器不是简单的平均组合, 而是通过加权的方式, 赋予每个基分类器不同的权重. 加权组合的结果可以看作是在原本假设空间基础上扩展了一个新的假设空间, 这个扩展后的假设空间更加灵活, 更优能力去逼近真正的分类函数

如我们通过组合25个二元基分类器得到了一个集成学习模型. 每一个二元基分类器的错误率\(\epsilon=0.35\), 即准度为\(0.65\).

  1. 若所有的基分类器都是相同的, 即会犯同样的错误. 那么得到的集成学习模型在测试集上的错误率为\(0.35\)
  2. 若所有的基分类器是独立的, 即他们犯的错误是没有关联的, 那么得到的集成学习模型是否错误取决于是否有超过半数的基分类器预测错误(假设采用投票的方式选出结果), 即有超过\(13\)个基分类器预测错误. 我们需要计算的是\(13\)个基分类器预测错误的概率+\(14\)次基分类器预测错误的概率+...+\(25\)次基分类器预测错误的概率, 即\(\sum_{i=13}^{25}\binom{25}{i}\epsilon^i(1-\epsilon)^{25-i}=0.06\)(符合二项分布). 可以看到出错的概率显著减小, \(0.06<0.35\)

在上述例子中, 基分类器错误率和得到的集成学习模型错误率的关系如图所示:

description

从图中我们可以看到, 当基分类器错误率大于\(0.5\)的时候, 集成学习模型的错误率甚至会高于基分类器的错误率. 这种情况下基分类器的预测比在两个类别之间随机猜的结果还差.

所以, 我们可以得出结论, 如果要使集成学习模型表现比单个基分类器更好:

  • 基分类器的错误率要低, 对于二元分类器来说, 至少至少你要比随机乱猜要好
  • 基分类器之间必须相互独立, 在实践中, 我们无法做到每个基分类器的所有训练样本都是不同的, 即我们无法做到基分类器之间的完全独立. 事实上, 经验表明, 当基分类器之间有轻微关联的时候, 往往得到的集成学习模型效果会更好

构建集成学习模型的方法

构建学习模型本质上是要产生不同的, 尽量没有依赖的基分类器. 这个可以通过以下几种方式实现:

  • 操纵训练数据: 通过抽样产生不同的训练数据/或同一份数据但是样本不同权重用于训练模型, 典型的集成学习模型有Bagging和Boosting
  • 操作属性: 通过使用总体属性的子属性集用于训练模型, 典型的集成学习模型有随机森林, Random Subspace
  • ... 待添加

Bagging

Bagging(Bootstrap Aggregating)由Breimam于1996年提出, 基本思想如下:

  1. 每次采用有放回的抽样从训练集中取出\(n\)个样本组成新的训练集
  2. 利用新的训练集, 训练得到\(M\)个子模型\(\{h_1, h_2, ..., h_M\}\)
  3. 对于分类问题, 采用投票的方法, 得票最多的分类为最终的类别; 对于回归问题, 采用简单的取平均方法得到预测值

注意, 初始状态是一个\(n\)个元素的训练集, Bagging产生的训练集也有\(n\)个元素, 是从原始训练集中有放回的抽样产生的, 所以其中有一些样本可能在新的训练集中出现多次, 有些可能一次都不出现. 任意一个样本不被选中的概率是\(1-\frac{1}{n}\), 因为我们进行的是有放回的抽样, 总共抽\(m\)次, 每次抽样都是独立事件, 因此一个特定版本在\(m\)次抽样中都不被选中的概率是\((1-\frac{1}{n})^m\), 那么, 这个样本至少被选中一次的概率就是\(1-(1-\frac{1}{n})^m\), 所以说, 对于\(n\)个元素的原始训练集, 平均会有\(1-(1-\frac{1}{n})^m\)的样本会被抽样到新的训练集中.

如图所示, 这是一个\(3\)次抽样的例子.

产生数个新的训练集后, 对于每一个训练集都训练一个基分类器, 获取所有基分类器的预测结果, 进行投票, 票数多的结果就是集成学习模型的预测结果. 注意, 这里所有的基分类器的权重都是一样的, 即所有基分类器的投票权都是相等的, 民主投票.

随机森林

随机森林(Random Forests)是一种利用决策树作为基分类器的Bagging集成学习算法. 随机森林的构建过程如下:

  1. 数据采样

    作为一种Bagging集成算法, 随机森林同样采取有放回的采样, 对于总体训练集\(T\), 抽样一个子集\(T_{sub}\)作为训练样本集. 除此之外, 假设总体训练集的特征个数为\(d\), 每次仅选择\(k(k<d)\)个作为训练样本集的特征. 因此, 随机森林除了能够做到抗样本扰动外, 还添加了特征扰动, 对于特征的选择个数, 推荐值为\(k=\log_2 d\).

  2. 树的构建

    每次根据采样得到的数据和特征构建一颗决策树. 在构建决策树的过程中, 会让决策树生长完全不进行预剪枝. 构建出的若干棵决策树组成了最终的随机森林. 预测的方法同Bagging.

Boosting

Boosting是一种提升算法, 可以将弱的学习算法提升为强的学习算法. 基本思想如下:

  1. 初始训练: 首先, 从初始训练数据集训练一个基分类器(如决策树, 线性模型等). 这个基分类器可能并不完美, 但是它会对大多数样本做出合理的预测
  2. 调整样本权重: 对于那些被机器学习错误预测的样本, 提高他们的权重. 这意味着在下一轮训练的时候, 这些错误分类的样本将获得更大的关注, 使得后续的基分类器能够更好地处理这些困难样本
  3. 迭代训练: 在每一轮中, 利用调整后的样本权重训练新的基分类器. 这个过程会重复多次, 每次都会生成一个新的分类器, 并且每个新的分类器都试图修正前一个分类器的错误
  4. 组合结果: 最终, 将所有的基分类器的结果进行组合. 对于分类问题, 采用有权重的投票方式来决定最终的分类结果; 对于回归问题, 采用加权平均的方式得到最终的预测值. 权重的分配依据每个基分类器的准确性, 表现好的分类器会获得更大的权重

Adaboost

Adaboost由Freund和Schapire在1996年发明.

Adaboost是Boosting的经典实现之一. 它的每一个训练样本都带有一个权重, 权重越高, 说明先前的基分类器在预测它的时候错误率较高, 表示这个样本“较难”预测. 这个样本在下一个新训练集中出现的可能性较高(出现的次数可能会多). 最终, 在所有基分类器结果组合的时候, 是非民主投票, 也就是说, 错误率小的分类器的投票权更大, 权重更高.

可以用图表表示:

其中, 1个矩形对应1个训练样本. 矩形的高度对应样本的权重. ✅和❌对应样本是否被当前的基分类器正确预测. 决策树图片的大小对应在最终预测结果里面的权重.

算法如下:

  1. 有\(N\)个样本\(\{x_n, y_n\}\), \(y_n\in \{+1, -1\}\)
  2. 初始化所有样本的权重\(w_1(n)=\frac{1}{n}\)
  3. 对于\(t\)从\(1\)到\(T\):
    1. 使用当前的的训练集训练一个基分类器\(h_t(x)\), 最小化错误率\(\epsilon_t = \sum_n w_t(n)\mathbb{I}[y_n\neq h_t(x_n)]\). 注意, \(\mathbb{I}\)表示指示函数, 当条件为真时, \(\mathbb{I}[\)条件\(]=1\), 当条件为假时, \(\mathbb{I}[\)条件\(]=0\)
    2. 计算基分类器在最终决策中的贡献\(\beta_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}\)
    3. 更新当前训练集样本的权重\(w_{t+1}(n)\propto w_t(n)e^{-\beta_ty_nh_t(x_n)}\), 为什么用\(\propto\)? 因为在更新权重之前, 还要进行归一化, 使得\(\sum_n w_{t+1}(n)=1\)
  4. 输出最终的分类器\(h[x]=sign[\sum_{t=1}^T\beta_th_t(x)]\)

下面是一个例子:

这里, 我们假设每次训练前抽样过程中被抽中的都是同一批样本.

注意:

  • 这些数据点显然不是线性可分的
  • 在一开始的时候, 所以的样本的权重都是相同的, 注意图中+和-号的大小
  • 选择的基分类器是一个很垃圾的分类器: 根据单一属性进行决策, 即"决策树桩", Decision Stump. 在图中会显示为横分割线或竖分割线

可以看到, 图中圈出来的三个+号是预测错误的, 错误率\(\epsilon_1\)为\(\frac{1}{10}+\frac{1}{10}+\frac{1}{10}=0.3\), 可以计算出该基分类器的权重为\(\beta_1 = 0.42\). 然后我们要更新当前训练集中样本的权重: 对于预测错误的样本, 其新的权重为\((\frac{1}{10}\times e^{-0.42\times 1\times -1})/[\frac{1}{10}\times e^{-0.42\times 1\times -1}\times 3 + \frac{1}{10}\times e^{-0.42\times 1\times 1}\times 2 + \frac{1}{10}\times e^{-0.42\times -1\times -1}\times 5]=0.072\). 对于预测正确的样本, 其新的权重为\(0.17\).

计算权重使用的代码, bn表示在归一化之前, an表示在归一化之后.

import math
import numpy as np

w_error_bn = (1/10)*math.e**(0.42)
w_not_error_bn = (1/10)*math.e**(-0.42)
w_bn = np.array([w_error_bn]*3+[w_not_error_bn]*7)
w_an = np.array(w_bn/np.sum(w_bn))

print(w_an)

输出:

[0.16605851 0.16605851 0.16605851 0.07168921 0.07168921 0.07168921
0.07168921 0.07168921 0.07168921 0.07168921]

可以看到, 图中圈出来的三个-号是预测错误的, 错误率为\(\epsilon_2\)为\(0.072\times 3=0.216\), 可以计算出该基分类器的权重为\(\beta_2=0.65\). 然后我们要更新当前训练集中样本的权重: 对于预测错误的样本, 其新的权重为\(0.167\), 对于预测正确的样本, 其新的权重为\(0.0456\)或\(0.105\).

代码为:

import math
import numpy as np

w_error_bn = 0.072*math.e**(0.65)
w_not_error_bn_1 = 0.072*math.e**(-0.65)
w_not_error_bn_2 = 0.166*math.e**(-0.65)
w_bn = np.array([w_error_bn]*3+[w_not_error_bn_1]*4+[w_not_error_bn_2]*3)
w_an = np.array(w_bn/np.sum(w_bn))

print(w_an)

输出:

[0.16736013 0.16736013 0.16736013 0.04561096 0.04561096 0.04561096 
0.04561096 0.10515859 0.10515859 0.10515859]

可以看到, 图中圈出来的2个+号和1个-号是预测错误的. 错误率\(\epsilon_3\)为\(0.0456*3=0.1368\), 可以算出该分类器的权重为\(\beta_3=0.921\). 不用更新训练集的权重, 因为已经是最后一个了.

最终, 得到最终的分类器, 经过非民主投票, 可以得到某一个新样本的预测结果, 如图:

原理

Adaboost最小化分类错误的损失函数. 假设我们现在有一个分类器\(h(x)=sign[f(x)]\), 如果\(f(x)>0\), 则\(h(x)=1\); 如果\(f(x)<0\), 则\(h(x)=-1\). 这里的\(f(x)\)指的就是集成学习加权投票的值, 即\(f(x)=\sum_{t=1}^T \beta_th_t(x)\), 经过取符号\(sign()\)之后就得到最终结果.

一种比较自然的损失函数为0-1损失函数, 即如果\(yf(x)>0\), 就是\(f(x)\)和\(y\)的符号相同, 则\(\ell(h(x), y)=0\); 如果\(yf(x)<0\), 就是\(f(x)\)和\(y\)的符号不同, 则\(\ell(h(x), y)=1\). 但是这种函数不是凸的, 也就是说局部最小值不是全局最小值, 可能存在多个局部最小值, 这增加了找到全局最优解的难度. 所以, 我们一般使用一个代理损失函数, 如指数损失函数\(\ell^{EXP}(h(x),y)=e^{-yf(x)}\). 这个函数的图像如下:

那么, 假设我们现在已经有了第\(t-1\)次训练后的集成学习的加权投票的值\(f_{t-1}(x)\), 现在需要加入一个新的基分类器\(h_t(x)\)得到最终的加权投票的值\(f(x)=f_{t-1}(x)+\beta_t h_t(x)\), 那么, 我们应该怎么选择最优的分类器\(h_t(x)\)和系数\(\beta_t\)呢?

我们使用\(h^*_t(x)\)和\(\beta_t^*\)表示\(t\)轮训练的最优值. 也就是说, 我们要最小化\(t\)轮的指数损失函数, \((h^*_t(x), \beta^*_t)=argmin_{(h_t(x), \beta_t)}\sum_n e^{-y_nf(x_n)}=argmin_{(h_t(x), \beta_t)}\sum_n e^{-y_n[f_{t-1}(x_n)+\beta_th_t(x_n)]}=argmin_{(h_t(x), \beta_t)}\sum_n w_t(n)e^{-y_n\beta_t h_t(x_n)}\), 其中\(w_t(n)=e^{-y_nf_{t-1}(x_n)}\).

现在, 我们可以将这个损失函数拆分为两个部分, \(\sum_n w_t(n)e^{-y_n\beta_th_t(x_n)}=\sum_n w_t(n)e^{\beta_t}\mathbb{I}[y_n\neq h_t(x_n)]+\sum_n w_t(n)e^{-\beta_t}\mathbb{I}[y_n=h_t(x_n)]=\sum_n w_t(n)e^{\beta_t}\mathbb{I}[y_n\neq h_t(x_n)]+\sum_n w_t(n)e^{-\beta_t}(1-\mathbb{I}[y_n\neq h_t(x_n)])=(e^{\beta_t}-e^{-\beta_t})\sum_n w_t(n)\mathbb{I}[y_n\neq h_t(x_n)]+e^{-\beta_t}\sum_n w_t(n)\).

我们可以这样拆分的原因是:

  • \(y_nh_t(x_n)\)的结果不是\(1\)就是\(-1\)
  • \(h_t(x_n)\)是当前弱分类器的判断
  • 指示器函数\(\mathbb{I}[y_n=h_t(x_n)]\)不是\(0\)就是\(1\), 所以\(1-\mathbb{I}[y_n=h_t(x_n)]\)不是\(0\)就是\(1\)

总结, \((h^*_t(x), \beta^*_t)=argmin_{(h_t(x), \beta_t)}(e^{\beta_t}-e^{-\beta_t})\sum_n w_t(n)\mathbb{I}[y_n\neq h_t(x_n)]+e^{-\beta_t}\sum_n w_t(n)\). 之前我们说过, \(w_t(n)=e^{-y_nf_{t-1}(x_n)}\), \(y_n\)是第\(n\)个样本的真实标签, \(f_{t-1}(x_n)\)是第\(t-1\)轮所有弱分类器加权投票后的值, 可以看出\(\sum_n w_t(n)\)这一部分其实等于\(1\)(因为在\(t-1\)轮结束之前会对所有的样本权重进行归一化处理), 和选择\(h_t(x)\)是没有关系的. 所以\(h^*_t(x)=argmin_{h_t(x)}\epsilon_t=\sum_n w_t(n)\mathbb{I}[y_n\neq h_t(x_n)]\), 正好对应于Adaboost算法的第3.1步. 细心的同学可能会发现, 那\(\beta_t\)不是和这个损失函数也有关系吗? 不错, 是有关系, 但是我们这里将联合优化问题分解, 采用分步优化, 首先选择的是最佳的\(h_t(x)\), 然后才选择最佳的\(\beta_t\). 我们可以通过损失函数对\(\beta_t\)求导, 令其等于\(0\), 从而求解最优的\(\beta_t\), 可以解出\(\beta^*_t=\frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}\), 正好对应于Adaboost算法的第3.2步.

当我们求出最优的弱分类器和它的权重之后, 我们就可以更新分类器\(f(x)=f_{t-1}(x)+\beta^*_t h_t^*(x)\). 第\(n\)个样本的权重\(w_{t+1}(n)\propto e^{-y_nf(x_n)}=e^{-y_n[f_{t-1}(x)+\beta^*_t h^*_t(x_n)]}=w_t(n)e^{-y_n\beta^*_th^*_t(x_n)}\), 然后对其进行归一化处理. 从而, 分类错误的样本它的权重会增加, 分类正确的样本它的权重会减少.

元算法

Adaboost是一种元算法. 因为它并不具体规定我们应该如何获取最优的弱分类器\(h^*_t(x)\). 它只关心在每一轮中, 我们选择的弱分类器能够最小化\(\epsilon_t=\sum_n w_t(n)\mathbb{I}[y_n\neq h_t(x_n)]\). 换句话说, 任何一种能够达到这一目标的分类器方法都可以被用于Adaboost中, 无论是决策树, 朴素贝叶斯, 支持向量机等, 都可以被作为Adaboost的弱分类器使用.

  1. 范叶亮. (n.d.). 集成学习算法 (Ensemble Learning) - 范叶亮 | Leo Van. 范叶亮的个人网站 | Leo Van’s Personal Website. From https://leovan.me/cn/2018/12/ensemble-learning/ ↩

评论