MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound

Technische Samenvatting: MIST – Betrouwbare Streaming Beslissingsbomen voor Online Class-Incrementeel Leren

1. Probleemstelling

Het artikel behandelt de uitdaging van Online Class-Incrementeel Leren (Online CIL) in tabulaire settings onder strikte beperkingen: verwerking in één doorgang, geen toegang tot historische data (exemplaar-vrij) en begrensd geheugen. Hoewel streaming beslissingsbomen theoretisch ideaal zijn voor dit regime vanwege hun lokale updates en statische beslissingsgrenzen, betogen de auteurs dat ze in de praktijk falen voor Online CIL door twee gekoppelde tekortkomingen:

1. Voorbarige Splits (K-Schaling Instabiliteit): Bestaande streamingbomen (bijv. VFDT, EFDT) vertrouwen op Hoeffding-begrenzingen afgeleid van Informatiewinst. Aangezien het bereik van Informatiewinst schaalt met $\log_2 K$ (waarbij $K$ het aantal klassen is), groeit de betrouwbaarheidsstraal naarmate $K$ toeneemt. Dit maakt het splitsingscriterium onbetrouwbaar in open-wereld settings waar $K$ onbegrensd is, wat leidt tot ofwel vertraagde noodzakelijke splitsen of voorbarige, ruisige splitsen.
2. Koude-start Instabiliteit: Wanneer een blad splitst, initialiseren standaard streamingbomen de kindknopen zonder voorafgaande informatie. In een exemplaar-vrije setting moeten deze kinderen voorspellende verdelingen vanaf nul herbouwen met behulp van schaarse data. Deze "koude-start" fase produceert onbetrouwbare voorspellingen en blaast onzuiverheidsschattingen op, wat verdere voorbarige splitsen triggert en instabiliteit versterkt.

2. Methodologie: Het MIST Kader

De auteurs stellen MIST (McDiarmid Incremental Streaming Tree) voor, dat deze tekortkomingen oplost via drie geïntegreerde componenten:

A. Strikte, K-Onafhankelijke Splitsingscriterium (McDiarmid Kalibratie)
In plaats van Informatiewinst gebruikt MIST Gini-onzuiverheid, die een bereik heeft dat begrensd is in $[0, 1)$ ongeacht $K$. De auteurs leiden een strakke begrensd-verschilconstante af voor de Gini-splitwinst onder vervanging van één steekproef.

• Theoretisch Resultaat: Zij bewijzen dat de begrensd-verschilconstante $c_i = 4/n$ is voor willekeurige $K$, wat een verbetering is ten opzichte van eerdere grenzen van $8/n$ (Rutkowski et al.) of $4/n$ alleen voor $K=2$ (De Rosa en Cesa-Bianchi).
• Operationele Straal: Dit levert een betrouwbaarheidsstraal $\epsilon = \sqrt{32 \ln(2dm/\delta)/n}$ op die onafhankelijk is van het globale aantal klassen $K$. Dit fungeert als een "structurele regularisator", wat voorbarige splitsen voorkomt naarmate de klassenruimte uitbreidt.

B. Bayesiaanse Kennisovererving
Om het koude-startprobleem aan te pakken, implementeert MIST een ouder-naar-kind projectieprotocol op het moment van splitsen:

• Afgekapt-Gaussische Projectie: Voor continue kenmerken worden de Gaussische parameters van de ouder (gemiddelde $\mu$ en variantie $\sigma^2$) geprojecteerd op de kindknopen met behulp van exacte afgekapt-Gaussische conditionele momenten gebaseerd op de splitsdrempel.
• Massa Herschaling: Klassmassa en Dirichlet pseudo-aantallen worden herschaald op basis van de massastroom die naar elk kind gaat.
• Variantiereductie: Theoretisch schaalt de variantie van de posterieure schattingen van het kind omgekeerd evenredig met het steekproefaantal van de ouder ($O(1/\alpha n_{ouder})$). Dit zorgt ervoor dat conservatieve splitsen (alleen getriggerd door data-rijke ouders) sterke, statistisch onderbouwde priors opleveren voor de kinderen, waardoor post-split onzekerheid wordt geminimaliseerd.

C. Unificatie Label-bewuste Schetsing (KLL Quantielen)
Om continue drempelbeoordeling te hanteren zonder ruwe data te behouden, maakt MIST gebruik van KLL quantiel-schetsen in elk blad:

• Dubbele Rol: Dezelfde schetsstructuur dient twee doelen: (1) het genereren van kandidaat-splitdrempels uit empirische klass-conditionele verdelingen, en (2) het aandrijven van een niet-parametrisch bladvoorspeller (MIST-K) voor geometrie-adaptieve inferentie.
• Geheugenefficiëntie: De schetsen ondersteunen continue drempelbeoordeling zonder bewaring van ruwe data. Naarmate bladeren zuiverder worden, neemt het aantal actieve klassen per blad ($K_{lokaal}$) af, wat het geheugengebruik op natuurlijke wijze begrenst.
• Adaptieve Voorspelling: MIST biedt twee configuraties: MIST-G (parametrisch, gebruikmakend van Gaussische accumulators voor voorspelling) en MIST-K (niet-parametrisch, gebruikmakend van uit schetsen afgeleide CDF's voor voorspelling), waardoor het systeem zich kan aanpassen aan Gaussische of niet-Gaussische data-geometrieën.

3. Belangrijkste Bijdragen

1. Strikte McDiarmid Kalibratie: De afleiding van een scherpe, K-onafhankelijke begrensd-verschilconstante ($4/n$) voor Gini-splitwinst, wat een splitsingscriterium mogelijk maakt dat niet degradeert naarmate nieuwe klassen arriveren.
2. Bayesiaanse Post-split Stabilisatie: Een formeel overervingsmechanisme met behulp van afgekapt-Gaussische momenten en Dirichlet-herschaling, met bewezen variantiereductiegaranties die schalen met het steekproefaantal van de ouder.
3. Unificatie Schetsarchitectuur: Een enkele datastructuur (KLL-schetsen) die zowel continue splitbeoordeling als distributie-vrije bladvoorspelling mogelijk maakt, waardoor de noodzaak voor bewaring van ruwe data wordt geëlimineerd.
4. Regime-bewuste Empirische Karakterisering: Identificatie van voorwaarden waarbij parametrische (Gaussische) versus niet-parametrische (op schetsen gebaseerde) voorspellers de voorkeur verdienen, gevalideerd door stress-tests op niet-Gaussische geometrieën.

4. Experimentele Resultaten

De auteurs evalueren MIST op standaard tabulaire benchmarks (bijv. Covertype, Split-MNIST, HAR) en synthetische stress-tests met niet-Gaussische geometrieën (Multimodaal, Scheef, Hoeksectoren, Antipodaal).

• Standaard Benchmarks: MIST-G en MIST-K zijn concurrerend met globale parametrische methoden (SLDA, SQDA) op bijna-Gaussische datasets. Opmerkelijk is dat MIST dit bereikt met aanzienlijk minder vergeten dan andere boom-gebaseerde methoden (VFDT, EFDT) en globale methoden.
• Niet-Gaussische Stress-tests: Op datasets met complexe geometrieën (bijv. Hoeksectoren, Multimodaal) zakken globale parametrische methoden en ensemblebomen (ARF-NR) af tot prestaties die dicht bij het toeval liggen. MIST-K, gebruikmakend van zijn niet-parametrische op schetsen gebaseerde voorspeller, blijft uniek robuust en presteert aanzienlijk beter dan alle baselines.
• Ablatie Studies:
  • Het verwijderen van overerving veroorzaakt een daling in nauwkeurigheid van ongeveer 9,5%, wat koude-start instabiliteit bevestigt als een primaire faalmodus.
  • Het vervangen van GNB-bladeren door meerderheidsstemming veroorzaakt een ineenstorting van ongeveer 72%, wat de noodzaak van dichtheidsmodellering benadrukt.
  • De McDiarmid-straal fungeert als een structurele regularisator; het gebruik van Hoeffding-begrenzingen leidt tot aanzienlijk grotere bomen met marginale nauwkeurigheidswinst maar hogere instabiliteit.

5. Betekenis en Claims

Het artikel beweert dat MIST aantoont dat streaming beslissingsbomen een natuurlijk modulaire architectuur kunnen zijn voor open-wereld continu leren. Door lokale voorspellende modules strikt te ontkoppelen terwijl op het moment van splitsen statistisch onderbouwde kennisoverdracht mogelijk wordt, biedt MIST een principiële basis voor leermiddelen die groeien zonder catastrofale vergetelheid.

De auteurs benadrukken dat hun aanpak exemplaar-vrij is (geen buffers met ruwe data), één-doorgang en onbegrensd in klassenset. Zij positioneren MIST als een oplossing die de kloof vult tussen streaming data mining (die vaak class-incrementaliteit negeert) en continu leren (dat vaak vertrouwen stelt op replay of voorgeprogrammeerde backbones). Het werk valideert dat lokale updates en begrensd vergeten niet ten koste hoeven te gaan van nauwkeurigheid, mits het splitsingscriterium structureel gezond is en kennisoverdracht is geformaliseerd.

Erkende Beperkingen:

• MIST-G vertrouwt op Gaussische aannames voor zijn overervingsprojectie, wat MIST-K omzeilt via schetsing.
• De huidige implementatie gebruikt per-beslissing uniebegrenzingen; de auteurs identificeren tijd-uniforme betrouwbaarheidssequenties via niet-negatieve supermartingalen als een richting voor toekomstig werk om het splitsmoment verder te optimaliseren over oneindige horizonnen.