An Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality

• URL: http://arxiv.org/abs/2107.09760v2
• Date: Mon, 26 Jul 2021 21:52:40 GMT
• Title: An Exploration of Exploration: Measuring the ability of lexicase selection to find obscure pathways to optimality
• Authors: Jose Guadalupe Hernandez, Alexander Lalejini, Charles Ofria
• Abstract summary: We introduce an "exploration diagnostic" that diagnoses a selection scheme's capacity for search space exploration. We verify that lexicase selection out-explores tournament selection. We find that relaxing lexicase's elitism with epsilon lexicase can further improve exploration.
• Score: 62.997667081978825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parent selection algorithms (selection schemes) steer populations through a problem's search space, often trading off between exploitation and exploration. Understanding how selection schemes affect exploitation and exploration within a search space is crucial to tackling increasingly challenging problems. Here, we introduce an "exploration diagnostic" that diagnoses a selection scheme's capacity for search space exploration. We use our exploration diagnostic to investigate the exploratory capacity of lexicase selection and several of its variants: epsilon lexicase, down-sampled lexicase, cohort lexicase, and novelty-lexicase. We verify that lexicase selection out-explores tournament selection, and we show that lexicase selection's exploratory capacity can be sensitive to the ratio between population size and the number of test cases used for evaluating candidate solutions. Additionally, we find that relaxing lexicase's elitism with epsilon lexicase can further improve exploration. Both down-sampling and cohort lexicase -- two techniques for applying random subsampling to test cases -- degrade lexicase's exploratory capacity; however, we find that cohort partitioning better preserves lexicase's exploratory capacity than down-sampling. Finally, we find evidence that novelty-lexicase's addition of novelty test cases can degrade lexicase's capacity for exploration. Overall, our findings provide hypotheses for further exploration and actionable insights and recommendations for using lexicase selection. Additionally, this work demonstrates the value of selection scheme diagnostics as a complement to more conventional benchmarking approaches to selection scheme analysis.

Related papers

• Lexicase Selection Parameter Analysis: Varying Population Size and Test Case Redundancy with Diagnostic Metrics [1.9570926122713395]
  We study how population size and number of generations affect lexicase's ability to exploit gradients and maintain specialists. By varying the population size with a fixed evaluation budget, we show that smaller populations tend to have greater exploitation capabilities. We also consider the effect redundant test cases have on specialist maintenance, and find that high redundancy may hinder the ability to optimize and maintain specialists.
  arXiv  Detail & Related papers  (2024-07-21T04:54:27Z)
• On the Robustness of Lexicase Selection to Contradictory Objectives [0.9208007322096533]
  We study lexicase and epsilon-lexicase selection's performance on contradictory objectives. We find that lexicase and epsilon-lexicase selection each have a region of parameter space where they are incapable of optimizing contradictory objectives. We propose theoretically-backed guidelines for parameter choice.
  arXiv  Detail & Related papers  (2024-03-11T15:23:35Z)
• Improving Recommendation System Serendipity Through Lexicase Selection [53.57498970940369]
  We propose a new serendipity metric to measure the presence of echo chambers and homophily in recommendation systems. We then attempt to improve the diversity-preservation qualities of well known recommendation techniques by adopting a parent selection algorithm known as lexicase selection. Our results show that lexicase selection, or a mixture of lexicase selection and ranking, outperforms its purely ranked counterparts in terms of personalization, coverage and our specifically designed serendipity benchmark.
  arXiv  Detail & Related papers  (2023-05-18T15:37:38Z)
• Lexicase Selection at Scale [5.4968949435821735]
  Lexicase selection is a semantic-aware parent selection method, which assesses individual test cases in a randomly-shuffled data stream. One potential drawback of lexicase selection and its variants is that the selection procedure requires evaluating training cases in a single data stream. We propose a novel method, fast lexicase selection, which incorporates lexicase selection and weighted shuffle with partial evaluation.
  arXiv  Detail & Related papers  (2022-08-23T03:58:47Z)
• Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions [78.31410227443102]
  We study the problem of adaptively identifying patient subpopulations that benefit from a given treatment during a confirmatory clinical trial. We propose AdaGGI and AdaGCPI, two meta-algorithms for subpopulation construction.
  arXiv  Detail & Related papers  (2022-08-11T14:27:49Z)
• ALLSH: Active Learning Guided by Local Sensitivity and Hardness [98.61023158378407]
  We propose to retrieve unlabeled samples with a local sensitivity and hardness-aware acquisition function. Our method achieves consistent gains over the commonly used active learning strategies in various classification tasks.
  arXiv  Detail & Related papers  (2022-05-10T15:39:11Z)
• A suite of diagnostic metrics for characterizing selection schemes [45.74830585715129]
  We introduce DOSSIER, a diagnostic suite initially composed of eight handcrafted metrics. These metrics are designed to empirically measure specific capacities for exploitation, exploration, and their interactions. We apply DOSSIER to six popular selection schemes: truncation, tournament, fitness sharing, lexicase, nondominated sorting, and novelty search.
  arXiv  Detail & Related papers  (2022-04-29T01:05:51Z)
• Problem-solving benefits of down-sampled lexicase selection [0.20305676256390928]
  We show that down-sampled lexicase selection's main benefit stems from the fact that it allows the evolutionary process to examine more individuals within the same computational budget. The reasons that down-sampling helps, however, are not yet fully understood.
  arXiv  Detail & Related papers  (2021-06-10T23:42:09Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  Group testing is a well-studied problem with several appealing solutions. Recent biological studies impose practical constraints for COVID-19 that are incompatible with traditional methods. We develop a new method combining Bloom filters with belief propagation to scale to larger values of n (more than 100) with good empirical results.
  arXiv  Detail & Related papers  (2020-07-21T19:31:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.