First, a word on naming conventions is due, for no other paradigm of EC has undergone more changes to its name space than this one. Initially, Holland called his cognitive models "Classifier Systems" abbrv. with CS, and sometimes CFS, as can be found in [GOLD89].
Whence Riolo came into play in 1986 and Holland added a reinforcement component to the overall design of a CFS, that emphasized its ability to learn. So, the word "learning" was prepended to the name, to make: "Learning Classifier Systems" (abbrv. to LCS). On October 6-9, 1992 the "1st Inter'l Workshop on Learning Classifier Systems" took place at the NASA Johnson Space Center, Houston, TX. A summary of this "summit" of all leading researchers in LCS can be found on ENCORE (See Q15.3) in file CFS/papers/lcs92.ps.gz
Today, the story continues, LCSs are sometimes subsumed under a "new" machine learning paradigm called "Evolutionary Reinforcement Learning" or ERL for short, incorporating LCSs, "Q-Learning", devised by Watkins (1989), and a paradigm of the same name, devised by Ackley and Littman [ALIFEIII].
And then, this latter statement is really somewhat confusing, as Marco Dorigo has pointed out in a letter to editors of this guide, since Q-Learning has no evolutionary component. So please let the Senior Editor explain: When I wrote this part of the guide, I just had in mind that Q-Learning would make for a pretty good replacement of Holland's bucket-brigade algorithm, so I used this litte speculation to see what comes out of it; in early December 95, almost two years later, it has finally caught Marco's attention. But meanwhile, I have been proven right: Wilson has suggested to use Q-Learning in CLASSIFIER SYSTEM (Wilson 1994) and Dorigo & Bersini (1994) have shown that Q-Learning and the bucket-brigade are truly equivalent concepts.
We would therefore be allowed to call a CFS that uses Q-Learning for rule discovery, rather than a bucket-brigade, a Q-CFS, Q-LCS, or Q-CS; in any case would the result be subsumed under the term ERL, even if Q-Learning itself is not an EVOLUTIONARY ALGORITHM!
Interestingly, Wilson called his system ZCS (apparantly no "Q" inside), while Dorigo & Bersini called their system a D-Max-VSCS, or "discounted max very simple classifier system" (and if you know Q-Learning at least the D-Max part of the name will remind you of that algorithm). The latter paper can be found on Encore (see Q15.3) in file CFS/papers/sab94.ps.gz
And by the way in [HOLLAND95] the term "classifier system" is not used anymore. You cannot find it in the index. Its a gone! Holland now stresses the adaptive component of his invention, and simply calls the resulting systems adaptive agents. These agents are then implemented within the framework of his recent invention called ECHO.
(See http://www.santafe.edu/projects/echo for more.)
So, to get back to the question above, "What are CFSs?", we first might answer, "Well, there are many interpretations of Holland's ideas...what do you like to know in particular?" And then we'd start with a recitation from [HOLLAND75], [HOLLAND92], and explain all the SCHEMA processors, the broadcast language, etc. But, we will take a more comprehensive, and intuitive way to understand what CLASSIFIER SYSTEMs are all about.
The easiest road to explore the very nature of classifier systems, is to take the animat (ANIMAl + ROBOT = ANIMAT) "lane" devised by Booker (1982) and later studied extensively by Wilson (1985), who also coined the term for this approach. Work continues on animats but is often regarded as ARTIFICIAL LIFE rather than EVOLUTIONARY COMPUTATION. This thread of research has even its own conference series: "Simulation of Adaptive Behavior (SAB)" (cf Q12), including other notions from machine learning, connectionist learning, evolutionary robotics, etc. [NB: the latter is obvious, if an animat lives in a digital microcosm, it can be put into the real world by implantation into an autonomous robot vehicle, that has sensors/detectors (camera eyes, whiskers, etc.) and effectors (wheels, robot arms, etc.); so all that's needed is to use our algorithm as the "brain" of this vehicle, connecting the hardware parts with the software learning component. For a fascinating intro to the field see, e.g. Braitenberg (1984)]
classifier systems, however, are yet another offspring of John Holland's aforementioned book, and can be seen as one of the early applications of GAs, for CFSs use this EVOLUTIONARY ALGORITHM to adapt their behavior toward a changing ENVIRONMENT, as is explained below in greater detail.
Holland envisioned a cognitive system capable of classifying the goings on in its environment, and then reacting to these goings on appropriately. So what is needed to build such a system? Obviously, we need (1) an environment; (2) receptors that tell our system about the goings on; (3) effectors, that let our system manipulate its environment; and (4) the system itself, conveniently a "black box" in this first approach, that has (2) and (3) attached to it, and "lives" in (1).
In the animat approach, (1) usually is an artificially created digital world, e.g. in Booker's Gofer system, a 2 dimensional grid that contains "food" and "poison". And the Gofer itself, that walks across this grid and tries (a) to learn to distinguish between these two items, and (b) survive well fed.
Much the same for Wilson's animat, called "*". Yes, its just an asterisk, and a "Kafka-esque naming policy" is one of the sign posts of the whole field; e.g. the first implementation by Holland and Reitmann 1978 was called CS-1, (cognitive system 1); Smith's Poker player LS-1 (1980) followed this "convention". Riolo's 1988 LCS implementations on top of his CFS-C library (cf Q20), were dubbed FSW-1 (Finite State World 1), and LETSEQ-1 (LETter SEQuence predictor 1).
So from the latter paragraph we can conclude that environment can also mean something completely different (e.g. an infinite stream of letters, time serieses, etc.) than in the animat approach, but anyway; we'll stick to it, and go on.
Imagine a very simple animat, e.g. a simplified model of a frog. Now, we know that frogs live in (a) Muppet Shows, or (b) little ponds; so we chose the latter as our demo environment (1); and the former for a non-Kafka-esque name of our model, so let's dub it "Kermit".
Kermit has eyes, i.e. sensorial input detectors (2); hands and legs, i.e. environment- manipulating effectors (3); is a spicy-fly-detecting-and-eating device, i.e. a frog (4); so we got all the 4 pieces needed.
The most primitive "black box" we can think of is a computer. It has inputs (2), and outputs (3), and a message passing system inbetween, that converts (i.e., computes), certain input messages into output messages, according to a set of rules, usually called the "program" of that computer. From the theory of computer science, we now borrow the simplest of all program structures, that is something called "production system" or PS for short. A PS has been shown to be computationally complete by Post (1943), that's why it is sometimes called a "Post System", and later by Minsky (1967). Although it merely consists of a set of if-then rules, it still resembles a full-fledged computer.
We now term a single "if-then" rule a "classifier", and choose a representation that makes it easy to manipulate these, for example by encoding them into binary strings. We then term the set of classifiers, a "classifier population", and immediately know how to breed new rules for our system: just use a GA to generate new rules/classifiers from the current POPULATION!
All that's left are the messages floating through the black box. They should also be simple strings of zeroes and ones, and are to be kept in a data structure, we call "the message list".
With all this given, we can imagine the goings on inside the black box as follows: The input interface (2) generates messages, i.e., 0/1 strings, that are written on the message list. Then these messages are matched against the condition-part of all classifiers, to find out which actions are to be triggered. The message list is then emptied, and the encoded actions, themselves just messages, are posted to the message list. Then, the output interface (3) checks the message list for messages concerning the effectors. And the cycle restarts.
Note, that it is possible in this set-up to have "internal messages", because the message list is not emptied after (3) has checked; thus, the input interface messages are added to the initially empty list. (cf Algorithm CFS, LCS below)
The general idea of the CFS is to start from scratch, i.e., from tabula rasa (without any knowledge) using a randomly generated classifier population, and let the system learn its program by induction, (cf Holland et al. 1986), this reduces the input stream to recurrent input patterns, that must be repeated over and over again, to enable the animat to classify its current situation/context and react on the goings on appropriately.
Let's take a look at the behavior emitted by Kermit. It lives in its digital microwilderness where it moves around randomly. [NB: This seemingly "random" behavior is not that random at all; for more on instinctive, i.e., innate behavior of non-artificial animals see, e.g. Tinbergen (1951)]
Whenever a small flying object appears, that has no stripes, Kermit should eat it, because its very likely a spicy fly, or other flying insect. If it has stripes, the insect is better left alone, because Kermit had better not bother with wasps, hornets, or bees. If Kermit encounters a large, looming object, it immediately uses its effectors to jump away, as far as possible.
So, part of these behavior patterns within the "pond world", in AI sometimes called a "frame," from traditional knowledge representation techniques, Rich (1983), can be expressed in a set of "if <condition> then <action>" rules, as follows:
IF small, flying object to the left THEN send @
IF small, flying object to the right THEN send %
IF small, flying object centered THEN send $
IF large, looming object THEN send !
IF no large, looming object THEN send *
IF * and @ THEN move head 15 degrees left
IF * and % THEN move head 15 degrees right
IF * and $ THEN move in direction head pointing
IF ! THEN move rapidly away from direction head pointing
Now, this set of rules has to be encoded for use within a CLASSIFIER SYSTEM. A possible encoding of the above rule set in CFS-C (Riolo) classifier terminology. The condition part consists of two conditions, that are combined with a logical AND, thus must be met both to trigger the associated action. This structure needs a NOT operation, (so we get NAND, and know from hardware design, that we can build any computer solely with NANDs), in CFS-C this is denoted by the `~' prefix character (rule #5).
IF THEN
0000, 00 00 00 00
0000, 00 01 00 01
0000, 00 10 00 10
1111, 01 ## 11 11
~1111, 01 ## 10 00
1000, 00 00 01 00
1000, 00 01 01 01
1000, 00 10 01 10
1111, ## ## 01 11
Obviously, string `0000' denotes small, and `00' in the fist part of the second column, denotes flying. The last two bits of column #2 encode the direction of the object approaching, where `00' means left, `01' means right, etc.
In rule #4 a the "don't care symbol" `#' is used, that matches `1' and `0', i.e., the position of the large, looming object, is completely arbitrary. A simple fact, that can save Kermit's (artificial) life.
Algorithm CFS is// start with an initial time t := 0;
// an initially empty message list initMessageList ML (t);
// and a randomly generated population of classifiers initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.) while not done do
// increase the time counter t := t + 1;
// 1. detectors check whether input messages are present ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches ML' := matchClassifiers ML,P (t);
// 3. process new messages through output interface ML := sendEffectors ML' (t); od end CFS.
To convert the previous, non-learning CFS into a learning CLASSIFIER SYSTEM, LCS, as has been proposed in Holland (1986), it takes two steps:
(1) the major cycle has to be changed such that the activation of each classifier depends on some additional parameter, that can be modified as a result of experience, i.e. reinforcement from the ENVIRONMENT;
(2) and/or change the contents of the classifier list, i.e., generate new classifiers/rules, by removing, adding, or combining condition/action-parts of existing classifiers.
The algorithm thus changes accordingly:
Algorithm LCS is// start with an initial time t := 0;
// an initially empty message list initMessageList ML (t);
// and a randomly generated population of classifiers initClassifierPopulation P (t);
// test for cycle termination criterion (time, fitness, etc.) while not done do
// increase the time counter t := t + 1;
// 1. detectors check whether input messages are present ML := readDetectors (t);
// 2. compare ML to the classifiers and save matches ML' := matchClassifiers ML,P (t);
// 3. highest bidding classifier(s) collected in ML' wins the // "race" and post the(ir) message(s) ML' := selectMatchingClassifiers ML',P (t);
// 4. tax bidding classifiers, reduce their strength ML' := taxPostingClassifiers ML',P (t);
// 5. effectors check new message list for output msgs ML := sendEffectors ML' (t);
// 6. receive payoff from environment (REINFORCEMENT) C := receivePayoff (t);
// 7. distribute payoff/credit to classifiers (e.g. BBA) P' := distributeCredit C,P (t);
// 8. Eventually (depending on t), an EA (usually a GA) is // applied to the classifier population if criterion then P := generateNewRules P' (t); else P := P' od end LCS.
Just to list the currently known problems that come with CFSs, would take some additional pages; therefore only some interesting papers dealing with unresolved riddles are listed; probably the best paper containing most of these is the aforementioned summary of the LCS Workshop:
Smith, R.E. (1992) "A report on the first Inter'l Workshop on LCSs" avail. from ENCORE (See Q15.3) in file CFS/papers/lcs92.ps.gz
Other noteworthy critiques on LCSs include:
Wilson, S.W. (1987) "Classifier Systems and the Animat Problem" Machine Learning, 2.
Wilson, S.W. (1988) "Bid Competition and Specificity Reconsidered" Complex Systems, 2(5):705-723.
Wilson, S.W. & Goldberg, D.E. (1989) "A critical review of classifier systems" [ICGA89], 244-255.
Goldberg, D.E., Horn, J. & Deb, K. (1992) "What makes a problem hard for a classifier system?" (containing the Goldberg citation below) is also available from Encore (See Q15.3) in file CFS/papers/lcs92-2.ps.gz
Dorigo, M. (1993) "Genetic and Non-genetic Operators in ALECSYS" Evolutionary Computation, 1(2):151-164. The technical report, the journal article is based on is avail. from Encore (See Q15.3) in file CFS/papers/icsi92.ps.gz
Smith, R.E. Forrest, S. & Perelson, A.S. (1993) "Searching for Diverse, Cooperative POPULATIONs with Genetic Algorithms" Evolutionary Computation, 1(2):127-149.
Generally speaking: "There's much to do in CFS research!"
No other notion of EC provides more space to explore and if you are interested in a PhD in the field, you might want to take a closer look at CFS. However, be warned!, to quote Goldberg: "classifier systems are a quagmire---a glorious, wondrous, and inventing quagmire, but a quagmire nonetheless."
References
Booker, L.B. (1982) "Intelligent behavior as an adaption to the task environment" PhD Dissertation, Univ. of Michigan, Logic of Computers Group, Ann Arbor, MI.
Braitenberg, V. (1984) "Vehicles: Experiments in Synthetic Psychology" Boston, MA: MIT Press.
Dorigo M. & H. Bersini (1994). "A Comparison of Q-Learning and Classifier Systems." Proceedings of From Animals to Animats, Third International Conference on SIMULATION of Adaptive Behavior (SAB94), Brighton, UK, D.Cliff, P.Husbands, J.-A.Meyer and S.W.Wilson (Eds.), MIT Press, 248-255. http://iridia.ulb.ac.be/dorigo/dorigo/conferences/IC.11-SAB94.ps.gz
Holland, J.H. (1986) "Escaping Brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems". In: R.S. Michalski, J.G. Carbonell & T.M. Mitchell (eds), Machine Learning: An Artificial Intelligence approach, Vol II, 593-623, Los Altos, CA: Morgan Kaufman.
Holland, J.H., et al. (1986) "Induction: Processes of Inference, Learning, and Discovery", Cambridge, MA: MIT Press.
Holland, J.H. (1992) "Adaptation in natural and artificial systems" Boston, MA: MIT Press.
Holland, J.H. (1995) "Hidden Order: How adaptation builds complexity" Reading, MA: Addison- Wesley. [HOLLAND95]:
Holland, J.H. & Reitman, J.S. (1978) "Cognitive Systems based on Adaptive Algorithms" In D.A. Waterman & F.Hayes-Roth, (eds) Pattern-directed inference systems. NY: Academic Press.
Minsky, M.L. (1961) "Steps toward Artificial Intelligence" Proceedings IRE, 49, 8-30. Reprinted in E.A. Feigenbaum & J. Feldman (eds) Computers and Thought, 406-450, NY: McGraw-Hill, 1963.
Minsky, M.L. (1967) "Computation: Finite and Infinite Machines" Englewood Cliffs, NJ: Prentice- Hall.
Post, Emil L. (1943) "Formal reductions of the general combinatorial decision problem" American Journal of Mathematics, 65, 197-215.
Rich, E. (1983) "Artificial Intelligence" NY: McGraw-Hill.
Tinbergen, N. (1951) "The Study of Instinct" NY: Oxford Univ. Press.
Watkins, C. (1989) "Learning from Delayed Rewards" PhD Dissertation, Department of Psychology, Cambridge Univ., UK.
Wilson, S.W. (1985) "Knowledge growth in an artificial animal" in [ICGA85], 16-23.
Wilson, S.W. (1994) "ZCS: a zeroth level classifier system" in EC 2(1), 1-18.
Mistakes in this page?
Hitch Hiker's Guide to Evolutionary Computation,
Issue 8.2, released 20 September 2000
Copyright © 1993-2000 by J. Heitkötter and
D. Beasley, all rights reserved.