Training the Classifiers - Design and Analysis of Learning Classifier Systems - page 88

Table 5.1. A summary of batch and incremental methods presented in this chapter for
training the linear regression model of a single classifier. The notation and initialisation
values are explained throughout the chapter.

Batch Learning
w =( X T MX ) − 1 X T My w =( √ MX ) + √ My or

τ − 1 =( c − D X ) − 1

2
M

X w − y with c =Tr( M )

Incremental Weight Vector Estimate Complexity

LMS
w N +1 = w N + γ N +1 m ( x N +1 ) x N +1 ( y N +1 − w N x N +1 ) O ( D X )

NLMS
w N +1 = w N + γ N +1 m ( x N +1 ) x N +1
x N +1

2 ( y N +1 − w N x N +1 )

O ( D X )

RLS (Inverse Covariance Form)
w N +1 = w N + m ( x N +1 ) Λ − 1

N +1 x N +1 ( y N +1 − w N x N +1 ) ,

3
X

O ( D )

Λ N +1 = Λ N + m ( x N +1 ) x N +1 x N +1
RLS (Covariance Form)
w N +1 = w N + m ( x N +1 ) Λ − 1
N +1 x N +1 ( y N +1 − w N x N +1 ) ,

2
X

O ( D )

N x N +1 x N +1 Λ − 1 N
1+ m ( x N +1 ) x N +1 Λ − 1

Λ − 1

Λ − 1

N +1 = Λ − 1

N − m

( x N +1 )

N x N +1

Kalman Filter (Covariance Form)
ζ N +1 = m ( x N +1 ) Λ − 1
N

x N +1 ` m ( x N +1 ) x N +1 Λ − 1
N N +1 ´ − 1

x N +1 + τ − 1

,

w N +1 = w N + ζ N +1 ` y N +1 − w N x N +1 ´ ,

2
X

O ( D )

Λ − 1
N +1 = Λ − 1 N − ζ N +1 x N +1 Λ − 1

N
Kalman Filter (Inverse Covariance Form)
Λ N +1 w N +1 = Λ N w N + m ( x N +1 ) τ N +1 x N +1 y N +1 ,
Λ N +1 = Λ N + m ( x N +1 ) τ N +1 x N +1 x N +1 ,

3
X

O ( D )

w N +1 = Λ N +1 ( Λ N +1 w N +1 ) − 1

Incremental Noise Precision Estimate Complexity

LMS (for biased estimate (5.62))
τ − 1

+ m ( x N +1 ) ` ( w N +1 x N +1 − y N +1 ) 2

´

N +1 = τ − 1

− τ − 1
N

O ( D X )

N

Direct tracking (for unbiased estimate (5.63))
Only valid in combination with RLS/Kalman filter in Inverse Covariance Form
or in Covariance Form with insignificant prior
X N +1 w N +1 − y N +1

2
M N
+ m ( x N +1 )( w N x N +1 − y N +1 )( w N +1 x N +1 − y N +1 ) ,

2
M N +1 = X N w N − y N

O ( D X )

c N +1 = c N + m ( x N +1 ) ,
τ − 1

N +1 =( c N +1 − D X ) − 1

2
M N +1

X N +1 w N +1 − y N +1

5.4 Empirical Demonstration

Having described the advantage of utilising the RLS algorithm to estimating the
weight vector and tracking the noise variance simultaneously, this section gives
a brief empirical demonstration of its superiority over gradient-based methods.
The two experiments show on one hand that the speed of convergence of the