Experiments with Optimal Model Trees

Dit artikel onderzoekt empirisch of modelbomen met lineaire support vector machines in de bladeren, die via gemengd-gehele lineaire programmering globaal optimaal worden geconstrueerd, concurrerende nauwkeurigheid kunnen bieden met zeer kleine en interpreteerbare bomen in vergelijking met traditionele, lokaal optimale algoritmen.

De kern

Stel je voor dat je een heel slimme, maar soms wat verwarrende gids hebt die je helpt om moeilijke beslissingen te nemen. Of het nu gaat om het voorspellen van de prijs van een huis, het diagnosticeren van een ziekte, of het bepalen of een e-mail spam is. In de wereld van kunstmatige intelligentie noemen we zo'n gids een machine learning-model.

Deze wetenschappelijke paper van Sabino Roselli en Eibe Frank gaat over een specifieke soort gids: de Modelboom. Laten we dit uitleggen alsof we in een koffiehuis zitten, zonder ingewikkelde wiskundige termen.

1. Het probleem: De "Stomme" Boom vs. De "Slimme" Boom

Stel je een gewone beslissingsboom voor als een gigantische "Wie is het?"-game.

• Vraag: Is de persoon ouder dan 30?
  • Ja: Ga naar links.
  • Nee: Ga naar rechts.
• Vraag: Heeft hij een baard?
  • Ja: Ga naar links...

Op het einde van zo'n boom (in het "blad" van de boom) staat een simpel antwoord: "Ja, dit is spam" of "Nee, dit is geen spam". Dit werkt goed, maar het is een beetje star. Het is alsof je zegt: "Alle mensen ouder dan 30 met een baard zijn spam." Dat is vaak te simpel.

Modelbomen zijn slimmer. Ze doen hetzelfde met de vragen (de takken), maar in de bladeren (het einde) geven ze geen simpel "Ja/Nee" of een vast getal. In plaats daarvan geven ze een formule.

• Voorbeeld: In plaats van te zeggen "De prijs is €200.000", zegt de boom in het blad: "De prijs is €50.000 + (€100 per vierkante meter)".
  Dit maakt de boom veel flexibeler en vaak nauwkeuriger, zonder dat hij onbegrijpelijk wordt.

2. Het dilemma: Snelheid vs. Perfectie

Hoe bouw je zo'n boom?

• De snelle methode (Gierig): De meeste computers bouwen bomen "gierig". Ze kijken naar de eerste vraag, kiezen de beste split die ze nu zien, en gaan dan direct door naar de volgende. Ze kijken nooit terug.
  • Analogie: Het is alsof je een wegkaart tekent door elke keer de eerste afslag te nemen die eruitziet alsof hij goed is. Je komt misschien wel op je bestemming, maar je rijdt vaak een omweg. De boom wordt groot en rommelig.
• De perfecte methode (Optimaal): Wat als we de hele boom in één keer zouden kunnen plannen? We zouden kunnen kijken naar alle mogelijke vragen en alle mogelijke formules, en de beste combinatie kiezen die de kleinste en meest accurate boom oplevert.
  • Analogie: Dit is alsof je een GPS gebruikt die alle mogelijke routes in de wereld berekent om de écht kortste weg te vinden. Dit is veel nauwkeuriger, maar het kost enorm veel tijd om te rekenen.

Vroeger was deze "perfecte" methode te traag om te gebruiken. Maar de auteurs van dit paper hebben een nieuwe manier gevonden om dit te doen met een krachtige rekenmachine (MILP-solvers).

3. Wat hebben ze gedaan?

De auteurs hebben gekeken of ze deze "perfecte" methode kunnen gebruiken om Modelbomen te bouwen. Ze wilden weten:

1. Kunnen we bomen bouwen die kleiner zijn (makkelijker te begrijpen voor mensen)?
2. Zijn ze nauwkeuriger dan de snelle, "gierige" methoden?
3. Hoeveel tijd kost het?

Ze hebben dit getest op veel verschillende datasets (zoals medische gegevens, financiële data, etc.) en vergeleken met andere bekende methoden zoals "Random Forests" (een groep van bomen die samenwerken) en standaard beslissingsbomen.

4. De resultaten: De verrassing

Hier zijn de belangrijkste bevindingen, vertaald naar alledaags taal:

• Kleiner en slimmer: De "perfecte" modelbomen die ze hebben gebouwd, waren vaak kleiner dan de bomen van de andere methoden, maar nauwkeuriger. Het is alsof ze een compacte, slimme gids hebben gebouwd die hetzelfde doet als een dikke, rommelige handleiding, maar dan in één pagina.
• De kracht van de formule: Omdat de bladeren van hun boom formules bevatten (in plaats van vaste getallen), hoefden ze niet zo'n diepe boom te maken om goede voorspellingen te doen.
• De prijs van perfectie (Tijd): Er is een nadeel. Het bouwen van deze perfecte boom kost veel rekenkracht. Voor sommige grote datasets duurde het uren (of zelfs tot de tijdslimiet van een uur) voordat de computer klaar was.
  • Analogie: Het is alsof je een meesterwerk schildert. Het resultaat is prachtig, maar het kost je een week. De "gierige" methode is alsof je een snel schetsje maakt in 5 minuten. Het schetsje is vaak goed genoeg, maar het meesterwerk is beter.
• Wanneer is het nuttig? De auteurs concluderen dat deze methode perfect is voor situaties waar begrijpelijkheid (interpretatie) heel belangrijk is. Als je in een ziekenhuis of bij een rechtbank zit, wil je misschien niet de snelste, maar de kleinste en duidelijkste uitleg. Dan is het de moeite waard om even te wachten op de perfecte boom.

5. Samenvatting in één zin

De auteurs hebben bewezen dat je met genoeg rekenkracht kleine, super-nauwkeurige en makkelijk te begrijpen "gidsen" kunt bouwen die beter presteren dan de standaard, snel gebouwd modellen, zelfs al kost het bouwen ervan wat meer tijd.

Het is een stap in de richting van betrouwbare en transparante AI, waar we niet alleen weten wat de computer voorspelt, maar ook precies hoe en waarom het dat doet, zonder in een woud van onbegrijpelijke regels te verdwalen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Experiments with Optimal Model Trees" van Roselli en Frank, geschreven in het Nederlands.

Titel: Experimenten met Optimale Modelbomen

Auteurs: Sabino Francesco Roselli en Eibe Frank

---

1. Probleemstelling

Modelbomen (model trees) zijn een krachtige methode voor interpretable machine learning die zowel voor classificatie als regressie kan worden gebruikt. In tegenstelling tot klassieke beslisbomen, die constante waarden in de bladeren gebruiken, gebruiken modelbomen lineaire combinaties van voorspellers in de bladeren. Dit kan leiden tot hogere nauwkeurigheid en kleinere bomen.

Het huidige probleem is dat de meeste algoritmen voor het leren van modelbomen gierig (greedy) werken. Ze bouwen de boom top-down op door lokaal optimale splitsingen te kiezen, zonder terug te kijken naar eerdere knopen. Dit leidt vaak tot:

• Lokaal optimale, maar niet globaal optimale bomen.
• Onnodig complexe en grote bomen om een bepaalde nauwkeurigheid te bereiken.
• Een verlies van interpreteerbaarheid door de grootte van de boom.

Hoewel er methoden zijn voor het vinden van optimale beslisbomen (met constante waarden) via Mixed-Integer Linear Programming (MILP), is er weinig onderzoek gedaan naar het vinden van globaal optimale modelbomen (met lineaire modellen in de bladeren) voor zowel classificatie als regressie.

2. Methodologie

De auteurs stellen een nieuwe aanpak voor die gebruikmaakt van Mixed-Integer Linear Programming (MILP) om globaal optimale modelbomen te construeren.

Kerncomponenten:

• MILP Formulering: Het leerproces wordt gemodelleerd als een optimalisatieprobleem waarbij zowel de discrete boomstructuur (welke splitsingen) als de continue parameters van de lineaire modellen in de bladeren gelijktijdig worden geoptimaliseerd.
• Leaf Node Modellen: In plaats van constante waarden, gebruiken de bladeren Lineaire Support Vector Machines (SVM):
  • Voor regressie: Lineaire SVM met $\epsilon$-insensitive loss (equivalent aan L1-geregulariseerde lineaire regressie).
  • Voor classificatie: Lineaire SVM (voor binair en meerklassig).
• Boomstructuur:
  • De boom wordt gedefinieerd als een perfecte boom van diepte $D$.
  • Variabelen bepalen of een knopen splitst ($d_n$) en op welk kenmerk (voor univariate) of welke lineaire combinatie (voor multivariate).
  • Er wordt gebruikgemaakt van "Big-M" methoden om logische voorwaarden (zoals "als de ouder niet splitst, splitst het kind ook niet") te lineariseren.
• Univariate vs. Multivariate:
  • Univariate: Splitsingen gebeuren op één enkel kenmerk.
  • Multivariate: Splitsingen gebeuren op een lineaire combinatie van kenmerken. Dit kan de nauwkeurigheid verhogen ten koste van de interpreteerbaarheid.
• Hyperparameter-tuning: De auteurs gebruiken een validatie-set om de beste combinatie van de regularisatieparameter $C$ (voor de SVM) en het maximale aantal splitsingen $S$ te vinden.

3. Belangrijkste Bijdragen

1. Nieuwe MILP Formuleringen: De auteurs presenteren specifieke MILP-formuleringen voor:
   • Univariate en multivariate regressie modelbomen (ORMT).
   • Univariate en multivariate classificatie modelbomen (OCMT), inclusief meerklassige classificatie.
2. Empirische Evaluatie: Een uitgebreide vergelijking op 25 classificatie-datasets (OpenML) en 20 regressie-datasets.
3. Vergelijking met State-of-the-Art: De methode wordt vergeleken met:
   • Andere optimale bomen (OCT, ORT, DL8.5).
   • Gierige algoritmen (CART, M5P, LMT).
   • Geavanceerde methoden met lokale zoekopdrachten (LS-OMT).
   • Random Forests en standaard SVM's.
4. Inzicht in Schaalbaarheid: Een analyse van de rekentijd en de haalbaarheid van het vinden van de globale optimum binnen redelijke tijdslimieten.

4. Resultaten

De experimenten tonen de volgende resultaten:

• Nauwkeurigheid vs. Grootte:
  • Optimale modelbomen (ORMT/OCMT) presteren aanzienlijk beter dan optimale bomen met constante waarden (ORT/OCT) van dezelfde grootte.
  • In vergelijking met gierige algoritmen (zoals CART en M5P) bereiken de optimale modelbomen vergelijkbare of betere nauwkeurigheid, maar zijn ze consistent kleiner (minder bladeren).
  • Voor regressie was ORT (met SVM's) in 9 van de 20 gevallen nauwkeuriger dan alle andere methoden, en vaak aanzienlijk beter dan ORT zonder SVM's.
• Interpreteerbaarheid:
  • Omdat de bomen kleiner zijn, blijven ze beter interpreteerbaar. Klassieke gierige methoden zoals CART produceerden vaak zeer grote bomen (tot wel 250 bladeren), terwijl de optimale methoden vaak onder de 10 bladeren bleven.
• Univariate vs. Multivariate:
  • Multivariate bomen (OCMT-H/ORMT-H) presteerden niet overal beter dan univariate bomen. Ze waren soms beter, maar vaak niet significant. De extra complexiteit en het verlies aan interpreteerbaarheid (door lineaire combinaties in splitsingen) wegen niet altijd op tegen de winst in nauwkeurigheid.
• Rekentijd en Schaalbaarheid:
  • De grootste beperking is de rekentijd. Het vinden van de globale optimum voor bomen met meer dan één split (d.w.z. meer dan 2 bladeren) leidde bijna altijd tot een time-out (na 3600 seconden) voor grotere datasets.
  • Desondanks waren de tussentijdse oplossingen (die binnen de tijdslimiet werden gevonden) vaak al goed genoeg om te concurreren met, of zelfs te verslaan, gierige algoritmen.
  • Voor datasets met een beperkte grootte (tot ~1000-2000 datapunten) is de methode haalbaar.

5. Betekenis en Conclusie

De studie bevestigt dat MILP een natuurlijke en krachtige aanpak is voor het leren van modelbomen, vanwege de mix van discrete structuur en continue parameters.

• Voor interpretatie-kritische toepassingen: Waar het belangrijk is om kleine, nauwkeurige en begrijpelijke modellen te hebben (bijvoorbeeld in gezondheidszorg of finance), biedt deze methode een superieur alternatief voor gierige bomen.
• Beperkingen: De methode schaalt niet goed naar zeer grote datasets of zeer diepe bomen binnen een redelijke tijdslimiet.
• Toekomst: De auteurs suggereren het gebruik van decompositiemethoden om de rekentijd te verkorten en het toepassen van deze technieken op optimale beleidsbomen (policy trees).

Kortom, hoewel de berekening duur is, levert deze aanpak modellen op die de balans tussen nauwkeurigheid en interpreteerbaarheid (kleine boomgrootte) beter optimaliseren dan bestaande methoden.