research-article

Theoretical XCS parameter settings of learning accurate classifiers

Authors:

Masaya Nakata,

Will Browne,

Tomoki Hamagami,

Keiki TakadamaAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 473 - 480

https://doi.org/10.1145/3071178.3071200

Published: 01 July 2017 Publication History

Get Access

Abstract

XCS 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 update times. The aim of this work is to derive a theoretical condition to mathematically guarantee that XCS identifies maximally accurate classifiers, such that subsequent deletion methods can be used optimally, in as few updates as possible. Consequently, our theory provides a universally usable setup guide for three important parameter settings; the learning rate, the accuracy update and the threshold for subsumption deletion. XCS with our best parameter settings solves the 70-bit multiplexer problem with only 21% of instances that the standard XCS setup needs. On a highly class-imbalanced multiplexer problem with inaccurate classifiers having more than 99.99% classification accuracy, our theory enables XCS to identify only 100% accurate classifiers as accurate and thus obtain the optimal performance.

Supplementary Material

ZIP File (p473-nakata.zip)

Supplemental material.

Download
123.67 KB

References

[1]

M. V. Butz. XCSJava 1.0: An Implementation of the XCS classifier system in Java. Tec. report, 2000.

Google Scholar

[2]

M. V. Butz. Rule-Based Evolutionary Online Learning Systems. Springer, 2006.

Google Scholar

[3]

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, 11(3):239--277, 2003.

Digital Library

Google Scholar

[4]

M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a Theory of Generalization and Learning in XCS. IEEE Trans. on Evo. Comp., 8(1):28--46, 2004.

Digital Library

Google Scholar

[5]

M. V. Butz and S. W. Wilson. An Algorithmic Description of XCS. Soft Computing, 6(3--4):144--153, 2002.

Google Scholar

[6]

J. Drugowitsch. Design and analysis of learning classifier systems. Sringer, Berlin, 2008.

Digital Library

Google Scholar

[7]

J. H. Holland. Escaping Brittleness: The Possibilities of General Purpose Learning Algorithms Applied to Parallel Rule-based system. Machine Learning, 2:593--623, 1986.

Google Scholar

[8]

M. Iqbal, W. Browne, and M. Zhang. Extending learning classifier system with cyclic graphs for scalability on complex, large-scale boolean problems, pages 1045--1052, New York, NY, USA, 2013. ACM.

Digital Library

Google Scholar

[9]

M. Iqbal, W. Browne, and M. Zhang. Reusing Building Blocks of Extracted Knowledge to Solve Complex, Large-Scale Boolean Problems. Evolutionary Computation, IEEE Transactions on, 18(4):465--480, 2014.

Google Scholar

[10]

M. Iqbal, S. S. Naqvi, W. Browne, C. Hollitt, and M. Zhang. Salient Object Detection Using Learning Classifiersystems That Compute Action Mappings. In GECCO2014, pages 525--532. ACM, 2014.

Digital Library

Google Scholar

[11]

T. Nguyen, S. Foitong, P. Srinil, and O. Pinngern. Towards Adapting XCS for Imbalance Problems. In PRICAI 2008, volume 5351 of LNCS, pages 1028--1033. Springer, 2008.

Digital Library

Google Scholar

[12]

A. Orriols-Puig and E. Bernadó-Mansilla. Bounding XCS's parameters for unbalanced datasets. In GECCO2006, pages 1561--1568. ACM, 2006.

Digital Library

Google Scholar

[13]

B. Widrow and M. E. Hoff. Adaptive Switching Circuits. 1960 IRE Western Electric Show and Convention Record 4, pages 96--104, 1960.

Google Scholar

[14]

S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, June 1995.

Digital Library

Google Scholar

Cited By

View all

Surhonne AWensauer MMaurer FWild THerkersdorf ALi XHandl J(2024)XCS with dynamic sized experience replay for memory constrained applicationsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664148(1807-1814)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664148
Albahri AHamid RAbdulnabi AAlbahri OAlamoodi ADeveci MPedrycz WAlzubaidi LSantamaría JGu Y(2024)Fuzzy decision-making framework for explainable golden multi-machine learning models for real-time adversarial attack detection in Vehicular Ad-hoc NetworksInformation Fusion10.1016/j.inffus.2023.102208105:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.inffus.2023.102208
Yatsu NShiraishi HSato HTakadama KSilva SPaquete L(2023)Exploring High-dimensional Rules Indirectly via Latent Space Through a Dimensionality Reduction for XCSProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590439(606-614)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590439
Show More Cited By

Index Terms

Theoretical XCS parameter settings of learning accurate classifiers
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Classification and regression trees
      2. Rule learning

Recommendations

Theoretical adaptation of multiple rule-generation in XCS
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Most 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 ...
Self-adaptation of XCS learning parameters based on learning theory
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

This paper proposes a self-adaptation technique of parameter settings used in the XCS learning scheme. Since we adaptively set those settings to their optimum values derived by the recent XCS learning theory, our proposal does not require any trial and ...
How XCS can prevent misdistinguishing rule accuracy: a preliminary study
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

On 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
235
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Surhonne AWensauer MMaurer FWild THerkersdorf ALi XHandl J(2024)XCS with dynamic sized experience replay for memory constrained applicationsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664148(1807-1814)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664148
Albahri AHamid RAbdulnabi AAlbahri OAlamoodi ADeveci MPedrycz WAlzubaidi LSantamaría JGu Y(2024)Fuzzy decision-making framework for explainable golden multi-machine learning models for real-time adversarial attack detection in Vehicular Ad-hoc NetworksInformation Fusion10.1016/j.inffus.2023.102208105:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.inffus.2023.102208
Yatsu NShiraishi HSato HTakadama KSilva SPaquete L(2023)Exploring High-dimensional Rules Indirectly via Latent Space Through a Dimensionality Reduction for XCSProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590439(606-614)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590439
Albahri AJoudar SHamid RZahid IAlqaysi MAlbahri OAlamoodi AKou GSharaf I(2023)Explainable Artificial Intelligence Multimodal of Autism Triage Levels Using Fuzzy Approach-Based Multi-criteria Decision-Making and LIMEInternational Journal of Fuzzy Systems10.1007/s40815-023-01597-926:1(274-303)Online publication date: 17-Nov-2023
https://doi.org/10.1007/s40815-023-01597-9
Albahri AZaidan AAlSattar HHamid RAlbahri OQahtan SAlamoodi A(2022) Towards physician's experience: Development of machine learning model for the diagnosis of autism spectrum disorders based on complex T ‐spherical fuzzy‐weighted zero‐inconsistency method Computational Intelligence10.1111/coin.1256239:2(225-257)Online publication date: 5-Dec-2022
https://doi.org/10.1111/coin.12562
Sugawara RNakata M(2022)Theoretical Analysis of Accuracy-Based Fitness on Learning Classifier SystemsIEEE Access10.1109/ACCESS.2022.318361810(64862-64872)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3183618
Albahri AHamid RZaidan AAlbahri O(2022)Early automated prediction model for the diagnosis and detection of children with autism spectrum disorders based on effective sociodemographic and family characteristic featuresNeural Computing and Applications10.1007/s00521-022-07822-035:1(921-947)Online publication date: 24-Sep-2022
https://doi.org/10.1007/s00521-022-07822-0
Heider MPätzel DStegherr HHähner J(2022)A Metaheuristic Perspective on Learning Classifier SystemsMetaheuristics for Machine Learning10.1007/978-981-19-3888-7_3(73-98)Online publication date: 13-Aug-2022
https://doi.org/10.1007/978-981-19-3888-7_3
Hamasaki KNakata M(2022)Minimum Rule-Repair Algorithm for Supervised Learning Classifier Systems on Real-Valued Classification TasksMetaheuristics and Nature Inspired Computing10.1007/978-3-030-94216-8_11(137-151)Online publication date: 21-Feb-2022
https://doi.org/10.1007/978-3-030-94216-8_11
Stein ANakata MKrawiec K(2021)Learning classifier systemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461414(498-527)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461414
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Theoretical adaptation of multiple rule-generation in XCS

Self-adaptation of XCS learning parameters based on learning theory

How XCS can prevent misdistinguishing rule accuracy: a preliminary study