The Optimal Set of Classifiers - Design and Analysis of Learning Classifier Systems - page 120

7 The Optimal Set of Classifiers

This chapter deals with the question of what it means for a set of classifiers to be
optimal in the light of the available data, and how to provide a formal solution
to this problem. As such, it tackles the core task of LCS, whose ultimate aim is
it to find such a set.
Up until now there is no general definition of what LCS ought to learn. Rather,
there is an intuitive understanding of what a desirable set of classifiers should
look like, and LCS algorithms are designed around such an understanding. Ho-
wever, having LCS that perform according to intuition in simple problems where
the desired solution is known does not mean that they will do so in more complex
tasks. Furthermore, how do we know that our intuition does not betray us?
While there are a small number of studies on what LCS want to learn and
how that can be measured [130, 133, 135], they concentrate exclusively on the
case where the input is encoded as a binary string, and even then they list
several possible approaches rather than providing a single conclusive answer.
However, considering the complexity of the problem at hand, it is understandable
that approaching it is anything but trivial. The solution structure is strongly
dependent on the chosen representation, but what is the best representation?
Do we want the classifiers to partition the input space such that each of them
independently provides a part of the solution, or do we expect them to cooperate?
Should we prefer default hierarchies, where predictions of more general classifiers,
that is, classifiers that match larger areas of the input space, are overridden by
more specific ones, in a tree-like structure? Are the predictions of the classifiers
supposed to be completely accurate, or do we allow for some error? And these
are just a few questions to consider.
Rather than listing all possible questions and going through them one by one,
the problem is here approached from another side, based on how LCS were cha-
racterised in Chapter 3: a fixed set of classifiers, that is, a fixed model structure
M

, provides a certain hypothesis about the data-generating process that gene-
rated the observed data

D

. With this in mind, “What do LCS want to learn?”
becomes “Which model structure

M D

best?”. But,
what exactly does “best” mean? Fortunately, evaluating the suitability of a

explains the available data