Ryan Boldi | publications

2024

ALIFE
Untangling the Effects of Down-Sampling and Selection in Genetic Programming

Ryan Boldi, Ashley Bao, Martin Briesch, Thomas Helmuth, and 3 more authors

In ALIFE 2024: Proceedings of the 2024 Artificial Life Conference Jul 2024

Abs Bib PDF

Genetic programming systems often use large training sets to evaluate the quality of candidate solutions for selection, which is often computationally expensive. Down-sampling training sets has long been used to decrease the computational cost of evaluation in a wide range of application domains. More specifically, recent studies have shown that both random and informed down-sampling can substantially improve problem-solving success for GP systems that use the lexicase parent selection algorithm. We test whether these down-sampling techniques can also improve problem-solving success in the context of three other commonly used selection methods, fitness-proportionate, tournament, implicit fitness sharing plus tournament selection, across six program synthesis GP problems. We verified that down-sampling can significantly improve the problem-solving success for all three of these other selection schemes, demonstrating its general efficacy. We discern that the selection pressure imposed by the selection scheme does not interact with the down-sampling method. However, we find that informed down-sampling can improve problem solving success significantly over random down-sampling when the selection scheme has a mechanism for diversity maintenance like lexicase or implicit fitness sharing. Overall, our results suggest that down-sampling should be considered more often when solving test-based problems, regardless of the selection scheme in use.
@inproceedings{boldi_untangling_2024, abbr = {ALIFE}, series = {Artificial {Life} {Conference} {Proceedings}}, title = {Untangling the {Effects} of {Down}-{Sampling} and {Selection} in {Genetic} {Programming}}, booktitle = {ALIFE 2024: Proceedings of the 2024 Artificial Life Conference}, url = {https://doi.org/10.1162/isal\_a\_00832}, author = {Boldi, Ryan and Bao, Ashley and Briesch, Martin and Helmuth, Thomas and Sobania, Dominik and Spector, Lee and Lalejini, Alexander}, month = jul, year = {2024}, bibtex_show = {true}, doi = {10.1162/isal_a_00832}, pdf = {https://direct.mit.edu/isal/proceedings-pdf/isal2024/36/88/2461089/isal\_a\_00832.pdf} }

Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving

Ryan Boldi*, Martin Briesch*, Dominik Sobania, Alexander Lalejini, and 4 more authors

Evolutionary Computation (MIT Press) Jul 2024

arXiv Bib Supp Code

@article{boldi2024informed,
  title = {Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving},
  author = {Boldi*, Ryan and Briesch*, Martin and Sobania, Dominik and Lalejini, Alexander and Helmuth, Thomas and Rothlauf, Franz and Ofria, Charles and Spector, Lee},
  journal = {Evolutionary Computation (MIT Press)},
  pages = {1--32},
  year = {2024},
  code = {https://github.com/ryanboldi/Informed-Down-Sampled-Lexicase/tree/main/propeller},
  supp = {https://ryanboldi.github.io/Informed-Down-Sampled-Lexicase/},
  arxiv = {2301.01488},
  preview = {IDS.png},
  bibtex_show = {true},
  selected = {true},
  publisher = {MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info~…}
}

2023

Objectives Are All You Need: Solving Deceptive Problems Without Explicit Diversity Maintenance

Ryan Boldi, Li Ding, and Lee Spector

In The Workshop on Agent Learning in Open-Endedness (ALOE) at the Conference on Neural Information Processing Systems (NeurIPS) Jul 2023

arXiv
Particularity

Lee Spector, Li Ding, and Ryan Boldi

In Genetic Programming Theory and Practice XX Jul 2023

PDF
A Static Analysis of Informed Down-Samples

Ryan Boldi, Alexander Lalejini, Thomas Helmuth, and Lee Spector

In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal Jul 2023

Abs Bib PDF

We present an analysis of the loss of population-level test coverage induced by different down-sampling strategies when combined with lexicase selection. We study recorded populations from the first generation of genetic programming runs, as well as entirely synthetic populations. Our findings verify the hypothesis that informed down-sampling better maintains population-level test coverage when compared to random down-sampling. Additionally, we show that both forms of down-sampling cause greater test coverage loss than standard lexicase selection with no down-sampling. However, given more information about the population, we found that informed down-sampling can further reduce its test coverage loss. We also recommend wider adoption of the static population analyses we present in this work.
@inproceedings{boldi2023static, abbr = {GECCO '23}, author = {Boldi, Ryan and Lalejini, Alexander and Helmuth, Thomas and Spector, Lee}, title = {A Static Analysis of Informed Down-Samples}, bibtex_show = {false}, preview = {static1.png}, booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal}, pdf = {https://arxiv.org/pdf/2304.01978.pdf}, year = {2023} }

The Problem Solving Benefits of Down-Sampling Vary by Selection Scheme

Ryan Boldi, Ashley Bao, Martin Briesch, Thomas Helmuth, and 3 more authors

In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal Jul 2023

Bib

@inproceedings{boldi2023TournDS,
  abbr = {GECCO '23},
  author = {Boldi, Ryan and Bao, Ashley and Briesch, Martin and Helmuth, Thomas and Sobania, Dominik and Spector, Lee and Lalejini, Alexander},
  title = {The Problem Solving Benefits of Down-Sampling Vary by Selection Scheme},
  booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal},
  year = {2023},
  preview = {interaction.png},
  bibtex_show = {false}
}

Can the Problem-Solving Benefits of Quality Diversity Be Obtained Without Explicit Diversity Maintenance?

Ryan Boldi, and Lee Spector

In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal Jul 2023

Abs Bib PDF

When using Quality Diversity (QD) optimization to solve hard exploration or deceptive search problems, we assume that diversity is extrinsically valuable. This means that diversity is important to help us reach an objective, but is not an objective in itself. Often, in these domains, practitioners benchmark their QD algorithms against single objective optimization frameworks. In this paper, we argue that the correct comparison should be made to \emphmulti-objective optimization frameworks. This is because single objective optimization frameworks rely on the aggregation of sub-objectives, which could result in decreased information that is crucial for maintaining diverse populations automatically. In order to facilitate a fair comparison between quality diversity and multi-objective optimization, we present a method that utilizes dimensionality reduction to automatically determine a set of behavioral descriptors for an individual, as well as a set of objectives for an individual to solve. Using the former, one can generate solutions using standard quality diversity optimization techniques, and using the latter, one can generate solutions using standard multi-objective optimization techniques. This allows for a level comparison between these two classes of algorithms, without requiring domain and algorithm specific modifications to facilitate a comparison.
@inproceedings{boldi2023QDBench, abbr = {GECCO '23}, title = {Can the Problem-Solving Benefits of Quality Diversity Be Obtained Without Explicit Diversity Maintenance?}, year = {2023}, author = {Boldi, Ryan and Spector, Lee}, bibtex_show = {false}, preview = {encoder.png}, booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '23 Companion), July 15--19, 2023, Lisbon, Portugal}, pdf = {https://arxiv.org/pdf/2305.07767.pdf} }

2022

The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection

Ryan Boldi, Thomas Helmuth, and Lee Spector

In 2022 Conference on Artificial Life - Why it Didn’t Work-Shop Jul 2022

Abs Bib PDF

Down-sampling training data has long been shown to improve the generalization performance of a wide range of machine learning systems. Recently, down-sampling has proved effective in genetic programming (GP) runs that utilize the lexicase parent selection technique. Although this down-sampling procedure has been shown to significantly improve performance across a variety of problems, it does not seem to do so due to encouraging adaptability through environmental change. We hypothesize that the random sampling that is performed every generation causes discontinuities that result in the population being unable to adapt to the shifting environment. We investigate modifications to down-sampled lexicase selection in hopes of promoting incremental environmental change to scaffold evolution by reducing the amount of jarring discontinuities between the environments of successive generations. In our empirical studies, we find that forcing incremental environmental change is not significantly better for evolving solutions to program synthesis problems than simple random down-sampling. In response to this, we attempt to exacerbate the hypothesized prevalence of discontinuities by using only disjoint down-samples to see if it hinders performance. We find that this also does not significantly differ from the performance of regular random down-sampling. These negative results raise new questions about the ways in which the composition of sub-samples, which may include synonymous cases, may be expected to influence the performance of machine learning systems that use down-sampling.
@inproceedings{boldi2022environmental, abbr = {ALIFE '22}, title = {The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection}, year = {2022}, author = {Boldi, Ryan and Helmuth, Thomas and Spector, Lee}, archiveprefix = {arXiv}, eprint = {2205.15931}, bibtex_show = {false}, preview = {environment.png}, booktitle = {2022 Conference on Artificial Life - Why it Didn't Work-Shop}, pdf = {https://arxiv.org/pdf/2205.15931v1.pdf} }
Lexicase Selection at Scale

Li Ding, Ryan Boldi, Thomas Helmuth, and Lee Spector

In Genetic and Evolutionary Computation Conference Companion (GECCO ’22 Companion), July 9–13, 2022, Boston, MA, USA Jul 2022

Abs Bib HTML PDF

Lexicase selection is a semantic-aware parent selection method, which assesses individual test cases in a randomly-shuffled data stream. It has demonstrated success in multiple research areas including genetic programming, genetic algorithms, and more recently symbolic regression and deep learning. One potential drawback of lexicase selection and its variants is that the selection procedure requires evaluating training cases in a single data stream, making it difficult to handle tasks where the evaluation is computationally heavy or the dataset is large-scale, e.g., deep learning. In this work, we investigate how the weighted shuffle methods can be employed to improve the efficiency of lexicase selection. We propose a novel method, fast lexicase selection, which incorporates lexicase selection and weighted shuffle with partial evaluation. Experiments on both classic genetic programming and deep learning tasks indicate that the proposed method can significantly reduce the number of evaluation steps needed for lexicase selection to select an individual, improving its efficiency while maintaining the performance.
@inproceedings{ding2022scale, abbr = {GECCO '22}, title = {Lexicase Selection at Scale}, year = {2022}, author = {Ding, Li and Boldi, Ryan and Helmuth, Thomas and Spector, Lee}, booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '22 Companion), July 9--13, 2022, Boston, MA, USA}, html = {https://dl.acm.org/doi/10.1145/3520304.3534026}, preview = {scale.png}, pdf = {https://arxiv.org/pdf/2208.10719.pdf}, bibtex_show = {false} }

Going Faster and Hence Further with Lexicase Selection

Li Ding, Ryan Boldi, Thomas Helmuth, and Lee Spector

In Genetic and Evolutionary Computation Conference Companion (GECCO ’22 Companion), July 9–13, 2022, Boston, MA, USA Jul 2022

Bib HTML Poster

@inproceedings{ding2022faster,
  abbr = {GECCO '22},
  title = {Going Faster and Hence Further with Lexicase Selection},
  year = {2022},
  author = {Ding, Li and Boldi, Ryan and Helmuth, Thomas and Spector, Lee},
  bibtex_show = {false},
  preview = {fast.png},
  poster = {gecco22poster.pdf},
  booktitle = {Genetic and Evolutionary Computation Conference Companion (GECCO '22 Companion), July 9--13, 2022, Boston, MA, USA},
  html = {https://dl.acm.org/doi/10.1145/3520304.3529059}
}

Under Review

2024

Pareto-Optimal Learning from Preferences with Hidden Context

Ryan Boldi, Li Ding, Lee Spector, and Scott Niekum

arXiv preprint arXiv:2406.15599 2024

arXiv

2023

Improving Recommendation System Serendipity Through Lexicase Selection

Ryan Boldi*, Aadam Lokhandwala*, Edward Annatone, Yuval Schechter, and 2 more authors

arXiv preprint arXiv:2305.11044 2023

arXiv Bib

@article{boldi2023improving,
  title = {Improving Recommendation System Serendipity Through Lexicase Selection},
  author = {Boldi*, Ryan and Lokhandwala*, Aadam and Annatone, Edward and Schechter, Yuval and Lavrenenko, Alexander and Sigrist, Cooper},
  publisher = {arXiv},
  journal = {arXiv preprint arXiv:2305.11044},
  url = {https://arxiv.org/abs/2305.11044},
  arxiv = {2305.11044},
  preview = {recsys.png},
  year = {2023},
  bibtex_show = {true},
  copyright = {arXiv.org perpetual, non-exclusive license}
}