Hyper-ellipsoidal conditions in XCS: rotation, linear approximation, and solution structure

ABSTRACT

The learning classifier system XCS is an iterative rule-learning system that evolves rule structures based on gradient-based prediction and rule quality estimates. Besides classification and reinforcement learning tasks, XCS was applied as an effective function approximator. Hereby, XCS learns space partitions to enable a maximally accurate and general function approximation. Recently, the function approximation approach was improved by replacing (1) hyperrectangular conditions with hyper-ellipsoids and (2) iterative linear approximation with the recursive least squares method. This paper combines the two approaches assessing the usefulness of each. The evolutionary process is further improved by changing the mutation operator implementing an angular mutation that rotates ellipsoidal structures explicitly. Both enhancements improve XCS performance in various non-linear functions. We also analyze the evolving ellipsoidal structures confirming that XCS stretches and rotates the evolving ellipsoids according to the shape of the underlying function. The results confirm that improvements in both the evolutionary approach and the gradient approach can result in significantly better performance.

REFERENCES

• 1: Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997 [doi>10.1023/A:1006559212014]
• 2: 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
• 3: 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]
• 4: 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]
• 5: Martin V. Butz, Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068320]
• 6: M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Foundations of Learning Classifier Systems, chapter Computational Complexity of the XCS Classifier System, pages 91--126. Studies in Fuzziness and Soft Computing. Springer-Verlag, Berlin Heidelberg, 2005.
• 7: 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]
• 8: Martin Butz , Stewart W. Wilson, An Algorithmic Description of XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.253-272, September 15-16, 2000
• 9: Marc Ebner , Mark Shackleton , Rob Shipman, How neutral networks influence evolvability, Complexity, v.7 n.2, p.19-33, November/December 2001 [doi>10.1002/cplx.10021]
• 10: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 11: Simon Haykin, Adaptive filter theory (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 12: 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.
• 13: P. L. Lanzi. Generalization in the XCSF classifier system: Analysis, improvement, and extensions. IlliGAL report 2005012, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2005.
• 14: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 15: E. W. Euler angles. From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EulerAngles.html, 1999.
• 16: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.
• 17: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000
• 18: 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]
• 19: Stewart W. Wilson, Compact Rulesets from XCSI, Revised Papers from the 4th International Workshop on Advances in Learning Classifier Systems, p.197-210, July 07-08, 2001
• 20: S. W. Wilson. Classifier systems for continuous payoff environments. Proceedings of the Sixth Genetic and Evolutionary Computation Conference (GECCO-2004): Part II, pages 824--835, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
LCS, XCS, function approximation, genetic algorithms, locally weighted learning, recursive least squares