Learning classifier system: Difference between revisions

Revision as of 15:11, 22 February 2020

Revision as of 22:50, 15 April 2020

Line 1:

[[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|last=Stalph|first=Patrick O.|last2=Butz|first2=Martin V.|date=2010-02-01|title=JavaXCSF: The XCSF Learning Classifier System in Java|journal=SIGEVOlution|volume=4|issue=3|pages=16–19|doi=10.1145/1731888.1731890|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]]) with a learning component (performing either [[supervised learning]], [[reinforcement learning]], or [[unsupervised learning]]).<ref name=":1">{{Cite journal|last=Urbanowicz|first=Ryan J.|last2=Moore|first2=Jason H.|date=2009-09-22|title=Learning Classifier Systems: A Complete Introduction, Review, and Roadmap|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|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|last=Bernadó-Mansilla|first=Ester|last2=Garrell-Guiu|first2=Josep M.|date=2003-09-01|title=Accuracy-Based Learning Classifier Systems: Models, Analysis and Applications to Classification Tasks|journal=Evolutionary Computation|volume=11|issue=3|pages=209–238|doi=10.1162/106365603322365289|pmid=14558911|issn=1063-6560}}</ref><ref name=":0">{{Cite journal|last=Urbanowicz|first=Ryan J.|last2=Moore|first2=Jason H.|date=2015-04-03|title=ExSTraCS 2.0: description and evaluation of a scalable learning classifier system|journal=Evolutionary Intelligence|language=en|volume=8|issue=2–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|title=Advances in Learning Classifier Systems|last=Bernadó|first=Ester|last2=Llorà|first2=Xavier|last3=Garrell|first3=Josep M.|date=2001-07-07|publisher=Springer Berlin Heidelberg|isbn=9783540437932|editor-last=Lanzi|editor-first=Pier Luca|series=Lecture Notes in Computer Science|pages=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|last=Bacardit|first=Jaume|last2=Butz|first2=Martin V.|date=2007-01-01|publisher=Springer Berlin Heidelberg|isbn=9783540712305|editor-last=Kovacs|editor-first=Tim|series=Lecture Notes in Computer Science|pages=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 book|last=Urbanowicz|first=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|journal=Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation|series=GECCO Companion '15|___location=New York, NY, USA|publisher=ACM|pages=1029–1036|doi=10.1145/2739482.2768453|isbn=9781450334884}}</ref> [[function approximation]],<ref>{{Cite journal|last=Butz|first=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|journal=IEEE Transactions on Evolutionary Computation|volume=12|issue=3|pages=355–376|doi=10.1109/TEVC.2007.903551|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.

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]]).

Line 68:

</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 book|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=978-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 a 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|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 book|last=Bonelli|first=Pierre|last2=Parodi|first2=Alexandre|last3=Sen|first3=Sandip|last4=Wilson|first4=Stewart|date=1990-01-01|title=NEWBOOLE: A Fast GBML System|url=https://archive.org/details/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=978-1558601413|url-access=registration}}</ref> (8) ''accuracy-based fitness''<ref>{{Cite journal|last=Frey|first=Peter W.|last2=Slate|first2=David J.|title=Letter recognition using Holland-style adaptive classifiers|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 Algorithms and Their Applications : Proceedings of the Second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=English}}</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 Algorithms and Their Applications : Proceedings of the Second International Conference on Genetic Algorithms : July 28–31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA|language=English}}</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.