Previous Next Contents

Chapter 4:   CMAC Architectures:

Now that we have discussed the neurobiological underpinnings for the CMAC model (Chapter 2) and provided a basic primer for the mechanics of implementing the N ® LN encoder (Chapter 3), we are now ready to go over this material in a fairly abstract manner. The Cerebellar Model Articulated Controller (CMAC) was first developed and described in a series of papers in the 1970's by (Albus, 2, 3, 4). Their use in robotic control was further developed by (Miller, 31, 36) and (Miller, Glanz and Kraft, 37) in a series of papers on real--time control of robotic arms. Essentially, a CMAC architecture maps the input space of the problem into a much larger virtual address space via what can be called coarse encoding. The number of entries in the virtual address space is usually quite large, perhaps 106 to 108 in number --- clearly far too large to be used for direct storage of tunable parameters. In practice, this large virtual address space is drastically reduced in size by hashing the virtual address to a smaller working address.

4.1   The CMAC Architecture:

We are interested in mappings whose domain and range are bounded subsets I Ì ÂN and D Ì ÂD, respectively. The elements of I will be called inputs and denoted by p®; similarly, D is the output space whose elements are denoted by z®. An example where the inputs come from a bounded region I of the two dimensional input space Â2 as shown in Figure 4.1. In this picture, we show the region I lying within a bounding box B.


Figure 4.1:
Now suppose that the input space is subdivided into K mutually disjoint subsets, Bi which cover the whole space; i.e.

I Ì Èk=0K-1 Bk.     (4.1)

We will call the individual subsets, Bi, blocks. An illustration of this type of partitioning for a given bounding box B is shown in Figure 4.2. Note that each element p® in B has a representation with respect to the (p0,p1) axes as pi = (pi0,pi1).


Figure 4.2:
In this figure, we see a bounded two--dimensional input space, I, subdivided into 48 disjoint blocks. Hence, by appropriate labeling,

I Ì Èk=047 Bk.     (4.2)

Note that each block is a rectangular subset of Â2 and that we must make a choice about the bounding box B that contains I. It must be noted that the choice of bounding box subinterval partitioning is a user decision. Once this decision is made, the bounding box can then be represented as a Cartesian cross product

B =
m0-1
Õ
i=0
m1-1
Õ
j=0
[p0i,p0,i+1] × [p1j,p1,j+1]
    (4.3)

where {p00,...,p0,m0} and {p10,...,p1,m1} denote the individual points in the partitioning of the p0 and p1 axes implied by the subinterval scheme. For convenience of notation, we denote all the intervals in the cross product (4.3) as closed at both ends even though the resulting rectangles are not disjoint. We let the reader choose any scheme desired that will give disjoint rectangles; one choice would be to have all subintervals be open at the right hand side except the last interval cross products, which would be closed at both ends. A standard labeling would then be of the form Bk º m0 i+j = [p0i,p0i+1] × [p1j,p1j+1].

From this discussion, it is clear that for each choice of B, we have a mechanism that assigns a unique index or address k to each input p® Î I by

®
p
 
Î I
Þ
$ unique index k '
®
p
 
Î Bk.
    (4.4)

We can think of each block Bk as the receptive field for a sensor Nk whose action is defined by

Nk(
®
p
 
)
=
ì
ï
í
ï
î
1,
®
p
 
Î Bk
0, otherwise
.
    (4.5)

Hence, Nk(p®) is a sensor which coarsely locates the input p®. In general, these sensors are constructed from a bounding box B having the form described in Table 4.1:

 
Coordinate Bounds
p0 [p00,p0,m0]
p1 [p10,p1,m1]
: :
pN-2 [pN-2,0,pN-2,mN-2]
pN-1 [pN-1,0,pN-1,mN-1]

Table 4.1: Bounding Box Structure
where pi0 and pi,mi denote the starting and ending points of the ith coordinates of the bounding box B. Thus,

B =
N-1
Õ
i=0
[pi0,p
 
i,mi
].
    (4.6)

Each bounding box interval is then partitioned as given in Table 4.2.

 
Coordinate Partition
p0 {p00 < p01 < p0,s < p0,m0 }
p1 {p10 < p11 < p1,s < p1,m1 }
: :
pN-2 {pN-2,0 < pN-2,1 < pN-2,s < pN-2,mN-2 }
pN-1 {pN-1,0 < pN-1,1 < pN-1,s < pN-1,mN-1 }

Table 4.2: Bounding Box Partitions
Define the blocks and sensors associated with this partition scheme by

B
 
s0,s1,...,sN-1
=
ì
ï
ï
ï
ï
í
ï
ï
ï
ï
î
®
p
 
Î B :
p
 
0,s0
£ p0 £ p
 
0,s0+1
p
 
1,s1
£ p1 £ p
 
1,s1+1
     ·
·
·
p
 
N-2,sN-2
£ pN-2 £ p
 
N-2,sN-2+1
p
 
N-1,sN-1
£ pN-1 £ p
 
N-1,sN-1+1
ü
ï
ï
ï
ï
ý
ï
ï
ï
ï
þ		 ,
    (4.7)

where we denote each subinterval [pi,si,pi,si+1] as closed on both ends for notational convenience only. As discussed earlier, these intervals must actually be chosen to be disjoint. Also, each sensor is defined by

N
 
s0,s1,...,sN-1
(
®
p
 
)
=
ì
ï
í
ï
î
1
®
p
 
Î B
 
s0,s1,...,sN-1
0 otherwise
.
    (4.8)

Note that here we do not order the blocks and sensors linearly as Bk and Nk respectively; it is however a straightforward exercise to find the mapping k « (s0,s1,...,sN-1) (see the discussion in Section 4.5). We see there are a total of K = m0 × ... × mN-1 blocks and associated sensors which we will henceforth relabel as Bk and Nk for 0 £ k £ K-1. We have thus divided I into K sensor fields of potentially coarse resolution. As before, the index k « (s0,s1,...,sN-1) will be the address of the input p®.

There is no reason for us to restrict ourselves to one cover of I. We can generate a different covering strategy for every choice of partitions. An easy way to do this is to start with a cover I Ì Èk0=0K0-1 Bk00 and construct a new cover by adding offsets to each element of the partitions. The details of this are discussed in Section 4.5. For the moment let's assume we have generated L distinct covers (no block can be in both the ath and bth covers for a ¹ b)

I Ì
È
K0-1
 
k=0
Bk0
I Ì
È
K1-1
 
k=0
Bk1
  ·
·
·		       (4.9)
I Ì
È
KL-2-1
 
k=0
BkL-2
I Ì
È
KL-1-1
 
k=0
BkL-1

and p® has associated with it the L addresses

k0 « (s00,s10,...,sN-10)
k1 « (s01,s11,...,sN-11)
  ·
·
·		       (4.10)
kL-2 « (s0L-2,s1L-2,...,sN-1L-2)
kL-1 « (s0L-1,s1L-1,...,sN-1L-1).

Hence, there are a total of K = åj=0L-1 Kj possible addresses, where for the jth cover, there are Kj = m0j × ... × mN-1j blocks, with mij + 1 denoting the number of partition points on the ith component axis for the jth cover. We can allocate a block of memory, the virtual address space, V using these addresses as follows:

V =
é
ê
ê
ê
ê
ê
ê
ê
ê
ë
V00 ...
V
 
0,K0-1
V10 ...
v
 
1,K1-1
·
·
·		 ·
·
·		 ·
·
·
VL-1,0 ...
V
 
L-1,KL-1-1
ù
ú
ú
ú
ú
ú
ú
ú
ú
û		 ,
    (4.11)

where the jth row corresponds to the jth cover and contains as many entries as there are addresses associated with that cover. We will say the jth cover is the jth level corresponding to our coarse encoding scheme. We can store any numbers we wish in the virtual array V and can thus define a function G(V) : I ® Â by

G(V)(
®
p
 
)
=
L-1
å
j=0
Kj-1
å
k=0
Nkj(
®
p
 
) Vjk,
    (4.12)

where Nkj is the sensor defined on the kth block, Bkj, of level j. There is a unique address, vj(p®) = kj(p®), associated with p® for each level j; thus from (4.8), we see that (4.13) collapses to

G(V)(
®
p
 
)
=
L-1
å
j=0
N
j
 
vj(
®
p
 
)
(
®
p
 
) V
 
j,vj(
®
p
 
)
  =
L-1
å
j=0
V
 
j,vj(
®
p
 
)
.
    (4.13)

From (4.13), it is clear that G(V) is not continuous or differentiable with respect to its input p®. In fact, the value of G(V) is calculated from the numbers stored in the virtual array V via what is basically a local look--up--table approach. Note also that, unlike standard feed forward architectures which use sigmoid transfer functions and therefore have a bounded output typically between 0 and 1, the CMAC output is obtained by summing values. Hence, the CMAC output need not remain between physically reasonable bounds without clipping.

Let the resolution of the partition of the jth level, ith component be given by

rij =
 
max
0 £ i £ mi-1
(pi+1j - pij).

If rij = r for some fixed value r for all allowable j and i, then the resolution of an L--level coarse encoding scheme is essentially r/L. Two vectors closer than this amount to each other could be mapped to the same address on each level, while vectors farther apart than this will be mapped to a different address on at least one level.

The value of the output G(V) depends on the numbers stored in the virtual array V. Hence, more properly, we can denote the function output as G(V)(p®). The coarse encoding scheme, the associated level structure and the function G(V)(p®) discussed in this section describe the output of a scalar CMAC architecture. If we desire to construct a function which assigns to each p® Î I a vector output z® Î ÂD, we simply construct a scalar CMAC architecture with associated function output Gd(Vd)(p®) for each output component zd and let the output of the vector CMAC architecture be defined by G(V0,...,VD-1)(p®) = (G0(V0)(p®),...,GD-1(VD-1)(p®))' .

4.2   Training the CMAC Architecture:

The utility of CMAC architectures arises from their ability to approximate mappings of the form
F : [a0,b0] × ... × [aN-1,bN-1] ® ÂD.     (4.14)

It is clear that the set [a0,b0] × ... × [aN-1,bN-1] plays the role of either the bounding box B or the input space I, while ÂD is the usual output space. Generally, we are given a set of input--output samples S = (x®t,y®t)t=0T-1, x®t Î I Ì ÂN and y®t Î ÂD; the set S is called the training set. The learning problem is to choose the values stored in the virtual array Vd so as to satisfy

Gd(Vd)(
®
x
 
t)
=
Ld-1
å
j=0
V
d
 
j,vjd(
®
x
 
t)
  = ydt,     (4.15)

where vjd and Ld denote the address function and the number of levels for the dth output component and ydt is the dth component of the tth output sample. The fundamental CMAC training law is then given in Table 4.3 and uses a scalar parameter l known as the learning rate (usually chosen to be between 0 and 1), user--defined tolerances e and d and the variable t to indicate the training iteration index. If this process converges, the values so obtained approximate Vd,¥ = limt ® ¥ Vd,t and will be denoted by Vd.
 
   
1 t = 0, t=0, d=0
2 " d, Vd,t,t = 0, Edt = 0
3 t=-1
4 Increment t
5 If edtt º ydt - Gd(Vd,t,t)(x®t) > e
     " components d, " levels j, set
     Vj,vjd(x®t)d,t,t+1 = Vj,vjd(x®t)d,t,t + l edtt/Ld
     Edt += edtt
     Go To 6
  If edtt £ e Continue
6 If t < T Go To 4
7 Compute Et º 1/TD(åd=0D-1 (Edt)2)
8 If Et < d, STOP
  Else,
     Increment t
     Go To 3

Table 4.3: CMAC Learning Algorithm

4.3   Comments on Training:

We will now work out several examples of CMAC training: for ease of exposition, we will drop the iteration index t on the parameter matrix V.

One Sample:

Assume that we have just one sample input and output; i.e. T = 1 and there is just one choice of sample index, t = 0. Initially Vj,vjd(x®0)d,0 = 0 and the new values of the virtual array are obtained from the CMAC learning algorithm of Table 4.3 as

V
d,1
 
j,vjd(
®
x
 
0)
=
V
d,0
 
j,vjd(
®
x
 
0)
+ l
yd0 - Gd(Vd,0)(
®
x
 
0)
Ld
  =
l
yd0 - Gd(0,
®
x
 
0)
Ld
  =
l
yd0
Ld
.
    (4.16)

Thus, if l = 1, the value of the desired output yd0 is divided equally among the Ld array entries addressed by vjd(x®0), for the levels 0 £ j £ Ld-1. Note that

Gd(Vd,1)(
®
x
 
0)
=
Ld-1
å
j=0
V
d,1
 
j,vjd(
®
x
 
0)
  =
Ld-1
å
j=0
l
yd0
Ld
  = l yd0.     (4.17)

Hence, if l = 1, the training procedure produces a CMAC output which exactly reproduces the desired output vector.
2 Sample Training:

Now we have 2 sample inputs and outputs. Initially Vj,vjd(x®0)d,0 = 0 and the new values of the virtual array are obtained from the CMAC learning algorithm of Table 4.3 as

V
d,1
 
j,vjd(
®
x
 
0)
=
V
d,0
 
j,vjd(
®
x
 
0)
+ l
yd0 - Gd(Vd,0)(
®
x
 
0)
Ld
  =
l
yd0 - Gd(0)(
®
x
 
0)
Ld
  =
l
yd0
Ld
.
V
d,2
 
j,vjd(
®
x
 
1)
=
V
d,1
 
j,vjd(
®
x
 
1)
+ l
yd1 - Gd(Vd,1)(
®
x
 
1)
Ld

Now if all the addresses associated with input x®1 are distinct from the addresses for input x®0, the values in Vd,1 corresponding to x®1 will still be zero and we will find

V
d,2
 
j,vjd(
®
x
 
1)
=
l
yd1
Ld
    (4.18)

However, if there is address overlap (that is at the level addresses for x®0 and x®1 match on at least one level j*, things will get more complicated. Let's assume that there is only one match. Then,

Gd(Vd,1)(
®
x
 
1)
=
Ld-1
å
j=0
V
d,1
 
j,vjd(
®
x
 
1)
  =
l
yd0
Ld
    only j* term is nonzero     (4.19)

and at j*,

V
d,2
 
j
*
 
,v
d
 
j
*
 
(
®
x
 
1)
=
V
d,1
 
j
*
 
,v
d
 
j
*
 
(
®
x
 
1)
+ l
yd1 - Gd(Vd,1)(
®
x
 
1)
Ld
  =
l
yd0
Ld
+ l
yd1 - l
yd0
Ld
Ld
  =
l
Ld
 (yd1+yd0) - (
l
Ld
)2 yd0.
    (4.20)

Thus,

Gd(Vd,2)(
®
x
 
1)
=
Ld-1
å
j=0
V
d,2
 
j,vjd(
®
x
 
1)
  =
l (Ld-1) 
yd0
Ld
+
l
Ld
 (yd1+yd0) - (
l
Ld
)2 yd0
  =
[l - (
l
Ld
)2] yd0  + 
l
Ld
 yd1.
    (4.21)

We clearly see that at this address location on level j*, there is an interaction between yd,0 and yd,1. Most importantly, Gd(Vd,2)(x®1) ¹ yd,1! In this case of address overlap, we can not in general expect to match targets.

4.4   Working Memory Via Hashing:

The virtual array memory discussed in Section 4.1 has a serious flaw: the size of the virtual address space can be enormous. For example, for a scalar problem, if N = 10 (input space is ten--dimensional), L = 5 (there are five levels) and the sensor structure is arranged so that there are only five sensors per input component, we see K0 = ··· K4 = 510 and there are 5 × 510 = 48,828,125 virtual addresses. If our implementation uses floats at eight bytes per float, this implies that storing V would require 372.5  MB. This is beyond our capability in most cases. We therefore will reduce the amount of memory used in the CMAC architecture by using a standard hashing technique.

We construct the working address for level j associated with input p® by computing wj(p®) º vj(p®) mod Hj, where Hj is the chosen hash size per level.

The working addresses are therefore organized into a vector, w, where

w =
é
ê
ê
ê
ê
ë
v0 mod H0
·
·
·
vL-1 mod HL-1
ù
ú
ú
ú
ú
û
    (4.22)

and memory usage is now Hj memories per level j giving a total memory usage of just H1 + H2 + ··· + HL-1.

We can therefore organize a collection of memory locations called working memory as a two-dimensional ``matrix'' W with elements Wja, where

W =
é
ê
ê
ê
ê
ê
ê
ê
ê
ë
W00 ...
W
 
0,H00-1
W10 ...
W
 
1,H1-1
·
·
·		 ·  
 · 
  ·		 ·
·
·
WL-1,0 ...
W
 
L-1,HL-1-1
ù
ú
ú
ú
ú
ú
ú
ú
ú
û		 .
    (4.23)

Note that W has L rows and the jth row has size Hj. The input p® therefore has an associated working address vector w® given by (4.23) which addresses the finite set of elements in working memory A,

ì
í
î		 W
 
0,w0
,W
 
1,w1
,...,W
 
L-1,wL-1
ü
ý
þ		 .

The output of the CMAC corresponding to the hashed address calculation for input p® is then denoted by G(W)(p®) and is defined as in Section 4.1 by

G(W)(
®
p
 
)
=
L-1
å
j=0
W
 
j,wj(
®
p
 
)
.
    (4.24)

The training algorithm then follows the same outline presented in Table 4.3. Although we have now reduced the size of our user memory to something manageable, there are fundamental problems:

  1. What do we do about collisions (i.e. inputs p®1 and p®2 which are distinct but whose hashed working addresses are the same)?
  2. How do we choose the hash sizes for the levels?

4.5   Implementing Scalar CMAC Architectures:

We will now discuss specific implementation details for a CMAC architecture using a fixed sensor width coupled with an offsetting scheme. For convenience of exposition, it is easiest to describe this CMAC architecture for a scalar valued output, i.e. D = 1; a vector--valued CMAC architecture would then require D potentially distinct CMAC structures, one for each output component.

The input space for this CMAC is coarse encoded as follows. The ith component of the input, pi, lives in [ai,bi]. Imagine that we have L levels of overlapping sensors that try to locate a given component in [ai,bi]. On level j, let the sensor for input component pi have a receptive field width of wij. This means that if the sensor becomes active at position x, then it remains active until position min(x + wij, bi). When the sensor is active, its output is 1 with value 0 everywhere outside of its region of reception. In general, we need to specify the sensor structure for each input component and each level. Any such partitioning of the component interval i for level j results in the creation of a finite number of sensor fields, Mji. This implies that we must specify for component i and level j information about the kth sensor, 0 £ k £ Mji-1,

  1. the beginning position of each sensor, Iijk,
  2. the width of each sensors' receptive field, wijk.
In practice, it is easier to assign some sort of regular structure to the sensor assignments. For example, we could assume that all the receptive field widths are a common size, g, and that the starting points of the sensors on a given level and input component can be specified by supplying a fixed offset, aij. Let Cij be the integer such that bi - ai - aij = Cij g + rij, where 0 £ rij £ aij is the remainder term. Then for level j, we can set up the starting points of each sensor as follows:

If rij > 0,

Iijk =
ì
ï
í
ï
î
ai k = 0
ai + aij k=1
ai + aij + (k-1) g 2 £ k £ Cij
ai + aij + Cij g k = Cij+1
,
    (4.25)

and there are two sensor fields of width less than g: field 0 of width aij and field Cij+2 of width bi - ai - aij - Cij g = rij. Note that Mji = Cij+2 in this case.

If rij = 0, then

Iijk =
ì
í
î
ai k = 0
ai + aij k = 1
ai + aij + (k-1) g 2 £ k £ Cij
.
    (4.26)

Note that ai + aij + Cij g = bi, and so all fields are of width g except field 0, which has width aij. Here Mji = Cij+1. The above discussion must be altered slightly if the offset aij is zero. Then the number of intervals Mji is one less in each case.

We can also determine each offset using an offset base, bi, where

aij = j bi (bi-ai), 0 £ j £ L-1.     (4.27)

The sensor structure for the ith input component and jth level can be then be constructed using (4.29), (4.27) and (4.28). Note that in this scheme, it is possible for the first sensor field for some levels to exceed the length wij. If this is not desirable, there are many ways to avoid this behavior. One is to simply choose bi so that L bi < g.

Note that in Section 4.1, we define the number of sensors (or blocks) per level using the symbol Kj; in terms of the notation used in this section, Kj = Õi=0N-1 Mji. Also, the discussion above is simply a particular choice for the partitioning scheme set out in Table 4.2. For the partitions of that table, Mji = mji; here, because we are using sensors of fixed width g and an offsetting scheme, the calculation of Mji is a little more complicated.


Example 1   Let's set up a CMAC architecture in which the number of levels is L = 5, the number of inputs is N = 16 with each input component residing in the interval [-.1,1.1], the receptive field widths are all wij = .60 and the offset base is bi = .1. Assume that the level structure is the same for each input component i. If the offsets aij are computed using (4.29), the level structure is then

LEVEL STRUCTURE NUMBER OF SUBINTERVALS
0 [-.1,.5), [.5,1.1] 2
1 [-.1,.02), [.02,.62), [.62,1.1] 3
2 [-.1,.14), [.14,.74), [.74,1.1] 3
3 [-.1,.26), [.26,.86), [.86,1.1] 3
4 [-.1,.38), [.38,.98), [.98,1.1] 3



Now, for a given level j, each component pi of input p® lies in a unique subinterval component aij. Hence, the N inputs of p® can be mapped to a N--tuple of integers {a0j,...,aN-1j}. The virtual address of p® for level j is then

vj(
®
p
 
)
=
N-1
å
i=0
aij Ti-1j
    (4.28)
Tij =
i
Õ
p=0
Mjp, i ³ 0
T-1j = 1,

where as usual Mji is the number of subintervals or sensors the coarse encoding provides on level j for input component pi. The virtual address therefore lies between 0 and Õp=0N-1 Mjp-1.

This large collection of addresses is called the virtual memory of the CMAC architecture and it is reduced to a much smaller sized working memory by hashing the virtual addresses as discussed in Section 4.4. We construct the working address for level j associated with input p® by computing wj(p®) º vj(p®) mod Hj, where Hj is the chosen hash size per level.

The working addresses are therefore organized into a vector, w, where

w =
é
ê
ê
ê
ê
ë
v0 mod H0
·
·
·
vL-1 mod HL-1
ù
ú
ú
ú
ú
û
    (4.29)

Hence, w has L elements. We can therefore organize a collection of memory locations called working memory as a two--dimensional ``matrix'' W with elements Aja, where

W =
é
ê
ê
ê
ê
ê
ê
ê
ê
ë
W00 ...
W
 
0,H00-1
W10 ...
W
 
1,H1-1
·
·
·		 ·
·
·		 ·
·
·
WL-1,0 ...
W
 
L-1,HL-1-1
ù
ú
ú
ú
ú
ú
ú
ú
ú
û		 .
    (4.30)

Note that W has L rows and the jth row has size Hj. The input p® therefore has an associated working address vector w® given by (4.31) which addresses the finite set of elements in working memory A,

ì
í
î		 W
 
0,w0
,W
 
1,w1
,...,W
 
L-1,wL-1
ü
ý
þ		 .


Example 2   Let's compute some representative virtual addresses using the CMAC architecture of example (1). For level 0, since we have the same sensor structure for all input components, T-10 = 1, T00 = 2, T10 = 4, T20 = 8 and Ti0 = 2i+1 and the virtual addresses lie in the range 0 £ vj £ 216 = 131,072. The remaining levels have three sensors per component; hence, T-1j = 1, T0j = 3, T1j = 9, T2j = 27 and Tij = 3i+1 for all other levels j and the virtual addresses lie in the range 0 £ vj £ 316 = 43,046,721.

For the input vector

®
p
 
=
<.21, .35, .02, 1.05, .87, -.05, .41, .20, .55, .93, .12, .47, .65, .78, .09, .82 >
'
 
    (4.31)

the subinterval strings and addresses for each level can be computed.

LEVEL SUBINTERVAL STRING VIRTUAL ADDRESS
0 0001100011001101 8+16+256+512+4096+8192+32786
    = 45,848
1 1112201112112212 1+3+9+2*27+2*81+729+2187+6561
    +2*19683+59049+177147+2*531441
    +2*1594323+4782969+2*14348907
    = 38,017,579
2 1102201112011202 1+3+2*27+2*81+729+2187+6561+2*19683
    177147+531441+2*1594323+2*14348907
    = 32,644,111
3 0102201012011101 3+2*27+2*81+729+6561+2*19683+177147
    +531441+1594323+14348907
    = 16,698,693
4 0002101011011101 2*27+81+729+6561+19683+177147+531441
    +1594323+14348907
    = 16,678,926




Exercise 1   Set up a CMAC architecture in which the number of levels is L = 6, the number of inputs is N = 16 with each input component residing in the interval [-.1,2.1], the receptive field widths are all wij = .80 and the offset base is bi = .1. Assume that the level structure is the same for each input component and compute the offsets aij using (4.29). Write out a table for the resulting level structure.



Exercise 2   For the input vector

®
p
 
=
<.21, .35, .02, 1.05, .87, -.05, 2.01, .20, .55, 1.93, .12, .47, .65, .78, 1.09, 1.82 >
'
 
    (4.32)

compute the subinterval strings and virtual addresses using the CMAC architecture of exercise (1) for all possible levels.


The output of the CMAC corresponding to the input p® is denoted by G(W)(p®) and is defined in Section 4.1 by

G(W)(
®
p
 
)
=
L-1
å
j=0
W
 
j,wj(
®
p
 
)
.
    (4.33)

If we are given a set of input--output samples S = (x®t,y®t)t=0T-1, x®t Î I Ì ÂN and yt Î Â, the standard CMAC learning algorithm of Section 4.2 (with discussion in Section 4.3) then leads to the following working memory update equation:

W
t,t + 1
 
j,wj(
®
x
 
t)
=
W
t,t
 
j,wj(
®
x
 
t)
+ l
yt-G(W
t,t
 
)(
®
x
 
t)
L
    (4.34)

where t is the training iteration index.

4.6   Implementing Vector CMAC Architectures:

It is straightforward to extend the scalar CMAC architecture discussed in Section 4.5 to a vector CMAC architecture.

The input--output maps we now wish the CMAC architectures to ``learn'' are of the form

F : [a0,b0] × ... × [aN-1,bN-1] ® ÂD     (4.35)

where D > 1. Using the principles outlined in Section 4.5, we can construct a potentially different CMAC architecture depending on parameter matrices Vd for each component d of the output space; i.e. we specify the details of the structure of the dth component of the function G given by (4.38),

Gd(Vd) : [a0,b0] × ... × [aN-1,bN-1] ® Â.     (4.36)

Now for a given output component d and level j, each component pi of input p® lies in a unique subinterval component sidj. Hence, the N inputs of p® can be mapped to a N--tuple of integers {s0dj,...,sN-1,dj}. The virtual address of p® for component d and level j is then

vjd(
®
p
 
)
=
N-1
å
i=0
aidj Ti-1dj
Tidj =
i
Õ
p=0
Mdjp, i ³ 0
T-1dj = 1,     (4.37)

where Mdji is the number of subintervals the coarse encoding provides for output component d on level j for input component i. The virtual address therefore lies between 0 and Õp=0N-1 Mdjp-1.

Since the level structure could be different for each output component d, let Ld denote the number of levels used in the kth CMAC architecture. The large collection of addresses calculated via (4.40) is called the virtual memory of the CMAC architecture. What is different now is that each input vector p® now corresponds to a two--dimensional ``matrix'' of virtual addresses; there is one row of virtual addresses for each of the D CMAC architectures. We have

v =
é
ê
ê
ê
ê
ê
ê
ê
ê
ë
v00 ...
v
0,L0-1
 
v10 ...
v
1,L1-1
 
·
·
·		 ·
·
·		 ·
·
·
vD-1,0 ...
v
D-1,LD-1-1
 
ù
ú
ú
ú
ú
ú
ú
ú
ú
û
    (4.38)

where we have suppressed the argument p® for each address. and the first superscript labels the output component and the second the particular level.

Each of these virtual addresses is reduced to a much smaller sized working memory by hashing the virtual addresses, vjd. We construct the working address for output d and level j associated with input p® by computing wjd(p®) º vjd(p®) mod Hdj, where Hdj is the chosen hash size per level. The working addresses are therefore organized into a two-dimensional ``matrix'' w with elements wkj, where

w =
é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë
w00 ...
w
0
 
L0-1
w01 ...
w
1
 
L1-1
·
·
·		 ·
·
·		 ·
·
·
w,D-10 ...
w
D-1
 
LD-1-1
ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û		 .
    (4.39)

Hence, w has D rows and the dth row has Ld elements. The input p® therefore has an associated working address wjd(p®) for each output d and level j. We can therefore organize working memory as a three--dimensional ``matrix'' W with elements Wjad, where, for fixed output component d, Wd is the two--dimensional ``matrix''

Wd =
é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë
W00d ...
W
d
 
0,H0d0-1
W10d ...
W
d
 
1,Hd1-1
·
·
·		 ·
·
·		 ·
·
·
W
d
 
Ld-1,0
...
W
d
 
Ld-1,H
d,Ld-1
 
-1
ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û		 .
    (4.40)

For fixed output component d, the input p® therefore has an associated working address vector

wd(
®
p
 
)
=
é
ê
ê
ê
ê
ê
ê
ê
ë
w0d
·
·
·
w
d
 
Ld-1
ù
ú
ú
ú
ú
ú
ú
ú
û
    (4.41)

which addresses the finite set of elements in working memory Wd,

ì
ï
ï
í
ï
ï
î		 W
d
 
0,w0d
,w
d
 
1,w1d
,..., W
d
 
Ld-1,w
d
 
Ld-1
ü
ï
ï
ý
ï
ï
þ		 .

The dth component of the output of the CMAC corresponding to the input p® is denoted by Gd(Wd)(p®) and is defined by

Gd(Wd)(
®
p
 
)
=
Ld-1
å
j=0
W
d
 
j,wjd(
®
p
 
)
.
    (4.42)

If we are given a set of input-output samples S = (x®t,y®t)t=0T-1, x®t Î I Ì ÂN and y®t Î Âd, the standard CMAC learning algorithm of Section 4.2 (with discussion in Section 4.3) then leads to the following working memory update equation:

W
d,t,t + 1
 
j,wjd(
®
x
 
t)
=
W
d,t,t
 
j,wjd(
®
x
 
t)
+ l
ydt-G(W
d,t,t
 
)(
®
x
 
t)
Ld
    (4.43)

where t is the training iteration index.

4.7   Future Extensions:

There is still much to do with these architectures. One very promising possibility is to adapt the multiple resolution ideas presented in (Moody, 40, 41) and develop a full hierarchical CMAC structure where CMAC architectures operating at different sensor resolutions cooperate in learning the underlying data model. This has been done in an boject oriented setting in [Bolling and Peterson, 6]. It is also reasonable to conjecture that multigrid ideas for accelerating the decay of error residuals in elliptic partial differential equations (Briggs, 8; Hunt, 22) may be applicable to hierarchical CMAC structures. In addition, the smoothness of the CMAC model may be enhanced by extending the training to local neighborhoods of the data. Local smoothing is extremely important in order to improve the continuity properties of the model.

Previous Next Contents