An Algorithmic Description - Design and Analysis of Learning Classifier Systems - page 193

considering the result of the MCMC search with a superior 29 . 39,

as shown in Fig. 8.15. The discovered model is clearly better, which is also re-
flected in a higher p (

L ( q ) − ln K ! ≈−

). Note, however, that this model was not discovered
after all restarts of the MCMC algorithm. Rather, model structures with 6 or 7
classifiers were sometimes preferred, as Fig. 8.15(b) shows. This indicates that
a further increase of the problem complexity will very likely cause the MCMC
search to fail as well.

M|D

8.4 Improving Model Structure Search

As previously emphasised, the model structure search procedures introduced in
this chapter are na ıve in the sense that they are ignorant about a lot of the
information that is available in the LCS model. Also, they are only designed for
batch learning and as such are unable to handle tasks where incremental learners
are required.
Here, a few suggestions are given on how, on one hand, more information can
be used to guide the model structure search, and, on the other hand, how the
batch learning method can be turned into an incremental learner. The introduced
model structure search methods are general such that modifying the LCS model
type to a linear LCS, for example, does not invalidate these methods. Guiding
the model structure search by information that is extracted from the probabilistic
model makes the search procedure depend on the model type. Thus, while it
might be more powerful thereafter, it is also only applicable to one particular
model structure. The modifications that are suggested here only apply to LCS
model types that train their classifiers independently.
Independent of the LCS model type, incremental learning can occur at two
different levels: On one hand, one can learn the LCS model parameters incre-
mentally while keeping the model structure fixed. On the other hand, the model
structure can be improved incrementally, as done by Michigan-style LCS.Both
levels will be discussed here, but as before, they will only be discussed for the
LCS model type that is introduced in this topic.

8.4.1 Using More Information

Suggestions on how the model structure search can be improved focus exclusively
on the GA, as it has the advantage of exploiting building blocks in the LCS model
(see Sect. 8.2.3). It can be improved on two levels: i) more information embedded
in the LCS model should be used than just the fitness of a model structure, and
ii) current theoretical and practical advances in evolutionary computation should
be used to improve the GA itself.
With respect to using the information that is available within the model itself,
model structure search operates on the classifiers, and in particular on their
matching function. Thus, it is of interest to gain more information about a single
classifier c k within a model structure

. Such information could, for example,
be gained by evaluating the probability p ( c k |M

M

, D ) of the classifier's model in