Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system

ABSTRACT

Many learning classifier system (LCS) implementations are restricted to the binary problem realm. Recently, the XCS classifier system was enhanced to be able to handle real-valued inputs among others. In the real-valued enhancement, XCSF applies as a function approximation system that partitions the input space in hyperrectangular subspaces specified in the classifiers. This paper changes the classifier conditions to hyperspheres and hyperellipsoids and investigates the consequent performance impact. It is shown that the modifications yield improved performance in continuous functions. Even in discontinuous functions with parallel boundaries, XCS's performance does not degrade. Thus, for the real-valued problem domain, ellipsoidal condition structures can improve XCS's performance. From a more general perspective, this paper shows that XCS is readily applicable in diverse problem domains. To apply the system even more successfully, suitable kernel-based bases need to be found and used as classifier conditions. XCS distributes the available structures over the problem space evolving more specialized structures in more complex problem subspaces.

REFERENCES

• 1: J. Bacardit, D. E. Goldberg, and M. V. Butz. Improving the performance of a Pittsburgh learning classifier system using a default rule, 2004. http://www.psychologie.uni-wuerzburg.de/IWLCS/.
• 2: John Barlow, Cerebellum and Adaptive Control, Cambridge University Press, New York, NY, 2002
• 3: Ester Bernadó i Mansilla , Xavier Llorà , Josep Maria Garrell i Guiu, XCS and GALE: A Comparative Study of Two Learning Classifier Systems on Data Mining, Revised Papers from the 4th International Workshop on Advances in Learning Classifier Systems, p.115-132, July 07-08, 2001
• 4: Ester Bernadó-Mansilla , Josep M. Garrell-Guiu, Accuracy-based learning classifier systems: models, analysis and applications to classification tasks, Evolutionary Computation, v.11 n.3, p.209-238, Fall 2003 [doi>10.1162/106365603322365289]
• 5: L. B. Booker , D. E. Goldberg , J. H. Holland, Classifier systems and genetic algorithms, Artificial Intelligence, v.40 n.1-3, p.235-282, Sep. 1989 [doi>10.1016/0004-3702(89)90050-7]
• 6: Larry Bull , Jacob Hurst, ZCS redux, Evolutionary Computation, v.10 n.2, p.185-205, Summer 2002 [doi>10.1162/106365602320169848]
• 7: Larry Bull , Toby O'Hara, Accuracy-based Neuro And Neuro-fuzzy Classifier Systems, Proceedings of the Genetic and Evolutionary Computation Conference, p.905-911, July 09-13, 2002
• 8: M. V. Butz, D. E. Goldberg, P. L. Lanzi, and K. Sastry. Bounding the population size to ensure niche support in XCS. IlliGAL report 2004033, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2004.
• 9: Martin V. Butz , David E. Goldberg , Kurian Tharakunnel, Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy, Evolutionary Computation, v.11 n.3, p.239-277, Fall 2003 [doi>10.1162/106365603322365298]
• 10: M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. How XCS evolves accurate classifiers. Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pages 927--934, 2001.
• 11: M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a theory of generalization and learning in XCS. IEEE Transactions on Evolutionary Computation, 8:28--46, 2004.
• 12: M. V. Butz and M. Pelikan. Analyzing the evolutionary pressures in XCS. Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pages 935--942, 2001.
• 13: M. V. Butz, K. Sastry, and D. E. Goldberg. Tournament selection in XCS. Proceedings of the Fifth Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1857--1869, 2003.
• 14: Zoubin Ghahramani , Michael I. Jordan, Factorial Hidden Markov Models, Machine Learning, v.29 n.2-3, p.245-273, Nov./Dec. 1997 [doi>10.1023/A:1007425814087]
• 15: J. H. Holland. Adaptation. In R. Rosen and F. Snell, editors, Progress in theoretical biology, volume 4, pages 263--293. Academic Press, New York, 1976.
• 16: J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms. In D. A. Waterman and F. Hayes-Roth, editors, Pattern directed inference systems, pages 313--329. Academic Press, New York, 1978.
• 17: P. L. Lanzi. Extending the Representation of Classifier Conditions Part I: From Binary to Messy Coding. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 337--344, 1999.
• 18: P. L. Lanzi. Extending the Representation of Classifier Conditions Part II: From Messy Coding to S-Expressions. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 345--352, 1999.
• 19: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 20: Christopher Stone , Larry Bull, For real! XCS with continuous-valued inputs, Evolutionary Computation, v.11 n.3, p.299-336, Fall 2003 [doi>10.1162/106365603322365315]
• 21: S. W. Wilson. ZCS: A zeroth level classifier system. Evolutionary Computation, 2:1--18, 1994.
• 22: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.
• 23: S. W. Wilson. Generalization in the XCS classifier system. Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674, 1998.
• 24: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000
• 25: S. W. Wilson. Function approximation with a classifier system. Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pages 974--981, 2001.
• 26: Stewart W. Wilson, Mining Oblique Data with XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.158-176, September 15-16, 2000
• 27: Stewart W. Wilson, Classifiers that approximate functions, Natural Computing: an international journal, v.1 n.2-3, p.211-234, June 2002 [doi>10.1023/A:1016535925043]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
  I.5 PATTERN RECOGNITION
      I.5.0 General
      I.5.1 Models
          Subjects: Neural nets; Statistical; Fuzzy set

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
GAs, XCS, function approximation, learning classifier systems, piece-wise linear approximation, radial bases