Martin Briesch

Informed down-sampling (IDS) is known to improve performance in symbolic regression when combined with various selection strategies, especially tournament selection. However, recent work found that IDS's gains are not consistent across all problems. Our analysis reveals that IDS performance is worse for problems containing outliers. IDS systematically favors including outliers in subsets which pushes GP towards finding solutions that overfit to outliers. To address this, we introduce ROIDS (Robust Outlier-Aware Informed Down-Sampling), which excludes potential outliers from the sampling process of IDS. With ROIDS it is possible to keep the advantages of IDS without overfitting to outliers and to compete on a wide range of benchmark problems. This is also reflected in our experiments in which ROIDS shows the desired behavior on all studied benchmark problems. ROIDS consistently outperforms IDS on synthetic problems with added outliers as well as on a wide range of complex real-world problems, surpassing IDS on over 80% of the real-world benchmark problems. Moreover, compared to all studied baseline approaches, ROIDS achieves the best average rank across all tested benchmark problems. This robust behavior makes ROIDS a reliable down-sampling method for selection in symbolic regression, especially when outliers may be included in the data set.

In today’s online world, bias is ubiquitous. In a Video-on-Demand (VOD) context, there are two main sources for bias: (1) content providers and their methods that generate recommendations; (2) user preferences. We use real world data from one of the largest German Public Service Media (PSM) platforms to study both possible causes by examining content recommendations and content consumption (classified as Education, Information, Culture, and Entertainment according to the regulations governing PSM operations). We find that Education and Entertainment content to be recommended disproportionately. Algorithmic personalized recommendations lead to a bias towards both Education and Entertainment for the recommendations. Editorial content recommendations favor Entertainment content. Additionally, we find that the bias introduced by the recommender systems to be larger than the one introduced by the viewer. We recommend testing an increased use of algorithmic recommendations as these might lead to a lower bias towards Entertainment content.

The success of lexicase selection has led to various extensions, including its combination with down-sampling, which further increased performance. However, recent work found that down-sampling also leads to significant improvements in the performance of tournament selection. This raises the question of whether tournament selection combined with down-sampling is the better choice, given its faster running times. To address this question, we run a set of experiments comparing epsilon-lexicase and tournament selection with different down-sampling techniques on synthetic problems of varying noise levels and problem sizes as well as real-world symbolic regression problems. Overall, we find that down-sampling improves generalization and performance even when compared over the same number of generations. This means that down-sampling is beneficial even with way fewer fitness evaluations. Additionally, down-sampling successfully reduces code growth. We observe that population diversity increases for tournament selection when combined with down-sampling. Further, we find that tournament selection and epsilon-lexicase selection with down-sampling perform similar, while tournament selection is significantly faster. We conclude that tournament selection should be further analyzed and improved in future work instead of only focusing on the improvement of lexicase variants.

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 number of program executions. However, sampling randomly can exclude important cases from the down-sample for a number of generations, while cases that measure the same behavior (synonymous cases) may be overused. In this work, we introduce Informed Down-Sampled Lexicase Selection. This method leverages population statistics to build down-samples that contain more distinct and therefore informative training cases. Through an empirical investigation across two different GP systems (PushGP and Grammar-Guided GP), we find that informed down-sampling significantly outperforms random down-sampling on a set of contemporary program synthesis benchmark problems. Through an analysis of the created down-samples, we find that important training cases are included in the down-sample consistently across independent evolutionary runs and systems. We hypothesize that this improvement can be attributed to the ability of Informed Down-Sampled Lexicase Selection to maintain more specialist individuals over the course of evolution, while still benefiting from reduced per-evaluation costs.

Genetic programming systems typically require large computational resource investments for training-set evaluations. Down-sampling these sets has proven to decrease costs and improve problem-solving success, particularly with the lexicase parent selection algorithm. We investigated its effectiveness when applied to three other common selection methods and across various program synthesis problems. Our findings show that down-sampling notably enhances all three methods, indicating its potential broad applicability. Additionally, we found informed down-sampling to be more successful than its random counterpart, particularly in selection schemes maintaining diversity like lexicase selection. We conclude that down-sampling is a promising strategy for test-based genetic programming problems, irrespective of selection scheme. This paper is a comprehensive extension of a previous poster paper [1].

This short paper presents the main findings of our work titled Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving, which was recently published in the Evolutionary Computation Journal. In this work, we introduce informed down-sampled lexicase selection to dynamically build diverse subsets of training cases during evolution using population statistics. We evaluate our method on a set of program synthesis problems in two genetic programming systems and find that informed down-sampling improves performance in both systems compared to random down-sampling when using lexicase selection. Additionally, we investigate the constructed down-samples and find that informed down-sampling can identify important training cases and does so across different evolutionary runs and systems.

Large language models have recently become known for their ability to generate computer programs, especially through tools such as GitHub Copilot, a domain where genetic programming has been very successful so far. Although they require different inputs (free-text vs. input/output examples) their goal is the same – program synthesis. Therefore, in this work we compare how well GitHub Copilot and genetic programming perform on common program synthesis benchmark problems. We study the structure and diversity of the generated programs by using well-known software metrics. We find that GitHub Copilot and genetic programming solve a similar number of benchmark problems (85.2% vs. 77.8%, respectively). We find that GitHub Copilot generated smaller and less complex programs as genetic programming, while genetic programming is able to find new and unique problem solving strategies. This increase in diversity of solutions comes at a cost. When analyzing the success rates for 100 runs per problem, GitHub Copilot outperforms genetic programming on over 50% of the problems.