An Analysis of Rule Deletion Scheme in XCS on Reinforcement Learning Problem

Masaya Nakata; Tomoki Hamagami

doi:10.20965/jaciii.2017.p0876

single-jc.php

« previous

JACIII Vol.21 No.5 pp. 876-884

doi: 10.20965/jaciii.2017.p0876

(2017)

Paper:

Views over last 60 days: 973

An Analysis of Rule Deletion Scheme in XCS on Reinforcement Learning Problem

Masaya Nakata and Tomoki Hamagami

Yokohama National University
79-5 Tokiwadai, Hodogaya, Yokohama, Japan

Received:

April 1, 2017

Accepted:

July 21, 2017

Published:

September 20, 2017

Keywords:

learning classifier system, evolutionary reinforcement learning, deletion scheme

Abstract

The XCS classifier system is an evolutionary rule-based learning technique powered by a Q-learning like learning mechanism. It employs a global deletion scheme to delete rules from all rules covering all state-action pairs. However, the optimality of this scheme remains unclear owing to the lack of intensive analysis. We here introduce two deletion schemes: 1) local deletion, which can be applied to a subset of rules covering each state (a match set), and 2) stronger local deletion, which can be applied to a more specific subset covering each state-action pair (an action set). The aim of this paper is to reveal how the above three deletion schemes affect the performance of XCS. Our analysis shows that the local deletion schemes promote the elimination of inaccurate rules compared with the global deletion scheme. However, the stronger local deletion scheme occasionally deletes a good rule. We further show that the two local deletion schemes greatly improve the performance of XCS on a set of noisy maze problems. Although the localization strength of the proposed deletion schemes may require consideration, they can be adequate for XCS rather than the original global deletion scheme.

Cite this article as:

M. Nakata and T. Hamagami, “An Analysis of Rule Deletion Scheme in XCS on Reinforcement Learning Problem,” J. Adv. Comput. Intell. Intell. Inform., Vol.21 No.5, pp. 876-884, 2017.

Data files:

References

[1] J. H. Holland, “Escaping Brittleness: The Possibilities of General Purpose Learning Algorithms Applied to Parallel Rule-based System,” Machine Learning, Vol.2, pp. 593-623, 1986.
[2] R. S. Sutton and A. G. Barto, “Reinforcement Learning . An Introduction,” MIT Press, 1998.
[3] P. L. Lanzi, “Learning classifier systems: then and now,” Evolutionary Intelligence, Vol.1, pp. 63-82, 2008.
[4] L. Bull, E. Bernadó-Mansilla, and J. H. Holmes (Eds.), “Learning Classifier Systems in Data Mining,” Studies in Computational Intelligence, Vol.125, Springer, 2008.
[5] J. Hurst and L. Bull, “A Self-Adaptive XCS,” Advances in Learning Classifier Systems, Lecture Notes in Computer Science, Vol.2321, pp. 57-73, Springer Berlin Heidelberg, 2002.
[6] S. W. Wilson, “Classifier Fitness Based on Accuracy,” Evolutionary Computation, Vol.3, No.2, pp. 149-175, June 1995.
[7] T. Kovacs, “Evolving Optimal Populations with XCS Classifier Systems,” Technical Report CSR-96-17 and CSRP-96-17, School of Computer Science, University of Birmingham, Birmingham, U.K., 1996.
[8] P. L. Lanzi, “An Analysis of Generalization in the Xcs Classifier System,” Evol. Comput., Vol.7, No.2, pp. 125-149, June 1999.
[9] M. Iqbal, W. Browne, and M. Zhang, “Reusing Building Blocks of Extracted Knowledge to Solve Complex, Large-Scale Boolean Problems,” Evolutionary Computation, IEEE Trans. on, Vol.18, No.4, pp. 465-480, Aug 2014.
[10] M. Iqbal, S. S. Naqvi, W. Browne, C. Hollitt, and M. Zhang, “Salient Object Detection Using Learning Classifiersystems That Compute Action Mappings,” GECCO 2014, pp. 525-532, ACM, 2014.
[11] M. Iqbal, W. Browne, and M. Zhang, “Extending Learning Classifier System with Cyclic Graphs for Scalability on Complex, Largescale Boolean Problems,” GECCO’13, pp. 1045-1052, New York, NY, USA, ACM, 2013.
[12] M. Nakata, T. Kovacs, and K. Takadama, “A Modified XCS Classifier System for Sequence Labeling,” Proc. of the 2014 Conf. on Genetic and Evolutionary Computation, GECCO’14, pp. 565-572, ACM, 2014.
[13] M. Nakata, W. Browne, T. Hamagami, and K. Takadama, “Theoretical XCS parameter settings of learning accurate classifiers,” GECCO’17, pp. 473-480, ACM, 2017.
[14] R. J. Urbanowicz and J. H. Moore, “Learning Classifier Systems: A Complete Introduction, Review, and Roadmap,” J. Artif. Evol. App., Vol.2009, January 2009.
[15] M. V. Butz, ”Rule-Based Evolutionary Online Learning Systems,” Springer, 2006.
[16] F. Kharbat, L. Bull, and M. Odeh, “Revisiting genetic selection in the XCS learning classifier system,” The 2005 IEEE Congress on Evolutionary Computation 2005, Vol.3, Sept 2005.
[17] M. V. Butz, D. E. Goldberg, and K. Tharakunnel, “Analysis and Improvement of Fitness Exploitation in XCS: Bounding Models, Tournament Selection, and Bilateral Accuracy,” Evolutionary Computation, Vol.11, No.3, pp. 239-277, 2003.
[18] M. V. Butz and S. W. Wilson, “An Algorithmic Description of XCS,” Soft Computing, Vol.6, No.3.4, pp. 144-153, 2002.
[19] M. V. Butz, D. E. Goldberg, and P. L. Lanzi, “Gradient Descent Methods in Learning Classifier Systems: Improving XCS Performance in Multistep Problems,” IEEE Trans. on Evolutionary Computation, Vol.9, No.5, pp. 452-473, October 2005.
[20] A. Wada, K. Takadama, K. Shimohara, and O. Katai, “Learning classifier system with convergence and generalization,” Foundations of Learning Classifier Systems, pp. 285-304, Springer, 2005.
[21] E. Bernadó-mansilla and J. M.Garrell-Guij, “Accuracy-based Learning Classifier Systems: Models, Analysis and Applications to Classification Tasks,” Evolutionary Computation, Vol.11, pp. 209-238, 2003.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] J. H. Holland, “Escaping Brittleness: The Possibilities of General Purpose Learning Algorithms Applied to Parallel Rule-based System,” Machine Learning, Vol.2, pp. 593-623, 1986.

[2] [2] R. S. Sutton and A. G. Barto, “Reinforcement Learning . An Introduction,” MIT Press, 1998.

[3] [3] P. L. Lanzi, “Learning classifier systems: then and now,” Evolutionary Intelligence, Vol.1, pp. 63-82, 2008.

[4] [4] L. Bull, E. Bernadó-Mansilla, and J. H. Holmes (Eds.), “Learning Classifier Systems in Data Mining,” Studies in Computational Intelligence, Vol.125, Springer, 2008.

[5] [5] J. Hurst and L. Bull, “A Self-Adaptive XCS,” Advances in Learning Classifier Systems, Lecture Notes in Computer Science, Vol.2321, pp. 57-73, Springer Berlin Heidelberg, 2002.

[6] [6] S. W. Wilson, “Classifier Fitness Based on Accuracy,” Evolutionary Computation, Vol.3, No.2, pp. 149-175, June 1995.

[7] [7] T. Kovacs, “Evolving Optimal Populations with XCS Classifier Systems,” Technical Report CSR-96-17 and CSRP-96-17, School of Computer Science, University of Birmingham, Birmingham, U.K., 1996.

[8] [8] P. L. Lanzi, “An Analysis of Generalization in the Xcs Classifier System,” Evol. Comput., Vol.7, No.2, pp. 125-149, June 1999.

[9] [9] M. Iqbal, W. Browne, and M. Zhang, “Reusing Building Blocks of Extracted Knowledge to Solve Complex, Large-Scale Boolean Problems,” Evolutionary Computation, IEEE Trans. on, Vol.18, No.4, pp. 465-480, Aug 2014.

[10] [10] M. Iqbal, S. S. Naqvi, W. Browne, C. Hollitt, and M. Zhang, “Salient Object Detection Using Learning Classifiersystems That Compute Action Mappings,” GECCO 2014, pp. 525-532, ACM, 2014.

[11] [11] M. Iqbal, W. Browne, and M. Zhang, “Extending Learning Classifier System with Cyclic Graphs for Scalability on Complex, Largescale Boolean Problems,” GECCO’13, pp. 1045-1052, New York, NY, USA, ACM, 2013.

[12] [12] M. Nakata, T. Kovacs, and K. Takadama, “A Modified XCS Classifier System for Sequence Labeling,” Proc. of the 2014 Conf. on Genetic and Evolutionary Computation, GECCO’14, pp. 565-572, ACM, 2014.

[13] [13] M. Nakata, W. Browne, T. Hamagami, and K. Takadama, “Theoretical XCS parameter settings of learning accurate classifiers,” GECCO’17, pp. 473-480, ACM, 2017.

[14] [14] R. J. Urbanowicz and J. H. Moore, “Learning Classifier Systems: A Complete Introduction, Review, and Roadmap,” J. Artif. Evol. App., Vol.2009, January 2009.

[15] [15] M. V. Butz, ”Rule-Based Evolutionary Online Learning Systems,” Springer, 2006.

[16] [16] F. Kharbat, L. Bull, and M. Odeh, “Revisiting genetic selection in the XCS learning classifier system,” The 2005 IEEE Congress on Evolutionary Computation 2005, Vol.3, Sept 2005.

[17] [17] M. V. Butz, D. E. Goldberg, and K. Tharakunnel, “Analysis and Improvement of Fitness Exploitation in XCS: Bounding Models, Tournament Selection, and Bilateral Accuracy,” Evolutionary Computation, Vol.11, No.3, pp. 239-277, 2003.

[18] [18] M. V. Butz and S. W. Wilson, “An Algorithmic Description of XCS,” Soft Computing, Vol.6, No.3.4, pp. 144-153, 2002.

[19] [19] M. V. Butz, D. E. Goldberg, and P. L. Lanzi, “Gradient Descent Methods in Learning Classifier Systems: Improving XCS Performance in Multistep Problems,” IEEE Trans. on Evolutionary Computation, Vol.9, No.5, pp. 452-473, October 2005.

[20] [20] A. Wada, K. Takadama, K. Shimohara, and O. Katai, “Learning classifier system with convergence and generalization,” Foundations of Learning Classifier Systems, pp. 285-304, Springer, 2005.

[21] [21] E. Bernadó-mansilla and J. M.Garrell-Guij, “Accuracy-based Learning Classifier Systems: Models, Analysis and Applications to Classification Tasks,” Evolutionary Computation, Vol.11, pp. 209-238, 2003.