A Learning Classifier Systems Model - Design and Analysis of Learning Classifier Systems - page 33

y , y 1 = i |

and defined as L 1 ( y , y ) y i −

,canbeused.TheL 1 norm has
the advantage that it only increases linearly with distance and is therefore more
resilient to outliers. Using the L 2 norm, on the other hand, makes analytical
solutions easier.
All LCS developed so far only handle univariate regression, which is characte-
rised by a 1-dimensional output space, that is

≡ y i |

Y R

= . Consequently, the output

vectors y collapse to scalars y

∈ R

and the output matrix Y becomes a column

N . For now we will also follow this convention, but will return to
multivariate regression with D Y > 1 in Chap. 7.

vector y ∈ R

3.1.3 Classification

The task of classification is characterised by an input space that is mapped into
a subset of a multidimensional real-valued space

D X of D X dimensions,

X⊆ R

and an output space Y that is a finite set of labels, mapped into a subset of the

natural numbers . Hence, the inputs are again real-valued column vectors

x =( x 1 ,...,x D X ) T , and the outputs are natural numbers y . The elements of
the input vectors are commonly referred to as attributes , and the outputs are
called the class labels . An alternative formulation is for the output space to be
Y

Y⊂ N

D Y ,where D Y is the number of classes. Rather than using natural
numbers to represent the correct class label, the output is given by a vector y
of 0s and a single 1. That 1 indicates which class the vector represents, with
y =(1 , 0 , 0 ,... ) T

= { 0 , 1 }

standing for class 1, y =(0 , 1 , 0 ,... ) T

representing class 2,

and so on.
XCS approaches classification tasks by modelling them as regression tasks:
each input vector x is augmented by its corresponding class label y ,givenbya
natural number, to get the new input vector x =( ,y ) T that is mapped

into some positive scalar that we can without loss of generality assume to be
1. Furthermore, each input vector in the training set is additionally augmented
by any other valid class label except for the correct one (that is, as given by
y ) and maps into 0. Hence, the new input space becomes

x T

− −

X

D X

⊂ R × N ,and

Y =[0 , 1]. Consequently, the correct class for a new
input x can be predicted by augmenting the input by each possible class label
and choosing the class for which the prediction of the model is closest to 1.
This procedure is not particularly ecient as it needlessly increases the size of
the input space

the output space becomes

X and subsequently also complicates the task of finding the best
localisation of the classifiers in that space. UCS [161] is an XCS-derivative spe-
cialised on classification that handles this tasks more eciently but still operates
on the label-augmented input space X . A more ecient alternative formulation

that does not require this augmentation is discussed in Sect. 4.2.2.

3.1.4 Sequential Decision

A sequential decision task, formulated as an MDP, requires an agent to maximise
the long-term reward it receives through the interaction with an environment.
At any time, the environment is in a certain state within the state space X .A