DALex: Lexicase-like Selection via Diverse Aggregation

• URL: http://arxiv.org/abs/2401.12424v2
• Date: Fri, 9 Feb 2024 00:44:22 GMT
• Title: DALex: Lexicase-like Selection via Diverse Aggregation
• Authors: Andrew Ni, Li Ding, Lee Spector
• Abstract summary: We show that DALex (for Diversely Aggregated Lexicase) achieves significant speedups over lexicase selection and its relaxed variants. Results on program synthesis, deep learning, symbolic regression, and learning systems demonstrate that DALex achieves significant speedups over lexicase selection and its relaxed variants.
• Score: 6.394522608656896
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lexicase selection has been shown to provide advantages over other selection algorithms in several areas of evolutionary computation and machine learning. In its standard form, lexicase selection filters a population or other collection based on randomly ordered training cases that are considered one at a time. This iterated filtering process can be time-consuming, particularly in settings with large numbers of training cases. In this paper, we propose a new method that is nearly equivalent to lexicase selection in terms of the individuals that it selects, but which does so significantly more quickly. The new method, called DALex (for Diversely Aggregated Lexicase), selects the best individual with respect to a weighted sum of training case errors, where the weights are randomly sampled. This allows us to formulate the core computation required for selection as matrix multiplication instead of recursive loops of comparisons, which in turn allows us to take advantage of optimized and parallel algorithms designed for matrix multiplication for speedup. Furthermore, we show that we can interpolate between the behavior of lexicase selection and its "relaxed" variants, such as epsilon or batch lexicase selection, by adjusting a single hyperparameter, named "particularity pressure," which represents the importance granted to each individual training case. Results on program synthesis, deep learning, symbolic regression, and learning classifier systems demonstrate that DALex achieves significant speedups over lexicase selection and its relaxed variants while maintaining almost identical problem-solving performance. Under a fixed computational budget, these savings free up resources that can be directed towards increasing population size or the number of generations, enabling the potential for solving more difficult problems.

Related papers

• Adapt-$\infty$: Scalable Lifelong Multimodal Instruction Tuning via Dynamic Data Selection [89.42023974249122]
  Adapt-$infty$ is a new multi-way and adaptive data selection approach for Lifelong Instruction Tuning. We construct pseudo-skill clusters by grouping gradient-based sample vectors. We select the best-performing data selector for each skill cluster from a pool of selector experts.
  arXiv  Detail & Related papers  (2024-10-14T15:48:09Z)
• Lexicase-based Selection Methods with Down-sampling for Symbolic Regression Problems: Overview and Benchmark [0.8602553195689513]
  This paper evaluates random as well as informed down-sampling in combination with the relevant lexicase-based selection methods on a wide range of symbolic regression problems. We find that for a given evaluation budget, epsilon-lexicase selection in combination with random or informed down-sampling outperforms all other methods.
  arXiv  Detail & Related papers  (2024-07-31T14:26:22Z)
• Diversified Batch Selection for Training Acceleration [68.67164304377732]
  A prevalent research line, known as online batch selection, explores selecting informative subsets during the training process. vanilla reference-model-free methods involve independently scoring and selecting data in a sample-wise manner. We propose Diversified Batch Selection (DivBS), which is reference-model-free and can efficiently select diverse and representative samples.
  arXiv  Detail & Related papers  (2024-06-07T12:12:20Z)
• Towards Free Data Selection with General-Purpose Models [71.92151210413374]
  A desirable data selection algorithm can efficiently choose the most informative samples to maximize the utility of limited annotation budgets. Current approaches, represented by active learning methods, typically follow a cumbersome pipeline that iterates the time-consuming model training and batch data selection repeatedly. FreeSel bypasses the heavy batch selection process, achieving a significant improvement in efficiency and being 530x faster than existing active learning methods.
  arXiv  Detail & Related papers  (2023-09-29T15:50:14Z)
• Probabilistic Lexicase Selection [6.177959045971966]
  We introduce probabilistic lexicase selection (plexicase selection), a novel parent selection algorithm that efficiently approximates the probability distribution of lexicase selection. Our method not only demonstrates superior problem-solving capabilities as a semantic-aware selection method, but also benefits from having a probabilistic representation of the selection process.
  arXiv  Detail & Related papers  (2023-05-19T13:57:04Z)
• Calculating lexicase selection probabilities is NP-Hard [0.0]
  I prove that this problem, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a well-known NP-Complete problem, to lex-prob in time.
  arXiv  Detail & Related papers  (2023-01-17T06:51:44Z)
• 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)
• 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)
• Continual Learning using a Bayesian Nonparametric Dictionary of Weight Factors [75.58555462743585]
  Naively trained neural networks tend to experience catastrophic forgetting in sequential task settings. We propose a principled nonparametric approach based on the Indian Buffet Process (IBP) prior, letting the data determine how much to expand the model complexity. We demonstrate the effectiveness of our method on a number of continual learning benchmarks and analyze how weight factors are allocated and reused throughout the training.
  arXiv  Detail & Related papers  (2020-04-21T15:20:19Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  We propose a novel Bayesian optimization (BO) algorithm to tackle the challenge of model selection in this setting. In order to solve the resulting multiple black-box function optimization problem jointly and efficiently, we exploit potential correlations among black-box functions. We are the first to formulate the problem of stepwise model selection (SMS) for sequence prediction, and to design and demonstrate an efficient joint-learning algorithm for this purpose.
  arXiv  Detail & Related papers  (2020-01-12T09:42:19Z)

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.