跳转至

统计机器学习09：提升Boosting与Ensemble

本页统计信息

  • 本页约 1577 个字, 预计阅读时间 5 分钟。

  • 本页总阅读量次

基本介绍

提升方法其实就是用多个不同的决策方法组合而成，根据不同方法的决策情况来进行最后的决策，也就是说不在一棵树上直接吊死，而是多找几棵树看看那棵树的风水最好再吊上去。

强可学习与弱可学习

如果可以用一个多项式复杂度的学习算法学习一个概念，并且正确率很高，那么这个概念就是强可学习的，如果学习的效果仅仅比随机猜测稍微好一点，那就是弱可学习的。如果预测的正确率还不如随机猜测，那这种算法属实没有存在的必要

弱可学习的算法一般比较容易学习，相比于强可学习算法更容易获得并且训练所需要的cost往往也更少，因此我们就产生了一个想法，是不是可以通过多个比较弱的学习算法一起预测结果，然后根据这些算法的预测结果再决定最后的分类结果。

  • 但是决策的结果往往是少数服从多数，即"极大似然法"，我们暂且不讨论是否会出现多数人的暴政

  • 可以给不同的分类器设定一个不同的权重，分类效果比较好的可以设置比较大的权重，这类通过组合多个算法共同预测的机器学习算法就是ensemble method

ensemble有效性的证明

这种看似缝合怪的机器学习方法也叫做Combining Models，顾名思义也就是将多个不同的model组合到一起共同预测结果，如果M个模型的权重是相同的，那么预测结果可以表示成：

\[ y_{COM}=\frac 1 M \sum_{i=1}^My_i(x) \]

那么为什么ensemble method的集体决策效果要比单个分类器的预测效果好呢？我们可以假设真实的模型是\(h(x)\)，那么M个不同的模型组合而成的新模型的误差期望是：

\[ \begin{aligned} E_{COM}=E((y_{COM}-h(x))^2)=E((\frac 1 M \sum_{i=1}^My_i(x)-h(x))^2)\\=\frac 1{M^2}\sum_{i=1}^ME((y_i-h(x)^2)=\frac 1M E_{AV} \end{aligned} \]

我们发现通过ensemble方法，模型的variance变成了原来的\(\frac 1M\)，因此这种方法确实可以提高预测的准确性，因为它减小了模型的variance，使得模型的预测结果更加稳定。

如何生成多个模型：Bagging

我们现在已经知道模型的组合可以提高预测结果的稳定性，那么我们如何来生成多个模型进行组合呢？常见的方法有两种，一种是Bagging，另一种是Boosting

Bagging是通过不同的数据集划分方式来训练出多个模型，是一种可以并行的模型训练方式，它的两个关键步骤可以概括为：

  • Bootstrap sampling：从数据集D中生成若干组不同的大小为N的训练集，并训练出一系列基学习器(Base Learner)

  • Aggregating：即模型组合的策略，往往在分类模型中采用voting策略，即选择可能性最高的，而在回归问题中使用averaging，取平均数

Bagging方法在基学习器是弱可学习的时候提升效果非常好，这一点也可以理解，因为Bagging方法的本质是生成了一系列乌合之众，然后用voting策略来预测结果，但是乌合之众的规模变大的时候准确度也会有所提高。

这里的基学习器可以选择各类线性模型或者神经网络，也可以使用决策树，因为决策树是一种比较容易获得的非线性分类器，并且bias非常小而variance非常高，我们用ensemble的方式刚好可以降低决策树的variance，得到bias和variance都比较小的模型，而这种使用决策树作为基学习器的Bagging模型叫做随机森林(Random Forest)，这个名字也比较形象，很多"树"聚集成了森林。

Boosting方法与AdaBoost

与Bagging方法不同Boosting方法是一种迭代式的训练算法，其中比较著名的就是AdaBoost，这是一种串行的Ensemble方法，通过若干次迭代的训练将训练数据学习成若干个弱分类器，然后通过调整权重来提高模型预测的准确度。

AdaBoost算法步骤

  1. 将训练集D中的N个训练数据赋予初始的权重，一般来说是所有样本之间都相等，即

$$ D_1=(w_{11},w_{12},\dots,w_{1N})\quad w_{1i}=\frac 1N $$

  1. 对数据进行一共M轮的迭代，第m轮的时候训练数据的权重分布是\(D_m\)，并训练得到一个弱分类器\(G_m(x)\)，然后计算这个分类器的训练误差：

$$ e_m=\sum_{i=1}NP(G_m(x_i)\not=y_i)=\sum_{i=1}Nw_{mi}\mathbb I(G_m(x_i)\not=y_i) $$

  1. 然后计算该分类器的系数：

$$ \alpha_m=\frac 12\log \frac {1-e_m}{e_m} $$

  1. 更新整个训练集的权重分布\(D_{m+1}=(w_{m+1,1},w_{m+1,2},\dots,w_{m+1,N})\)，其中\(Z_m\)叫做规范化因子，很明显这样的规范化因子使得前面的系数的和变成了1，也就是说权重系数成为了一个概率分布
\[ \begin{aligned} w_{m+1,i}=\frac{\exp(-\alpha_my_iG_m(x_i))}{Z_m}w_{m,i}\\ Z_m=\sum_{i=1}^N\exp(-\alpha_my_iG_m(x_i))w_{m,i} \end{aligned} \]
  1. 最后生成一个各个若分类器进行线性组合，形成权重不同的强分类器：
\[ \begin{aligned} f(x)&=\sum_{i=1}^M\alpha_mG_m(x)\\G(x)&=\mathrm{sign}(f(x))=\mathrm{sign}(\sum_{i=1}^M\alpha_mG_m(x)) \end{aligned} \]

AdaBoost误差分析

AdaBoost存在一个误差上界：

\[ \frac 1N\sum_{i=1}^N\mathbb I(G_m(x_i)\not=y_i)\le \frac 1N\sum_i\exp(-y_if(x_i))=\prod_mZ_m \]

而对于一个二分类的问题，有：

\[ \begin{aligned} \prod_{m=1}^MZ_m&=\prod_{m=1}^M2\sqrt{e_m(1-e_m)}\\ &=\prod_{m=1}^M\sqrt{1-4\gamma_m^2}\le\exp(-2\prod_{m=1}^M\gamma^2_m) \end{aligned} \]

其中\(\gamma_m=\frac 12-e_m\)

颜色主题调整

评论区~

有用的话请给我个star或者follow我的账号!! 非常感谢!!
快来跟我聊天~