🔭 astrophysics

The Inefficiency of Genetic Programming for Symbolic Regression

Dit artikel analyseert het zoekgedrag van genetische programmering voor symbolische regressie in beperkte settings en concludeert dat deze methode inefficiënt is omdat het slechts een klein deel van de semantisch unieke expressies verkent en herhaaldelijk congruente expressies evalueert, in vergelijking met een gerandomiseerde zoektocht.

Oorspronkelijke auteurs: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Gepubliceerd 2026-03-30

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Probleem: Zoeken in een Labyrint

Stel je voor dat je op zoek bent naar de perfecte recept voor een taart. Je hebt een enorme lijst met ingrediënten (zoals bloem, suiker, eieren) en je mag ze op elke mogelijke manier combineren. Dit noemen we Symbolische Regressie: een computer probeert wiskundige formules te vinden die precies passen bij een verzameling data (zoals hoe snel een auto rijdt of hoe sterren bewegen).

Deze computer gebruikt een slimme zoekmethode genaamd Genetisch Programmeren (GP). Je kunt dit vergelijken met een groepje koks die recepten uitwisselen. Ze nemen twee goede recepten, knippen er stukjes van af, plakken die aan elkaar en hopen dat het nieuwe recept nog lekkerder is. Ze doen dit keer op keer, hoping op de "perfecte taart".

Wat hebben de onderzoekers ontdekt?

De onderzoekers van dit paper hebben gekeken of deze "koks" (de computer) echt slim zijn, of dat ze eigenlijk maar wat rondlopen. Ze hebben twee echte, moeilijke problemen opgelost:

Water in ruwe pijpen: Hoe stroomt water door een pijp met een ruwe binnenkant?
Sterrenbeweging: Hoe bewegen sterren in een melkwegstelsel?

Om te weten of de computer echt slim is, hebben ze eerst elk mogelijk recept (elke mogelijke formule) die binnen een bepaalde lengte past, één voor één uitgeschreven. Dit is als een "perfecte lijst" van alle mogelijke taarten. Vervolgens hebben ze gekeken hoe goed de computer (GP) deze lijst kon vinden.

De Verbluffende Resultaten

De resultaten waren verrassend en een beetje zorgwekkend:

1. De computer loopt in rondjes
De computer (GP) denkt dat hij nieuwe, unieke recepten bedenkt, maar in werkelijkheid bedenkt hij vaak dingen die al eerder zijn bedacht, alleen dan in een iets andere vorm.

De Analogie: Stel je voor dat je een recept schrijft als "2 eieren + 1 bloem". De computer bedenkt later "1 bloem + 2 eieren". Voor de computer zijn dit twee verschillende dingen, maar voor een kok is het exact hetzelfde recept.
Het onderzoek toont aan dat de computer ongeveer 90% van de tijd tijd verspillen aan het opnieuw bedenken van recepten die hij al heeft gezien of die exact hetzelfde zijn als eerdere recepten. Hij loopt in rondjes in plaats van vooruit te komen.

2. Een slechtere zoekmachine dan een willekeurige gok
De onderzoekers vergeleken de slimme computer met iemand die gewoon willekeurig een recept uit de hoed trekt (Random Search).

Het verdict: Als je de zoekruimte beperkt tot korte formules, is de "slimme" computer vaak traagder en minder succesvol dan iemand die gewoon willekeurig gokt. De computer probeert te veel tijd te steken in het verbeteren van recepten die al goed zijn, of hij blijft vastzitten in een hoekje van de lijst met recepten en mist de echte winnaars.

3. De "Gouden Formules" zijn zeldzaam
In de enorme lijst met alle mogelijke formules, zijn er maar heel weinig die echt goed werken (zoals 1 op de 10.000). De meeste formules zijn waardeloos. Omdat de computer zo vaak dezelfde "dumme" formules opnieuw bedenkt, heeft hij veel minder kans om die ene zeldzame, perfecte formule te vinden dan als hij gewoon elke optie één keer zou proberen.

Waarom gebeurt dit?

De computer gebruikt een trucje om te evolueren (zoals in de natuur: overerving en mutatie). Maar deze trucjes hebben een nadeel:

Ze creëren veel redundantie. Ze maken veel variaties van hetzelfde idee.
Ze hebben geen goed geheugen. Ze vergeten dat ze een bepaalde formule al hebben gezien, tenzij ze er heel precies naar kijken (wat ze vaak niet doen).

Wat betekent dit voor de toekomst?

De onderzoekers concluderen dat we misschien te veel vertrouwen op deze "slimme" computers voor het vinden van wiskundige formules. Ze zijn niet zo efficiënt als we denken.

De les: Misschien moeten we de computer dwingen om te kijken of een formule echt nieuw is, voordat hij er tijd in steekt. Of we moeten andere methoden bedenken die minder tijd verspillen aan het opnieuw bedenken van dingen die we al weten.

Kortom: De computer is als een hond die op zoek is naar een bot. Hij snuffelt overal, maar hij snuffelt vaak op plekken waar hij al eerder was, of hij vindt een bot die er precies hetzelfde uitziet als de vorige. Terwijl een willekeurige hond die gewoon rondloopt, soms sneller bij de echte schat is omdat hij niet vastloopt in zijn eigen patronen.

Probleemstelling

Symbolische regressie (SR) is een machine learning-taak waarbij het doel is om een wiskundige expressie te vinden die een dataset zo goed mogelijk beschrijft. Genetisch programmeren (GP) is een populaire evolutionaire algoritme voor dit doel. Het artikel adresseert echter een fundamenteel probleem: de inefficiëntie van GP bij het verkennen van de zoekruimte.

De kern van het probleem ligt in de redundantie in de zoekruimte van GP:

Veel verschillende genotypen (boomstructuren) vertegenwoordigen hetzelfde fenotype (dezelfde wiskundige functie).
GP-systemen evalueren vaak structuren die semantisch identiek zijn aan eerder bezochte structuren, maar die er anders uitzien door parameterwaarden of algebraïsche manipulaties (bijv. $x(x+1)$ versus $x^2+x$ ).
Het is onduidelijk hoe groot het aandeel van deze "verspilde" evaluaties is en of GP in staat is om de beste mogelijke expressies te vinden binnen een beperkt aantal iteraties, vergeleken met een ideale zoekstrategie.

Methodologie

De auteurs hebben een experimenteel kader opgezet om de zoekgedragingen van GP te analyseren door de zoekruimte volledig te enumereren en te vergelijken met een ideale willekeurige zoektocht.

1. Uitgebreide Exhaustive Symbolic Regression (ESR):

De auteurs hebben een verbeterde implementatie van het ESR-algoritme ontwikkeld in Julia.
In plaats van alleen fitness-waarden te gebruiken om duplicaten te detecteren (wat afhankelijk is van geoptimaliseerde parameters), gebruiken ze equality saturation (eq-sat).
Dit maakt gebruik van e-graphs (equality graphs) en een reeks herschrijvingsregels (commutativiteit, associativiteit, distributiviteit, etc.) om alle expressies om te zetten naar een canonieke vorm.
Hierdoor kunnen semantisch identieke expressies, ongeacht hun parameterwaarden of syntactische vorm, worden gedetecteerd en gedupliceerd.
Dit stelt de auteurs in staat om de volledige ruimte van semantisch unieke expressies te genereren voor een beperkte lengte (maximaal 10, 12 en 20 knopen).

2. Vergelijkende Experimenten:

Datasets: Twee real-world datasets uit de natuurkunde werden gebruikt:
- De Nikuradse-dataset (stroming in ruwe pijpen).
- De Radial Acceleration Relation (RAR) (galactische dynamica).
Algoritmen:
- Genetisch Programmeren (GP): Geïmplementeerd via TinyGP en geverifieerd met Operon (een state-of-the-art implementatie).
- Random Search (RS): Een geïdealiseerde zoektocht die willekeurig unieke expressies uit de volledige geënumereerde ruimte selecteert zonder herhaling. Dit dient als een ondergrens voor efficiëntie.
Metingen: De auteurs meten het succespercentage (het vinden van een oplossing met een bepaalde kwaliteit) als functie van het aantal bezochte expressies en het aantal functionele evaluaties.

Belangrijkste Bijdragen

Nieuwe Methode voor Semantische Detectie: Het toepassen van equality saturation op SR om duplicaten te detecteren op basis van canonieke vormen, ongeacht parameteroptimalisatie. Dit is een significant vooruitgang ten opzichte van eerdere methoden die alleen op fitness-waarden leunden.
Exhaustieve Analyse: Voor het eerst is de volledige zoekruimte van semantisch unieke expressies voor praktische datasets volledig geënumereerd, waardoor een exacte vergelijking tussen GP en een ideale zoektocht mogelijk is.
Kwantificering van Inefficiëntie: Het artikel levert harde bewijzen dat GP een groot deel van zijn rekentijd verspillen aan het evalueren van semantisch identieke expressies en dat het vaak faalt om de beste oplossingen te vinden in beperkte zoekruimtes.

Resultaten

De resultaten tonen een zorgwekkende inefficiëntie van GP aan:

Laag succespercentage: GP vond in geen enkele van de 50 onafhankelijke runs de globale optimum voor de beperkte zoekruimtes (lengte 10 en 12). Zelfs met een langere limiet (lengte 20) vond GP geen betere oplossing dan de beste gevonden door ESR voor de kortere lengtes.
Vergelijking met Random Search:
- Een geïdealiseerde Random Search (RS) die alleen unieke expressies bezoekt, is aanzienlijk efficiënter.
- GP moet ongeveer een orde van grootte meer expressies bezoeken om hetzelfde succespercentage te bereiken als RS.
- Voor de RAR-dataset vond GP zelfs maar één oplossing met een log-likelihood onder de -1000 in 50 runs, terwijl RS dit veel sneller deed.
Hoge mate van redundantie:
- GP genereert een groot aantal semantisch identieke expressies.
- Voor lengte 10 en 12 zijn slechts 10% tot 20% van de door GP bezochte expressies uniek na simplificatie.
- Ongeveer 50% van de geëvalueerde expressies kan worden vereenvoudigd tot een constante ( $p_1$ ), wat aangeeft dat GP veel tijd besteedt aan triviale oplossingen.
- Zelfs bij een grotere zoekruimte (lengte 20) blijft het percentage unieke expressies laag (40-60%), en blijft GP achter bij RS in het vinden van de beste oplossingen.
Operon vs. TinyGP: De resultaten waren kwalitatief identiek voor zowel de eenvoudige TinyGP als de geavanceerde Operon-implementatie, wat suggereert dat dit een fundamenteel probleem is van de GP-methode zelf en niet alleen van een specifieke implementatie.

Betekenis en Conclusie

Het artikel concludeert dat Genetisch Programmeren voor Symbolische Regressie in beperkte zoekruimtes fundamenteel inefficiënt is. De algoritme verspillen een groot deel van hun rekencapaciteit aan het herbezoeken van semantisch identieke oplossingen en triviale expressies.

De studie suggereert dat:

De huidige zoekstrategieën van GP (crossover en mutatie) niet goed zijn afgestemd om de "semantische" ruimte efficiënt te verkennen.
Het vermijden van semantische duplicaten (bijvoorbeeld door het gebruik van eq-sat tijdens de evolutie) essentieel zou kunnen zijn om de efficiëntie te verbeteren.
De resultaten vragen de vraag op of de redundantie in de representatie echt nodig is om het globale optimum te bereiken, of dat het eerder een obstakel is.

De auteurs benadrukken dat dit onderzoek beperkt is tot korte expressies en één variabele, maar dat de bevindingen een ernstige waarschuwing zijn voor de toepassing van GP in wetenschappelijke contexten waar nauwkeurigheid en efficiëntie cruciaal zijn.