A Comparative Study of Model Selection Criteria for Symbolic Regression

Technische Zusammenfassung: Eine vergleichende Studie zu Modellselektionskriterien für die Symbolische Regression

Problemstellung
Die Symbolische Regression (SR), die typischerweise mittels Genetischer Programmierung (GP) gelöst wird, zielt darauf ab, mathematische Ausdrücke zu entdecken, die Genauigkeit und Komplexität in Einklang bringen. Während moderne GP-Implementierungen eine Pareto-Front von Kandidatenlösungen generieren, bleibt die automatische Auswahl eines einzelnen Modells, das sich gut auf ungesehene Daten verallgemeinert, eine offene Herausforderung. Die bestehende Literatur bietet verschiedene informationstheoretische und bayessche Ansätze, doch umfassende empirische Vergleiche ihrer Leistung über unterschiedliche Datenregime hinweg sind begrenzt. Es fehlt an praktischer Anleitung, welches Selektionskriterium unter spezifischen Bedingungen zu bevorzugen ist, um Overfitting zu vermeiden und gleichzeitig die Interpretierbarkeit zu wahren.

Methodik
Die Autoren führten einen systematischen empirischen Vergleich von sechs weit verbreiteten Modellselektionskriterien durch:

1. Akaike-Informationskriterium (AIC)
2. Korrigiertes AIC (AICc)
3. Bayessches Informationskriterium (BIC)
4. Minimum Description Length (MDL)
5. Efrons bootstrapp-basierter In-Sample-Fehlerschätzer ($Err_{in}$)
6. Trainings-Mittlerer Quadratischer Fehler ($MSE_{train}$), verwendet als Baseline.

Experimentelles Setup:

• Datensätze: Sieben synthetische Benchmark-Funktionen (in der GP-Literatur üblich) wurden verwendet. Die Trainingsdaten bestanden aus 100 Punkten mit hinzugefügtem Gaußschen Rauschen ($\epsilon \sim N(0, (0,1\sigma(y))^2)$), während die Testdaten aus 10.000 rauschfreien Punkten bestanden.
• Generierung von Kandidaten: Um die Evaluation von spezifischen SR-Algorithmen zu entkoppeln, wurde ein kontrollierter Pool von Kandidatenausdrücken durch Perturbierung der Ground-Truth-Funktionen generiert. Ein Mutationsverfahren ersetzte zufällige Knoten in den Ground-Truth-Bäumen durch zufällige Teilbäume. Diese Kandidaten wurden unter Verwendung der BFGS-Optimierung (wiederholt 100 Mal, um lokale Optima zu vermeiden) an die Trainingsdaten angepasst. Der Prozess generierte 100 überfittete Modelle pro Benchmark (jene mit niedrigerem Trainings-MSE als die Ground Truth), um die Fähigkeit der Kriterien zu testen, das wahre Modell aus einer Menge überfitteter Alternativen wiederherzustellen.
• Evaluationsmetriken:
  • Durchschnittlicher $MSE_{test}$: Leistung der top-$k$ gerankten Modelle.
  • Präzision bei $k$: Der Anteil der top-$k$ ausgewählten Modelle, die basierend auf dem Testfehler zu den wahren top-$k$ gehören.
  • Durchschnittliche Ausdrucksgröße: Mittlere strukturelle Komplexität (Knotenzahl) der ausgewählten Modelle.
  • Ground-Truth-Treffer: Der minimale Rang $k$, bei dem der exakte Ground-Truth-Ausdruck wiederhergestellt wird.

Hauptbeiträge und Ergebnisse
Die Studie liefert eine detaillierte Rangliste der Selektionskriterien basierend auf den oben genannten vier Metriken:

• MDL (Minimum Description Length): Erwies sich konsistent als das robusteste Kriterium. Es identifizierte Modelle mit dem niedrigsten Testfehler für kleines $k$ in sechs von sieben Benchmarks und erzeugte die sparsamsten (kleinsten) Ausdrücke. MDL und BIC zeigten die höchste Effizienz bei der Wiederherstellung des Ground-Truth-Ausdrucks, mit mittleren First-Hit-Rängen von 5,14 bzw. 6,00.
• BIC: Leistete in Bezug auf die Ground-Truth-Wiederherstellung ähnlich wie MDL und lieferte stabile, mittlere Ergebnisse über die Benchmarks hinweg, wobei oft prägnante Formeln resultierten.
• AIC und AICc: Rangierten im Allgemeinen unter MDL und BIC hinsichtlich der Verallgemeinerung. Während AICc für bestimmte Funktionen ($f_1, f_2$) leichte Verbesserungen gegenüber dem Standard-AIC zeigte, tendierten beide dazu, komplexere Modelle als MDL auszuwählen.
• $Err_{in}$ (Bootstrap In-Sample Error): Zeigte gemischte Ergebnisse. Während es für einige Datensätze ($f_1, f_2, f_3, f_6, f_7$) gute Präzision und Verallgemeinerung erreichte, performte es bei anderen schlecht ($f_4, f_5$), wählte oft größere Ausdrücke aus und scheiterte daran, die Ground Truth effizient wiederherzustellen (mittlerer Rang 31,71). Die Autoren führen diese Inkonsistenz auf die Abhängigkeit von Random-Forest-Rauschvarianzschätzungen zurück.
• $MSE_{train}$: Performte konsistent am schlechtesten und bestätigte, dass unregulierter Trainingsfehler zu schwerem Overfitting und schlechter Verallgemeinerung führt.

Rechenkomplexität
Die Arbeit analysiert den Rechenaufwand dieser Kriterien:

• AIC, AICc, BIC: Am effizientesten ($O(n)$), erfordern nur einen einzigen Durchlauf über die Daten nach der Parameterschätzung.
• MDL: Etwas teurer ($O(n \cdot p)$) aufgrund der Berechnung der Fisher-Information-Matrix, bleibt aber für typische SR-Ausdrucksgrößen effizient.
• $Err_{in}$: Deutlich am rechenintensivsten, erfordert $B$ Bootstrap-Iterationen (typischerweise 200) und wiederholtes Anpassen der Parameter, was es für iterative evolutionäre Suchprozesse potenziell unpraktisch macht.

Bedeutung und Behauptungen
Die Autoren behaupten, dass ihre Erkenntnisse praktische Anleitung für SR-Pipelines bieten. Sie kommen zu dem Schluss, dass MDL eine starke Standardwahl für eine robuste frühe Selektion und kompakte Modelle ist, mit BIC als sekundärer Option. Sie schlagen vor, dass AIC/AICc möglicherweise nur dann vorzuziehen sind, wenn etwas größere Modelle akzeptabel sind und die Strafe von MDL als übermäßig konservativ erachtet wird. Umgekehrt empfehlen sie $Err_{in}$ aufgrund seiner hohen Rechenkosten und inkonsistenten Leistung in ihren Experimenten nicht.

Die Studie weist explizit auf Einschränkungen hin, darunter die Verwendung eines einzigen Rauschniveaus für die Datengenerierung und die Tatsache, dass die Kriterien an einem nachgelagerten Pool von Kandidaten evaluiert wurden, anstatt direkt in die GP-Suchschleife integriert zu sein. Die Autoren stellen fest, dass zukünftige Arbeiten variierende Rauschintensitäten untersuchen und die Integration dieser Kriterien in den evolutionären Suchprozess erforschen sollten.