解决流式决策树在增量分类中的可靠性问题,提升持续学习性能。
MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound

- 用麦克迪阿米德界构建与类别数无关的稳定分裂准则
- 在非高斯数据上优于当前最佳方法,且保持内存恒定
- 适合需要持续学习和低内存占用的工业级流数据场景
流式决策树是开放世界持续学习的自然选择,因其支持局部更新、内存有界和静态决策边界。然而,在在线增量分类任务中仍表现不佳,主要源于两个耦合的校准偏差:(i) 随着类别数K增加,分裂准则的可靠性下降;(ii) 分裂时缺乏知识传递。两者根源相同:信息增益的范围本质上随log2 K增长。因此,任何基于此的信息增益置信半径必然随类别数扩大,导致实现与类别数无关的分裂准则在结构上不可行。为此,本文提出MIST(McDiarmid Incremental Streaming Tree),通过三个集成模块解决上述问题:(i) 采用紧致、与类别数无关的麦克迪阿米德置信半径用于基尼分裂,作为结构正则化;(ii) 设计贝叶斯继承协议,通过截断正态矩将父节点统计量投影至子节点,其方差缩减保证在最保守分裂时最强;(iii) 每个叶节点使用KLL分位数草图,统一支持连续阈值评估与几何自适应预测。在标准及压力测试的表格流数据上,MIST在近高斯基准上媲美全局参数方法,在非高斯几何下尤为鲁棒,而现有顶尖方法在此类数据上已崩溃。
原文摘要 · Abstract (English)
Streaming decision trees are natural candidates for open-world continual learning, as they perform local updates, enjoy bounded memory, and static decision boundaries. Despite these, they still fail in online class-incremental learning due to two coupled miscalibrations: (i) their split criterion grows unreliable as the class count K expands, and (ii) the absence of knowledge transfer at split time. Both failures share a common root: the range of Information Gain intrinsically scales with log2 K. Consequently, any Hoeffding-style confidence radius derived from it must inevitably grow with the class count, making a K-independent split criterion structurally impossible, taking away the potential benefits of applying streaming decision trees to continual learning. To fix this issue, we present MIST (McDiarmid Incremental Streaming Tree), which resolves both failures through three integrated components: (i) a tight, K-independent McDiarmid confidence radius for Gini splitting that acts as a structural regulariser; (ii) a Bayesian inheritance protocol that projects parent statistics to child nodes via truncated-Gaussian moments, with variance reduction guarantees strongest precisely when splitting is most conservative; and (iii) per-leaf KLL quantile sketches that support both continuous threshold evaluation and geometry-adaptive leaf prediction from a single data structure. On standard and stress-test tabular streams, MIST is competitive with global parametric methods on near-Gaussian benchmarks and uniquely robust on non-Gaussian geometry where SOTA benchmarks collapse.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。