Learning classifier system: Difference between revisions

Revision as of 18:04, 15 February 2017

Latest revision as of 08:35, 11 August 2025

(48 intermediate revisions by 33 users not shown)

Line 1:

{{short description|Paradigm of rule-based machine learning methods}}

[[File:Function approximation with LCS rules.jpg|thumb|2D visualization of LCS rules learning to approximate a 3D function. Each blue ellipse represents an individual rule covering part of the solution space. (Adapted from images taken from XCSF<ref name=":9">{{Cite journal|lastlast1=Stalph|firstfirst1=Patrick O.|last2=Butz|first2=Martin V.|date=2010-02-01|title=JavaXCSF: The XCSF Learning Classifier System in Java|url=http://doi.acm.org/10.1145/1731888.1731890|journal=ACM SIGEVOlution|volume=4|issue=3|pages=16–19|doi=10.1145/1731888.1731890|s2cid=16861908|issn=1931-8499}}</ref> with permission from Martin Butz)]]

'''Learning classifier systems''', or '''LCS''', are a paradigm of [[rule-based machine learning]] methods that combine a discovery component (e.g. typically a [[genetic algorithm]] in [[evolutionary computation]]) with a learning component (performing either [[supervised learning]], [[reinforcement learning]], or [[unsupervised learning]]).<ref name=":1">{{Cite journal|lastlast1=Urbanowicz|firstfirst1=Ryan J.|last2=Moore|first2=Jason H.|date=2009-09-22|title=Learning Classifier Systems: A Complete Introduction, Review, and Roadmap|url=http://www.hindawi.com/archive/2009/736398/|journal=Journal of Artificial Evolution and Applications|language=en|volume=2009|pages=1–25|doi=10.1155/2009/736398|issn=1687-6229|doi-access=free}}</ref> Learning classifier systems seek to identify a set of context-dependent rules that collectively store and apply knowledge in a [[piecewise]] manner in order to make predictions (e.g. [[behavior modeling]],<ref>{{Cite journal|last=Dorigo|first=Marco|title=Alecsys and the AutonoMouse: Learning to control a real robot by distributed classifier systems|url=http://link.springer.com/article/10.1007/BF00996270|journal=Machine Learning|language=en|volume=19|issue=3|pages=209–240|doi=10.1007/BF00996270|issn=0885-6125|year=1995|doi-access=free}}</ref> [[Statistical classification|classification]],<ref>{{Cite journal|lastlast1=Bernadó-Mansilla|firstfirst1=Ester|last2=Garrell-Guiu|first2=Josep M.|date=2003-09-01|title=Accuracy-Based Learning Classifier Systems: Models, Analysis and Applications to Classification Tasks|url=http://dx.doi.org/10.1162/106365603322365289|journal=Evolutionary Computation|volume=11|issue=3|pages=209–238|doi=10.1162/106365603322365289|pmid=14558911|s2cid=9086149|issn=1063-6560}}</ref><ref name=":0">{{Cite journal|lastlast1=Urbanowicz|firstfirst1=Ryan J.|last2=Moore|first2=Jason H.|date=2015-04-03|title=ExSTraCS 2.0: description and evaluation of a scalable learning classifier system|url=http://link.springer.com/article/10.1007/s12065-015-0128-8|journal=Evolutionary Intelligence|language=en|volume=8|issue=2-32–3|pages=89–116|doi=10.1007/s12065-015-0128-8|issn=1864-5909|pmc=4583133|pmid=26417393}}</ref> [[data mining]],<ref name=":0" /><ref>{{Cite book|url=http://link.springer.com/chapter/10.1007/3-540-48104-4_8|title=Advances in Learning Classifier Systems|lasturl=https://archive.org/details/advanceslearning00lanz|url-access=limited|last1=Bernadó|firstfirst1=Ester|last2=Llorà|first2=Xavier|last3=Garrell|first3=Josep M.|chapter=XCS and GALE: A Comparative Study of Two Learning Classifier Systems on Data Mining |date=2001-07-07|publisher=Springer Berlin Heidelberg|isbn=9783540437932|editor-last=Lanzi|editor-first=Pier Luca|series=Lecture Notes in Computer Science|volume=2321 |pages=115–132[https://archive.org/details/advanceslearning00lanz/page/n120 115]–132|language=en|doi=10.1007/3-540-48104-4_8|editor-last2=Stolzmann|editor-first2=Wolfgang|editor-last3=Wilson|editor-first3=Stewart W.}}</ref><ref>{{Cite book|title=Learning Classifier Systems|url=httphttps://linkarchive.springer.comorg/chapterdetails/10.1007/978-3-540-71231-2_19learningclassifi00kova_690|titleurl-access=Learning Classifier Systemslimited|lastlast1=Bacardit|firstfirst1=Jaume|last2=Butz|first2=Martin V.|chapter=Data Mining in Learning Classifier Systems: Comparing XCS with GAssist |date=2007-01-01|publisher=Springer Berlin Heidelberg|isbn=9783540712305|editor-last=Kovacs|editor-first=Tim|series=Lecture Notes in Computer Science|volume=4399 |pages=282–290[https://archive.org/details/learningclassifi00kova_690/page/n291 282]–290|language=en|doi=10.1007/978-3-540-71231-2_19|editor-last2=Llorà|editor-first2=Xavier|editor-last3=Takadama|editor-first3=Keiki|editor-last4=Lanzi|editor-first4=Pier Luca|editor-last5=Stolzmann|editor-first5=Wolfgang|editor-last6=Wilson|editor-first6=Stewart W.|citeseerx = 10.1.1.553.4679}}</ref> [[Regression analysis|regression]],<ref>{{Cite journalbook|lastlast1=Urbanowicz|firstfirst1=Ryan|last2=Ramanand|first2=Niranjan|last3=Moore|first3=Jason|date=2015-01-01|title=Continuous Endpoint Data Mining with ExSTraCS: A Supervised Learning Classifier System|url=http://doi.acm.org/10.1145/2739482.2768453|journal=Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation |chapter=Continuous Endpoint Data Mining with ExSTraCS |date=2015-01-01|series=GECCO Companion '15|___location=New York, NY, USA|publisher=ACM|pages=1029–1036|doi=10.1145/2739482.2768453|isbn=9781450334884|s2cid=11908241}}</ref> [[function approximation]],<ref>{{Cite journal|lastlast1=Butz|firstfirst1=M. V.|last2=Lanzi|first2=P. L.|last3=Wilson|first3=S. W.|date=2008-06-01|title=Function Approximation With XCS: Hyperellipsoidal Conditions, Recursive Least Squares, and Compaction|url=http://ieeexplore.ieee.org/document/4380293/|journal=IEEE Transactions on Evolutionary Computation|volume=12|issue=3|pages=355–376|doi=10.1109/TEVC.2007.903551|s2cid=8861046|issn=1089-778X}}</ref> or [[Strategy (game theory)|game strategy]]). This approach allows complex [[Feasible region|solution spaces]] to be broken up into smaller, simpler parts for the reinforcement learning that is inside artificial intelligence research.

The founding concepts behind learning classifier systems came from attempts to model [[complex adaptive system]]s, using rule-based agents to form an artificial cognitive system (i.e. [[artificial intelligence]]).

== Methodology ==

The architecture and components of a given learning classifier system can be quite variable. It is useful to think of an LCS as a machine consisting of several interacting components. Components may be added or removed, or existing components modified/exchanged to suit the demands of a given problem ___domain (like algorithmic building blocks) or to make the algorithm flexible enough to function in many different problem domains. As a result, the LCS paradigm can be flexibly applied to many problem domains that call for [[machine learning]]. The major divisions among LCS implementations are as follows: (1) Michigan-style architecture vs. Pittsburgh-style architecture,<ref>[http://ryanurbanowicz.com/wp-content/uploads/2016/09/Urbanowicz_Browne_2015_Introducing-Rule-Based-Machine-Learning-A-Practical-Guide-GECCO15-CRC-Copy.pdf Introducing Rule-Based Machine Learning: A Practical Guide], Ryan J. Urbanowicz and Will Browne, see pp. 72-73 for Michigan-style architecture vs. Pittsburgh-style architecture.</ref> (2) [[reinforcement learning]] vs. [[supervised learning]], (3) incremental learning vs. batch learning, (4) [[Online machine learning|online learning]] vs. [[offline learning]], (5) strength-based fitness vs. accuracy-based fitness, and (6) complete action mapping vs best action mapping. These divisions are not necessarily mutually exclusive. For example, XCS,<ref name=":10" /> the best known and best studied LCS algorithm, is Michigan-style, was designed for reinforcement learning but can also perform supervised learning, applies incremental learning that can be either online or offline, applies accuracy-based fitness, and seeks to generate a complete action mapping.

=== Elements of a generic LCS algorithm ===

[[File:Generic Michigan-style Supervised LCS Schematic.png|thumb|A step-wise schematic illustrating a generic Michigan-style learning classifier system learning cycle performing supervised learning.]]

Keeping in mind that LCS is a paradigm for genetic-based machine learning rather than a specific method, the following outlines key elements of a generic, modern (i.e. post-XCS) LCS algorithm. For simplicity let us focus on Michigan-style architecture with supervised learning. See the illustrations on the right laying out the sequential steps involved in this type of generic LCS.

==== Environment ====

The environment is the source of data upon which an LCS learns. It can be an offline, finite [[Training data set|training dataset]] (characteristic of a [[data mining]], [[Statistical classification|classification]], or regression problem), or an online sequential stream of live training instances. Each training instance is assumed to include some number of ''features'' (also referred to as ''attributes'', or [[Dependent and independent variables|''independent variables'']]), and a single ''endpoint'' of interest (also referred to as the [[Class (set theory)|class]], ''action'', ''[[phenotype]]'', ''prediction'', or [[Dependent and independent variables|''dependent variable'']]). Part of LCS learning can involve [[feature selection]], therefore not all of the features in the training data need to be informative. The set of feature values of an instance is commonly referred to as the ''state''. For simplicity let's assume an example problem ___domain with [[Boolean data type|Boolean]]/[[Binary number|binary]] features and a [[Boolean data type|Boolean]]/[[Binary number|binary]] class. For Michigan-style systems, one instance from the environment is trained on each learning cycle (i.e. incremental learning). Pittsburgh-style systems perform batch learning, where rule- sets are evaluated in each iteration over much or all of the training data.

==== Rule/classifier/population ====

A rule is a context dependent relationship between state values and some prediction. Rules typically take the form of an {IF:THEN} expression, (e.g. {''IF 'condition' THEN 'action'},'' or as a more specific example, ''{IF 'red' AND 'octagon' THEN 'stop-sign'}''). A critical concept in LCS and rule-based machine learning alike, is that an individual rule is not in itself a model, since the rule is only applicable when its condition is satisfied. Think of a rule as a "local-model" of the solution space.

Rules can be represented in many different ways to handle different data types (e.g. binary, discrete-valued, ordinal, continuous-valued). Given binary data LCS traditionally applies a ternary rule representation (i.e. rules can include either a 0, 1, or '#' for each feature in the data). The 'don't care' symbol (i.e. '#') serves as a wild card within a rule's condition allowing rules, and the system as a whole to generalize relationships between features and the target endpoint to be predicted. Consider the following rule (#1###0 ~ 1) (i.e. condition ~ action). This rule can be interpreted as: IF the second feature = 1 AND the sixth feature = 0 THEN the class prediction = 1. We would say that the second and sixth features were specified in this rule, while the others were generalized. This rule, and the corresponding prediction are only applicable to an instance when the condition of the rule is satisfied by the instance. This is more commonly referred to as matching. In Michigan-style LCS, each rule has its own fitness, as well as a number of other rule-parameters associated with it that can describe the number of copies of that rule that exist (i.e. the ''numerosity''), the age of the rule, its accuracy, or the accuracy of its reward predictions, and other descriptive or experiential statistics. A rule along with its parameters is often referred to as a ''classifier''. In Michigan-style systems, classifiers are contained within a ''population'' [P] that has a user defined maximum number of classifiers. Unlike most [[stochastic]] search algorithms (e.g. [[evolutionary algorithm]]s), LCS populations start out empty (i.e. there is no need to randomly initialize a rule population). Classifiers will instead be initially introduced to the population with a covering mechanism.

In any LCS, the trained model is a set of rules/classifiers, rather than any single rule/classifier. In Michigan-style LCS, the entire trained (and optionally, compacted) classifier population forms the prediction model.

==== Matching ====

One of the most critical and often time -consuming elements of an LCS is the matching process. The first step in an LCS learning cycle takes a single training instance from the environment and passes it to [P] where matching takes place. In step two, every rule in [P] is now compared to the training instance to see which rules match (i.e. are contextually relevant to the current instance). In step three, any matching rules are moved to a ''match set'' [M]. A rule matches a training instance if all feature values specified in the rule condition are equivalent to the corresponding feature value in the training instance. For example, assuming the training instance is (001001 ~ 0), these rules would match: (###0## ~ 0), (00###1 ~ 0), (#01001 ~ 1), but these rules would not (1##### ~ 0), (000##1 ~ 0), (#0#1#0 ~ 1). Notice that in matching, the endpoint/action specified by the rule is not taken into consideration. As a result, the match set may contain classifiers that propose conflicting actions. In the fourth step, since we are performing supervised learning, [M] is divided into a correct set [C] and an incorrect set [I]. A matching rule goes into the correct set if it proposes the correct action (based on the known action of the training instance), otherwise it goes into [I]. In reinforcement learning LCS, an action set [A] would be formed here instead, since the correct action is not known.

==== Covering ====

At this point in the learning cycle, if no classifiers made it into either [M] or [C] (as would be the case when the population starts off empty), the covering mechanism is applied (fifth step). Covering is a form of ''online smart population initialization''. Covering randomly generates a rule that matches the current training instance (and in the case of supervised learning, that rule is also generated with the correct action. Assuming the training instance is (001001 ~ 0), covering might generate any of the following rules: (#0#0## ~ 0), (001001 ~ 0), (#010## ~ 0). Covering not only ensures that each learning cycle there is at least one correct, matching rule in [C], but that any rule initialized into the population will match at least one training instance. This prevents LCS from exploring the search space of rules that do not match any training instances.

==== Parameter updates/credit assignment/learning ====

In the sixth step, the rule parameters of any rule in [M] are updated to reflect the new experience gained from the current training instance. Depending on the LCS algorithm, a number of updates can take place at this step. For supervised learning, we can simply update the accuracy/error of a rule. Rule accuracy/error is different than model accuracy/error, since it is not calculated over the entire training data, but only over all instances that it matched. Rule accuracy is calculated by dividing the number of times the rule was in a correct set [C] by the number of times it was in ana match set [M]. Rule accuracy can be thought of as a 'local accuracy'. Rule fitness is also updated here, and is commonly calculated as a function of rule accuracy. The concept of fitness is taken directly from classic [[genetic algorithm]]s. Be aware that there are many variations on how LCS updates parameters in order to perform credit assignment and learning.

==== Subsumption ====

In the seventh step, a ''subsumption'' mechanism is typically applied. Subsumption is an explicit generalization mechanism that merges classifiers that cover redundant parts of the problem space. The subsuming classifier effectively absorbs the subsumed classifier (and has its numerosity increased). This can only happen when the subsuming classifier is more general, just as accurate, and covers all of the problem space of the classifier it subsumes.

==== Rule discovery/genetic algorithm ====

In the eighth step, LCS adopts a highly elitist [[genetic algorithm]] (GA) which will select two parent classifiers based on fitness (survival of the fittest). Parents are selected from [C] typically using [[tournament selection]]. Some systems have applied [[roulette wheel selection]] or deterministic selection, and have differently selected parent rules from either [P] - panmictic selection, or from [M]). [[Crossover (genetic algorithm)|Crossover]] and [[Mutation (genetic algorithm)|mutation]] operators are now applied to generate two new offspring rules. At this point, both the parent and offspring rules are returned to [P]. The LCS [[genetic algorithm]] is highly elitist since each learning iteration, the vast majority of the population is preserved. Rule discovery may alternatively be performed by some other method, such as an [[estimation of distribution algorithm]], but a GA is by far the most common approach. Evolutionary algorithms like the GA employ a stochastic search, which makes LCS a stochastic algorithm. LCS seeks to cleverly explore the search space, but does not perform an exhaustive search of rule combinations, and is not guaranteed to converge on an optimal solution.

==== Deletion ====

The last step in a generic LCS learning cycle is to maintain the maximum population size. The deletion mechanism will select classifiers for deletion (commonly using roulette wheel selection). The probability of a classifier being selected for deletion is inversely proportional to its fitness. When a classifier is selected for deletion, its numerosity parameter is reduced by one. When the numerosity of a classifier is reduced to zero, it is removed entirely from the population.

==== Training ====

LCS will cycle through these steps repeatedly for some user defined number of training iterations, or until some user defined termination criteria have been met. For online learning, LCS will obtain a completely new training instance each iteration from the environment. For offline learning, LCS will iterate through a finite training dataset. Once it reaches the last instance in the dataset, it will go back to the first instance and cycle through the dataset again.

==== Rule compaction ====

Once training is complete, the rule population will inevitably contain some poor, redundant and inexperienced rules. It is common to apply a ''rule compaction'', or ''condensation'' heuristic as a post-processing step. This resulting compacted rule population is ready to be applied as a prediction model (e.g. make predictions on testing instances), and/or to be interpreted for [[knowledge discovery]].

==== Prediction ====

Whether or not rule compaction has been applied, the output of an LCS algorithm is a population of classifiers which can be applied to making predictions on previously unseen instances. The prediction mechanism is not part of the supervised LCS learning cycle itself, however it would play an important role in a reinforcement learning LCS learning cycle. For now we consider how the prediction mechanism can be applied for making predictions to test data. When making predictions, the LCS learning components are deactivated so that the population does not continue to learn from incoming testing data. A test instance is passed to [P] where a match set [M] is formed as usual. At this point the match set is differently passed to a prediction array. Rules in the match set can predict different actions, therefore a voting scheme is applied. In a simple voting scheme, the action with the strongest supporting 'votes' from matching rules wins, and becomes the selected prediction. All rules do not get an equal vote. Rather the strength of the vote for a single rule is commonly proportional to its numerosity and fitness. This voting scheme and the nature of how LCS's store knowledge, suggests that LCS algorithms are implicitly ''ensemble learners''.

==== Interpretation ====

Individual LCS rules are typically human readable IF:THEN expression. Rules that constitute the LCS prediction model can be ranked by different rule parameters and manually inspected. Global strategies to guide knowledge discovery using statistical and graphical have also been proposed.<ref name=":11" /><ref name=":12" /> With respect to other advanced machine learning approaches, such as [[artificial neural network]]s, [[random forest]]s, or [[genetic programming]], learning classifier systems are particularly well suited to problems that require interpretable solutions.

== History ==

=== Early years ===

[[John Henry Holland]] was best known for his work popularizing [[genetic algorithm]]s (GA), through his ground-breaking book "Adaptation in Natural and Artificial Systems"<ref>{{Cite book|title=Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence|last=Holland|first=John|publisher=Michigan Press|year=1975|isbn=9780262581110|___locationurl=|pages=|quote=|viahttps://books.google.com/books?id=5EgGaBkwvWcC}}</ref> in 1975 and his formalization of [[Holland's schema theorem]]. In 1976, Dr. Holland conceptualized an extension of the GA concept to what he called a "cognitive system",<ref>Holland JH (1976) Adaptation. In: Rosen R, Snell F (eds) Progress in theoretical biology, vol 4. Academic Press, New York, pp 263–293</ref> and provided the first detailed description of what would become known as the first learning classifier system in the paper "Cognitive Systems based on Adaptive Algorithms".<ref name=":2">Holland JH, Reitman JS (1978) Cognitive systems based on

adaptive algorithms Reprinted in: Evolutionary computation.

The fossil record. In: David BF (ed) IEEE Press, New York

1998. {{ISBN |0-7803-3481-7}}

</ref> This first system, named '''Cognitive System One (CS-1)''' was conceived as a modeling tool, designed to model a real system (i.e. ''environment'') with unknown underlying dynamics using a population of human readable rules. The goal was for a set of rules to perform [[online machine learning]] to adapt to the environment based on infrequent payoff/reward (i.e. reinforcement learning) and apply these rules to generate a behavior that matched the real system. This early, ambitious implementation was later regarded as overly complex, yielding inconsistent results.<ref name=":1" /><ref name=":3">{{Cite journal|last=Lanzi|first=Pier Luca|date=2008-02-08|title=Learning classifier systems: then and now|url=http://link.springer.com/article/10.1007/s12065-007-0003-3|journal=Evolutionary Intelligence|language=en|volume=1|issue=1|pages=63–82|doi=10.1007/s12065-007-0003-3|s2cid=27153843|issn=1864-5909}}</ref>

Beginning in 1980, [[Kenneth A De Jong|Kenneth Dede Jong]] and his student Stephen Smith took a different approach to rule-based machine learning with '''(LS-1)''', where learning was viewed as an offline optimization process rather than an online adaptation process.<ref>Smith S (1980) A learning system based on genetic adaptive

algorithms. Ph.D. thesis, Department of Computer Science,

University of Pittsburgh

</ref><ref>Smith S (1983) [https://www.researchgate.net/profile/Stephen_Smith14/publication/220815785_Flexible_Learning_of_Problem_Solving_Heuristics_Through_Adaptive_Search/links/0deec52c18dbd0dd53000000.pdf Flexible learning of problem solving heuristics through adaptive search]. In: Eighth international joint conference

on articial intelligence. Morgan Kaufmann, Los Altos, pp

421–425

</ref><ref>De Jong KA (1988) Learning with genetic algorithms: an overview. Mach Learn 3:121–138</ref> This new approach was more similar to a standard genetic algorithm but evolved independent sets of rules. Since that time LCS methods inspired by the online learning framework introduced by Holland at the [[University of Michigan]] have been referred to as '''Michigan-style LCS''', and those inspired by Smith and De Jong at the [[University of Pittsburgh]] have been referred to as '''Pittsburgh-style LCS'''.<ref name=":1" /><ref name=":3" /> In 1986, Holland developed what would be considered the standard Michigan-style LCS for the next decade.<ref name=":4">[http://dl.acm.org/citation.cfm?id=216016 Holland, John H. "Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based system." ''Machine learning''(1986): 593-623.]</ref>

Other important concepts that emerged in the early days of LCS research included (1) the formalization of a ''bucket brigade algorithm'' (BBA) for credit assignment/learning,<ref>{{Cite journalbook|last=Holland|first=John H.|date=1985-01-01|title=Properties of the Bucket Brigade|url=http://dl.acm.org/citation.cfm?id=645511.657087|journal=Proceedings of the 1st International Conference on Genetic Algorithms|___location=Hillsdale, NJ, USA|publisher=L. Erlbaum Associates Inc.|pages=1–7|isbn=0805804269978-0805804263}}</ref> (2) selection of parent rules from a common 'environmental niche' (i.e. the ''match set'' [M]) rather than from the whole ''population'' [P],<ref>{{Cite thesis|last=Booker|first=L|title=Intelligent Behavior as aan Adaptation to the Task Environment|date=1982-01-01|publisher=University of Michigan|url=http://www.citeulike.org/group/664/article/431772}}</ref> (3) ''covering'', first introduced as a ''create'' operator,<ref name=":5">Wilson, S. W. "[http://www.cs.sfu.ca/~vaughan/teaching/415/papers/wilson_animat.pdf Knowledge growth in an artificial animal]. Proceedings of the First International Conference on Genetic Algorithms and their Applications." (1985).</ref> (4) the formalization of an ''action set'' [A],<ref name=":5" /> (5) a simplified algorithm architecture,<ref name=":5" /> (6) ''strength-based fitness'',<ref name=":4" /> (7) consideration of single-step, or supervised learning problems<ref>{{Cite journal|last=Wilson|first=Stewart W.|title=Classifier systems and the animat problem|url=http://link.springer.com/article/10.1007/BF00058679|journal=Machine Learning|language=en|volume=2|issue=3|pages=199–228|doi=10.1007/BF00058679|issn=0885-6125|year=1987|doi-access=free}}</ref> and the introduction of the ''correct set'' [C],<ref>{{Cite journalbook|lastlast1=Bonelli|firstfirst1=Pierre|last2=Parodi|first2=Alexandre|last3=Sen|first3=Sandip|last4=Wilson|first4=Stewart|date=1990-01-01|title=NEWBOOLE: A Fast GBML System|url=httphttps://dl.acmarchive.org/citation.cfm?id=101883.102047details/machinelearningp0000inte/page/153|journal=Proceedings of the Seventh International Conference (1990) on Machine Learning|___location=San Francisco, CA, USA|publisher=Morgan Kaufmann Publishers Inc.|pages=[https://archive.org/details/machinelearningp0000inte/page/153 153–159]|isbn=1558601414978-1558601413|url-access=registration}}</ref> (8) ''accuracy-based fitness''<ref>{{Cite journal|lastlast1=Frey|firstfirst1=Peter W.|last2=Slate|first2=David J.|title=Letter recognition using Holland-style adaptive classifiers|url=http://link.springer.com/article/10.1007/BF00114162|journal=Machine Learning|language=en|volume=6|issue=2|pages=161–182|doi=10.1007/BF00114162|issn=0885-6125|year=1991|doi-access=free}}</ref> (9) the combination of fuzzy logic with LCS<ref>Valenzuela-Rendón, Manuel. "[http://sci2s.ugr.es/sites/default/files/files/TematicWebSites/GeneticFuzzySystems/(1991)_Valenzuela-Rendon.pdf The Fuzzy Classifier System: A Classifier System for Continuously Varying Variables]." In ''ICGA'', pp. 346-353. 1991.</ref> (which later spawned a lineage of ''fuzzy LCS algorithms''), (10) encouraging ''long action chains'' and ''default hierarchies'' for improving performance on multi-step problems,<ref>{{Cite thesis|last=Riolo|first=Rick L.|title=Empirical Studies of Default Hierarchies and Sequences of Rules in Learning Classifier Systems|date=1988-01-01|publisher=University of Michigan|url=http://dl.acm.org/citation.cfm?id=914945|place=Ann Arbor, MI, USA}}</ref><ref>{{Cite journal|last=R.L.|first=Riolo,|date=1987-01-01|title=Bucket brigade performance. I. Long sequences of classifiers|url=http://agris.fao.org/agris-search/search.do?recordID=US201301782174|journal=Genetic algorithmsAlgorithms and their applicationsTheir Applications: proceedingsProceedings of the secondSecond International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=Englishen}}</ref><ref>{{Cite journal|last=R.L.|first=Riolo,|date=1987-01-01|title=Bucket brigade performance. II. Default hierarchies|url=http://agris.fao.org/agris-search/search.do?recordID=US201301782175|journal=Genetic algorithmsAlgorithms and their applicationsTheir Applications: proceedingsProceedings of the secondSecond International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=Englishen}}</ref> (11) examining [[latent learning]] (which later inspired a new branch of ''anticipatory classifier systems'' (ACS)<ref name=":7">W. Stolzmann, "Anticipatory classifier systems," in Proceedings

of the 3rd Annual Genetic Programming Conference, pp.

658–664, 1998.

</ref>), and (12) the introduction of the first [[Q-learning]]-like credit assignment technique.<ref>{{Cite journalbook|last=Riolo|first=Rick L.|date=1990-01-01|title=Lookahead Planning and Latent Learning in a Classifier System|url=http://dl.acm.org/citation.cfm?id=116517.116553|journal=Proceedings of the First International Conference on Simulation of Adaptive Behavior on Fromfrom Animals to Animats|___location=Cambridge, MA, USA|publisher=MIT Press|pages=316–326|isbn=0262631385978-0262631389}}</ref> While not all of these concepts are applied in modern LCS algorithms, each were landmarks in the development of the LCS paradigm.

=== The revolution ===

Interest in learning classifier systems was reinvigorated in the mid 1990's1990s largely due to two events; the development of the [[Q-learning|Q-Learning]] algorithm<ref>Watkins, Christopher John Cornish Hellaby. "Learning from delayed rewards." PhD diss., University of Cambridge, 1989.</ref> for [[reinforcement learning]], and the introduction of significantly simplified Michigan-style LCS architectures by Stewart Wilson.<ref name=":10">{{Cite journal|last=Wilson|first=Stewart W.|date=1995-06-01|title=Classifier Fitness Based on Accuracy|url=http://dx.doi.org/10.1162/evco.1995.3.2.149|journal=Evol. Comput.|volume=3|issue=2|pages=149–175|doi=10.1162/evco.1995.3.2.149|issn=1063-6560|citeseerx=10.1.1.363.2210|s2cid=18341635}}</ref><ref name=":6">{{Cite journal|last=Wilson|first=Stewart W.|date=1994-03-01|title=ZCS: A Zeroth Level Classifier System|url=http://dx.doi.org/10.1162/evco.1994.2.1.1|journal=Evolutionary Computation|volume=2|issue=1|pages=1–18|doi=10.1162/evco.1994.2.1.1|issn=1063-6560|citeseerx=10.1.1.363.798|s2cid=17680778}}</ref> Wilson's '''Zeroth-level Classifier System (ZCS)'''<ref name=":6" /> focused on increasing algorithmic understandability based on Hollands standard LCS implementation.<ref name=":4" /> This was done, in part, by removing rule-bidding and the internal message list, essential to the original BBA credit assignment, and replacing it with a hybrid BBA/[[Q-learning|Q-Learning]] strategy. ZCS demonstrated that a much simpler LCS architecture could perform as well as the original, more complex implementations. However, ZCS still suffered from performance drawbacks including the proliferation of over-general classifiers.

In 1995, Wilson published his landmark paper, "Classifier fitness based on accuracy" in which he introduced the classifier system '''XCS'''.<ref name=":10" /> XCS took the simplified architecture of ZCS and added an accuracy-based fitness, a niche GA (acting in the action set [A]), an explicit generalization mechanism called ''subsumption'', and an adaptation of the [[Q-learning|Q-Learning]] credit assignment. XCS was popularized by its ability to reach optimal performance while evolving accurate and maximally general classifiers as well as its impressive problem flexibility (able to perform both [[reinforcement learning]] and [[supervised learning]]) . XCS later became the best known and most studied LCS algorithm and defined a new family of ''accuracy-based LCS''. ZCS alternatively became synonymous with ''strength-based LCS''. XCS is also important, because it successfully bridged the gap between LCS and the field of [[reinforcement learning]]. Following the success of XCS, LCS were later described as reinforcement learning systems endowed with a generalization capability.<ref>{{Cite journal|last=Lanzi|first=P. L.|title=Learning classifier systems from a reinforcement learning perspective|url=http://link.springer.com/article/10.1007/s005000100113|journal=Soft Computing|language=en|volume=6|issue=3-43–4|pages=162–170|doi=10.1007/s005000100113|issn=1432-7643|year=2002|s2cid=39103390}}</ref> [[Reinforcement learning]] typically seeks to learn a value function that maps out a complete representation of the state/action space. Similarly, the design of XCS drives it to form an all-inclusive and accurate representation of the problem space (i.e. a ''complete map'') rather than focusing on high payoff niches in the environment (as was the case with strength-based LCS). Conceptually, complete maps don't only capture what you should do, or what is correct, but also what you shouldn't do, or what's incorrect. Differently, most strength-based LCSs, or exclusively supervised learning LCSs seek a rule set of efficient generalizations in the form of a ''best action map'' (or a ''partial map''). Comparisons between strength vs. accuracy-based fitness and complete vs. best action maps have since been examined in greater detail.<ref>Kovacs, Timothy Michael Douglas. ''A Comparison of Strength and Accuracy-based Fitness in Learning and Classifier Systems''. 2002.</ref><ref>[http{{cite book | chapter-url=https://link.springer.com/chapter/10.1007/3-540-48104-4_6 Kovacs,| Timdoi=10.1007/3-540-48104-4_6 "| chapter=Two viewsViews of classifierClassifier systems."Systems In| ''Internationaltitle=Advances Workshop onin Learning Classifier Systems'', pp.| 74-87.series=Lecture SpringerNotes Berlinin Heidelberg,Computer 2001]Science | date=2002 | last1=Kovacs | first1=Tim | volume=2321 | pages=74–87 | isbn=978-3-540-43793-2 }}</ref>

=== In the wake of XCS ===

XCS inspired the development of a whole new generation of LCS algorithms and applications. In 1995, Congdon was the first to apply LCS to real-world [[Epidemiology|epidemiological]] investigations of disease <ref name=":8" /> followed closely by Holmes who developed the '''BOOLE++''',<ref>{{Cite journal|last=Holmes|first=John H.|date=1996-01-01|title=A Genetics-Based Machine Learning Approach to Knowledge Discovery in Clinical Data|journal=Proceedings of the AMIA Annual Fall Symposium|pages=883|issn=1091-8280|pmc=2233061}}</ref> '''EpiCS''',<ref>Holmes, John H. "[https://web.archive.org/web/20180820234915/https://pdfs.semanticscholar.org/71e4/eb6c630dee4b762e74b2970f6dc638a351ab.pdf Discovering Risk of Disease with a Learning Classifier System]." In ''ICGA'', pp. 426-433. 1997.</ref> and later '''EpiXCS'''<ref>Holmes, John H., and Jennifer A. Sager. "[https://link.springer.com/10.1007%2F11527770_60 Rule discovery in epidemiologic surveillance data using EpiXCS: an evolutionary computation approach]." In''Conference on Artificial Intelligence in Medicine in Europe'', pp. 444-452. Springer Berlin Heidelberg, 2005.</ref> for [[Epidemiology|epidemiological]] classification. These early works inspired later interest in applying LCS algorithms to complex and large-scale [[data mining]] tasks epitomized by [[bioinformatics]] applications. In 1998, Stolzmann introduced '''anticipatory classifier systems (ACS)''' which included rules in the form of 'condition-action-effect, rather than the classic 'condition-action' representation.<ref name=":7" /> ACS was designed to predict the perceptual consequences of an action in all possible situations in an environment. In other words, the system evolves a model that specifies not only what to do in a given situation, but also provides information of what will happen after a specific action will be executed. This family of LCS algorithms is best suited to multi-step problems, planning, speeding up learning, or disambiguating perceptual aliasing (i.e. where the same observation is obtained in distinct states but requires different actions). Butz later pursued this anticipatory family of LCS developing a number of improvements to the original method.<ref>Butz, Martin V. "[https://web.archive.org/web/20180820234943/https://pdfs.semanticscholar.org/3572/7a56fcce7a73ccc43e5bfa19389780e6d436.pdf Biasing exploration in an anticipatory learning classifier system]." In ''International Workshop on Learning Classifier Systems'', pp. 3-22. Springer Berlin Heidelberg, 2001.</ref> In 2002, Wilson introduced '''XCSF''', adding a computed action in order to perform function approximation.<ref>{{Cite journal|last=Wilson|first=Stewart W.|title=Classifiers that approximate functions|url=http://link.springer.com/article/10.1023/A:1016535925043|journal=Natural Computing|language=en|volume=1|issue=2-32–3|pages=211–234|doi=10.1023/A:1016535925043|issn=1567-7818|year=2002|s2cid=23032802}}</ref> In 2003, Bernado-Mansilla introduced a '''sUpervised Classifier System (UCS)''', which specialized the XCS algorithm to the task of [[supervised learning]], single-step problems, and forming a best action set. UCS removed the [[reinforcement learning]] strategy in favor of a simple, accuracy-based rule fitness as well as the explore/exploit learning phases, characteristic of many reinforcement learners. Bull introduced a simple accuracy-based LCS '''(YCS)'''<ref>Bull, Larry. "[https://web.archive.org/web/20180820234941/https://pdfs.semanticscholar.org/120c/8f5057995c36ee60ec320c2263b20af05444.pdf A simple accuracy-based learning classifier system]." ''Learning Classifier Systems Group Technical Report UWELCSG03-005, University of the West of England, Bristol, UK'' (2003).</ref> and a simple strength-based LCS '''Minimal Classifier System (MCS)'''<ref>Bull, Larry. "[https://link.springer.com/chapter/10.1007/978-3-540-30217-9_104 A simple payoff-based learning classifier system]." In''International Conference on Parallel Problem Solving from Nature'', pp. 1032-1041. Springer Berlin Heidelberg, 2004.</ref> in order to develop a better theoretical understanding of the LCS framework. Bacardit introduced '''GAssist'''<ref>Peñarroya, Jaume Bacardit. "Pittsburgh genetic-based machine learning in the data mining era: representations, generalization, and run-time." PhD diss., Universitat Ramon Llull, 2004.</ref> and '''BioHEL''',<ref>{{Cite journal|lastlast1=Bacardit|firstfirst1=Jaume|last2=Burke|first2=Edmund K.|last3=Krasnogor|first3=Natalio|date=2008-12-12|title=Improving the scalability of rule-based evolutionary learning|url=http://link.springer.com/article/10.1007/s12293-008-0005-4|journal=Memetic Computing|language=en|volume=1|issue=1|pages=55–67|doi=10.1007/s12293-008-0005-4|s2cid=775199|issn=1865-9284}}</ref> Pittsburgh-style LCSs designed for [[data mining]] and [[scalability]] to large datasets in [[bioinformatics]] applications. In 2008, Drugowitsch published the book titled "Design and Analysis of Learning Classifier Systems" including some theoretical examination of LCS algorithms.<ref>{{Cite book|url=http://link.springer.com/book/10.1007/978-3-540-79866-8|title=Design and Analysis of Learning Classifier Systems - Springer|volume = 139|doi=10.1007/978-3-540-79866-8|series = Studies in Computational Intelligence|year = 2008|isbn = 978-3-540-79865-1|last1 = Drugowitsch|first1 = Jan}}</ref> Butz introduced the first rule online learning visualization within a [[Graphical user interface|GUI]] for XCSF<ref name=":9" /> (see the image at the top of this page). Urbanowicz extended the UCS framework and introduced '''ExSTraCS,''' explicitly designed for [[supervised learning]] in noisy problem domains (e.g. epidemiology and bioinformatics).<ref>Urbanowicz, Ryan J., Gediminas Bertasius, and Jason H. Moore. "[http://www.seas.upenn.edu/~gberta/uploads/3/1/4/8/31486883/urbanowicz_2014_exstracs_algorithm.pdf An extended michigan-style learning classifier system for flexible supervised learning, classification, and data mining] {{Webarchive|url=https://web.archive.org/web/20170829055517/http://www.seas.upenn.edu/~gberta/uploads/3/1/4/8/31486883/urbanowicz_2014_exstracs_algorithm.pdf |date=2017-08-29 }}." In ''International Conference on Parallel Problem Solving from Nature'', pp. 211-221. Springer International Publishing, 2014.</ref> ExSTraCS integrated (1) expert knowledge to drive covering and genetic algorithm towards important features in the data,<ref>Urbanowicz, Ryan J., Delaney Granizo-Mackenzie, and Jason H. Moore. "[https://web.archive.org/web/20180820234834/https://pdfs.semanticscholar.org/b407/8f8bb6aa9e39e84b0b20874662a6ed8b7df1.pdf Using expert knowledge to guide covering and mutation in a michigan style learning classifier system to detect epistasis and heterogeneity]." In''International Conference on Parallel Problem Solving from Nature'', pp. 266-275. Springer Berlin Heidelberg, 2012.</ref> (2) a form of long-term memory referred to as attribute tracking,<ref>{{Cite journalbook|lastlast1=Urbanowicz|firstfirst1=Ryan|last2=Granizo-Mackenzie|first2=Ambrose|last3=Moore|first3=Jason|date=2012-01-01|title=Instance-linkedProceedings Attributeof Trackingthe and14th Feedbackannual forconference Michigan-styleon SupervisedGenetic Learningand Classifierevolutionary computation Systems|urlchapter=http://doi.acm.org/10.1145/2330163.2330291|journal=ProceedingsInstance-linked ofattribute thetracking 14thand Annualfeedback Conferencefor onmichigan-style Geneticsupervised andlearning Evolutionaryclassifier Computationsystems |date=2012-01-01|series=GECCO '12|___location=New York, NY, USA|publisher=ACM|pages=927–934|doi=10.1145/2330163.2330291|isbn=9781450311779|s2cid=142534}}</ref> allowing for more efficient learning and the characterization of heterogeneous data patterns, and (3) a flexible rule representation similar to Bacardit's mixed discrete-continuous attribute list representation.<ref>{{Cite journalbook|lastlast1=Bacardit|firstfirst1=Jaume|last2=Krasnogor|first2=Natalio|date=2009-01-01|title=AProceedings Mixedof Discrete-continuousthe Attribute11th ListAnnual Representationconference foron LargeGenetic Scaleand Classificationevolutionary computation Domains|urlchapter=http://doi.acm.org/10.1145/1569901.1570057|journal=ProceedingsA ofmixed thediscrete-continuous 11thattribute Annuallist Conferencerepresentation onfor Geneticlarge andscale Evolutionaryclassification domains Computation|date=2009-01-01|series=GECCO '09|___location=New York, NY, USA|publisher=ACM|pages=1155–1162|doi=10.1145/1569901.1570057|isbn=9781605583259|citeseerx=10.1.1.158.7314|s2cid=10906515}}</ref> Both Bacardit and Urbanowicz explored statistical and visualization strategies to interpret LCS rules and perform knowledge discovery for data mining.<ref name=":11">{{Cite journal|lastlast1=Urbanowicz|firstfirst1=R. J.|last2=Granizo-Mackenzie|first2=A.|last3=Moore|first3=J. H.|date=2012-11-01|title=An analysis pipeline with statistical and visualization-guided knowledge discovery for Michigan-style learning classifier systems|url=http://ieeexplore.ieee.org/document/6331728/|journal=IEEE Computational Intelligence Magazine|volume=7|issue=4|pages=35–45|doi=10.1109/MCI.2012.2215124|issn=1556-603X|pmc=4244006|pmid=25431544}}</ref><ref name=":12">{{cite journal | last1 = Bacardit | first1 = Jaume | last2 = Llorà | first2 = Xavier | year = 2013 | title = Large‐scaleLarge-scale data mining using genetics‐basedgenetics-based machine learning | url = | journal = Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery | volume = 3 | issue = 1| pages = 37–61 | doi=10.1002/widm.1078| s2cid = 43062613 }}</ref> Browne and Iqbal explored the concept of reusing building blocks in the form of code fragments and were the first to solve the 135-bit mulitplexermultiplexer benchmark problem by first learning useful building blocks from simpler multiplexer problems.<ref>{{Cite journal|lastlast1=Iqbal|firstfirst1=Muhammad|last2=Browne|first2=Will N.|last3=Zhang|first3=Mengjie|date=2014-08-01|title=Reusing Building Blocks of Extracted Knowledge to Solve Complex, Large-Scale Boolean Problems|url=http://dx.doi.org/10.1109/TEVC.2013.2281537|journal=IEEE Transactions on Evolutionary Computation|publisher=IEEE|pages=465–480|volume=18|issue=4|doi=10.1109/tevc.2013.2281537|s2cid=525358}}</ref> '''ExSTraCS 2.0''' was later introduced to improve Michigan-style LCS scalability, successfully solving the 135-bit multiplexer benchmark problem for the first time directly.<ref name=":0"/> The n-bit [[multiplexer]] problem is highly [[Epistasis|epistatic]] and [[Homogeneity and heterogeneity|heterogeneous]], making it a very challenging [[machine learning]] task.

== Variants ==

Line 89 ⟶ 90:

=== Pittsburgh-Style Learning Classifier System ===

Pittsburgh-Style LCSs are characterized by a population of variable length rule-sets where each rule-set is a potential solution. The genetic algorithm typically operates at the level of an entire rule-set. Pittsburgh-style systems also can also uniquely evolvedevolve ordered rule lists, as well as employ a default rule. These systems have the natural advantage of identifying smaller rule sets, making these systems more interpretable with regards to manual rule inspection.

=== Hybrid systems ===

Line 97 ⟶ 98:

* Adaptive: They can acclimate to a changing environment in the case of online learning.

* Model free: They make limited assumptions about the environment, or the patterns of association within the data.

** TheThey can model complex, epistatic, heterogeneous, or distributed underlying patterns without relying on prior knowledge.

** They make no assumptions about the number of predictive vs. non-predictive features in the data.

* Ensemble Learner: No single model is applied to a given instance that universally provides a prediction. Instead a relevant and often conflicting set of rules contribute a 'vote' which can be interpreted as a fuzzy prediction.

* Stochastic Learner: Non-deterministic learning is advantageous in large-scale or high complexity problems where deterministic or exhaustive learning becomes intractable.

* Implicitly Multi-objective: Rules evolve towards accuracy with implicit and explicit pressures encouraging maximal generality/simplicity. This implicit generalization pressure is unique to LCS. Effectively, more general rules, will appear more often in match sets. In turn, they have a more frequent opportunity to be selected as parents, and pass on their more general (genomes) to offspring rules.

* Interpretable:In the interest of data mining and knowledge discovery individual LCS rules are logical, and can be made to be human interpretable IF:THEN statements. Effective strategies have also been introduced to allow for global knowledge discovery identifying significant features, and patterns of association from the rule population as a whole.<ref name=":11" />

* Flexible application

** Single or multi-step problems

Line 115 ⟶ 116:

== Disadvantages ==

* Limited Software Availability: There are a limited number of open source, accessible LCS implementations, and even fewer that are designed to be user friendly or accessible to machine learning practitioners.

* Interpretation: While LCS algorithms are certainly more interpretable than some advanced machine learners, users must interpret a set of rules (sometimes large sets of rules to comprehend the LCS model. ). Methods for rule compaction, and interpretation strategies remains an area of active research.

* Theory/Convergence Proofs: There is a relatively small body of theoretical work behind LCS algorithms. This is likely due to their relative algorithmic complexity (applying a number of interacting components) as well as their stochastic nature.

* Overfitting: Like any machine learner, LCS can suffer from [[overfitting]] despite implicit and explicit generalization pressures.

Line 130 ⟶ 131:

* Game-Play

* Image Classification

* Knowledge HandelingHandling

* Medical Diagnosis

* Modeling

Line 144 ⟶ 145:

== Terminology ==

The name, "Learning Classifier System (LCS)", is a bit misleading since there are many [[machine learning]] algorithms that 'learn to classify' (e.g. [[decision tree]]s, [[artificial neural network]]s), but are not LCSs. The term 'rule-based machine learning ([[Rule-based machine learning|RBML]])' is useful, as it more clearly captures the essential 'rule-based' component of these systems, but it also generalizes to methods that are not considered to be LCSs (e.g. [[association rule learning]], or [[artificial immune system]]s). More general terms such as, 'genetics-based machine learning', and even 'genetic algorithm'<ref name=":8">Congdon, Clare Bates. "A comparison of genetic algorithms and other machine learning systems on a complex classification task from common disease research." PhD diss., The University of Michigan, 1995.</ref> have also been applied to refer to what would be more characteristically defined as a learning classifier system. Due to their similarity to [[genetic algorithm]]s, Pittsburgh-style learning classifier systems are sometimes generically referred to as 'genetic algorithms'. Beyond this, some LCS algorithms, or closely related methods, have been referred to as 'cognitive systems',<ref name=":2" /> 'adaptive agents', '[[production system (computer science)|production system]]s', or generically as a 'classifier system'.<ref>{{Cite journal|lastlast1=Booker|firstfirst1=L. B.|last2=Goldberg|first2=D. E.|last3=Holland|first3=J. H.|date=1989-09-01|title=Classifier systems and genetic algorithms|url=http://www.sciencedirect.com/science/article/pii/0004370289900507|journal=Artificial Intelligence|volume=40|issue=1|pages=235–282|doi=10.1016/0004-3702(89)90050-7|hdl=2027.42/27777|url=https://deepblue.lib.umich.edu/bitstream/2027.42/27777/1/0000171.pdf|hdl-access=free}}</ref><ref>Wilson, Stewart W., and David E. Goldberg. "A critical review of classifier systems." In ''Proceedings of the third international conference on Genetic algorithms'', pp. 244-255. Morgan Kaufmann Publishers Inc., 1989.</ref> This variation in terminology contributes to some confusion in the field.

Up until the 2000's2000s nearly all learning classifier system methods were developed with reinforcement learning problems in mind. As a result, the term ‘learning classifier system’ was commonly defined as the combination of ‘trial-and-error’ reinforcement learning with the global search of a genetic algorithm. Interest in supervised learning applications, and even unsupervised learning have since broadened the use and definition of this term.

== See also ==

* [[Rule-based machine learning]]

* [[Production system (computer science)|Production system]]

* [[Expert system]]