Extending XCSF beyond linear approximation

ABSTRACT

XCSF is the extension of XCS in which classifier prediction is computed as a linear combination of classifier inputs and a weight vector associated to each classifier. XCSF can exploit classifiers' computable prediction to evolve accurate piecewise linear approximations of functions. In this paper, we take XCSF one step further and show how XCSF can be easily extended to allow polynomial approximations. We test the extended version of XCSF on various approximation problems and show that quadratic/cubic approximations can be used to significantly improve XCSF's generalization capabilities.

REFERENCES

• 1: Justin A. Boyan, Least-Squares Temporal Difference Learning, Proceedings of the Sixteenth International Conference on Machine Learning, p.49-56, June 27-30, 1999
• 2: Steven J. Bradtke , Andrew G. Barto, Linear least-squares algorithms for temporal difference learning, Machine Learning, v.22 n.1-3, p.33-57, Jan./Feb./March 1996 [doi>10.1007/BF00114723]
• 3: M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3--4):144--153, 2002.
• 4: M. Galassi, J. Davies, J. Theiler, B. Gough, G. Jungman, M. Booth, and F. Rossi. GNU Scientific Library Reference Manual -- Second Edition. Network Theory Ltd., 2003. (paperback).
• 5: S. A. Glantz and B. K. Slinker. Primer of Applied Regression & Analysis of Variance. McGraw Hill, 2001. second edition.
• 6: S Haykin, Adaptive filter theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 7: Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 8: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 9: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 10: P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. Generalization in the XCSF classifier system: Analysis, improvement, and extension. Technical Report 2005012, Illinois Genetic Algorithms Laboratory -- University of Illinois at Urbana-Champaign, 2005.
• 11: William H. Press , William T. Vetterling , Saul A. Teukolsky , Brian P. Flannery, Numerical Recipes in C++: the art of scientific computing, 2001
• 12: Bernard Widrow , Marcian E. Hoff, Adaptive switching circuits, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 13: S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995. http://prediction-dynamics.com/.
• 14: 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
• 15: 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]
• 16: I. Zelinka. Analytic programming by means of soma algorithm. In Proceedings of the 8th International Conference on Soft Computing, Mendel'02, pages 93--101, Brno,Czech Republic, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation; Linear approximation

General Terms:
Algorithms, Performance

Keywords:
LCS, XCS, function approximation, least squares