Cited By
View all- Heider MPätzel DWagner AWagner M(2022)An overview of LCS research from 2021 to 2022Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533985(2086-2094)Online publication date: 9-Jul-2022
Convergence analysis of rule-generality on the XCS classifier system
Pages 332 - 339
Abstract
The XCS classifier system adaptively controls a rule-generality of a rule-condition through a rule-discovery process. However, there is no proof that the rule-generality can eventually converge to its optimum value even under some ideal assumptions. This paper conducts a convergence analysis of the rule-generality on the rule-discovery process with the ternary alphabet coding. Our analysis provides the first proof that an average rule-generality of rules in a population can converge to its optimum value under some assumptions. This proof can be used to mathematically conclude that the XCS framework has a natural pressure to explore rules toward optimum rules if XCS satisfies our derived conditions. In addition, our theoretical result returns a rough setting-up guideline for the maximum population size, the mutation rate, and the GA threshold, improving the convergence speed of the rule-generality and the XCS performance.
References
[1]
Isidro M Alvarez, Will N Browne, and Mengjie Zhang. 2014. Reusing learned functionality in XCS: code fragments with constructed functionality and constructed features. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation. 969--976.
[2]
Muhammad Hassan Arif, Muhammad Iqbal, and Jianxin Li. 2019. Extracting and reusing blocks of knowledge in learning classifier systems for text classification: a lifelong machine learning approach. Soft Computing (2019), 1--10.
[3]
Seok-Jun Bu and Sung-Bae Cho. 2020. A convolutional neural-based learning classifier system for detecting database intrusion via insider attack. Information Sciences 512 (2020), 123--136.
[4]
Martin V Butz, David E Goldberg, and Kurian Tharakunnel. 2003. Analysis and improvement of fitness exploitation in XCS: Bounding models, tournament selection, and bilateral accuracy. Evolutionary computation 11, 3 (2003), 239--277.
[5]
M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. 2004. Toward a theory of generalization and learning in XCS. IEEE Transactions on Evolutionary Computation 8, 1 (2004), 28--46.
[6]
Martin V. Butz and Stewart W. Wilson. 2002. An Algorithmic Description of XCS. Soft Computing 6, 3-4 (2002), 144--153.
[7]
J. H. Holland. 1986. Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based System. Machine Learning 2 (1986), 593--623.
[8]
Andreas Holzinger, Chris Biemann, Constantinos S Pattichis, and Douglas B Kell. 2017. What do we need to build explainable AI systems for the medical domain? arXiv preprint arXiv:1712.09923 (2017).
[9]
David Howard, Larry Bull, and Pier-Luca Lanzi. 2016. A cognitive architecture based on a learning classifier system with spiking classifiers. Neural Processing Letters 44, 1 (2016), 125--147.
[10]
Muhammad Iqbal, Will N Browne, and Mengjie Zhang. 2017. Extending xcs with cyclic graphs for scalability on complex boolean problems. Evolutionary computation 25, 2 (2017), 173--204.
[11]
Ji-Yoon Kim and Sung-Bae Cho. 2019. Exploiting deep convolutional neural networks for a neural-based learning classifier system. Neurocomputing 354 (2019), 61--70.
[12]
Tim Kovacs. 1996. 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.
[13]
Pier Luca Lanzi. 1999. An Analysis of Generalization in the Xcs Classifier System. Evol. Comput. 7, 2 (June 1999), 125--149.
[14]
Megan Liang, Gabrielle Palado, and Will N Browne. 2019. Identifying Simple Shapes to Classify the Big Picture. In 2019 International Conference on Image and Vision Computing New Zealand (IVCNZ). IEEE, 1--6.
[15]
Kazuma Matsumoto, Ryo Takano, Takato Tatsumi, Hiroyuki Sato, Tim Kovacs, and Keiki Takadama. 2018. XCSR based on compressed input by deep neural network for high dimensional data. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 1418--1425.
[16]
Kazuma Matsumoto, Takato Tatsumi, Hiroyuki Sato, Tim Kovacs, and Keiki Takadama. 2017. XCSR Learning from Compressed Data Acquired by Deep Neural Network. Journal of Advanced Computational Intelligence and Intelligent Informatics 21, 5 (2017), 856--867.
[17]
Masaya Nakata, Will Browne, and Tomoki Hamagami. 2018. Theoretical adaptation of multiple rule-generation in XCS. In Proceedings of the Genetic and Evolutionary Computation Conference. 482--489.
[18]
Masaya Nakata, Will Browne, Tomoki Hamagami, and Keiki Takadama. 2017. Theoretical XCS parameter settings of learning accurate classifiers. In Proceedings of the Genetic and Evolutionary Computation Conference. 473--480.
[19]
Masaya Nakata and Will Neil Browne. 2019. How XCS can prevent misdistinguishing rule accuracy: a preliminary study. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 183--184.
[20]
Masaya Nakata and Will N Browne. 2021. Learning Optimality Theory for Accuracy-based Learning Classifier Systems. IEEE Transactions on Evolutionary Computation 25, 1 (2021), 61--74.
[21]
David Pätzel and Jörg Hähner. 2018. An algebraic description of XCS. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. 1434--1441.
[22]
David Pätzel, Anthony Stein, and Jörg Hähner. 2019. A Survey of Formal Theoretical Advances Regarding XCS. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19). ACM, New York, NY, USA, 1295--1302.
[23]
David Pätzel, Anthony Stein, and Masaya Nakata. 2020. An Overview of LCS Research from IWLCS 2019 to 2020. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. 1782--1788.
[24]
Arun Rai. 2020. Explainable AI: From black box to glass box. Journal of the Academy of Marketing Science 48, 1 (2020), 137--141.
[25]
Wojciech Samek, Grégoire Montavon, Andrea Vedaldi, Lars Kai Hansen, and Klaus-Robert Müller. 2019. Explainable AI: interpreting, explaining and visualizing deep learning. Vol. 11700. Springer Nature.
[26]
Anthony Stein and Masaya Nakata. 2020. Learning classifier systems: from principles to modern systems. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. 561--589.
[27]
Masakazu Tadokoro, Satoshi Hasegawa, Takato Tatsumi, Hiroyuki Sato, and Keiki Takadama. 2019. Knowledge Extraction from XCSR Based on Dimensionality Reduction and Deep Generative Models. In 2019 IEEE Congress on Evolutionary Computation (CEC). IEEE, 1883--1890.
[28]
Stewart W. Wilson. 1995. Classifier Fitness Based on Accuracy. Evolutionary Computation 3, 2 (June 1995), 149--175.
Index Terms
- Convergence analysis of rule-generality on the XCS classifier system
Recommendations
Theoretical adaptation of multiple rule-generation in XCS
GECCO '18: Proceedings of the Genetic and Evolutionary Computation ConferenceMost versions of the XCS Classifier System have been designed to evolve only two rules for each rule discovery invocation, which restricts the search capacity. A difficulty behind generating multiple rules each time is the increase in the probability of ...
How XCS can prevent misdistinguishing rule accuracy: a preliminary study
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference CompanionOn the XCS classifier system, an ideal assumption in the latest XCS learning theory means that it is impossible for XCS to distinguish accurate rules from any other rules with 100% success rate in practical use. This paper presents a preliminary work to ...
Theoretical XCS parameter settings of learning accurate classifiers
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceXCS is the most popular type of Learning Classifier System, but setting optimum parameter values is more of an art than a science. Early theoretical work required the impractical assumption that classifier parameters had fully converged with infinite ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2021
1219 pages
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 June 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '21
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 99Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025
Other Metrics
Citations
Cited By
View all- Heider MPätzel DWagner AWagner M(2022)An overview of LCS research from 2021 to 2022Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533985(2086-2094)Online publication date: 9-Jul-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in