On Imbalanced Regression with Hoeffding Trees

Dit artikel introduceert een streaming-variant van kernel density schatting en integratie van hiërarchische shrinkage voor Hoeffding-bomen in onbalansregressie, waarbij empirische resultaten aantonen dat kernel density schatting de vroege prestaties verbetert terwijl hiërarchische shrinkage beperkte winst oplevert.

De kern

De Grote Droom: Een slimme voorspeller die nooit stopt

Stel je voor dat je een enorme stroom van data hebt, zoals een rivier die nooit droogvalt. Denk aan sensoren die de temperatuur meten, taxi's die door New York rijden, of machines in een fabriek die trillen. Deze data komt continu binnen, seconde voor seconde.

In de wereld van kunstmatige intelligentie proberen we modellen te bouwen die deze stroom kunnen "lezen" en voorspellingen kunnen doen. Een van de populairste manieren om dit te doen is met Hoeffding-bomen.

De Analogie: De Snelweg-Verkeersagent
Stel je een Hoeffding-boom voor als een slimme verkeersagent op een drukke snelweg.

• Hij kijkt naar de auto's (de data) die voorbijrijden.
• Hij maakt snelle beslissingen: "Als het regent en het is donker, ga dan linksaf."
• Hij doet dit niet door de hele dag te wachten tot alle auto's voorbij zijn (dat is te langzaam), maar hij neemt beslissingen op basis van wat hij nu ziet.

Het Probleem: De "Rare" Auto's

Het probleem is dat deze data vaak ongelijk verdeeld is (in het Engels: imbalanced).

• In de stroom van New York-taxi's zijn er duizenden ritjes van 5 kilometer, maar misschien maar één ritje van 500 kilometer.
• In fabrieksdata zijn er duizenden normale metingen, maar slechts één meting die aangeeft dat een machine bijna kapot gaat.

De verkeersagent (het model) wordt zo gewend aan de "normale" auto's, dat hij de "rare" auto's (de zeldzame, maar belangrijke waarden) helemaal negeert. Hij leert alleen wat de meeste mensen doen, en vergeet de uitzonderingen.

De Oplossing: Twee Nieuwe Hulpmiddelen

De auteurs van dit paper hebben twee nieuwe trucjes bedacht om deze verkeersagent slimmer te maken, zodat hij ook de rare auto's goed kan voorspellen.

1. De "Drukte-kaart" (KDE - Kernel Density Estimation)

Stel je voor dat je de verkeersagent een speciale bril geeft. In plaats van alleen naar de auto's te kijken die nu voorbijrijden, ziet hij een drukte-kaart van de hele rivier.

• Hoe het werkt: Als er een zeldzame, lange rit komt, kijkt de agent niet alleen naar die ene auto. Hij kijkt ook naar de auto's die er iets voor of iets na kwamen. Hij "gladstrijkt" de data.
• De Metafoor: Het is alsof je in een drukke menigte probeert iemand te vinden. Als je alleen naar die ene persoon kijkt, zie je misschien niets. Maar als je kijkt naar de hele groep mensen om die persoon heen, zie je duidelijk dat er iemand is.
• Het Resultaat: De onderzoekers hebben deze techniek (KDE) aangepast zodat hij werkt in een snelle stroom (online learning). Het bleek een grote winst te zijn. De agent werd veel beter in het voorspellen van die rare, zeldzame waarden.

2. De "Ouderwetse Regel" (Hierarchical Shrinkage - HS)

De tweede truc is een beetje als een strenge leraar die de verkeersagent probeert te corrigeren.

• Hoe het werkt: De agent maakt een voorspelling. De "leraar" (HS) kijkt naar de hele route die de agent heeft afgelegd (van de start tot de beslissing) en zegt: "Hé, je bent misschien te ver gegaan in je conclusie. Laten we de voorspelling iets meer naar het gemiddelde trekken, voor de zekerheid."
• De Metafoor: Het is alsof je een jongen die een bal gooit, zegt: "Je gooit te hard, probeer het iets zachter."
• Het Resultaat: De onderzoekers dachten dat dit ook zou helpen, maar het bleek niet echt te werken in deze snelle stroomsituatie. Het gaf nauwelijks een verbetering. De agent had de "drukte-kaart" (KDE) veel harder nodig dan de "strenge leraar" (HS).

Wat hebben ze gedaan? (Het Experiment)

De onderzoekers hebben dit getest op echte data:

• Oesters: Hoe zwaar is een oester? (Vaak kleine oesters, zelden grote).
• Huisprijzen: Hoeveel kost een huis in Californië?
• Taxi's: Hoe ver reist een taxi?
• Stroomverbruik: Hoeveel energie gebruiken huishoudens?

Ze lieten hun modellen (de verkeersagenten) deze data stromen en keken of de nieuwe bril (KDE) en de strenge leraar (HS) hielpen.

De Conclusie in Eén Zin

Als je een slimme computer wilt bouwen die continu data verwerkt en goed moet voorspellen, zelfs bij rare gebeurtenissen, geef hem dan een "drukte-kaart" (KDE) om de data te gladder te maken. De "strenge leraar" (HS) is leuk om te hebben, maar helpt in dit geval niet echt.

Kort samengevat:

• Hoeffding-bomen: Snelle beslissingsbomen voor datastromen.
• Het probleem: Ze vergeten zeldzame waarden.
• De oplossing: Gebruik een techniek om de data te "gladstrijken" (KDE).
• Het resultaat: De voorspellingen worden veel beter, vooral voor de zeldzame dingen. De andere techniek (HS) werkt niet zo goed.

De code die ze hebben geschreven is gratis beschikbaar, zodat iedereen deze "slimme bril" voor hun eigen datastromen kan gebruiken.

Technische samenvatting

Probleemstelling

Het paper adresseert twee fundamentele uitdagingen in het machine learning-domein die vaak samen voorkomen in real-world toepassingen:

1. Datastromen (Data Streams): Veel sensoren en systemen genereren continue datastromen die online (incrementeel) verwerkt moeten worden, waarbij modellen niet opnieuw getraind kunnen worden op de volledige dataset. Hoeffding-bomen (en hun varianten) zijn hierin de standaard voor incrementele besluitbomen.
2. Ongelijke Regressie (Imbalanced Regression): In tegenstelling tot classificatie, waar onbalans vaak verwijst naar zeldzame klassen, verwijst dit in regressie naar een scheefverdeling van de doelvariabele (labels). Bijvoorbeeld, het voorspellen van extreme weersomstandigheden of zeldzame leeftijdsgroepen. Bestaande methoden voor onbalans zijn vaak gericht op batch-learning (waar alle data vooraf bekend is) of op classificatie, en zijn niet direct toepasbaar op streaming regressie.

De auteurs onderzoeken hoe bestaande batch-methoden voor onbalans en regularisatie geïntegreerd kunnen worden in incrementele besluitboom-algoritmen voor regressie.

Methodologie

De auteurs combineren twee recente technieken uit het batch-learning domein met incrementele besluitbomen:

1. Kernel Density Estimation (KDE) voor Streaming:

   • In batch-learning wordt KDE gebruikt om voorspellingen te "gladstrijken" (smoothen) door de verdeling van de labels te schatten.
   • De auteurs passen dit toe op datastromen door een telescopische update-formule te gebruiken. In plaats van de volledige dataset te herberekenen, wordt de KDE-schatting voor een bin (interval) bijgewerkt op basis van de vorige schatting en de nieuwste observatie.
   • Ze gebruiken een "tumbling window" (een schuifvenster) om de lokale verdeling van de labels te schatten. Dit helpt bij het voorspellen van waarden in gebieden met weinig data (de "staart" van de verdeling).

2. Hiërarchische Schroefing (Hierarchical Shrinkage - HS):

   • HS is een regularisatietechniek waarbij de voorspelling niet alleen afhangt van het bladknooppunt, maar een gewogen som is van alle knooppunten langs het pad van de wortel tot het blad.
   • Dit wordt geïmplementeerd als een post-hoc correctie die de structuur van de boom niet verandert, maar de voorspelling regulariseert door de invloed van knooppunten met weinig steekproeven te verminderen.
   • De auteurs integreren dit in incrementele bomen door de nodige statistieken (aantal samples per knooppunt) tijdens het streamen bij te houden.

3. Online Learning en Tuning:

   • Er wordt een variatie van het Follow-the-Leader (FTL) algoritme gebruikt voor hyperparameter-tuning.
   • Het systeem wisselt periodiek tussen een "tuning-fase" (waar meerdere modelconfiguraties parallel worden getraind op een deel van de stream) en een "voorspellingsfase". De beste configuratie wordt vervolgens geselecteerd voor de volgende fase.

Belangrijkste Bijdragen

1. Implementatie van HS in Incrementele Bomen: De auteurs zijn de eersten die Hiërarchische Schroefing integreren in incrementele besluitbomen (specifiek in de bibliotheken scikit-multiflow en River) voor regressie-taken.
2. Streaming KDE: Ze hebben KDE succesvol aangepast voor datastromen via een telescopische update-methode, waardoor het toepasbaar wordt voor onbalans in regressie zonder de volledige dataset te hoeven opslaan.
3. Empirische Evaluatie: Uitgebreide experimenten op standaard online regressie-benchmarks (zoals Abalone, California Housing, NY Taxi, E-Power en Semi) om de effectiviteit van deze technieken te testen.
4. Open Source: De implementatie is openbaar beschikbaar gesteld, wat de reproduceerbaarheid en verdere ontwikkeling bevordert.

Resultaten

De experimenten leverden de volgende inzichten op:

• KDE is zeer effectief: De integratie van KDE resulteert consequent in een verbeterde prestatie, vooral in de vroege fasen van de datastream en bij onbalans.
  • In de scikit-multiflow experimenten presteerden KDE-varianten (met of zonder HS) in alle datasets beter dan de basismodellen, behalve bij E-Power waar de basis HT soms beter scoorde.
  • In de River experimenten (zonder online tuning vanwege tijdbeperkingen) verbeterde KDE de prestaties in 18 van de 24 gevallen voor RMSE en in 15 van de 24 gevallen voor WRMSE (Weighted RMSE).
• HS levert beperkte winst op: Hoewel Hiërarchische Schroefing een interessante regularisatiemethode is, leverde het in de meeste gevallen slechts minimale of geen extra verbetering op ten opzichte van de basismodellen of KDE alleen.
• Vroege Prestaties: KDE helpt vooral bij het verbeteren van de voorspellingen in het begin van de stream, waar de dataverdeling nog niet goed is ingeschat.
• Metrieken: De verbeteringen zijn het meest zichtbaar in Weighted RMSE (WRMSE), een metriek die zwaarder weegt voor zeldzame labelwaarden, wat aantoont dat de methode effectief is voor onbalans.

Betekenis en Toekomstperspectief

Dit paper is significant omdat het de kloof overbrugt tussen geavanceerde batch-methoden voor onbalans en de eisen van online learning. Het bewijst dat KDE een krachtige tool is om de voorspelling van incrementele regressiemodellen te verbeteren in onbalante scenario's.

De auteurs concluderen dat:

• KDE een robuuste oplossing biedt voor onbalans in datastromen.
• HS minder kritisch is voor deze specifieke toepassing, hoewel het een nuttige regularisatiemethode blijft.
• Toekomstig werk zich moet richten op het combineren van deze technieken met concept drift (veranderingen in de dataverdeling over tijd), aangezien dit een cruciale uitdaging is in echte datastromen.
• De principes van KDE mogelijk ook toepasbaar zijn op ensemble-methoden zoals Random Forests voor streaming data.

Kortom, het paper biedt een praktische en effectieve aanpak om de voorspelbaarheid van Hoeffding-bomen voor regressie te verbeteren in realistische, onbalante datastromen.