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

where we have used our previous assumption p ( A = add) = p ( A =remove),
K = K t + 1, and (8.5). When choosing the action remove , on the other hand,
the candidate model M is accepted with probability

min

) , 1

M t |M ,A = add) p ( A = add) M |D p ( p ( )

p ( M |M t ,A =remove) p ( A =remove) p ( M t |D

≈ min (exp ( L M ( q ) −L M t ( q ) − 2ln K t ) , 1) , (8.8)

based on K = K t − 1, and (8.5). Note that in case of having K =0,the

variational bound will be , and the candidate model will be al-

ways rejected, which confirms that a model without a single classifier is of no
value. Finally, a candidate model

L M ( q )= −∞

M where a single classifier from

M t has been

changed by action change is accepted with probability
min p (

) , 1

M t |M ,A = change) p ( A = change) M |D

p ( )

p ( M |M t ,A = change) p ( A = change) p ( M t |D

≈ min(exp( L M ( q ) −L M t ( q )) , 1) . (8.9)

To summarise, the MCMC algorithm starts with a randomly initialised model
structure M 0 with K 0 classifiers and at each step t + 1 performs either change ,

add ,or remove to create a candidate model structure M from M t that is either

M ) with a probability that, dependent on the chosen action,
is given by (8.7), (8.8) or (8.9), and otherwise rejected (

accepted ( M t +1 =

M t +1 = M t ).

8.2.3 Building Blocks in Classifier Sets

As apparent from the above descriptions, the most pronounced difference bet-
ween the GA and the MCMC search procedures is that the MCMC search only
considers a single model structure at a time, while the GA operates on a po-
pulation of them simultaneously. This parallelism allows the GA to maintain
several competing model structure hypotheses that might contain valuable buil-
ding blocks to form better model structures. In GA, building blocks refer to a
group of alleles that in combination provide a part of the solution [95]. With re-
spect to the model structure search, a building block is a subset of the classifiers
in a model structure that in combination provides a good model for a sub-
set of the data. A good model structure search maintains such building blocks
and recombines them with other building blocks to form new model structure
hypotheses.
Do such building blocks really exist in the given LCS model, and in LCS in
general? Let us consider a simple example where the model structure contains a
single classifier that matches all inputs with about equal probability. The only
sensible action that MCMC search can perform is to add another classifier to
see if it improves the model structure, which results in a classifier that matches
all observations about equally, and a possibly more specific classifier that con-
centrates on a subset of the data. Only in rare cases will such a combination
provide a better model for the data (see Sect. 8.3.3 for an example where it