Source-linked AI summary
Epsilon-Lexicase Selection for Regression
William La Cava, Lee Spector, Kourosh Danai
TL;DR
Continuous regression exposes a limitation of lexicase selection because exact test-case elitism is too stringent. The paper introduces epsilon-lexicase selection with absolute and automatically adapted thresholds, finding that adaptive variants perform best across the studied regression problems with comparable wall-clock times.
Problem
Lexicase selection performs well in discrete error spaces but struggles with continuous regression because exact case-wise elitism is rare and pass criteria are too stringent.
Method
Epsilon-lexicase selection redefines each test case’s pass condition with an epsilon threshold, including thresholds adapted from population error dispersion.
Results
Automatic-threshold epsilon-lexicase variants perform best on the studied regression problems, with test fitness promising and wall-clock times comparable to tournament selection.
Takeaways & Limitations
The results support epsilon-lexicase selection as a parent-selection technique for symbolic regression and motivate further study of non-elitist lexicase methods for continuous-valued GP problems.
Takeaways & Limitations
Lexicase selection has worst-case time complexity O(|P|^2N), although the paper reports that practical overhead is typically small and measures wall-clock times empirically.
Abstract
from arXiv · showhide
Lexicase selection is a parent selection method that considers test cases separately, rather than in aggregate, when performing parent selection. It performs well in discrete error spaces but not on the continuous-valued problems that compose most system identification tasks. In this paper, we develop a new form of lexicase selection for symbolic regression, named epsilon-lexicase selection, that redefines the pass condition for individuals on each test case in a more effective way. We run a series of experiments on real-world and synthetic problems with several treatments of epsilon and quantify how epsilon affects parent selection and model performance. epsilon-lexicase selection is shown to be effective for regression, producing better fit models compared to other techniques such as tournament selection and age-fitness Pareto optimization. We demonstrate that epsilon can be adapted automatically for individual test cases based on the population performance distribution. Our experiments show that epsilon-lexicase selection with automatic epsilon produces the most accurate models across tested problems with negligible computational overhead. We show that behavioral diversity is exceptionally high in lexicase selection treatments, and that epsilon-lexicase selection makes use of more fitness cases when selecting parents than lexicase selection, which helps explain the performance improvement.
1. INTRODUCTION
Aggregate fitness compresses the information in individual test-case errors, while standard lexicase selection struggles with continuous regression errors. The paper introduces epsilon-lexicase selection by relaxing the test-case pass condition.
- Clarification: A corrected version clarifies that epsilon-lexicase pass conditions are relative to the best population error on each training case, not the selection pool.This correction affects the interpretation of the algorithm’s defining equations.
- Problem setup: The paper uses the training set T as a collection of input-target test cases and typically evaluates programs with mean absolute error.For program i, the aggregate fitness is computed over the training cases rather than preserving the full case-wise error profile.
- Motivation: Aggregate fitness reduces information about program behavior by collapsing the absolute error vector into one value.This can underuse information that might guide the search and assumes test cases are equally informative.
- Motivation: Lexicase selection rewards uniquely strong test-case performance but fails to provide the same benefits on continuous symbolic regression problems.Its test-case elitism is effective in discrete settings but problematic when exact case-wise elitism is rare.
- Contribution: Epsilon-lexicase selection redefines the test-case pass condition with an epsilon threshold to extend lexicase selection to continuous domains.The paper proposes several epsilon definitions and evaluates them on real-world and symbolic regression problems.
2. ϵ LEXICASE SELECTION
Epsilon-lexicase selection replaces exact case-wise elitism with thresholded passing rules suited to continuous errors. Its thresholds can be absolute or population-adaptive, while the procedure retains lexicase’s sequential filtering structure.
- Standard lexicase procedure: Standard lexicase selection shuffles fitness cases and repeatedly filters the population pool by the best remaining case performance.The first case acts as the initial filter, and later cases are used only when multiple individuals remain.
- Motivation: Continuous regression errors make exact elitism rare, so standard lexicase can select parents using overly stringent case-passing criteria.Real-world regression also includes noise and measurement error, unlike uncompromising problems requiring exact solutions.
- Epsilon-lexicase: Epsilon-lexicase filters individuals only when their case errors fall outside a predefined epsilon threshold.The method experiments with four epsilon definitions, including absolute and adaptive forms.
- Absolute thresholds: The absolute epsilon_e rule compares an individual’s case error with the best error on that case, ensuring that at least one population member passes.The epsilon_y rule instead requires the program output to lie within ±epsilon_y of the target and may provide no selection pressure when no adequate prediction exists.
- Adaptive thresholds: Absolute epsilon values must be user-specified and problem-dependent, whereas adaptive thresholds use the population’s case-error distribution to modulate selectivity.The paper defines epsilon_eλ and epsilon_yλ analogously to the absolute forms using a population-based dispersion measure.
- Computational considerations: Lexicase selection has worst-case complexity O(|P|^2N), versus O(|P|N) for tournament selection, although typical use examines only a small number of cases.The paper measures wall-clock time to assess the practical overhead of its variants.
3. RELATED WORK
The paper situates epsilon-lexicase selection among behavior-based and population-performance-weighted GP methods, while distinguishing test cases from optimization objectives. It presents epsilon-threshold discretization as a new way to apply lexicase selection effectively to regression.
- Multiobjective methods: Multiobjective methods treat objectives as task goals, whereas test cases estimate progress and may number in the hundreds or thousands.Symbolic regression commonly uses one or two objectives alongside many test cases.
- Population-performance weighting: Population-performance-weighted methods include implicit fitness sharing, historically assessed hardness, and discovery of objectives by clustering.These methods scale, weight, or cluster test-case errors according to population performance.
- Epsilon-threshold discretization: Epsilon-threshold discretization had appeared in Novelty Search GP, but this paper proposes it for the first time to apply lexicase selection effectively to regression.The threshold converts real-valued fitness into discrete values used in a reduced error vector.
- Behavior-based search: Lexicase shares behavior-based search motivation with Semantic GP and Behavioral GP, despite differing substantially in approach.The paper also notes that structural diversity may affect GP performance.
4. EXPERIMENTAL ANALYSIS
The experiments compare epsilon-lexicase variants with standard selection methods across synthetic and real-world regression problems, then examine parameter effects, accuracy, runtime, case usage, and behavioral diversity. Automatically adapted epsilon variants achieve the strongest overall test performance, while maintaining near-tournament runtime and substantially higher diversity.
- Compared Methods: The benchmark includes three synthetic and three real-world symbolic regression problems, with methods compared against standard lexicase, tournament, random, and age-fitness Pareto selection.Most datasets use 70/30 training/testing splits; UBall5D has a predefined test set.
- Parameter Tuning: For error-based epsilon, εe = 5.0 gives the lowest median test fitness on the Tower problem and increases test-case usage and behavioral diversity as tolerance grows.Subsequent experiments use εe = 5.0 based on the Tower parameter study.
- Parameter Tuning: For output-based epsilon, εy = 0.10 gives the lowest median test fitness, whereas εy ≥ 1.0 uses nearly all cases and suggests loss of selection pressure.The authors associate higher εy values with long runtimes and performance similar to random selection on this problem.
- Results: Across all problems, Lex εeλ or Lex εyλ obtains the median best test fitness, significantly outperforming random, tournament, standard lexicase, and Lex εe on 6/6 problems.These variants also rank highest on mean performance across tests; comparisons with AFP and Lex εe show partial interval overlap.
- Results: Epsilon-lexicase runtime averages 105% of tournament selection, despite higher worst-case complexity, while standard lexicase takes 41% of tournament time because it usually uses one case.The epsilon variants report 82%–120% of tournament runtime across treatments.
- Results: Lexicase methods produce exceptionally high behavioral diversity, and epsilon-lexicase gains over random selection reflect promotion of individuals with strong performance across diverse case orderings.Epsilon variants also use more cases than standard lexicase, whose single-case selections help explain its poorer performance in continuous error spaces.
5. DISCUSSION
The discussion characterizes epsilon-lexicase selection as a non-elitist lexicase variant that performs well on symbolic regression while retaining high behavioral diversity and practical runtime. It also identifies untested choices in pool size and test-case ordering as directions for further investigation.
- Method and open design choices: ϵ-lexicase selection is a global-pool, uniformly shuffled, non-elitist version of lexicase selection that performs well on symbolic regression problems.The authors note that alternative pool sizes and test-case orderings have not yet been reported in the literature.
- Performance and runtime: Table 2 compares median best-of-run test-set MAE, statistical significance across methods, and median total time for 30 trials.Significance uses pairwise Wilcoxon rank-sum tests with Holm correction at p < 0.05.
- Performance and runtime: Figure 6 reports best-of-run test-set fitness statistics for all problems, while Figure 7 reports training-set fitness by generation with standard-error bars.These plots provide complementary views of final test performance and learning over generations.
- Selection behavior: Figure 8 measures the number of fitness cases used during selection, and Figure 9 measures mean population diversity across generations with standard-error bars.Together, they track selection-case usage and behavioral diversity over time.
- Method and open design choices: Alternative case orderings or reductions might improve lexicase selection, but clustering-derived cases previously decreased performance.The paper presents these possibilities as future research rather than established improvements.
- Behavioral diversity: Lexicase treatments create large numbers of distinct behavioral clusters in the population.The discussion links this observation to Figure 9’s population-diversity results.
6. CONCLUSIONS
The paper concludes that epsilon-lexicase selection, particularly with automatically adapted thresholds, performs best among the studied GP methods on the tested regression problems. It also reports comparable runtime and motivates further research on non-elitist lexicase methods for continuous-valued GP problems.
- Conclusions: ϵ-lexicase selection, especially with automatic threshold adaptation, performs best on the studied regression problems compared with the other GP methods.The automatic thresholds are denoted ϵeλ and ϵyλ.
- Conclusions: ϵ-lexicase selection achieves promising test fitness with wall-clock times comparable to tournament selection.The reported average runtime is 105% of tournament selection across the listed ϵ treatments.
- Conclusions: The paper demonstrates that epsilon can be set automatically from the population’s error dispersion on each test case.The threshold definition was observed to be insensitive to the elite error offset e∗.
- Conclusions: The results motivate using ϵ-lexicase selection for symbolic regression and pursuing non-elitist lexicase methods for continuous-valued GP problems.This conclusion is stated within the scope of the regression problems studied.