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 两者的好处了。