🤖 machine learning

Enhancing Generalization in Evolutionary Feature Construction for Symbolic Regression through Vicinal Jensen Gap Minimization

This paper proposes an evolutionary feature construction framework for symbolic regression that enhances generalization by dynamically minimizing the vicinal Jensen gap as a regularization term, incorporating noise estimation and manifold intrusion detection to effectively control overfitting across diverse datasets.

Original authors: Hengzhe Zhang, Qi Chen, Bing Xue, Wolfgang Banzhaf, Mengjie Zhang

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengzhe Zhang, Qi Chen, Bing Xue, Wolfgang Banzhaf, Mengjie Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot to Learn Without Cheating

Imagine you are trying to teach a robot (an algorithm called Genetic Programming) how to predict the weather or stock prices based on a set of clues (data). The robot is very smart and creative; it can invent its own complex formulas to solve the problem.

However, the robot has a bad habit: Overfitting.

Think of overfitting like a student who memorizes the answers to a specific practice test perfectly but fails the real exam because they didn't understand the concepts, they just memorized the noise and quirks of the practice questions. In the world of data, this means the robot learns the "noise" (random errors) in the training data instead of the true pattern.

This paper introduces a new way to teach the robot to be a "good learner" rather than a "memorizer." They call this method Vicinal Jensen Gap Minimization.

The Problem: Why "Memorizing" is Bad

In the past, scientists tried to stop robots from memorizing by forcing them to keep their formulas short and simple (like limiting the number of words in an essay). But the authors found that a short essay can still be nonsense, and a long essay can be brilliant. Size isn't the only thing that matters; smoothness and logic matter more.

The Solution: The "Neighbor Test"

The authors realized that a good model shouldn't just be right on the exact data points it saw; it should also be right on the "neighbors" of those points.

Imagine you are walking through a forest. If you see a tree at a specific spot, you expect the trees nearby to look somewhat similar. If you take a tiny step and the tree suddenly turns into a banana, that's weird. A good model should be "smooth"—small changes in input should lead to small, logical changes in output.

To test this, the researchers use two main tricks to create "fake" neighbor data:

The "Shaky Hand" Trick (Noise Perturbation): They take a data point and add a tiny bit of random "jitter" to it, like shaking a camera slightly. If the robot's answer changes wildly with this tiny shake, it's too sensitive (overfitting).
The "Smoothie" Trick (Mixup): They take two data points (like a red apple and a green apple) and blend them together to create a "new" data point (a slightly orange apple). They check if the robot's prediction for this "orange apple" makes sense based on the red and green ones.

The Secret Sauce: Breaking the Problem in Two

The paper's biggest breakthrough is a mathematical proof that shows they can split the robot's learning goal into two separate parts:

The "Accuracy" Score: How well does the robot predict the real data? (We want this high).
The "Smoothness" Score (The Jensen Gap): How weird does the robot get when we test it on our "fake" neighbor data? (We want this low).

The Analogy:
Imagine you are grading a student.

Old Way: You just look at their final exam score. If they got a 100%, they pass. (But they might have cheated or memorized).
New Way (This Paper): You give them two grades.
1. Grade A: How well did they do on the real questions?
2. Grade B: How well did they do on a "trick" version of the questions where we slightly changed the numbers?
- If they get a perfect Grade A but a terrible Grade B, you know they are cheating (overfitting).
- The paper creates a formula that balances these two grades perfectly.

Adapting to the Environment (Noise Estimation)

The authors noticed that some datasets are "noisy" (full of errors) and some are "clean."

Analogy: Imagine trying to hear a conversation.
- In a quiet library (low noise), you can listen very closely to every word.
- In a rock concert (high noise), you need to ignore the background noise and focus on the main melody.

The paper creates a "Noise Detector." If the data is messy (like the rock concert), the robot automatically becomes stricter about the "Smoothness" score to ignore the noise. If the data is clean, it focuses more on getting the details right. This happens automatically without human intervention.

The "Manifold Intrusion" Guard

Sometimes, when you blend two data points (the "Smoothie" trick), you might accidentally create a fake data point that doesn't make sense in the real world.

Analogy: If you mix a "hot coffee" and a "cold ice cube," you get lukewarm water. But if you mix a "fire" and a "snowflake," you might get a "burning snowflake," which doesn't exist in reality.

The paper adds a Manifold Intrusion Detector. This is like a security guard who checks the "fake" data points. If the guard sees a "burning snowflake" (a fake point that breaks the laws of physics/logic), they throw it out so the robot doesn't get confused by it.

What Happened in the Experiments?

The team tested this new method on 58 different real-world datasets (like predicting house prices, chemical concentrations, etc.).

The Result: The new method (VJM-GP) was much better at predicting new, unseen data than the old methods.
The Comparison: It beat 15 other popular machine learning algorithms, including standard Genetic Programming, deep learning models, and decision trees.
The Trade-off: The new method takes a little more time to train (like studying harder for a test), but the results are much more reliable and the final formulas are often simpler and easier for humans to understand.

Summary

This paper teaches robots to stop memorizing and start understanding. By splitting the learning process into "Accuracy" and "Smoothness," and by automatically adjusting how strict the robot is based on how messy the data is, the authors created a system that builds better, more reliable models that don't fall apart when faced with new situations.

Technical Summary: Enhancing Generalization in Evolutionary Feature Construction through Vicinal Jensen Gap Minimization

Problem Statement

Genetic Programming (GP)-based feature construction has emerged as a powerful automated machine learning technique for symbolic regression. However, a persistent challenge limiting its broader applicability is overfitting. While GP methods often achieve high performance on training data, the constructed features frequently fail to generalize to unseen data. Traditional approaches to controlling overfitting, such as regulating model size (parsimony pressure), have been shown to be insufficient for characterizing the complexity of modern evolutionary models. Furthermore, existing theoretical metrics like VC-dimension or Rademacher complexity often fail to accurately predict generalization performance in deep-learning-inspired contexts. Additionally, applying Vicinal Risk Minimization (VRM)—a technique successful in deep learning for mitigating overfitting via data augmentation—directly to GP regression is problematic because standard VRM assumes target labels remain stable under small perturbations, an assumption that often fails in regression tasks where target values are continuous.

Methodology

The paper proposes a framework to enhance generalization by decomposing Vicinal Risk into an empirical loss component and a regularization term. This decomposition allows for the independent optimization of training accuracy and model smoothness.

1. Theoretical Decomposition of Vicinal Risk

The authors prove that vicinal risk is bounded by the sum of empirical risk and a regularization term, depending on the data augmentation strategy:

Noise Perturbation: If vicinal examples are synthesized via noise perturbation (e.g., Gaussian noise), the regularization term is a Finite Difference. This penalizes rapid changes in the function's output in response to small input variations.
Mixup Augmentation: If vicinal examples are synthesized using the Mixup method (linear interpolation of inputs and labels), the regularization term is the Vicinal Jensen Gap. This term, defined as $(\lambda f(x_i) + (1-\lambda)f(x_j) - f(\lambda x_i + (1-\lambda)x_j))^2$ , penalizes convexity and concavity, promoting local linearity between nearby data points.

The authors argue that decomposing the risk is superior to optimizing the raw vicinal risk because it allows for:

Flexible Trade-offs: Fine-grained control over the balance between empirical loss and smoothness.
Accurate Error Estimation: Ensuring the empirical loss is calculated precisely on original data rather than being conflated with noisy augmented samples.
Validation Loss Integration: Enabling the use of cross-validation loss (rather than just empirical loss) as the primary accuracy metric.

2. The Proposed Algorithm (VJM-GP)

The authors introduce Vicinal Jensen Gap Minimization-based GP (VJM-GP), an evolutionary feature construction framework that jointly optimizes:

Empirical Loss: Measured via Leave-One-Out Cross-Validation (LOOCV) to ensure robustness.
Regularization Term: The Vicinal Jensen Gap (or Finite Difference).

Key components of the algorithm include:

Multi-Objective Optimization: Uses non-dominated sorting with crowding distance to evolve a Pareto front of solutions, balancing cross-validation loss and the regularization term.
Noise Estimation Strategy: Since datasets vary in noise levels, the authors propose a dynamic strategy to adjust the regularization weight ( $\tau$ ). They use the $R^2$ score of Extremely Randomized Trees (Extra Trees) on the dataset to estimate noise; higher noise levels trigger a stronger regularization weight to prevent fitting noise.
Manifold Intrusion Detection: To address the issue where Mixup-generated samples fall outside the true data manifold (creating unrealistic samples), the authors propose a detection mechanism. If a synthesized sample's label (predicted by an Extra Trees model trained on original data) deviates significantly from the linear interpolation of its parents, the sample is discarded. This prevents the Jensen gap minimization from overly penalizing effective models in highly non-linear regions.

Key Contributions

Theoretical Decomposition: The paper derives upper bounds showing that perturbation-based VRM decomposes into empirical risk and finite difference, while mixup-based VRM decomposes into empirical risk and the vicinal Jensen gap.
Regularized GP Framework: A novel GP framework (VJM-GP) is proposed that optimizes cross-validation loss and the vicinal Jensen gap simultaneously, offering a more effective control over overfitting than traditional complexity measures.
Adaptive Regularization: A noise estimation strategy is introduced to dynamically adjust regularization strength based on dataset characteristics, avoiding excessive penalization in low-noise scenarios.
Manifold Intrusion Mitigation: A detection strategy is proposed to filter out unrealistic augmented samples, ensuring the regularization term reflects the true data manifold geometry.

Experimental Results

The proposed method was evaluated on 58 real-world regression datasets from the Penn Machine Learning Benchmark (PMLB).

Comparison of Regularizers: The Vicinal Jensen Gap was found to be a more effective regularizer than Finite Difference, outperforming it on 15 datasets while underperforming on only 5.
Comparison with Complexity Measures: VJM-GP significantly outperformed standard GP and seven other complexity control methods (including Parsimony Pressure, Tikhonov Regularization, Rademacher Complexity, and P-VRM) in terms of test $R^2$ scores. It achieved superior generalization on 36 datasets compared to standard GP.
Comparison with Baselines: VJM-GP was compared against 15 state-of-the-art symbolic regression and machine learning algorithms (including XGBoost and ExcelFormer). It achieved competitive or superior performance, particularly in scenarios with limited sample sizes, while maintaining significantly smaller model sizes than gradient boosting methods.
Ablation Studies:
- Manifold Intrusion Detection: Removing this strategy resulted in lower test performance on 6 datasets, confirming its necessity.
- Noise Estimation: The adaptive weighting strategy significantly improved performance on 12 datasets compared to a fixed weight, validating the need for dynamic regularization.
Label Noise: In experiments with noisy labels, VJM-GP demonstrated superior robustness compared to standard GP and P-VRM.

Significance and Claims

The paper claims that the proposed decomposition of vicinal risk provides a deeper theoretical understanding of overfitting in evolutionary feature construction. By separating empirical loss from the regularization term, the method allows for a more nuanced control of model complexity that focuses on functional complexity (smoothness and linearity) rather than just syntactic complexity (tree size).

The authors assert that their approach enables GP to achieve top-tier performance in symbolic regression tasks, particularly when data is scarce or noisy. They emphasize that effective overfitting control requires balancing accuracy and smoothness, and that blindly minimizing model size is insufficient. The work suggests that the proposed framework can be integrated into other evolutionary algorithms and potentially adapted for deep learning-based symbolic regression methods in the future.