Lexicase selection in learning classifier systems

Sneha Aenugu, Lee Spector

Introduction

In the field of evolutionary machine learning, Learning Classifier Systems (LCS) aim to evolve a population of rules—typically in the form of "If condition X, then Class Y"—that collectively describe a dataset. Traditionally, the fitness of these rules is determined by their aggregate accuracy across the entire training set. While effective for simple problems, this reliance on aggregate scores often leads to "overfitting" or the creation of overly specialized rules that fail to generalize to unseen data, especially when training samples are sparse or noisy.

This paper explores a shift in selection strategy, introducing batch-lexicase selection to the LCS framework. By moving away from global averages and evaluating rules on specific subsets of data, the authors demonstrate a significant improvement in the evolution of robust, general-purpose rules.

Methods

The study compares four distinct parent selection methods within a supervised LCS architecture (UCS):

  1. Fitness Proportionate (Roulette Wheel): Selection probability is directly proportional to a rule's aggregate accuracy.
  2. Tournament Selection: Randomly selects a small group of rules and picks the one with the highest accuracy as the parent.
  3. Lexicase Selection: A survival-of-the-fittest gauntlet where rules are tested against individual data points in a randomized order. A rule is eliminated as soon as it fails a point; the process continues until one rule remains.
  4. Batch-Lexicase Selection: A novel variant designed to mitigate the "harshness" of standard lexicase in LCS. Instead of individual points, rules are tested against batches of data. To survive, a rule must meet a specific fitness threshold on that batch. This allows for fine-tuning selection pressure through batch size and survival thresholds.

Generalization and Rule Quality

A primary goal of this research was to encourage generality—the ability of a single rule to accurately describe many different data instances. The authors found that batch-lexicase selection acts as a natural pressure for this trait. Because a rule must survive multiple diverse batches to be selected for reproduction, it is forced to be accurate across a wide variety of data subsets.

Figure 2: Distribution of rule coverage. Batch-lexicase evolves rules that correctly describe a larger number of data instances on average compared to tournament selection.

In experiments using the 11-bit multiplexer, the difference in rule quality was stark. As shown in the histogram above, rules evolved via tournament selection tended to be highly specific, often describing fewer than 10 data instances. In contrast, batch-lexicase produced a distribution shifted toward higher coverage, resulting in a more compact and powerful rule set that achieved the same accuracy with fewer distinct rules.

Performance on Sparse Data

The true strength of batch-lexicase selection is revealed in scenarios with missing or partial data. In the 20-bit multiplexer problem—where only 0.2% of the total data space was available for training—traditional selection methods struggled to generalize.

Figure 5: Performance comparison on the 20-bit Multiplexer with partial data. Batch-lexicase (B-Lexicase) achieves superior test accuracy and more efficient rule reduction compared to traditional methods.

As illustrated in the results above, batch-lexicase achieved nearly 100% test accuracy, effectively "filling in the gaps" left by the missing training data. Tournament selection, by comparison, hovered at significantly lower accuracy levels. Furthermore, the number of distinct rules generated by batch-lexicase dropped sharply during training, indicating that the system was successfully condensing its knowledge into a few highly general rules rather than a bloated population of specific ones.

Limitations and Future Work

While batch-lexicase selection offers clear advantages in generalization, it is not without trade-offs. The authors note that the computational cost of training increases by approximately a factor of two due to the iterative nature of the lexicase gauntlet. Additionally, standard lexicase performed poorly on noisy datasets like the LED problem, where rules are inherently specialized; this highlights the importance of the "batch" variant for maintaining flexibility.

Future research will focus on optimizing computational efficiency through data caching and developing a deeper theoretical framework to provide fine-grained control over selection pressure across different evolutionary contexts.

Conclusion

Batch-lexicase selection represents a significant advancement for Learning Classifier Systems. By evaluating rules on their ability to handle diverse subsets of data rather than global averages, it enables the evolution of more general, robust, and efficient rule sets. This approach is particularly valuable for complex real-world problems where data may be sparse, biased, or incomplete.

Summary updated

BibTeX
@inproceedings{aenugu2019lexicase,
  author = {Sneha Aenugu and Lee Spector},
  title = {{Lexicase selection in learning classifier systems}},
  booktitle = {GECCO},
  year = {2019},
  doi = {10.1145/3321707.3321828},
}
Figure