 |
    |
Bounding Learning Time in XCS
Martin V. Butz, David E. Goldberg, and Pier Luca Lanzi
Illinois Genetic Algorithms Laboratory (IlliGAL), University of Illinois at Urbana-Champaign, Urbana, IL, 61801butz@illigal.ge.uiuc.edu
deg@illigal.ge.uiuc.edu
lanzi@illigal.ge.uiuc.edu
Abstract. It has been shown empirically that the XCS classifier system solves typical classification problems in a machine learning competitive way. However, until now, no learning time estimate has been derived analytically for the system. This paper introduces a time estimate that bounds the learning time of XCS until maximally accurate classifiers are found. We assume a domino convergence model in which each attribute is successively specialized to the correct value. It is shown that learning time in XCS scales polynomially in problem length and problem complexity and thus in a machine learning competitive way.
LNCS 3103, p. 739 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004