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

8.4.2 Incremental Implementations
An even more challenging task is to turn the developed batch implementation
into an incremental learner. Incremental learning can be performed on two levels,
each of which will be discussed separately: i) the model parameters θ can be
updated incrementally, while holding the model structure fixed ii) the model

structure can be updated incrementally under the assumption that the correct
model parameters are known immediately after each update. The aim of an
incremental learner is to perform incremental learning on both levels. To do this
successfully, however, we firstly have to be able to handle incremental learning
on each of the two levels separately.
Incremental learning on the model parameter level alone is sucient to handle
reinforcement learning tasks. Incrementally learning the model structure, on the
other hand, is computationally more ecient as it only requires working with
a single model structure at a time (making it a Michigan-style LCS)rather
than having to maintain several model structures at once (as is the case for
Pittsburgh-style LCS). Thus, performing incremental learning on either level
alone is already a useful development.

M

Incremental Model Parameter Update
Having provided a Bayesian LCS model for a fixed model structure

, one could
assume that it automatically provides the possibility of training its parameters
incrementally by using the posterior of one update as the prior of the next
update. However, due to the use of hyperpriors, this does not always apply.
Assuming independent classifier training, let us initially focus on the classi-
fiers. The classification model that was used does not use a hyperprior and thus
can be easily updated incrementally. The update (7.129) of its only parame-
ter α k is a simple sum over all observations, which can be performed for each
observation separately.
Classifier models for regression, on the other hand, have several interlinked
parameters W , τ and α that are to be updated in combination. Let us consider
the posterior weight (7.98) and precision (7.97) of the classifier model, which also
results from performing matching-weighted ridge regression with ridge comple-
xity

M

E α ( α k ) (see Sect. 7.3.1). As shown in Sect. 5.3.5, ridge regression can, due
to its formal equivalence to RLS, be performed incrementally. Note, however,
that the ridge complexity is set by the expectation of the prior on α k that is
modelled by the hyperprior (7.9) and is updated together with the classifier mo-
del parameters. A direct change of the ridge complexity after having performed
some RLS updates is not feasible. However, there remain two possibilities for
an incremental update of these parameters: one could fix the prior parameters
by specifying α k directly rather than modelling it by a hyperprior. Potentially
good values for α k are given in Sect. 7.2.3. Alternatively, one can incrementally

update n m ( x n ) x n x n and recover Λ k after each update by using (7.97) di-
rectly, which requires a matrix inversion of complexity

( D 3
X

O ) rather than the

( D 2
X

O ) of the RLS algorithm. Thus, either the bias of the model or the compu-

tational complexity of the update is increased. Using uninformative priors, the