Research map / Continual learning / Class-incremental
MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MIST, a streaming decision tree for exemplar-free online class-incremental tabular learning, using a K-independent McDiarmid radius for Gini splits, Bayesian truncated-Gaussian inheritance at splits, and per-leaf KLL sketches for thresholds and non-parametric prediction.
Problem
Streaming decision trees fail in online class-incremental learning on tabular data because Hoeffding-style split radii derived from Information Gain grow with the class count, and children start cold after splits.
Approach
Derives a tight bounded-difference constant (4/n) for Gini split gain that is independent of K, pairs it with a Bayesian parent-to-child inheritance via truncated-Gaussian moments, and uses per-leaf label-aware KLL sketches for both split thresholds and a distribution-free leaf predictor.
Key results
- MIST-G average accuracy 0.8225 and MIST-K 0.8323 on ten standard datasets, versus 0.6397 for VFDT and 0.7578 for ARF-NR among tree methods.
- Removing Bayesian inheritance drops average accuracy by 9.55% relative (0.8225 to 0.7439).
- On the AngularSectors stress test MIST-K reaches 0.436 while SQDA gets 0.235 and ARF-NR 0.255; non-tree SLDA/SQDA/NCM baselines reach 0.8420/0.8863/0.7845 averages, above MIST on standard tables.
Surprising findings
- Non-tree global parametric baselines such as SQDA (0.8863 mean) outperform MIST on standard benchmarks, with MIST's advantage confined to non-Gaussian stress tests.
- Disabling drift detectors in EFDT and HAT was needed to avoid near-random performance, indicating drift-reset failures are protocol mismatch.
Limitations
- Gaussian leaf (MIST-G) inheritance relies on Gaussian assumptions; MIST-K bypasses this via sketches at higher memory cost.
- Split decisions use a per-decision union bound rather than time-uniform confidence sequences, so multiple-testing effects over infinite horizons are not formally handled.
- Non-tree baselines outperform MIST on near-Gaussian standard benchmarks; Letter yields zero splits under default settings.
Experimental setup
Datasets: Synth-10 Synth-50 Covertype Split-MNIST Pendigits Shuttle Letter Wine Iris HAR
Benchmarks: Synth-10 Synth-50 Covertype Split-MNIST Pendigits Shuttle Letter Wine Iris HAR Antipodal Multimodal
Metrics: final mean accuracy average forgetting prequential accuracy
Baselines: VFDT Rutkowski EFDT (NR) HAT (NR) ARF-NR SLDA SQDA NCM RLS PEC
Builds on: VFDT EFDT Hoeffding Adaptive Tree Rutkowski et al. McDiarmid Gini bound KLL sketch
Closest papers by meaning
- Non-exemplar Online Class-Incremental Continual Learning via Dual-Prototype Self-Augment and Refinement (AAAI 2024 · similarity 0.86)
- Enhancing Online Continual Learning with Plug-and-Play State Space Model and Class-Conditional Mixture of Discretization (CVPR 2025 · similarity 0.85)
- Adaptive Decision Boundary for Few-Shot Class-Incremental Learning (AAAI 2025 · similarity 0.85)
- Adaptive Discovering and Merging for Incremental Novel Class Discovery (AAAI 2024 · similarity 0.84)
- Long-Tail Class Incremental Learning via Independent Sub-prototype Construction (CVPR 2024 · similarity 0.84)
- MIND: Multi-Task Incremental Network Distillation (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.