Multi-Level Symbolic Regression: Function Structure Learning for Multi-Level Data

Kei Sen Fong, Mehul MotaniAISTATS 2024 · OpenReview

Abstract

Symbolic Regression (SR) is an approach which learns a closed-form function relating the predictors to the outcome in a dataset. Datasets are often multi-level (MuL), meaning that certain features can be used to split data into groups for analysis (we refer to these features as levels). The advantage of viewing datasets as MuL is that we can exploit the high similarity of data within a group. SR is well-suited for MuL datasets, in which the learnt function structure serves as ‘shared information’ between the groups while the learnt parameter values capture the unique relationships within each group. In this context, this paper makes three contributions: (i) We design an algorithm, Multi-level Symbolic Regression (MSR), which runs multiple parallel SR processes for each group and merges them to produce a single function structure. (ii) To tackle datasets that are not explicitly MuL, we develop a metric termed MLICC to select the best feature to serve as a level. (iii) We also release MSRBench, a database of MuL datasets (synthetic and real-world) which we developed and collated, that can be used to evaluate MSR. Our results and ablation studies demonstrate that MSR achieves a higher recovery rate and lower error on MSRBench compared to SOTA methods for SR and MuL datasets.

Introduction: The Challenge of Multi-Level Data

Symbolic Regression (SR) is a powerful machine learning technique that searches for a closed-form mathematical expression (e.g., $y = ax^2 + b$) to describe a dataset. Unlike "black-box" neural networks, SR provides formulas that humans can actually understand and verify.

However, traditional SR assumes all data points come from the same distribution—a "single-level" approach. In reality, data is often multi-level (MuL). For example, in a dataset of student test scores, students are grouped by schools. While the relationship between study time and grades might have the same general shape across all schools (the function structure), the specific impact might vary due to school-specific factors (the parameters).

Figure 1: Comparison of MSR fitting vs. traditional SR on multi-level linear data.

Existing SR tools either ignore these groups, leading to poor fits that average out distinct group trends (as seen in the red dashed line above), or treat every group as a completely separate dataset, leading to overfitting and a loss of "shared information." This paper introduces Multi-Level Symbolic Regression (MSR) to bridge this gap by learning a single shared function structure while allowing numerical parameters to vary between groups.

Methodology

The authors propose two major innovations to handle multi-level structures:

  1. The MSR Algorithm: MSR runs multiple SR processes in parallel—one for each group in the data. It uses DistilSR (an exhaustive search algorithm) to find candidate function structures. The merging step identifies a single function structure that performs well across all groups. To ensure the model isn't biased by one particularly noisy group, they use the harmonic mean of the Mean Squared Error (MSE) to score candidates, which forces the algorithm to find a structure that works robustly for everyone.
  2. MLICC (Mean Local Intraclass Correlation Coefficient): Sometimes the grouping feature isn't obvious. Standard statistical tools like the Intraclass Correlation Coefficient (ICC) fail when relationships are non-linear. The authors developed MLICC, which uses "balanced k-means" clustering to break the data into local linear regions before calculating the correlation. This allows the system to automatically identify the best "level" or grouping variable for the model.

Datasets: MSRBench

The researchers introduced MSRBench, a new benchmark specifically for multi-level symbolic regression. It includes:

  • Synthetic Datasets: 1,200 datasets generated from 20 different mathematical structures, featuring varying levels of noise and group sizes.
  • Real-World Datasets: Seven setups covering diverse fields, including public health (melanoma mortality), education (pupil attainment), economics (housing prices), and finance (US Government bond yields).

Key Results and Discussion

MSR demonstrates significant improvements over existing methods in both formula recovery and predictive accuracy.

Table 1: Formula recovery rates of MSR variants compared to state-of-the-art symbolic regression methods.
  • Formula Recovery: As shown in Table 1, on synthetic data, MSR achieved a recovery rate of 73% to 89%. In contrast, state-of-the-art SR methods like Deep Symbolic Optimization (DSO-SR) and gplearn-SR failed to recover the ground-truth formulas (0% recovery) because they couldn't account for group-level parameter shifts.
  • Prediction Accuracy: On real-world data, MSR consistently produced the lowest error (NRMSE). For US bond yields, MSR discovered a formula that outperformed the standard "hand-crafted" model used by economists (the Gürkaynak model), using one fewer parameter.
  • Level Identification: MLICC proved to be a much more reliable "level selector" than the standard ICC, especially as data became noisier, maintaining higher coefficient values across varying levels of permutation noise.

Conclusion

By forcing all groups to share the same mathematical formula, MSR acts as a natural regularizer, preventing the model from "hallucinating" complex patterns in noisy groups. While MSR's performance is currently tied to the numerical optimization of parameters, it represents a significant step forward in making symbolic regression applicable to complex, hierarchical real-world data. Future work will focus on integrating more robust numerical optimization and extending the framework to handle deeper hierarchies.

Summary updated

Abstract

Symbolic Regression (SR) is an approach which learns a closed-form function relating the predictors to the outcome in a dataset. Datasets are often multi-level (MuL), meaning that certain features can be used to split data into groups for analysis (we refer to these features as levels). The advantage of viewing datasets as MuL is that we can exploit the high similarity of data within a group. SR is well-suited for MuL datasets, in which the learnt function structure serves as ‘shared information’ between the groups while the learnt parameter values capture the unique relationships within each group. In this context, this paper makes three contributions: (i) We design an algorithm, Multi-level Symbolic Regression (MSR), which runs multiple parallel SR processes for each group and merges them to produce a single function structure. (ii) To tackle datasets that are not explicitly MuL, we develop a metric termed MLICC to select the best feature to serve as a level. (iii) We also release MSRBench, a database of MuL datasets (synthetic and real-world) which we developed and collated, that can be used to evaluate MSR. Our results and ablation studies demonstrate that MSR achieves a higher recovery rate and lower error on MSRBench compared to SOTA methods for SR and MuL datasets.
BibTeX
@inproceedings{fong2024multi,
  author = {Kei Sen Fong and Mehul Motani},
  title = {{Multi-Level Symbolic Regression: Function Structure Learning for Multi-Level Data}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=7GnB8FlnFD},
}
Figure