在线Bagging
- 提出者
- Oza, N. C. & Russell, S.
- 年份
- 2001
- 类型
- Online ensemble (streaming bagging)
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
在线Bagging是由Oza和Russell在2001年提出的一种流式集成方法,它将经典的bootstrap聚合(Bagging)框架适应于在线学习场景。每个传入的实例不是通过重采样固定数据集获得,而是以服从泊松分布(泊松(1))的次数被馈送到每个基学习器中,从而在流演进过程中忠实地近似bootstrap采样。其结果是一个鲁棒的、增量更新的集成模型,能够处理概念漂移和连续数据到达,而无需存储整个数据集。
方法背后的直觉
经典的Bagging从固定数据集中抽取随机bootstrap样本,并为每个样本训练一棵树。在线Bagging在从未一次性看到整个数据集的情况下模仿了这一点:当新样本到达时,它会根据从均值为1的泊松分布中抽取的随机次数被传递给每个基学习器。平均而言,每个学习器会看到该样本一次——这正是bootstrap重采样在批量模式下实现的效果——但这种随机性会使学习器去相关。由于不需要存储数据,集成模型可以随着流的增长而无限增长,并随着时间的推移自然地适应分布的变化。
历史学
在线Bagging由Nitesh Oza和Stuart Russell在2001年的AISTATS会议上提出,作为Breiman 1996年Bagging算法在在线场景下的理论和实践扩展。关键的创新——用每个实例的泊松(1)加权替换bootstrap重采样——使得近似在数学上严谨。它成为流式机器学习文献中的基础算法,并且是MOA(Massive Online Analysis)等平台的基线集成模型,自2010年以来,MOA驱动了大多数流式分类器的实证评估。
何时使用
当数据以连续流的形式到达,并且存储完整数据集不可行或被禁止时(例如,传感器日志、点击流、金融Tick数据、实时监控),请使用在线Bagging。当您需要分类或回归,并且模型需要随着每个新观测值进行更新,能够容忍轻微的概念漂移,并且保持内存效率时,它就很合适。不要将在线Bagging作为批量随机森林在固定、中小型数据集上的即插即用替代品——在这些情况下,具有交叉验证的批量集成模型会表现得更好。当数据流表现出严重 abrupt 漂移而没有添加显式的漂移检测机制时,也要避免使用它。
局限与注意事项
- 在静态数据集上,批量方法(如随机森林或XGBoost)的表现始终优于在线Bagging,因为它们可以使用完整的交叉验证和最优分裂。
- 基本的在线Bagging对严重的概念漂移的抵抗能力有限;必须外部添加专门的漂移检测器(例如,ADWIN)。
- 泊松加权为每个实例引入了额外的方差,这可能会减慢短流的收敛速度。
- 可解释性较低:许多增量增长的树组成的集成模型比单个决策树更难检查。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 一次处理一个实例,内存恒定,支持真正无界的数据流。
- 泊松加权被证明可以近似bootstrap重采样,从而提供与批量Bagging相当的集成方差降低效果。
- 自然可并行化:每个基学习器独立更新,适合分布式流式架构。
- 没有像树深度那样敏感的超参数——集成模型通过多样性进行自我正则化。
- 无需结构性改变即可轻松扩展到多类分类和回归。
应用
- 对连续交易流进行实时欺诈检测。
- 在工业物联网环境中,从传感器数据流中进行预测性维护。
- 在线广告中的点击率预测,其中用户行为不断演变。
- 对高吞吐量数据包流进行网络入侵检测。
- 环境监测:对空气质量或天气传感器读数进行增量分类。
使用方式
使用方式
对于每个到达的实例,都会为每个基学习器独立地从泊松(1)分布中采样一个权重k。权重为0意味着学习器完全跳过该实例;权重为2意味着它学习该实例两次。这种随机加权是bootstrap重采样的在线对应物,也是该算法的数学核心。
公式
k \sim \text{Poisson}(1)每个基学习器——通常是增量决策树,如Hoeffding树——接收带有其分配权重的当前实例,并立即更新其内部模型。处理完后不存储任何实例。这种单遍处理的特性使内存保持有界,并允许集成模型扩展到任意长的流。
当需要进行预测时,所有M个基学习器都会为查询实例产生其个体输出。集成模型通过多数投票(分类)或算术平均(回归)组合这些输出,产生与批量Bagging相同的聚合逻辑,但计算的是增量训练的模型。
公式
\hat{y} = \text{mode/mean of } M \text{ base learners}常见陷阱
- 使用在训练开始前创建的保留测试集来评估在线Bagging——应改用预取(先测试后训练)评估,这是流式机器学习的标准。
- 假设默认的基学习器数量(通常为10)足够;通常需要至少50-100个学习器的集成模型才能获得稳定的预测。
- 忽略概念漂移:在没有漂移检测的情况下,在漂移流上部署在线Bagging会导致准确率的静默下降。
- 在静态基准上将准确率与批量方法进行比较,并得出在线Bagging较差的结论——正确的比较是在流式基准上每看到一个实例的准确率。
- 使用并非真正增量的基学习器(例如,重新训练的批量树),这会抵消在线框架的内存和速度优势。
常见问题
为什么是泊松(1)?
当n趋于无穷大时,均值为1的泊松分布近似了观测值在大小为n的bootstrap样本中出现的次数。每个学习器每个实例使用泊松(1)精确地复制了这种极限行为,使得在线近似在理论上是合理的。
在线Bagging与自适应随机森林有何不同?
自适应随机森林(Gomes等,2017)通过在每个分裂点添加随机特征子采样(类似于批量随机森林)并集成每个树的漂移检测器(当检测到概念漂移时重置单个学习器)来扩展在线Bagging。在线Bagging是更简单的基础;自适应随机森林是建立在其之上的当前最先进的流式集成模型。
应该使用哪个基学习器?
最常见的选择是Hoeffding树(也称为VFDT),它是典型的增量决策树。它使用Hoeffding界来决定在节点上看到多少数据足以进行分裂,从而使树无需存储过去实例即可进行更新。
需要多少个基学习器?
MOA框架中的实证基准测试表明,对于大多数流式任务,需要50-100个基学习器才能获得稳定的集成性能。较少的学习器会降低计算成本,但会增加预测方差,尤其是在流的早期阶段。
如何评估在线Bagging分类器?
使用预取评估:对于每个传入的实例,首先预测其标签,然后更新模型。准确率计算为正确预测的运行平均值。这避免了任何前瞻性偏差,并反映了真实的部署条件。
相关方法
参考文献
Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.
打开出版物文献已复制。Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.
打开出版物文献已复制。