Classifiers that approximate functions.
A classifier system, XCSF, is introduced in which the prediction estimation mechanism is used to learn approximations to functions. The addition of weight vectors to the classifiers allows piecewise-linear approximation, where the classifier's prediction is calculated instead of being a fixed scalar. The weight vector and the classifier's condition co-adapt. Results on functions of up to six dimensions show high accuracy. The idea of calculating the prediction leads to the concept of a generalized classifier in which the payoff prediction approximates the environmental payoff function over a subspace defined by the classifier condition and an action restriction specified in the classifier, permitting continuous-valued actions.
Introduction
There is considerable recent research on the properties and performance of the learning classifier
system XCS (Wilson 1995; Butz and Wilson 2001). Areas of interest include data
mining (e.g. Bernad'o, Llor'a, and Garrell 2001), generalization over inputs (Butz and Pelikan
2001), self-adaptation of learning parameters (Hurst and Bull 2001), and learning in
non-Markov environments (Lanzi and Wilson 2000), among others. One area that has not
received attention is function approximation, which XCS's accuracy-based fitness makes pos-
sible. This paper demonstrates XCS as a function approximator, then shows how, somewhat
surprisingly, this leads to a generalized classifier structure that embraces traditional classifier
formats and, for the first time, permits classifiers capable of continuous-valued actions.
XCS's classifiers estimate payoff. That is, the rules (classifiers) evolved by XCS each
keep a statistical estimate of the payoff (reward, reinforcement) expected if the classifier's
condition is satisfied and its action is executed by the system. Moreover, the classifiers form
quite accurate payoff estimates, or predictions, since the classifiers' fitnesses under the genetic
algorithm depend on their prediction accuracies. In effect, XCS approximates the mapping
is the set of possible inputs, A the system's set of available actions
(typically finite and discrete), and P is the set of possible payoffs. If attention is restricted
to a single action a i 2 A, the mapping has the form X \Theta a i ) P, which is a function from
input vectors x to scalar payoffs. Thus the system approximates a separate function for each
a i .
In the reinforcement learning contexts in which classifier systems are typically used, the
reason for forming these payoff function approximations is to permit the system to choose,
for each x, the best (highest-paying) action from A. However, there are contexts where the
output desired from a learning system is not a discrete action but a continuous quantity.
For instance in predicting continuous time series, the output might be a future series value.
In a control context, the output might be a vector of continuous quantities such as angles
or thrusts. Apart from classifier systems based on fuzzy logic (Valenzuela-Rend'on 1991;
Bonarini 2000), there are none which produce real-valued outputs. Our hypothesis was that
the payoff function approximation ability of XCS could be adapted to produce real-valued
outputs, as well as be used for function approximation in general applications.
To test this we adapted XCS to learn approximations to functions of the form
where y is real and x is a vector with integer components x . The results demonstrated
approximation to high accuracy, together with evolution of classifiers that tended to distribute
themselves efficiently over the input domain. The research fed back, however, on
basic classifier concepts. It was realized that thinking of a classifier as a function approximator
implied a new, generalized, classifier syntax that covered most existing classifier formats
and included not only discrete-action classifiers but ones with continuous actions.
The next section describes modifications of XCS for function approximation. Section
3 has results on a simple piecewise-constant approximation. In Section 4 we introduce a
new classifier structure that permits piecewise-linear approximations. Results on simple
functions are shown in Section 5. In Section 6 we demonstrate accurate approximation of a
six-dimensional function. Section 7 presents the generalized classifier syntax and examines
its use. The final section has our conclusions and suggestions for future work.
2 Modification of XCS
XCS was modified in two respects (later, a third). The first was to adapt the program
for integer instead of binary input vectors. The second, very simple, was to make the
program's payoff predictions directly accessible at the output and to restrict the system to
a single (dummy) action. The resulting program was called XCSF. (We omit a description
of basic XCS, but refer the reader to Wilson (1995), Wilson (1998), and the updated formal
description in Butz and Wilson (2001) that XCSF follows most closely.)
The changes to XCS for integer inputs were as follows (drawn from Wilson (2001)). The
classifier condition was changed from a string from f0,1,#g to a concatenation of "interval
predicates", int are integers. A classifier
matches an input x with attributes x i if and only if l i - x i - u i for all x i .
Crossover (two-point) in XCSF operates in direct analogy to crossover in XCS. A crossover
point can occur between any two alleles, i.e., within an interval predicate or between pred-
icates, and also at the ends of the condition (the action is not involved in crossover). Mu-
tation, however, is different. The best method appears to be to mutate an allele by adding
an amount \Sigmarand(m 0 ), where m 0 is a fixed integer, rand picks an integer uniform randomly
from (0; m 0 ], and the sign is chosen uniform randomly. If a new value of l i is less than the
minimum possible input value, in the present case 0, the new value is set to 0. If the new
value is greater than u i , it is set equal to u i . A corresponding rule holds for mutations of u i .
The condition of a "covering" classifier (a classifier formed when no existing classifier
matches an input) has components l
limited by the minimum possible input value, and each u limited by the
maximum possible input value; rand 1 picks a random integer from [0; r 0 ], with r 0 a fixed
integer.
For the subsumption deletion operations, we defined subsumption of one classifier by
another to occur if every interval predicate in the first classifier's condition subsumes the
corresponding predicate in the second classifier's condition. An interval predicate subsumes
another one if its l i is less than or equal to that of the other and its u i is greater than or equal
to that of the other. For purposes of action-set subsumption, a classifier is more general than
another if its generality is greater. Generality is defined as the sum of the widths u
of the interval predicates, all divided by the maximum possible value of this sum.
3 Piecewise-Constant Approximation
The simplest way to approximate the function with XCSF is to let x be the input
and y the payoff. After sufficient sampling of the input space, the system prediction (a
fitness-weighted average of matching classifiers' predictions) should, given an x, more or less
accurately predict the corresponding y. In all XCS-like systems the fitness of a classifier
depends on its accuracy of prediction, so that XCSF should converge to a population of
classifiers that, over their respective input ranges, predict payoff well. The closeness of the
approximation should be controllable with the error threshold ffl 0 , as follows. A classifier
with prediction error ffl 1 has higher accuracy than a classifier with error ffl 2 if
and Wilson 2001). Since classifier fitness depends on accuracy, classifiers with lower errors
will win out in the evolutionary competition. However, by definition, classifiers with errors
less than ffl 0 have constant fitness, so no further fitness pressure applies. Thus ffl 0 should limit
the closeness of the approximation.
It is important that besides evolving accurate classifiers, the system employ the classifiers
efficiently over the input domain. In slowly-changing or low-gradient regions of the function
we would hope to evolve classifiers with relatively large interval predicates. The function
value, and thus a given classifier's error, would change relatively little over such regions; so,
as in XCS, a tendency toward accurate, maximally general conditions (Wilson 1995) should
cause the interval predicates to expand. Conversely, we should expect classifiers with small
interval predicates where the function is changing rapidly. We also hope for an efficient
distribution of classifiers over the domain in the sense that the tiling minimizes overlaps
between classifier predicates.

Figure

shows typical results from an experiment in which XCSF approximated the
function over the interval 0 - x ! 100. (In all experiments reported
here, the input value range was [0,99].) Plotted are XCSF's prediction for each possible x
as well as the function itself.
The system learned from a dataset consisting of 1000 x; y pairs, with x chosen randomly
and y the corresponding function value. In the experiment, a pair was drawn randomly
from the dataset, its x value presented to XCSF as input, and the y value used as reward
or reinforcement. XCSF formed a match set [M] of classifiers matching x and calculated
the system prediction for each possible action in the usual way; since there was only one,
dummy, action, just one system prediction was calculated and that became the system's
output. An action set [A] was formed consisting of classifiers in [M] having the dummy
action (i.e., all classifiers in [M]), and the predictions of the classifiers in [A] were adjusted
using the reward, y, in the usual way; the other classifier parameters were also adjusted. A
genetic algorithm was run in [A] if called for. This cycle was repeated 50,000 times after
x
Prediction

Figure

1: Piecewise-constant approximation to the parabola function
which the plot in Figure 1 was obtained by sweeping through all possible values of x and
recording the resulting system predictions.
Parameter settings for the experiment were as follows, using the notation of Butz and
population size learning rate
fitness power
probability deletion threshold ' del = 50, fitness fraction for accelerated deletion
In addition: mutation increment covering interval r
subsumption was enabled, with time threshold '
Several aspects of Figure 1 are of interest. The Prediction curve has a "staircase" appearance
typical of a piecewise-constant approximation. The height of the major "steps" varies
between about 1000 and 2000. Examination of individual steps indicates an average error
roughly consistent with the value of ffl 0 , suggesting that ffl 0 is controlling the closeness of the
approximation. The width of the steps is, again roughly, wider in the "flatter" part of the
function and narrower in the steep part. Finally, it is significant that the Prediction curve
indeed takes the form of a staircase, instead of being smoother. Long flat "steps" suggest
that one set of classifiers is in control (forms [M]) after which, on the next step, another
set takes over. This in turn suggests a tendency toward efficient distribution of classifier
resources over the domain.

Figure

another perspective. It is a listing of the (macro)classifiers of the population
at the end of the experiment, 15 in all. Shown are each classifier's condition, prediction, error,
fitness, and numerosity. Note that most classifiers with substantial fitnesses have errors less
than ffl 0 . A special graphic notation is used to represent the condition. Since x has just
one component, the condition contains just one interval predicate. The possible range of x,
0-99, is divided into 20 equal subranges. An interval predicate is indicated by a cluster of
"O"s that covers its range. If an interval predicate entirely covers a subrange, e.g., 35-39,
an "O" is placed at that range's position. If the interval predicate covers some of but less
than the whole of a subrange, a small "o" is put there. This notation has been found more
perspicuous than using the raw numbers.
Note how, consistent with Figure 1, the classifier conditions are larger toward the beginning
of the domain, where the function slope is lower. It is also interesting that the
classifiers with higher fitnesses and numerosities cover the domain without a great deal of
overlap. These classifiers dominate the calculation of the system prediction, since the latter
CONDITION PRED ERR FITN NUM
0.oO- 8992. 283.796 31
1.Oo.- 7876. 322.906
2.oOO.- 6162. 503.564 20
3.OOO.- 5990. 570.188 9
4.oOOO.- 5988. 569.028 1
5.oOOo.- 5668. 413.075 3
6.oOO.- 5534. 281.090 3
8.oOOOo.- 5053. 524.002 1
9.oOOo.- 4861. 465.054 5
10.OOOo.- 3854. 468.862
12.OOOOO.- 1359. 377.358
13. -OOOOOOOOOo.- 821. 378.372 15
14. -OOOOOOOOo.- 820. 377.371 15

Figure

2: Classifiers from experiment of Figure 1. (PREDiction, ERRor, FITNess, NUMerosity.)
is a fitness-weighted average of the predictions of matching classifiers. Because they dom-
inate, the Prediction curve takes the form of a staircase. Apart from the presence of the
remaining, lower fitness, classifiers, the distribution of resources over the domain is thus
relatively efficient.
In sum, XCSF succeeds in approximating the function in accordance with a stated error
criterion (confirmed for additional values of ffl 0 ) and the classifiers are employed reasonably
well. Still, a piecewise-constant approximation is primitive compared with an approximation
where the approximating segments more closely follow the function's contour. The simplest
such approach is a piecewise-linear approximation. But how could a piecewise-linear approximation
be done with a classifier system?
4 Piecewise-linear Approximation
Traditionally, a classifier's prediction is a number intended to apply for all inputs x that
satisfy its condition. However, for function approximation, it would be desirable if the
prediction could vary over the condition's domain, since the function being approximated
generally varies. In effect, the prediction itself should be a function, the simplest form of
which would be a linear polynomial in the input components, call it h(x). The function h(x)
would substitute for the classifier's traditional (scalar) prediction, p. Then, given an input
x, each matching classifier would calculate its prediction by computing h(x).
For approximating a one-dimensional function f(x), h(x) would be a two-term polynomial
In this case, w 1 can be thought of as the slope of an approximating
straight line, with w 0 its intercept. For an n-dimensional f(x),
is a weight vector (w is the input vector x augmented by a constant
In this case h(x) computes a hyperplane approximation to
f(x). Classifiers would have different weight vectors w since in general the domains of their
conditions differ.
Of course, the classifiers' weight vectors must be adapted. If classifiers are to predict
with a given accuracy, the coefficients w i of their weight vectors must be appropriate. One
approach is to use an evolutionary algorithm. The weight vector would be evolved along with
the classifier condition. For this, the w i could be concatenated with the interval predicates
of the condition and the whole thing evolved as a unit. Or, it might be preferable to use
separate processes. For example, the Evolutionsstrategie might be more suitable than the
GA for the weight vector because optimizing the weights of a linear network is unimodal,
and ES is generally better at unimodal tasks. In the present work, however, we did not use
an evolutionary technique for the weight vector but instead adapted it using a modification
of the delta rule (Mitchell 1997).
The delta rule is given by
where w i and x i are the ith components of w and x 0 , respectively. In the quantity
is the output, in the present case the classifier prediction, and t is the target, in this case the
correct value of y according to is the amount by which the prediction
should be corrected (the negative of the classifier's instantaneous error). Finally, j is the
correction rate. The delta rule says to change the weight proportionally to the product of
the input value and the correction.
Notice that correcting the w i in effect changes the output by
Because jx 0 j 2 is factored in, it is difficult to choose j so as to get a well-controlled overall rate
of correction: j too large results in the weights fluctuating and not converging; if j is too
small the convergence is unnecessarily slow. After some experimentation with this issue, we
noticed that in its original use (Widrow and Hoff 1988), the correction rate was selected so
that the entire error was corrected in one step; this was possible, however, because the input
vector was binary, so its absolute value was a constant. In our problem, reliable one-step
correction would be possible if a modified delta rule were employed:
Now the total correction would be strictly proportional to (t \Gamma o) and could be reliably
controlled by j. For instance, would give the one-step correction of Widrow and
Hoff. In the experiments that follow, we used the modified delta rule with various values of
Use of a delta rule requires selection of an appropriate value for x 0 , the constant that
augments the input vector. In tests, we found that if x 0 was too small, weight vectors would
not learn the right slope, and would tend to point toward the origin-i.e. w
that x i is a factor in the above equation for \Deltaw i . If x 0 is small compared with the other x i ,
then adjustments of w 0 will tend to be swamped by adjustments of the other w i , keeping w 0
small. Choosing x 100-the same order of magnitude as the other x i -appeared to solve
the problem.
For piecewise-linear approximation, no changes were necessary to XCSF except for addition
of the weight vectors to the classifiers, and provision for calculation of the predictions
and application of the modified delta rule to the action set classifiers on every time-step. In
a classifier created by covering, the weight vector was randomly initialized with weights from
offspring classifiers inherited the parents' weight vectors. Both policies yielded
performance improvements over other initializations. In the experiments, most parameter
settings were the same as those given in Section 3; differences will be noted. Settings of the
new parameter, j, will be given.
x
Prediction
"2-line"

Figure

3: Piecewise-linear approximation to piecewise-linear function "2-line". ffl
CONDITION PRED ERR FITN NUM
0.oOOOOOOOOOO- 4705. 19.158 62
1.oOOOOOOOOO- 4670. 0.706 274
2.oOOOOOOOOO- 4670. 0.044
4. -OOOOOOOOOOo.- 3057. 16.005 6
5. -OOOOOOOOOOo.- 3050. 0.676 247
6. -OOOOOOOOOo.- 3050. 0.377 164

Figure

4: Classifiers from experiment of Figure 3
5 Tests on Simple Functions
Preliminary testing was carried out approximating functions that were themselves linear or
piecewise linear. For example, tests were done on the function "2-line", defined as
Parameters for the experiment were the same as previously, except for
0:4. The approximation obtained (Figure was so close that the
plots of the prediction and the function itself are difficult to distinguish visually.

Figure

4 shows the seven classifiers at the end of the run 1 . They are clearly divided into
one group for the upper segment of the function and another for the lower segment. The
dominant classifier in the upper group, no. 1, has error zero and a predicate covering the
interval 52-99 (inclusive). In the lower group, the dominant classifier, no. 5, also has error
zero and covers the interval 0-50.
Raising the error threshold caused the approximation to deteriorate. In Figure 5, ffl
The prediction curve seems to ignore the break at reflecting the change in slope only
gradually. The classifier list showed several that bridged the break point, with predictates
from about 30 to 70. Evidently, with a larger error threshold, the system was not forced, as
in

Figure

3, to evolve classifiers that corresponded closely to the two function segments.
1 The prediction values represent the most recent weight-vector calculation and are not particularly significant. As in Section
3, this and all following experiments were run for 50,000 input cycles.
x
Prediction
"2-line"

Figure

5: Approximation to "2-line" with ffl
x
Prediction

Figure

Piecewise-linear approximation to parabola with ffl

Figures

6 through 12 show typical results on parabola and sine functions. Parameters
were the same as in the "2-line" experiments except (an insignificant difference).
Values for ffl 0 are given in the captions. The two values chosen for each function are equivalent
to 5% and 1% of the functions' ranges. To highlight the dominant classifiers and save space,
the classifier lists include only the highest-fitness classifiers; the full populations are three or
four times larger.
While the parabola figures show good linear approximations with a small number of
classifiers, it is somewhat surprising that-unlike the piecewise-constant case-the sizes of
the interval predicates do not seem to reflect the function's slope. Perhaps for piecewise-linear
approximation a different analysis is in order: predicate length may be more related
to curve straightness than steepness. For the sinewaves, the approximation overshoots the
peaks when ffl 0 is large (Figure 10), but this effect disappears with smaller values and the
curve is quite nicely matched (Figure 12). Figure 11 suggests that the system divides the
approximation into classifiers for the beginning, middle, and end of the curve.
CONDITION PRED ERR FITN NUM
0.OOOOOOOOOOO- 9375. 246.286 151
1.OOOOOOOOOOOOOO- 9014. 431.122 54
2.oOOOOOOOOOOOOOO- 8985. 432.176 80
3.oOOOOOOOOOOOOOO- 8906. 456.037 37
4.oOOOOOOOOOOOOOOO- 8744. 456.035 33
5. -OOOOOOOOOOOOOOo.- 4184. 379.077 35
6. -OOOOOOOOOOOOOO.- 3756. 247.258 122
7. -OOOOOOOOOOOOOo.- 3564. 256.066
8. -OOOOOOOOOOOOo.- 3193. 262.035
9. -OOOOOOOOOOo.- 2250. 204.211 125

Figure

7: High fitness classifiers from experiment of Figure 6.2000600010000
x
Prediction

Figure

8: Piecewise-linear approximation to parabola with ffl
CONDITION PRED ERR FITN NUM
0.oOOOOOO- 9591. 77.823 212
1.oOOOOOO.- 7734. 75.081 21
2.oOOOOOOO.- 7687. 89.035 9
3.oOOOOOOo.- 4438. 79.731 184
4.oOOOOo.- 3149. 26.123 41
6.oOOOOOo.- 1621. 61.072 13
7. -OOOOOOO.- 967. 104.607 219
8. -OOOOOOo.- 749. 85.074

Figure

9: High fitness classifiers from experiment of Figure 8.
x
Prediction

Figure

10: Piecewise-linear approximation to sine function with ffl
CONDITION PRED ERR FITN NUM
1. -OOOOOo.- 118. 10.083 22
2. -OOOOO.- 111. 7.572 158
3.OOOOo.- 66. 5.032 15
4.oOOOO-20. 4.792 173
5.oOOOOOO-23. 12.101 78
6.OOOOOOOOOOo.-130. 8.888 234

Figure

11: High fitness classifiers from experiment of Figure 10.
x
Prediction

Figure

12: Piecewise-linear approximation to sine function with ffl 2.
Instances
System

Figure

13: System error/100 and population size/3200 for approximation to six-dimensional "rms" function.
1.
6 Multi-dimensional Input
XCSF was initially tested on functions of more than one variable by letting
a linear function, i.e., a hyperplane function. The system rapidly evolved solutions with one
or a few classifiers and arbitrary accuracy. This was expected, since the classifiers' weight
vectors are effectively linear functions. To test XCSF on a multi-dimensional nonlinear
function, we chose, somewhat arbitrarily,
of "rms" function. Experiments with went well, so Parameters
were the same as previously, except 1:0. The
error threshold ffl of the range). In contrast to previous experiments in which
instances were chosen randomly from a fixed data set, instances were picked randomly from
the domain. Figure 13 plots the system error and population size.
Starting initially very high, the system error (a moving average of the absolute difference
between XCSF's prediction and the actual function value) fell rapidly to less than 1 (or .01 as
plotted on this graph). The population size-in macroclassifiers-rose quickly to about 2400
and stayed there. The system seemed to have little difficulty approximating the function to
within though quite a few classifiers were required.
7 Generalized Classifiers
7.1 Definition
In XCS, as in other classifier systems, the classifier prediction is a scalar, and the system
adapts the classifier conditions and the prediction scalars to find accurate classifiers that are
as general as possible. In XCSF, the prediction was replaced by a weight vector computing
a linear function, leading to a more powerful and subtle co-adaptation of the condition
and the prediction. As an extreme but instructive example, XCSF can approximate a very
high-dimensional linear function with O(1) classifiers, far less than required using scalar
predictions.
What do the results with XCSF suggest for classifier architecture? The essential novelty
in XCSF is that the prediction is calculated, instead of being a fixed scalar. The prediction is
a linear function of x, the input vector. More precisely, the prediction function approximates
a desired output function over the input subdomain defined by the classifier's condition.
Other classifiers approximate other parts of the desired output function. Taken together,
the classifiers evolve to approximate, within a specified error criterion, the input-output
mapping defined by y
In the Introduction it was noted that XCS approximates the mapping X \Theta A ) P, which
includes actions as well as inputs. But this is just another way of saying that the desired
output y (a payoff prediction) is a function of both the input x and the action a taken by
the system. We can certainly imagine approximating y with a linear function of both x and
a. Further, we can define a generalized classifier
that expresses these ideas. The generalized classifier says: "Within the subdomain of X \Theta A
defined by the truth function t(x) and the action restriction r(a), the payoff is approximated
by the prediction function p(x; a)."
The components of (4) are as follows. The truth function t(x) defines the subdomain of X
within which the classifier applies ("matches", in the traditional terminology). For example
in a binary input space t(x) could be simply "01#0", meaning of course the set of strings
f0110, 0100g. Or t(x) could be an S-expression such as (? x 1 x 3 ) (Lanzi 1999). It could
also be a representation of a neural network (Bull and O'Hara 2001). Whatever its specific
form, a classifier's t(x) determines, given an x, whether or not the classifier applies.
The action restriction r(a) defines a range of effector values. For example, r(a) might
specify a range of rudder angles between -10 and +34 degrees. More generally, if there were
more than one effector (e.g. rudder, aileron, throttle) r(a) is an expression that defines a
subdomain of the effector space: a set of effector vectors each taking values, e.g., rudder and
aileron angles and throttle positions. In a very simple special case, r(a) would just name an
action, such as "turn left", as occurs in traditional classifier systems. Whatever its specific
form, a classifier's r(a) specifies an allowed set of effector values should the system decide to
act according to this classifier, as will be described.
Finally, the prediction function p(x; a) serves to calculate the classifier's payoff prediction
just in case t(x) is satisfied and the system intends to take an action a (generally a vector)
from r(a). According to its form-e.g. a linear expression in x and a or a combination of
other basis functions-p(x; a) calculates a prediction, which is of course an approximation
of expected payoff to within a given error criterion. In XCS, of course, p(x; a) is simply a
constant. Consider, however, a robot taking fixed-length steps in a plane, but able to turn
through any angle. If the robot were supposed to learn to orient and move toward a goal,
environmental payoff would probably depend on a (and maybe x), so that the prediction
function p(x; a) would depend at least on a. More generally, the prediction function of a
given classifier would depend on some or all of the input and effector variables.
7.2 Operation
How would generalized classifiers be used in the system's performance, reinforcement, and
discovery cycles? In performance, the main step would be to calculate a payoff prediction for
each classifier that matches the input x. Since the prediction function p(x; a) also depends
on a, what value for a should be used? The answer, if the system is in an exploit mode (i.e.,
seeking to act on its best information so as to maximize payoff), is to choose a such that
this classifier's payoff is maximized. Thus
a
a2r(a)
where a   is the chosen action and x   is the current input. In many situations this is not a
lengthy calculation. For instance, if p(x; a) is linear in x and a, e.g. of the form
where the a i correspond to separate effectors, the maximum is obtained by choosing each
a i so that the associated term is maximized. Once it had calculated a   and the associated
each classifier in the match set [M], the system would carry out the action whose
prediction was highest.
If, on the other hand, the system is in an explore mode (seeking to try new actions in hopes
of gaining new information about environmental payoff), a   for each classifier in [M] would
be selected at random from r(a), or according to some other exploration regime. The system
would then randomly choose one of the resulting actions for execution in the environment.
The reinforcement or update cycle would consist of updating the classifier whose action
was taken (often, updating occurs only in explore mode). The update would occur exactly as
in XCSF: the prediction function would be adjusted according to the difference between its
prediction and the actual payoff received; then the error and fitness values would be adjusted
as in XCS.
The discovery cycle would also occur as in XCSF, except that genetic operators, besides
acting on the truth function t(x), would also act on the action restriction r(a). For this the
syntax of r(a) must of course be amenable to the genetic operators. For example, if the
action restriction was of the form
(v
and this was encoded by concatenating the the genetic operators would apply
exactly as they do in XCSF.
7.3 A Special Case
To illustrate the generality of (4), it is interesting to see how the Boolean multiplexer problem
(Wilson 1995) might be represented. As is quite well known, in a typical learning experiment
on the 6-multiplexer, XCS evolves pairs of classifiers such as
Each is accurate and maximally general (i.e. can't be generalized further without losing
accuracy). There are two classifiers for the same condition because the two possible actions-
1 or 0-result in different payoffs, and XCS evolves accurate classifiers whether or not they
are "correct" (payoff 1000) or "wrong" (payoff 0).
In the generalized representation, however, the above pair would be covered by a single
classifier
where r(a) is "#", meaning a can take on either 1 or 0, and p(x; a) is the linear expression
1000a. It can be seen that substituting 1 or 0 in p(x; a) results in the correct payoff for that
action. Thus, in this example, the binary-input, discrete action, step-wise payoff case is fully
captured by the generalized representation.
7.4 Continuous Actions
In what sense does the generalized classifier of (4) lead to a system capable of continuous
actions? As discussed in Sec. 7.2 a classifier is in principle capable of advocating any action
value permitted by r(a). But in practice, when the system is in exploit mode, the classifier
will choose just the action that maximizes its prediction. Thus for a given state of the
classifier system a certain discreteness of actions is maintained. However, the degree of
discreteness depends on the quality of the prediction function approximations: the better
the approximations, the less discretized the action space, since each classifier will cover a
smaller portion of that space. Therefore, one can perhaps say that the generalized classifier
permits continuous actions in the limit.
Why are continuous actions desirable in the first place? It is desirable for a system to
be able to choose actions that maximize the payoff available from the environment. In
continuous environments, payoff-maximizing actions (precise angles of turns, etc.) will be
difficult for a system designer to anticipate, and so it is important that the system can
choose them itself to within the limits of its resources-e.g. the quality of approximation
permitted by its population size. In general this will be better than any predefined set of
fixed actions. However, at some point the actions chosen by the generalized classifier system
will be fine-grained enough, so that further resolution-or perfect continuity-will not add
significantly to payoff returns.
8 Summary and Conclusions
This paper introduced a classifier system, XCSF, designed to learn approximations to func-
tions. The prediction estimation mechanism was used to form the approximations: given
an input vector x, the value y of the function to be approximated was treated as a payoff
to be learned. In its first incarnation, XCSF produced piecewise-constant approximations.
A more advanced version added a weight vector to each classifier, permitting the approximation
to be piecewise-linear. Tests on simple one-dimensional functions yielded arbitrarily
close approximations, according to the setting of an error parameter. The system tended
to evolve classifiers that distributed themselves reasonably efficiently over the function's do-
main, though some overlap occurred together with the presence of a moderate number of
redundant low-fitness classifiers. In limited tests on a six-dimensional nonlinear function,
XCSF rapidly formed highly accurate approximations, though the number of classifiers required
was much larger than for the one-dimensional functions.
Future work should continue with multi-dimensional functions, to determine the tech-
nique's general viability and estimate its complexity in terms of learning time and resources
(classifiers) required. Since XCSF approximates linear functions effortlessly, regardless of
dimensionality, it is likely that the complexity will relate to the degree of "smoothness" or
"flatness" in hyperspace that the function exhibits. Comparisons should be made with fuzzy
classifier systems, which appear to be quite different in concept: the output of a fuzzy system
is computed jointly by more than one classifier, whereas in XCSF an accurate output can in
principal be computed by just one.
Function approximation with XCSF could be useful for on-line learning of any function
or mapping from a vector of input values to an output value. An example would be financial
time-series prediction, where a future price is presumably an approximable function of known
prices or other quantities at earlier times in the series.
Piecewise-linear function approximation in XCSF is based on the idea of calculating a
classifier's prediction, and this leads to the concept of a generalized classifier in which the
condition is a truth function t(x) of the input x and the prediction is an approximation
function p(x; a) that depends on x and an action a. Such a classifier would apply in the
subspace of the X \Theta A ) P mapping defined by t(x) and an action restriction r(a) specified
in the classifier. Given x, the best action to take would be determined by maximizing
a) over the restriction's range. This architecture would appear to permit the system to
evolve classifiers that take actions that optimally match the environment's payoff landscape-
instead of generally suboptimal actions from a pre-specified finite set.
Since we have only presented generalized classifiers conceptually, the next step is to do
experiments, especially in domains where they would appear to have advantages. The first
advantage is of course continuous vs. discrete actions, so tests in continuous robotic environ-
ments, either actual or simulated, are in order. The second advantage lies in the potential
generalization power of generalized classifiers. If the payoff function relates to x and a in a
way that is readily handled by piecewise-linear approximation, then a generalization advantage
should be expected compared with conventional XCS systems. This means savings in
space complexity (population size) as well as increased transparency in the system's model.
Furthermore, approximation bases other than linear should be tried where promising.

Acknowledgement

This work was supported in part by NuTech Solutions Inc.



--R

XCS and GALE: A comparative study of two learning classifier systems with six other learning algorithms on classification tasks.

An Introduction to Learning Fuzzy Classifier Systems.
A neural rule representation for learning classifier systems.
Analyzing the evolutionary pressures in XCS.


Extending the Representation of Classifier Conditions Part II: From Messy Coding to S-Expressions

Toward optimal classifier system performance in non-Markov environments
Machine Learning.

The Fuzzy Classifier System: a Classifier System for Continuously Varying Variables.
Adaptive switching circuits.
Classifier Fitness Based on Accuracy.
Generalization in the XCS classifier system.
Genetic Programming
Mining Oblique Data with XCS.
--TR

--CTR
Lashon B. Booker, Adaptive value function approximations in classifier systems, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C.
Amin Nikanjam , Adel Rahmani, An anticipatory approach to improve XCSF, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Daniele Loiacono , Pier Luca Lanzi, Improving generalization in the XCSF classifier system using linear least-squares, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C.
Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, XCS with computed prediction in multistep environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
Hau Trung Tran , Cdric Sanza , Yves Duthen , Thuc Dinh Nguyen, XCSF with computed continuous action, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Classifier prediction based on tile coding, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Prediction update algorithms for XCSF: RLS, Kalman filter, and gain adaptation, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
Pier Luca Lanzi , Stewart W. Wilson, Using convex hulls to represent classifier conditions, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Martin V. Butz , Pier Luca Lanzi , Stewart W. Wilson, Hyper-ellipsoidal conditions in XCS: rotation, linear approximation, and solution structure, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Pier Luca Lanzi , Daniele Loiacono, Classifier systems that compute action mappings, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Daniele Loiacono , Andrea Marelli , Pier Luca Lanzi, Support vector regression for classifier prediction, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Pier Luca Lanzi , Daniele Loiacono, Standard and averaging reinforcement learning in XCS, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Martin V. Butz, Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
Martin V. Butz , Martin Pelikan, Studying XCS/BOA learning in Boolean functions: structure encoding and random Boolean functions, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Generalization in the XCSF Classifier System: Analysis, Improvement, and Extension, Evolutionary Computation, v.15 n.2, p.133-168, Summer 2007
Jan Drugowitsch , Alwyn M. Barry, A formal framework and extensions for function approximation in learning classifier systems, Machine Learning, v.70 n.1, p.45-88, January   2008
Jorge Muruzbal, A probabilistic classifier system and its application in data mining, Evolutionary Computation, v.14 n.2, p.183-221, June 2006
function approximation;continuous actions;generalized classifier;classifier systems