A Comparative Study of Model Selection Criteria for Symbolic Regression

Technische Samenvatting: Een Comparatieve Studie van Criteria voor Modelselectie bij Symbolische Regressie

Probleemstelling
Symbolische Regressie (SR), doorgaans opgelost via Genetische Programmering (GP), streeft naar het ontdekken van wiskundige expressies die nauwkeurigheid en complexiteit in evenwicht brengen. Hoewel moderne GP-implementaties een Pareto-front van kandidaatoplossingen genereren, blijft de automatische selectie van een enkel model dat goed generaliseert naar ongezette data een open uitdaging. Bestaande literatuur biedt diverse informatie-theoretische en Bayesiaanse benaderingen, maar uitgebreide empirische vergelijkingen van hun prestaties over verschillende data-regimes zijn beperkt. Er ontbreekt praktische richtlijnen over welk selectiecriterium onder specifieke omstandigheden de voorkeur verdient om overfitting te voorkomen terwijl interpreteerbaarheid behouden blijft.

Methodologie
De auteurs hebben een systematische empirische vergelijking uitgevoerd van zes wijdverbreide criteria voor modelselectie:

1. Akaike Informatiecriterium (AIC)
2. Gecorrigeerd AIC (AICc)
3. Bayesiaans Informatiecriterium (BIC)
4. Minimum Beschrijvingslengte (MDL)
5. Efron's op bootstrap gebaseerde schatting van de fout binnen de steekproef ($Err_{in}$)
6. Trainings-Middelpuntkwadratenfout ($MSE_{train}$) gebruikt als basislijn.

Experimentele Opstelling:

• Datasets: Zeven synthetische benchmarkfuncties (gangbaar in GP-literatuur) werden gebruikt. Trainingsdata bestond uit 100 punten met toegevoegd Gaussisch ruis ($\epsilon \sim N(0, (0.1\sigma(y))^2)$), terwijl testdata uit 10.000 ruisvrije punten bestond.
• Generatie van Kandidaten: Om de evaluatie te ontkoppelen van specifieke SR-algoritmen, werd een gecontroleerde pool van kandidaatexpressies gegenereerd door de grondwaarheidsfuncties te verstoren. Een mutatieprocedure verving willekeurige knopen in de grondwaarheidsbomen met willekeurige subbomen. Deze kandidaten werden gefit op de trainingsdata met BFGS-optimatie (herhaald 100 keer om lokale optima te vermijden). Het proces genereerde 100 overfitted modellen per benchmark (die met een lagere trainings-MSE dan de grondwaarheid) om het vermogen van de criteria te testen om het ware model te herwinnen uit een set overfitted alternatieven.
• Evaluatiemetrics:
  • Gemiddelde $MSE_{test}$: Prestaties van de top-$k$ gerangschikte modellen.
  • Precisie bij $k$: Het fractie van de top-$k$ geselecteerde modellen die behoren tot de ware top-$k$ op basis van testfout.
  • Gemiddelde Expressiegrootte: Gemiddelde structurele complexiteit (aantal knopen) van geselecteerde modellen.
  • Grondwaarheid Treffer: De minimale rang $k$ waarbij de exacte grondwaarheidsexpressie wordt herwonnen.

Belangrijkste Bijdragen en Resultaten
De studie biedt een gedetailleerde rangschikking van selectiecriteria op basis van de vier bovenstaande metrics:

• MDL (Minimum Beschrijvingslengte): Steeds naar voren gekomen als het meest robuuste criterium. Het identificeerde modellen met de laagste testfout voor kleine $k$ in zes van de zeven benchmarks en produceerde de meest parsimonieuze (kleinste) expressies. MDL en BIC toonden de hoogste efficiëntie in het herwinnen van de grondwaarheidsexpressie, met gemiddelde eerste-treffer-rangen van respectievelijk 5,14 en 6,00.
• BIC: Presteerde vergelijkbaar met MDL wat betreft herwinning van de grondwaarheid en leverde stabiele, intermediaire resultaten over benchmarks, vaak resulterend in beknopte formules.
• AIC en AICc: Over het algemeen lager gerangschikt dan MDL en BIC wat betreft generalisatie. Hoewel AICc lichte verbeteringen toonde ten opzichte van standaard AIC voor specifieke functies ($f_1, f_2$), neigden beide naar het selecteren van complexere modellen dan MDL.
• $Err_{in}$ (Bootstrap Fout binnen de Steekproef): Toonde gemengde resultaten. Hoewel het goede precisie en generalisatie bereikte voor sommige datasets ($f_1, f_2, f_3, f_6, f_7$), presteerde het slecht op andere ($f_4, f_5$), vaak door grotere expressies te selecteren en het grondwaarheidsmodel niet efficiënt te herwinnen (gemiddelde rang 31,71). De auteurs schrijven deze inconsistentie toe aan de afhankelijkheid van schattingen van de ruisvariatie via Random Forests.
• $MSE_{train}$: Presteerde consequent het slechtst, wat bevestigt dat ongeregelde trainingsfout leidt tot ernstige overfitting en slechte generalisatie.

Berekeningscomplexiteit
Het artikel analyseert de computatie-overhead van deze criteria:

• AIC, AICc, BIC: Meest efficiënt ($O(n)$), vereisen slechts één doorgang over de data na parameter-schatting.
• MDL: Iets duurder ($O(n \cdot p)$) door de berekening van de Fisher-informatiematrix, maar blijft efficiënt voor typische SR-expressiegroottes.
• $Err_{in}$: Significante de meest rekenintensieve, vereist $B$ bootstrap-iteraties (doorgaans 200) en herhaalde parameter-herfitting, waardoor het potentieel onpraktisch is voor iteratieve evolutionaire zoekprocessen.

Betekenis en Beweringen
De auteurs beweren dat hun bevindingen praktische richtlijnen bieden voor SR-pijplijnen. Zij concluderen dat MDL een sterke standaardkeuze is voor robuuste vroege selectie en compacte modellen, met BIC als secundaire optie. Zij suggereren dat AIC/AICc mogelijk alleen de voorkeur verdient wanneer iets grotere modellen acceptabel zijn en de straf van MDL als te conservatief wordt beschouwd. Omgekeerd raden zij $Err_{in}$ niet aan vanwege de hoge computatiekosten en inconsistente prestaties in hun experimenten.

De studie wijst expliciet op beperkingen, waaronder het gebruik van één ruisniveau voor datageneratie en het feit dat de criteria werden geëvalueerd op een post-hoc pool van kandidaten in plaats van direct te worden geïntegreerd in de GP-zoeklus. De auteurs stellen dat toekomstig werk variërende ruisintensiteiten en de integratie van deze criteria in het evolutionaire zoekproces moet onderzoeken.