Toward a theory of generalization and learning in XCS

Takes initial steps toward a theory of generalization and learning in the learning classifier system XCS. We start from Wilson's generalization hypothesis, which states that XCS has an intrinsic tendency to evolve accurate, maximally general classifiers. We analyze the different evolutionary pr...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2004-02, Vol.8 (1), p.28-46
Main Authors: Butz, M.V., Kovacs, T., Lanzi, P.L., Wilson, S.W.
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Classifiers
Computer science
Computer science
control theory
systems
Data analysis
Differential equations
Evolutionary
Exact sciences and technology
Fitness
Foundations
Insurance
Java
Learning
Learning and adaptive systems
Machine learning
Mathematical analysis
Mathematical models
Multiplexing
Psychology
Robots
Testing
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Takes initial steps toward a theory of generalization and learning in the learning classifier system XCS. We start from Wilson's generalization hypothesis, which states that XCS has an intrinsic tendency to evolve accurate, maximally general classifiers. We analyze the different evolutionary pressures in XCS and derive a simple equation that supports the hypothesis theoretically. The equation is tested with a number of experiments that confirm the model of generalization pressure that we provide. Then, we focus on the conditions, termed "challenges," that must be satisfied for the existence of effective fitness or accuracy pressure in XCS. We derive two equations that suggest how to set the population size and the covering probability so as to ensure the development of fitness pressure. We argue that when the challenges are met, XCS is able to evolve problem solutions reliably. When the challenges are not met, a problem may provide intrinsic fitness guidance or the reward may be biased in such a way that the problem will still be solved. The equations and the influence of intrinsic fitness guidance and biased reward are tested on large Boolean multiplexer problems. The paper is a contribution to understanding how XCS functions and lays the foundation for research on XCS's learning complexity.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2003.818194