Learning classifier system: Difference between revisions

Revision as of 23:18, 5 July 2022

Revision as of 12:13, 19 August 2022

Line 69:

</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|last1=Bonelli|first1=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|last1=Frey|first1=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=en}}</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=en}}</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.

Line 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_learningbased 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|last1=Booker|first1=L. B.|last2=Goldberg|first2=D. E.|last3=Holland|first3=J. H.|date=1989-09-01|title=Classifier systems and genetic algorithms|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 2000s 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.