A Comparative Study of Model Selection Criteria for Symbolic Regression

Technical Summary: A Comparative Study of Model Selection Criteria for Symbolic Regression

Problem Statement
Symbolic Regression (SR), typically solved via Genetic Programming (GP), aims to discover mathematical expressions that balance accuracy and complexity. While modern GP implementations generate a Pareto front of candidate solutions, the automatic selection of a single model that generalizes well to unseen data remains an open challenge. Existing literature offers various information-theoretic and Bayesian approaches, but comprehensive empirical comparisons of their performance across different data regimes are limited. There is a lack of practical guidance on which selection criterion to prefer under specific conditions to avoid overfitting while maintaining interpretability.

Methodology
The authors conducted a systematic empirical comparison of six widely used model selection criteria:

1. Akaike Information Criterion (AIC)
2. Corrected AIC (AICc)
3. Bayesian Information Criterion (BIC)
4. Minimum Description Length (MDL)
5. Efron's bootstrap-based in-sample error estimate ($Err_{in}$)
6. Training Mean Squared Error ($MSE_{train}$) used as a baseline.

Experimental Setup:

• Datasets: Seven synthetic benchmark functions (common in GP literature) were used. Training data consisted of 100 points with added Gaussian noise ($\epsilon \sim N(0, (0.1\sigma(y))^2)$), while test data comprised 10,000 noise-free points.
• Candidate Generation: To decouple the evaluation from specific SR algorithms, a controlled pool of candidate expressions was generated by perturbing the ground-truth functions. A mutation procedure replaced random nodes in the ground-truth trees with random subtrees. These candidates were fitted to training data using BFGS optimization (repeated 100 times to avoid local optima). The process generated 100 overfitted models per benchmark (those with lower training MSE than the ground truth) to test the criteria's ability to retrieve the true model from a set of overfitted alternatives.
• Evaluation Metrics:
  • Average $MSE_{test}$: Performance of the top-$k$ ranked models.
  • Precision at $k$: The fraction of top-$k$ selected models that belong to the true top-$k$ based on test error.
  • Average Expression Size: Mean structural complexity (node count) of selected models.
  • Ground-Truth Hit: The minimum rank $k$ at which the exact ground-truth expression is recovered.

Key Contributions and Results
The study provides a detailed ranking of selection criteria based on the four metrics above:

• MDL (Minimum Description Length): Consistently emerged as the most robust criterion. It identified models with the lowest test error for small $k$ in six of seven benchmarks and produced the most parsimonious (smallest) expressions. MDL and BIC demonstrated the highest efficiency in recovering the ground-truth expression, with mean first-hit ranks of 5.14 and 6.00, respectively.
• BIC: Performed similarly to MDL in terms of ground-truth recovery and provided stable, intermediate results across benchmarks, often yielding concise formulas.
• AIC and AICc: Generally ranked lower than MDL and BIC regarding generalization. While AICc showed slight improvements over standard AIC for specific functions ($f_1, f_2$), both tended to select more complex models than MDL.
• $Err_{in}$ (Bootstrap In-Sample Error): Showed mixed results. While it achieved good precision and generalization for some datasets ($f_1, f_2, f_3, f_6, f_7$), it performed poorly on others ($f_4, f_5$), often selecting larger expressions and failing to recover the ground truth efficiently (mean rank 31.71). The authors attribute this inconsistency to the dependence on Random Forest noise variance estimates.
• $MSE_{train}$: Consistently performed the worst, confirming that unregularized training error leads to severe overfitting and poor generalization.

Computational Complexity
The paper analyzes the computational overhead of these criteria:

• AIC, AICc, BIC: Most efficient ($O(n)$), requiring only a single pass over data after parameter estimation.
• MDL: Slightly more expensive ($O(n \cdot p)$) due to the calculation of the Fisher-information matrix, but remains efficient for typical SR expression sizes.
• $Err_{in}$: Significantly the most computationally intensive, requiring $B$ bootstrap iterations (typically 200) and repeated parameter refitting, making it potentially impractical for iterative evolutionary search processes.

Significance and Claims
The authors claim that their findings offer practical guidance for SR pipelines. They conclude that MDL is a strong default choice for robust early selection and compact models, with BIC as a secondary option. They suggest that AIC/AICc may be preferable only when slightly larger models are acceptable and MDL's penalty is deemed overly conservative. Conversely, they do not recommend $Err_{in}$ due to its high computational cost and inconsistent performance in their experiments.

The study explicitly notes limitations, including the use of a single noise level for data generation and the fact that the criteria were evaluated on a post-hoc pool of candidates rather than integrated directly into the GP search loop. The authors state that future work should investigate varying noise intensities and the integration of these criteria into the evolutionary search process.