A Comparative Study of Model Selection Criteria for Symbolic Regression

Riepilogo Tecnico: Uno Studio Comparativo dei Criteri di Selezione del Modello per la Regressione Simbolica

Enunciato del Problema
La Regressione Simbolica (SR), tipicamente risolta tramite Programmazione Genetica (GP), mira a scoprire espressioni matematiche che bilancino accuratezza e complessità. Sebbene le moderne implementazioni di GP generino un fronte di Pareto di soluzioni candidate, la selezione automatica di un singolo modello che generalizzi bene su dati non visti rimane una sfida aperta. La letteratura esistente offre varie approcci basati sulla teoria dell'informazione e bayesiani, ma sono limitati i confronti empirici completi delle loro prestazioni attraverso diversi regimi di dati. Manca una guida pratica su quale criterio di selezione preferire in condizioni specifiche per evitare l'overfitting mantenendo al contempo l'interpretabilità.

Metodologia
Gli autori hanno condotto un confronto empirico sistematico di sei criteri di selezione del modello ampiamente utilizzati:

1. Criterio di Informazione di Akaike (AIC)
2. AIC Corretto (AICc)
3. Criterio di Informazione Bayesiano (BIC)
4. Lunghezza Minima di Descrizione (MDL)
5. Stima dell'errore intra-campione basata sul bootstrap di Efron ($Err_{in}$)
6. Errore Quadratico Medio di Addestramento ($MSE_{train}$) utilizzato come baseline.

Setup Sperimentale:

• Dataset: Sono state utilizzate sette funzioni sintetiche di riferimento (comuni nella letteratura GP). I dati di addestramento consistevano in 100 punti con rumore gaussiano aggiunto ($\epsilon \sim N(0, (0.1\sigma(y))^2)$), mentre i dati di test comprendevano 10.000 punti privi di rumore.
• Generazione delle Candidate: Per disaccoppiare la valutazione da specifici algoritmi SR, è stato generato un pool controllato di espressioni candidate perturbando le funzioni di verità fondamentale. Una procedura di mutazione ha sostituito nodi casuali negli alberi di verità fondamentale con sotto-alberi casuali. Queste candidate sono state adattate ai dati di addestramento utilizzando l'ottimizzazione BFGS (ripetuta 100 volte per evitare ottimi locali). Il processo ha generato 100 modelli overfitted per ogni benchmark (quelli con MSE di addestramento inferiore alla verità fondamentale) per testare la capacità dei criteri di recuperare il modello vero da un insieme di alternative overfitted.
• Metriche di Valutazione:
  • $MSE_{test}$ Media: Prestazione dei modelli classificati nei primi $k$.
  • Precisione a $k$: La frazione dei modelli selezionati nei primi $k$ che appartengono ai veri primi $k$ basati sull'errore di test.
  • Dimensione Media dell'Espressione: Complessità strutturale media (conteggio dei nodi) dei modelli selezionati.
  • Colpo alla Verità Fondamentale: Il rango minimo $k$ al quale viene recuperata l'espressione esatta di verità fondamentale.

Contributi e Risultati Chiave
Lo studio fornisce una classificazione dettagliata dei criteri di selezione basata sulle quattro metriche sopra indicate:

• MDL (Lunghezza Minima di Descrizione): È emerso costantemente come il criterio più robusto. Ha identificato modelli con il più basso errore di test per piccoli valori di $k$ in sei dei sette benchmark e ha prodotto le espressioni più parsimoniose (più piccole). MDL e BIC hanno dimostrato la massima efficienza nel recuperare l'espressione di verità fondamentale, con ranghi medi di primo colpo di 5,14 e 6,00 rispettivamente.
• BIC: Ha performance simili a MDL in termini di recupero della verità fondamentale e ha fornito risultati intermedi stabili attraverso i benchmark, producendo spesso formule concise.
• AIC e AICc: Generalmente classificati più in basso rispetto a MDL e BIC per quanto riguarda la generalizzazione. Sebbene AICc abbia mostrato lievi miglioramenti rispetto all'AIC standard per funzioni specifiche ($f_1, f_2$), entrambi tendevano a selezionare modelli più complessi rispetto a MDL.
• $Err_{in}$ (Errore Intra-campione Bootstrap): Ha mostrato risultati misti. Sebbene abbia raggiunto buona precisione e generalizzazione per alcuni dataset ($f_1, f_2, f_3, f_6, f_7$), ha performato male su altri ($f_4, f_5$), selezionando spesso espressioni più grandi e fallendo nel recuperare la verità fondamentale in modo efficiente (rango medio 31,71). Gli autori attribuiscono questa incoerenza alla dipendenza dalle stime della varianza del rumore basate su Random Forest.
• $MSE_{train}$: Ha performato costantemente peggio, confermando che l'errore di addestramento non regolarizzato porta a un grave overfitting e a una scarsa generalizzazione.

Complessità Computazionale
Il documento analizza il sovraccarico computazionale di questi criteri:

• AIC, AICc, BIC: I più efficienti ($O(n)$), richiedendo un singolo passaggio sui dati dopo la stima dei parametri.
• MDL: Leggermente più costoso ($O(n \cdot p)$) a causa del calcolo della matrice di informazione di Fisher, ma rimane efficiente per le dimensioni tipiche delle espressioni SR.
• $Err_{in}$: Significativamente il più intensivo dal punto di vista computazionale, richiede $B$ iterazioni di bootstrap (tipicamente 200) e ripetuti riadattamenti dei parametri, rendendolo potenzialmente impraticabile per processi di ricerca evolutiva iterativi.

Significato e Affermazioni
Gli autori affermano che i loro risultati offrono una guida pratica per le pipeline SR. Concludono che MDL è una scelta predefinita solida per una selezione precoce robusta e per modelli compatti, con BIC come opzione secondaria. Suggeriscono che AIC/AICc possano essere preferibili solo quando sono accettabili modelli leggermente più grandi e la penalità di MDL è considerata eccessivamente conservativa. Al contrario, non raccomandano $Err_{in}$ a causa del suo alto costo computazionale e delle prestazioni incoerenti nei loro esperimenti.

Lo studio nota esplicitamente le limitazioni, inclusa l'uso di un singolo livello di rumore per la generazione dei dati e il fatto che i criteri siano stati valutati su un pool di candidati post-hoc piuttosto che integrati direttamente nel ciclo di ricerca GP. Gli autori affermano che il lavoro futuro dovrebbe investigare intensità di rumore variabili e l'integrazione di questi criteri nel processo di ricerca evolutiva.