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

• URL: http://arxiv.org/abs/2304.07089v2
• Date: Thu, 1 Aug 2024 15:13:42 GMT
• Title: Untangling the Effects of Down-Sampling and Selection in Genetic Programming
• Authors: Ryan Boldi, Ashley Bao, Martin Briesch, Thomas Helmuth, Dominik Sobania, Lee Spector, Alexander Lalejini,
• Abstract summary: Genetic programming systems often use large training sets to evaluate the quality of candidate solutions for selection. Recent studies have shown that both random and informed down-sampling can substantially improve problem-solving success.
• Score: 40.05141985769286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• 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)
• Learning Fair Policies for Multi-stage Selection Problems from Observational Data [4.282745020665833]
  We consider the problem of learning fair policies for multi-stage selection problems from observational data. This problem arises in several high-stakes domains such as company hiring, loan approval, or bail decisions where outcomes are only observed for those selected. We propose a multi-stage framework that can be augmented with various fairness constraints, such as demographic parity or equal opportunity.
  arXiv  Detail & Related papers  (2023-12-20T16:33:15Z)
• Selecting Learnable Training Samples is All DETRs Need in Crowded Pedestrian Detection [72.97320260601347]
  In crowded pedestrian detection, the performance of DETRs is still unsatisfactory due to the inappropriate sample selection method. We propose Sample Selection for Crowded Pedestrians, which consists of the constraint-guided label assignment scheme (CGLA) Experimental results show that the proposed SSCP effectively improves the baselines without introducing any overhead in inference.
  arXiv  Detail & Related papers  (2023-05-18T08:28:01Z)
• In Search of Insights, Not Magic Bullets: Towards Demystification of the Model Selection Dilemma in Heterogeneous Treatment Effect Estimation [92.51773744318119]
  This paper empirically investigates the strengths and weaknesses of different model selection criteria. We highlight that there is a complex interplay between selection strategies, candidate estimators and the data used for comparing them.
  arXiv  Detail & Related papers  (2023-02-06T16:55:37Z)
• Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving [40.683810697551166]
  Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases allowing for more individuals to be explored with the same amount of program executions. In Informed Down-Sampled Lexicase Selection, we use population statistics to build down-samples that contain more distinct and therefore informative training cases.
  arXiv  Detail & Related papers  (2023-01-04T08:47:18Z)
• The Environmental Discontinuity Hypothesis for Down-Sampled Lexicase Selection [0.0]
  Down-sampling has proved effective in genetic programming (GP) runs that utilize the lexicase parent selection technique. 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 find that forcing incremental environmental change is not significantly better for evolving solutions to program synthesis problems than simple random down-sampling.
  arXiv  Detail & Related papers  (2022-05-31T16:21:14Z)
• HardVis: Visual Analytics to Handle Instance Hardness Using Undersampling and Oversampling Techniques [48.82319198853359]
  HardVis is a visual analytics system designed to handle instance hardness mainly in imbalanced classification scenarios. Users can explore subsets of data from different perspectives to decide all those parameters. The efficacy and effectiveness of HardVis are demonstrated with a hypothetical usage scenario and a use case.
  arXiv  Detail & Related papers  (2022-03-29T17:04:16Z)
• 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.