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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Holland, J.H.: Processing and processors for schemata. In: Jacks, E.L. (ed.) Associative Information Techniques, pp. 127–146. American Elsevier, New York (1971)
Wilson, S.W.: ZCS: A zeroth level classifier system. Evolutionary Computation 2, 1–18 (1994)
Bull, L., Hurst, J.: ZCS redux. Evolutionary Computation 10, 185–205 (2002)
Wilson, S.W.: Classifier fitness based on accuracy. Evolutionary Computation 3, 149–175 (1995)
Butz, M.V., Goldberg, D.E., Tharakunnel, K.: Analysis and improvement of fitness exploitation in XCS: Bounding models, tournament selection, and bilateral accuracy. Evolutionary Computation 11, 239–277 (2003)
Bernadó, E., Llorà, X., Garrell, J.M.: XCS and GALE: A comparative study of two learning classifier systems and six other learning algorithms on classification tasks. In: Lanzi, P.L., Stolzmann, W., Wilson, S.W. (eds.) IWLCS 2001. LNCS (LNAI), vol. 2321, pp. 115–132. Springer, Heidelberg (2002)
Dixon, P.W., Corne, D.W., Oates, M.J.: A preliminary investigation of modified XCS as a generic data mining tool. In: Lanzi, P.L., Stolzmann, W., Wilson, S.W. (eds.) IWLCS 2001. LNCS (LNAI), vol. 2321, pp. 133–150. Springer, Heidelberg (2002)
Butz, M.V., Kovacs, T., Lanzi, P.L., Wilson, S.W.: How XCS evolves accurate classifiers. In: Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 927–934 (2001)
Butz, M.V., Pelikan, M.: Analyzing the evolutionary pressures in XCS. In: Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 935–942 (2001)
Butz, M.V., Kovacs, T., Lanzi, P.L., Wilson, S.W.: Toward a theory of generalization and learning in XCS. IEEE Transactions on Evolutionary Computation 8, 28–46 (2004)
Holland, J.H., Reitman, J.S.: Cognitive systems based on adaptive algorithms. In: Waterman, D.A., Hayes-Roth, F. (eds.) Pattern directed inference systems, pp. 313–329. Academic Press, New York (1978)
Lanzi, P.L.: Learning classifier systems from a reinforcement learning perspective. Soft Computing: A Fusion of Foundations, Methodologies and Applications 6, 162–170 (2002)
Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975) second edition 1992
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA (1989)
Butz, M.V., Sastry, K., Goldberg, D.E.: Tournament selection in XCS. In: Proceedings of the Fifth Genetic and Evolutionary Computation Conference (GECCO-2003), pp. 1857–1869 (2003)
Kovacs, T.: Towards a theory of strong overgeneral classifiers. Foundations of Genetic Algorithms 6 (2001)
Kovacs, T.: Deletion schemes for classifier systems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), pp. 329–336 (1999)
Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Francisco (1993)
Thierens, D., Goldberg, D.E., Pereira, A.G.: Domino convergence, drift, and the temporal-salience structure of problems. In: Proceedings of the 1998 IEEE World Congress on Computational Intelligence, New York, NY, pp. 535–540. IEEE Press, Los Alamitos (1998)
Wilson, S.W.: Generalization in the XCS classifier system. In: Genetic Programming 1998: Proceedings of the Third Annual Conference, pp. 665–674 (1998)
Bull, L.: Investigating fitness sharing in a simple payoff-based learning classifier system. Technical Report UWELCSG03-009, University of Western England, Learning Classifier System Group, Bristol, UK (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Butz, M.V., Goldberg, D.E., Lanzi, P.L. (2004). Bounding Learning Time in XCS. In: Deb, K. (eds) Genetic and Evolutionary Computation – GECCO 2004. GECCO 2004. Lecture Notes in Computer Science, vol 3103. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24855-2_89
Download citation
DOI: https://doi.org/10.1007/978-3-540-24855-2_89
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22343-6
Online ISBN: 978-3-540-24855-2
eBook Packages: Springer Book Archive