3.5 Learning Classifier Systems
Learning Classifier Systems (LCS) originated in the GA community as a way of applying GAs to learning problems. The LCS field is one of the oldest, largest and most active areas of GBML. The majority of LCS research is currently carried out on XCS [301,50] and its derivatives XCSF [305,306] for regression/function approximation and UCS [23,222] for supervised learning.
The difficulty in naming the field relates in part to the difficulty in defining what an LCS is [254,126]. In practise, what is accepted as an LCS has become more inclusive over the years. A reasonable definition of an LCS would be an evolutionary rule-based system - except that a significant minority of LCS are not evolutionary! On the other hand, most non-evolutionary rule-based systems are not considered LCS, so the boundaries of the field are defined more by convention than principle. Even EA practitioners are far from unanimous; work continues to be published which some would definitely consider forms of LCS, but which make no reference to the term and which contain few or no LCS references.
(L)CS has at times been taken to refer to Michigan systems only (see e.g. [111]) but it now generally includes Pitt systems as well, as implied by the name and content of IWLCS - the International Workshop on Learning Classifier Systems - which includes both Pitt and Michigan, evolutionary and non-evolutionary systems. As a final terminological note, rules in LCS are often referred to as ``classifiers''.
LCS evolve condition-action (IF-THEN) rules. Recall from §2.2 and figure 2 that in Michigan rule-based systems a chromosome is a single rule while in Pittsburgh systems a chromosome is a variable-length set of rules. Pittsburgh, Michigan, IRL and GCCL are all used. Michigan systems are rare elsewhere but are the most common form of LCS. Within LCS, IRL is most common with fuzzy systems, but see [4] for a non-fuzzy version. In LCS, we typically evolve rule conditions and actions although non-evolutionary operators may act upon them. In addition, each phenotype has parameters associated with it and these parameters are typically learned rather than evolved using the Widrow-Hoff update or similar (see [178] for examples). In Michigan LCS parameters are associated with each rule but in Pittsburgh systems they are associated with each ruleset. For example, in UCS the parameters are: fitness, mean action set size (to bias a deletion process which seeks to balance action set sizes) and experience (a count of the number of times a rule has been applied, in order to estimate confidence in its fitness). In GAssist (a supervised Pittsburgh system) the only parameter is fitness. Variations of the above exist; in some cases rules predict the next input or read and write to memory.
The most common representation in LCS uses fixed-length strings with
binary inputs and outputs and ternary condition. In a simple Michigan
version (see e.g. [301]) each rule has one action and
one condition from 
where # is a wildcard, matching both
0 and 1 in inputs. For example, the condition 01# matches two inputs:
010 and 011. Similar representations were used almost exclusively
prior to approximately 2000 and are inherited from GAs and their
preference for minimal alphabets. (Indeed, ternary conditions have an
interesting parallel with ternary schemata [235] for
binary GAs.) Such rules individually have limited expressive power
[248] (but see also [28]) which
necessitates that solutions are sets of rules. More insidiously, the
lack of individual expressiveness can be a factor in pathological
credit assignment (strong/fit overgenerals
[154]). Various extensions to the simple scheme described
above have been studied (see [154] §2.2.2).
1) has been added to the
ternary representation. This rule matches all inputs and states that
the output is always 1. This rule is incorrect by itself, but the two
rules above it provide exceptions and, taken together, the three
accurately represent the function using one less rule than the middle
representation. One difficulty in evolving such default/exception
structures lies in identifying which rules are the defaults and which
the exceptions; a simple solution is to maintain the population in
some order and make earlier rules exceptions to later ones (as in a
decision list [237]). This is straightforward in Pitt
systems in which individual rulesets are static but is more complex in
Michigan populations in which individual rules are created and deleted
dynamically. The other issue is how to assign credit to the overall
multi-rule structure. In Pittsburgh systems this is again
straightforward since fitness is assigned only at the level of
rulesets, but in Michigan systems each rule has a fitness, and it is
not obvious how to credit the three rules in the default/exception
structure in a way which recognises their cooperation.
The Pittsburgh GABIL [144] and GAssist [13] use decision lists and often evolve default rules spontaneously (e.g. a fully general last rule). Bacardit found that enforcing a fully general last rule in each ruleset in GAssist (and allowing evolution to select the most useful class for such rules) was effective [13].
In Michigan systems default/exception structures are called default hierarchies. Rule specificity has been used as the criterion for determining which rules are exceptions and accordingly conflict resolution methods have been biased according to specificity. There are, however, many problems with this approach [258]. It is difficult for evolution to produce these structure since they depend on cooperation between otherwise competing rules. The structures are unstable since they are interdependent; unfortunate deletion of one member alters the utility of the entire structure. As noted they complicate credit assignment and conflict resolution since exception rules must override defaults [299,258]. There are also problems with the use of specificity to prioritise rules. For one, having fewer #s does not mean a rule actually matches fewer inputs; counting #s is a purely syntactic measure of generality. For another, there is no reason why exception rules should be more specific. The consequence of these difficulties is that there has not been much interest in Michigan default hierarchies since the early 1990s (but see [285]) and indeed not all Michigan LCS support them (e.g. ZCS [300], XCS/XCSF and UCS do not). Nonetheless, the idea should perhaps be revisited and an ensembles perspective might prove useful.
logic [206] as used in GIL
[140], first-order logic
[203,204,205], decision lists as used in
GABIL [144] and GAssist [13], messy
encoding [172], ellipses [51] and
hyperellipses [57], hyperspheres [200],
convex hulls [187], tile coding [177] and a
closely related hyperplane coding [30,29], GP
trees [5,173,174], Boolean networks
defined by GP [38], support vectors [198],
edges of an Augmented Transition Network [170], Gene
Expression Programming [309], fuzzy rules (see
§3.6) and neural networks
[257,75,259,41,211,76,131,130].
GALE [194,193,197] has used particularly
complex representations, including the use of GP to evolve trees
defining axis-parallel and oblique hyper-rectangles [197],
and evolved prototypes which are used with a k-nearest-neighbour
classifier. The prototypes need not be fully specified; some
attributes can be left undefined. This representation has also been
used in GAssist [13].
There has been limited work with alternative action representations
including computed actions [278,186] and continuous
actions [308].
As we have seen there are many representations to chose
from. Unfortunately it is generally not clear which might be best for
a given problem or part of a problem. One approach is to let evolution
make these choices. This can be seen as a form of meta-learning in
which evolution adapts the inductive bias of the learner.
In [13,14] evolution was used to select
default actions in decision lists in GAssist. GAssist's initial
population was seeded with last rules which together advocated all
possible classes and over time evolution selected the most suitable of
these rules. To obtain good results it was necessary to encourage
diversity in default actions.
In GALE [193] evolution selects both classification
algorithms and representations. GALE has elements Cellular Automata
and Artificial Life: individuals are distributed on a 2-dimensional
grid. Only neighbours within 
cells interact: two neighbours may
perform crossover, an individual may be cloned and copied to a
neighbouring cell, and an individual may die if its neighbours are
fitter. A number of representations have been used: rule sets,
prototypes, and decision trees (orthogonal, oblique, and multivariate
based on nearest neighbor). Decision trees are evolved using GP while
prototypes are used by a k-nearest-neighbour algorithm to select
outputs. An individual uses a particular representation and
classification algorithm and hence evolutionary selection operates on
both. Populations may be homogeneous or heterogeneous and in
[197] GALE was modified to interbreed orthogonal and
oblique trees.
In the representational ecology approach [200] condition shapes were selected by evolution. Two Boolean classification tasks were used: a plane function which is easy to describe with hyperplanes but hard with hyperspheres, and a sphere function which has the opposite characteristics. Three versions of XCS were used: with hyperplane conditions (XCS-planes), with hyperspheres (XCS-spheres), and both (XCS-both). XCS was otherwise unchanged, but in XCS-both the representations compete due to XCS's pressure against overlapping rules [154]. In XCS-both planes and spheres do not interbreed; they constitute genetically independent populations, that is, species. In terms of classification accuracy XCS-planes did well on the plane function and poorly on the sphere function while XCS-sphere showed the opposite results. XCS-both performed well on both; there was no significant difference in accuracy compared to the better single-representation version on each problem. Furthermore, XCS-both selected the more appropriate representation for each function. In terms of the amount of training needed, XCS-both was similar to XCS-sphere on the sphere function but was significantly slower than XCS-plane on the plane function.
In [301] Wilson introduced an optimisation for Michigan
populations called macroclassifiers. He noted that as an XCS
population converges on the solution set many identical copies of this
set accumulate. A macroclassifier is simply a rule with an additional
numerosity parameter which indicates how many identical virtual
rules it represents. Using macroclassifiers saves a great deal of
run-time compared to processing a large number of identical rules.
Furthermore, macroclassifiers provide interesting statistics on
evolutionary dynamics. Empirically macroclassifiers perform
essentially as the equivalent `micro'classifiers [151].
Figure 9 illustrates how the rules m and m
in the top can be represented by m alone in the bottom by adding a
numerosity parameter.
LCS are interesting from an evolutionary perspective, particularly Michigan systems in which evolutionary dynamics are more complex than in Pittsburgh systems. Where Pittsburgh systems face two objectives (evolving accurate and parsimonious rulesets) Michigan systems face a third: coverage of the input (or input/output) space. Furthermore, Michigan systems have coevolutionary dynamics as rules both cooperate and compete. Since the level of selection (rules) is lower than the level of solutions (rulesets) researchers have attempted to coax better results by modifying rule fitness calculations with various methods. Fitness sharing and crowding have been used to encourage diversity and hence coverage. Fitness sharing is naturally based on inputs (see ZCS) while crowding has been implemented by making deletion probability proportional to the degree of overlap with other rules (as in XCS). Finally, restricted mating as implemented by a niche GA plays an important role in XCS and UCS (see §3.5.3).
strata, each
with the same class distribution as the entire set. A different
stratum is used for fitness evaluation each generation. On larger data
sets speed-up can be an order of magnitude. Windowing has become a
standard part of recent Pittsburgh systems applied to real-world
problems (e.g. [15,11,10]).
Many ensemble methods improve classification accuracy by sampling data in similar ways to windowing techniques which suggests the potential for both improved accuracy and run-time but this has not been investigated in LCS.
logically subsumes a rule
when matches a superset of the inputs matches and they
have the same action. For example, 00#0 subsumes 000
0 and 001 0. In XCS is allowed to
subsume if: i) logically subsumes , ii) is sufficiently
accurate and iii) is sufficiently experienced (has been evaluated
sufficiently) so we can have confidence in its accuracy.
Subsumption deletion was introduced in XCS (see [50]) and
takes two forms. In GA subsumption, when a child is created we
check to see if its parents subsume it, which constrains accurate
parents to only produce more general children. In action set
subsumption, the most general of the sufficiently accurate and
experienced rules in the action set is given the opportunity to
subsume the others. This removes redundant, specific rules from the
population but is too aggressive for some problems.
Note that XCS continues to refine its solution (population) after 100% performance is reached and that it finds the minimal representation (at the point where %[O] reaches the top of the figure) but that continued crossover and mutation generate extra transient rules which make the population much larger.
While credit assignment in Pittsburgh LCS is a straightforward matter of multi-objective fitness evaluation, as noted in §3.5.3 it is far more complex in Michigan systems with their more complex evolutionary dynamics. Credit assignment is also more complex in some learning paradigms, particularly reinforcement learning, which we will not cover here. Within supervised learning credit assignment is more complex in regression tasks than in classification. These difficulties have been the major issue for Michigan LCS and have occupied a considerable part of the literature, particularly prior to the development of XCS which provided a reasonable solution for both supervised and reinforcement learning.
In older (pre-1995) reinforcement learning LCS fitness is proportional to the magnitude of reward and is called strength. Strength is used both for conflict resolution and as fitness in the GA (see e.g. ZCS [300]). Such LCS are referred to as strength-based and they suffer from many difficulties with credit assignment [154], the analysis of which is quite complex. Although some strength-based systems incorporate accuracy as a component of fitness, their fitness is still proportional to reward. In contrast, the main feature of XCS is that it adds a prediction parameter which estimates the reward to be obtained if the action advocated by a rule is taken. Rule fitness is proportional to the accuracy of reward prediction and not to its magnitude which avoids many problems strength-based systems have with credit assignment. In XCS accuracy is estimated from the variance in reward and since overgeneral rules have high variance they have low fitness. Although XCS has proved robust in a range of applications, a major limitation is that the accuracy estimate conflates several things: i) overgenerality in rules, ii) noise in the training data and iii) stochasticity in the transition function in sequential problems. In contrast, strength-based systems may be less affected by noise and stochasticity since they are little affected by reward variance. See [154] for analysis of the two approaches.
![\begin{figure}\begin{center}
\begin{tabular}{\vert ccc\vert c\vert} \hline
\mu...
...\rightarrow$}\condWorker 1] \ \hline
\end{tabular}
\end{center}\end{figure}](img15.png)
![\begin{figure}\begin{center}
\begin{tabular}{c c c c} \hline
{\bf Rule} & {\bf...
... 001110] & \condWorker 1] & 100.0 & 1
\end{tabular} \end{center}
\end{figure}](img19.png)
