Empirical analysis of generalization and learning in XCS with gradient descent

ABSTRACT

We analyze generalization and learning in XCS with gradient descent. At first, we show that the addition of gradient in XCS may slow down learning because it indirectly decreases the learning rate. However, in contrast to what was suggested elsewhere, gradient descent has no effect on the achieved generalization. We also show that when gradient descent is combined with roulette wheel selection, which is known to be sensitive to small values of the learning rate, the learning speed can slow down dramatically. Previous results reported no difference in the performance of XCS with gradient descent when roulette wheel selection or tournament selection were used. In contrast, we suggest that gradient descent should always be combined with tournament selection, which is not sensitive to the value of the learning rate. When gradient descent is used in combination with tournament selection, the results show that (i) the slowdown in learning is limited and (ii) the generalization capabilities of XCS are not affected.

REFERENCES

• 1: Alwyn M. Barry. Limits in long path learning with XCS. In Springer-Verlag, editor, Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1832--1843, Chicago, IL, 2003.
• 2: Alwyn M. Barry, John H. Holmes, and Xavier Llorà. Data mining using learning classifier systems. In Bull {5}, pages 15--67.
• 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: Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In G. Tesauro et al., editors, Advances in Neural Information Processing Systems 7, pages 369--376, 1995. The MIT Press.
• 5: Larry Bull, Applications of Learning Classifier Systems, SpringerVerlag, 2004
• 6: Martin Butz, David G. Goldberg, and Pier Luca Lanzi. Gradient descent methods in learning classifier systems. Technical Report 2003028, Illinois Genetic Algorithms Laboratory - University of Illinois at Urbana-Champaign, 117 Transportation Building, 104 S. Mathews Avenue, Urbana, IL 61801, January 2003.
• 7: Martin V. Butz. Rule-Based Evolutionary Online Learning Systems: A Principled Approach to LCS Analysis and Design. Springer-Verlag, Berlin, 2006
• 8: Martin V. Butz, David E. Goldberg, and Pier Luca Lanzi. Gradient descent methods in learning classifier systems: Improving XCS performance in multistep problems. IEEE Transaction on Evolutionary Computation, 9(5):452--473, October 2005.
• 9: Martin V. Butz , Kumara Sastry , David E. Goldberg, Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection, Genetic Programming and Evolvable Machines, v.6 n.1, p.53-77, March 2005 [doi>10.1007/s10710-005-7619-9]
• 10: Martin V. Butz and Stewart W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3-4):144--153, 2002.
• 11: Marco Dorigo. Genetic and non-genetic operators in alecsys. Evolutionary Computation, 1(2):151--164, 1993.
• 12: Jan Drugowitsch and Alwyn M. Barry. A formal framework and extensions for function approximation in learning classifier systems. Technical Report CSBU-2006-02, Department of Computer Science, University of Bath, January 2006.
• 13: Jan Drugowitsch and Alwyn M. Barry. A formal framework for reinforcement learning with function approximation in learning classifier systems. Technical Report CSBU-2006-02, Department of Computer Science, University of Bath, January 2006.
• 14: Geoffrey J. Gordon. Online fitted reinforcement learning from the value function approximation. Workshop on Value Function Approximation held during the 12th International Conference on Machine Learning, 1995.
• 15: Pier Luca Lanzi. An Analysis of Generalization in the XCS Classifier System. Evolutionary Computation Journal, 7(2):125--149, 1999.
• 16: Pier Luca Lanzi. Learning classifier systems from a reinforcement learning perspective. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 6(3):162--170, 2002
• 17: Pier Luca Lanzi , Daniele Loiacono, Standard and averaging reinforcement learning in XCS, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144241]
• 18: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Classifier prediction based on tile coding, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144242]
• 19: Pier Luca Lanzi, Wolfgang Stolzmann, and Stewart W. Wilson, editors. Learning Classifier Systems: From Foundations to Applications, volume 1813 of Lecture Notes in Computer Science. Springer-Verlag, April 2000.
• 20: Stuart Ian Reynolds. Reinforcement Learning with Exploration. PhD thesis, School of Computer Science. The University of Birmingham, Birmingham, B15 2TT, December 2002.
• 21: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 22: Atsushi Wada , Keiki Takadama , Katsunori Shimohara, Learning classifier system equivalent with reinforcement learning with function approximation, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102277]
• 23: Atsushi Wada, Keiki Takadama, Katsumori Shimohara, and Osamu Katai. Learning classifier systems with convergence and generalization. In Larry Bull and Tim Kovacs, editors, Foundations of Learning Classifier Systems, volume 183 of Studies in Fuzziness and Soft Computing, pages 285--304. Springer, 2005.
• 24: Stewart W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995. http://prediction-dynamics.com/.
• 25: Stewart W. Wilson. Generalization in the XCS classifier system. In Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674. Morgan Kaufmann, 1998.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
LCS, RL, XCS, generalization, gradient descent