去年,俄罗斯的研究者 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 两者的好处了。