Qintong Wu作者

InfiniteBoosting: 集成bagging与boosting的混合算法

去年,俄罗斯的研究者 Alex Rogozhnikov 和 Tatiana Likhomanenko提出了一种集 bagging 和 boosting 两者之长的混合算法 InfiniteBoosting。机器之心对相关论文进行了简要解读和编译。相关算法的实现也已发布在 GitHub 上。

论文地址:https://arxiv.org/abs/1706.01109

代码地址:https://github.com/arogozhnikov/infiniteboost

引言

集成方法有广泛的应用和优良的准确度,因此自发明伊始就一直很引人注目。在集成方法大家庭中,bagging 和 boosting 算法具有一些共同特性,但训练过程却不一样。一般而言,bagging 有益于降低方差,而 boosting 则同时注重偏差和方差。但众所周知 boosting 往往会与数据集过拟合,从而导致方差更高。

集成方法的有效性已经在数据竞赛中得到了成功证明:Kaggle 挑战赛中 60% 的获胜方案都使用了 XGBoost(一种常见的 boosting 算法)。一位竞赛获胜者 Qingchen Wang 甚至做出了这样的极端表述:“我只使用 XGBoost。”

为了将 bagging 和 boosting 的最优特性结合到一起,该论文提出了一种混合算法——InfiniteBoosting,其会构造一个任意大的集成树(ensemble tree)并以梯度提升(gradient boosting)的方式训练每个弱学习器。由于其混合特性,这个算法构建的分类器能在每个训练步骤降低偏差,同时还能控制过拟合

bagging 和 boosting

首先看看 bagging 方法。bagging 是 bootstrap aggregatin(自举汇聚算法)的缩写,下面的等式展示了它的原理:在自举的数据集上训练许多弱学习器 f_b(x),然后取平均,输出学习结果。这里,自举(bootstrap)的意思是从原始数据集随机生成不同的数据样本(掷 n 次 n 面骰子)。

遵循这一思想,可以很自然地引入随机森林算法,因为决策树就是弱学习器的一种完美候选方法。单个决策树具有低偏差和高方差等特性。在聚合了很多树之后,偏差仍保持不变,但方差会下降。通过构建足够大的随机森林,我们可以实现尽可能低的恒定偏差。

现在再看 boosting。boosting 背后的基本思想是能否通过重点关注弱点的提升来修改弱学习器,使其变得更好。这是通过多次使用弱学习方法来获得连续假设而实现的,其中每一次都会再次关注之前认为困难和误分类的样本。通过这种做法,boosting 能帮助弱学习器变强。下面的等式表明 boosting 的最终输出是弱学习器的加权平均(投票法),其中 α_t 是考虑了前一次迭代的误差后计算得到的权重

下图展示了 boosting 算法的典型学习过程。每个学习器都会从上一个学习器的失败中学习,并通过累积所有学习器的输出而输出正确结果。

InfiniteBoosting

InfiniteBoosting 的目标是通过 boosting 过程构建一个无限集成方法。不同于梯度提升方法,InfiniteBoosting 通过在每次迭代用权重 α_t 求所有弱学习器的平均,然后乘以被称为 capacity 的常量 c,而不是梯度提升方法中那样的线性组合。为了详细说明它们的不同之处,这里引用了原论文中的算法过程:

分析

InfiniteBoosting 算法引入了 bagging 和 boosting 的特性,其具有与梯度提升一样的学习过程,但不同之处是会更新重新加权的输出,而不是数学累积。我们可以轻松得出结论:这个算法是一个随机森林,其每个树都会从其它树中的错误中学习;或者说这是梯度提升的修改版本,只是更新方法不同。

该论文展示了这个算法的有效性:只要每个树在训练数据上的输出都是有界且连续的,那么该算法几乎就肯定会收敛到解。同时,我们应该注意到任何机器学习算法的误差都是偏差和方差的总和。bagging 方法通过学习器之间的不关联性来最小化方差,从而降低方差,但这会导致偏差略微上升。boosting 方法通过聚合不同模型的输出来降低偏差,但这会导致方差增大。因此,这两种方法的混合方法 InfiniteBoosting 永远无法突破其中任意一种方法的局限性,而且它可能无限逼近 bagging 或 boosting 的结果。

InfiniteBoosting 的明显优势是能让 bagging 或 boosting 处理它们一开始并不适合处理的任务。换句话说,这种方法在不同的数据集或任务上是稳健的。当数据足够时,其总能实现 bagging 和 boosting 其中之一的最佳表现。

但是,要收敛到一个固定点,其需要足够大的数据集和更长的训练时间。我猜测这个缺点不会妨碍太多应用,因为现在数据无处不在,计算资源也在随时间增长。

实验结果

我们可以根据结果得到结论:相比于梯度提升随机森林方法,InfiniteBossting 的结果相近但稍好一点。这个结果也与上一节的分析吻合。

结论

InfiniteBoosting 克服了 bagging 和 boosting 两者的缺点,从而略微提升了表现水平。其最重要的方面是适应性。其延展了任何单独的 bagging 和 boosting 方法的处理范围,所以更多应用都能享受到 bagging 和 boosting 两者的好处了。



理论随机森林梯度提升过拟合
1
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

提升算法技术

Boosting是一种主要用于减少偏差的机器学习集成元算法,也是监督学习的一个变化,是一种将弱学习器转换为强学习器的机器学习算法家族。 Boosting是基于Kearns和Valiant(1988,1989)提出的问题:一组弱学习器能创造一个强大的学习器吗?一个弱的学习器被定义为一个分类器,它与真实的分类只有轻微的相关性(它可以比随机猜测更好地标注示例)。相反,强大的学习器是一个与真实分类任意相关的分类器。

梯度提升技术

梯度提升是用于回归和分类问题的机器学习技术,其以弱预测模型(通常为决策树)的集合的形式产生预测模型。 它像其他增强方法一样以阶段式方式构建模型,并且通过允许优化任意可微损失函数来推广它们。

随机森林技术

在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。而"Random Forests"是他们的商标。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林(random decision forests)而来的。这个方法则是结合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造决策树的集合。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

XGBoost技术

XGBoost是一个开源软件库,为C ++,Java,Python,R,和Julia提供了渐变增强框架。 它适用于Linux,Windows,MacOS。从项目描述来看,它旨在提供一个“可扩展,便携式和分布式的梯度提升(GBM,GBRT,GBDT)库”。 除了在一台机器上运行,它还支持分布式处理框架Apache Hadoop,Apache Spark和Apache Flink。 由于它是许多机器学习大赛中获胜团队的首选算法,因此它已经赢得了很多人的关注。

推荐文章
暂无评论
暂无评论~