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

3.2.6 Considerations for Model Structure Search

The space of possible model structures is potentially huge, and hence to search
this space, evaluating the suitability of a single model structure to explain

the data needs to be ecient to keep searching the model structure space com-
putationally tractable. Additionally, one wants to guide the search by using all
the available information about the quality of the classifiers within a certain
model structure by fitting this model structure to the data.
Each classifier in the LCS model represents some information about the in-
put/output mapping, limited to the subspace of the input space that it matches.
Hence, while preserving classifiers that seem to provide a good model of the
matched data, the model structure ought to be refined in areas of the input
space for which none of the current classifiers provides an adequate model. This
can be achieved by either modifying the localisation of current classifiers that do
not provide an adequate fit, removing those classifiers, or adding new classifiers
to compare their goodness-of-fit to the current ones. Intuitively, interpreting a
classifier as a localised hypothesis for the data-generating process, we want to
change or discard bad hypotheses, or add new hypotheses to see if they are
favoured in comparison to already existing hypotheses.
In terms of the model structure search, the search space is better traversed by
modifying the current model structure rather than discarding it at each search
step. By only modifying part of the model, we have satisfied the aim of facilitating
knowledge of the suitability of the current model structure to guide the structure
search. Additionally, if only few classifiers are changed in their localisation in
each step of the search, only modified or added classifiers need to be re-trained,
given that the classifiers are trained independently. This is an important feature
that makes the search more ecient, and that will be revisited in Sect. 4.4.
Such a search strategy clearly relates to how current LCS traverse the search
space: In Michigan-style LCS, such as XCS, new classifiers are added either if no
classifier is localised in a certain area of the input space, or to provide alternative
hypotheses by merging and modifying the localisation structure of two other
current classifiers with a high goodness-of-fit. Classifiers in XCS are removed
with a likelihood that is proportional to on average how many other classifiers
match the same area of the input space, causing the number of classifiers that
match a particular input to be about the same for all inputs. Pittsburgh-style
LCS also traverse the structure search space by merging and modifying sets
of classifiers of two model structures that were evaluated to explain the data
well. However, few current Pittsburgh-style LCS retain the evaluation of single
classifiers to improve the eciency of the search - a feature that is used in the
prototype implementation described in Chap. 8.

M

3.2.7 Relation to the Initial LCS Idea

Recall that originally LCS addressed the problems of parallelism and coordi-
nation, credit assignment, and rule discovery, as described in Sect. 2.2.1. The
following describes how these problems are addressed in the proposed model.