Illinois Genetic Algorithms Laboratory

Butz, M. V., Goldberg, D. E., Lanzi, P.-L. (2004)
TR No.: 2004011 | Download PDF | Download PS

Abstract:
Although Learning Classifier Systems date back more than twenty years ago,
theory regarding issues like convergence or computational effort remained sparse. This paper establishes a PAC learning bound for the accuracy-based classifier system XCS. XCS is a flexible genetic-based learning mechanism applicable in classification problems, reinforcement learning problems, as well as different types of representations. Using a facet-wise analysis focusing on the learning of Boolean functions, we show that given several assumptions, k-DNF and related Boolean functions are PAC-learnable by XCS. The facet-wise analysis is modular, flexible, and extendable to other problem types and representations.