Chapter 5: CMAC Convergence:

5.1 Introduction:

We now provide a proof of the convergence of the CMAC learning algorithm under very general conditions. The convergence proof is essentially insensitive to the type of hashing used to construct the working addresses. In addition, we develop a closed form solution that sheds insight into the range of the CMAC architecture and the intelligent choice of the crucial CMAC parameters of levels, hashing strategy and sensor field width. This paper extends the convergence analyses of (Lin, 27) and (Wong, 54) to handle rigorously the explicit use of hashing. We derive criteria that suggest how to choose the number of levels, hash size and so forth so as to achieve a first--order measure of quality, thereby enhancing the discussions of (Brown, 9).

5.2 CMAC Training:

The weight update rule given by (4.37) can be cast into an iterative algorithm for training the weights of a CMAC architecture to approximate a given set of I/O data. Assume we are given a collection of S input--output data pairs, (p_i,b_i), 0 £ i £ S-1. We solve for the appropriate values of the weights W_j,_n_{_j}_(p_{_s}^_®₎ via an iterative procedure indexed by both the iteration time t and the exemplar s. The procedure works by starting with a zero weight matrix and using (4.37) repeatedly to alter the values of the weights stored in W. This procedure passes through the complete training set from s = 0 to s = S-1 in a serial fashion. Hence, each t iteration consists of S serial update calculations. So, we need to label the values stored in W to reflect the fact that they depend on four indexing variables. We will label these values as W_jk^ts, where t indicates the iteration count, j denotes the level, k gives the active sensor at that level and s reminds us that these values have been determined after seeing exemplars x = 0 to x =s during this iteration t. Once these values have been calculated, we can evaluate the CMAC function at any input p_i; i.e., at iteration t, after we have passed through the first s inputs, we have at any input p_i,

p_i

)

L-1

j=0

j,n_j

(

p_i

)

The value of g is clearly dependent on the weights stored in W^ts. Hence, for a given input p_i^®, we will use the notation

g^ts(

p_i

)

L-1

j=0

j,n_j

(

p_i

)

The basic training algorithm can then be restated as an update law for the weights at iteration t having passed through the first s inputs, W_i,j^ts, in terms of the weights already computed with the pass through the first s-1 items:

j,n_j

(

p_s

)

t,s-1

j,n_j

(

p_s

)

( b_s-g^t,s-1(

p_s

)).

We can now state a complete training algorithm. We start at t = 0 with all weights zero (W^0,-1 is the zero matrix) and g^0,-1 is identically zero. From examination of Table 5.1, it is clear that our convergence investigation centers on the existence of the limit lim_{t ¾® ¥} W_j,k^t,-1.

W_j,k^0,-1 = 0, " j, k

for(t = 0; t < ¥; ++t) {

   for(s = 0; s < S; ++s) {

     for(j = 0; j < L; ++ j) {

        W_j,_n_{_j}_(p_{_s}^_®₎^ts = W_j,_n_{_j}_(p_{_s}^_®₎^t,s-1 + l/L ( b_s-g^t,s-1(p_s^® ))

        }

     }

   W_j,k^t+1,-1 = W_j,k^t,S-1, " j,k

   }

Table 5.1: CMAC Learning Algorithm

5.3 The Matrix Form:

Consider the usual scalar CMAC with or without hashing of size H. If there is no hashing, we can find a hash size, H_c, so large that all the virtual addresses on all the levels are smaller than this critical number H_c. Thus, we may assume without loss of generality that we are dealing with a hashed CMAC architecture with hash size H.

In order to investigate the convergence of the CMAC learning algorithm carefully, it is very useful to recast the algorithm of Table 5.1 into standard matrix and vector notation that will show structure more clearly. First, the variables we need to determine are stored in the matrix W. We can lexographically order these variables into a column vector consisting of L subblocks of length H. Let x^® denote the LH × 1 column vector whose components are

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

x₀

·
·
·

x_H-1

x_H

·
·
·

x_2H-1

·
·
·

x_(L-1)H

·
·
·

x_LH-1

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

W₀₀

·
·
·

W_0,H-1

W₁₀

·
·
·

W_1,H-1

·
·
·

W_L-1,0

·
·
·

W_L-1,H-1

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(5.1)

Note that only one element out of each subblock of x^® is accessed by the working address vector n^®(p^®), where

(

)

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

n₀(

)

n₁(

)

·
·
·

n_L-1(

)

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(5.2)

This particular structure of the weight matrix is independent of hash strategy. Hence, the CMAC output corresponding to the input p^® can be written as the matrix product of the row vector, A and x^® as follows:

)

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

·
·
·

position

n₀(

)

·
·
·

position

H + n₁(

)

·
·
·

position

(L-1)H + n_L-1(

)

·
·
·

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

(5.3)

Note that the row A consists of L subblocks that match the subblocks of x^®. Let's assume that we are training on a data set of size S. Hence there are input vectors {p₀,···,p_S-1 }, desired outputs {b₀,···,b_S-1 } and associated rows {A₀,···,A_S-1 } with the output of the CMAC at each p_i^® given by g(p_i^®) = A_i x^®. We can rewrite the weight updating algorithm as

new

jH+n_j

(

p_i

)

old

jH+n_j

(

p_i

)

æ
ç
ç
è

b_i - A_i

^old

ö
÷
÷
ø

(5.4)

The product A_i x^®^t should only be used to update the elements of x^® accessed by the address n(p_i)^®. Note that A_i^T is a column vector whose only nonzero elements are the elements residing in the positions accessed by the working address n(p_i)^®. Hence, we can rewrite (5.4) as

^new

^old +

A_i^T( b_i - A_i

^old )

^old -

A_i^T A_i

^old +

A_i^T b_i

(I-b A_i^T A_i)

^old + b A_i^T b_i

C_i

^old + b A_i^T b_i,

(5.5)

where b = l/L and I denotes the LH × LH identity matrix, and we define the LH × LH square matrix C_i by C_i = I-b A_i^T A_i.

We can now rewrite the full algorithm presented in Table 5.1 by eliminating the level loop (it is subsumed in the lexicographic ordering of the weight matrix). The new algorithm is shown in Table 5.2.

x^®^0,-1 = 0

for(t = 0; t < ¥; ++t) {

   for(s = 0; s < S; ++s) {

     x^®^t,s = (I-b A_i^T A_i) x^®^t,s-1 + b A_i^T b_i

     }

   x^®^t+1,-1 = x^®^t,S-1

   }

Table 5.2: CMAC Vector Learning Algorithm

We are interested in establishing the convergence of the vector sequence {x^®^t,-1 }_t=0^¥ º {x^®^t,S-1 }_t=0^¥; i.e., does lim_{t ¾® ¥} x^®^t,-1 exist?

5.3.1 The CMAC Training Generator Matrix:

Using Table 5.2, we can compute the iterates of x^®^t,-1 recursively:

x^®^0,-1 = 0
x^®^0,0 = C₀ x^®^0,-1 + b A₀^T b₀

^0,1

C₁

^0,0 + b A₁^T b₁

C₁ (C₀

^0,-1 + b A₀^T b₀) + b A₁^T b₁

C₁ C₀

^0,-1 + b (C₁ A₀^T b₀ + A₁^T b₁)

^0,2

C₂

^0,1 + b A₂^T b₂

C₂ C₁ C₀

^0,-1 + b (C₂ C₁ A₀^T b₀ + C₂ A₁^T b₁ + A₂^T b₂)

D₀²

^0,-1 + b (D₁² A₀^T b₀ + D₂² A₁^T b₁ + A₂^T b₂)

D₀²

^0,-1 + b

æ
ç
ç
è

k=1

D_k² A_k-1^T b_k-1 + A₂^T b₂

ö
÷
÷
ø

where for p ³ q, we use the notation D_q^p º C_p C_p-1 ··· C_q. An easy induction argument then shows that the general structure for x^®^0,p is

^0,p

D₀^p

^0,-1 + b

æ
ç
ç
è

k=1

D_k^p A_k-1^T b_k-1 + A_p^T b_p

ö
÷
÷
ø

and so after the first sweep through the data set is completed, we have

^0,S-1

D₀^S-1

^0,-1 + b

æ
ç
ç
è

S-1

k=1

D_k^S-1 A_k-1^T b_k-1 + A_S-1^T b_S-1

ö
÷
÷
ø

(5.6)

In general, we can repeat the argument above for a given iteration and express x^®^t+1,S-1 in terms of x^®^t,-1:

^t+1,S-1

^t,-1 + b

æ
ç
ç
è

S-1

k=1

D_k^S-1 A_k-1^T b_k-1 + A_S-1^T b_S-1)

ö
÷
÷
ø

^t,-1 + b V^T

(5.7)

where we have set D º D₀^S-1, and we use

V^T =

S-1

k=1

D_k^S-1 A_k-1^T b_k-1 + A_S-1^T b_S-1.

Applying (5.7) recursively, we can show

^t+1,S-1

^t,-1 + b V^T

D ( D

^t-1,-1 + b V^T) + b V^T

^t-1,-1 + b (I + D) V^T

^t-2,-1 + b (I + D + D² ) V^T

^t-2,-1 + b (

k=0

D^k) V^T

where D⁰ º I. A standard induction argument then shows

^t+1,S-1

l +1

t-l ,-1

+ b (

k=0

D)^k V^T

(5.8)

^t+1

^0,-1 + b (

k=0

D^k) V^T.

(5.9)

We know that we initialize the algorithm using x^®^0,-1 = 0; hence, (5.10) becomes

^t+1,S-1

b (

k=0

D^k) V^T.

(5.10)

Thus, our original question about convergence can be rephrased using the matrix form above: convergence of the sequence is established if and only if (å_t=0^¥ D^k ) V^T exists. Hence, we must investigate the structure of the geometric series

(I + D + ··· + D^t + ··· ) V^T.

5.3.2 The Structure of D:

Note that A_i A_j^T is the dot product of the address vectors due to input vectors p_i and p_j. If these address vectors were identical --- that is, the CMAC architecture could not distinguish between these vectors --- then this dot product will have value L. If these addresses are not identical, then A_i A_j^T < L. In general, we will use the notation for all possible exemplar indices i and j:

m_ij

A_i A_j^T £ L

p_ij

m_ij

Î [0,1]

where we refer to p_ij as the amount of overlap between address A_i and A_j. Consider the following matrix products:

C₁ C₀ = I - b (A₀^T A₀ + A₁^T A₁) + b² A₁^T A₁ A₀^T A₀

= I - b (A₀^T A₀ + A₁^T A₁) + b² A₁ A₀^T (A₁^T A₀)

= I - b (A₀^T A₀ + A₁^T A₁) + b² m₁₀ (A₁^T A₀)
C₂ C₁ C₀ =

I - b

2

å

k=0
A_k^T A_k + b² (m₁₀ A₁^T A₀ + m₂₁ A₂^T A₁ + m₂₀ A₂^T A₀) - b³ m₂₁ m₁₀ A₂^T A₀

We can package the last result more concisely by introducing the following notation: For p £ q, let N_q = {0,1,···,q } and

Q_q^p

{ (i₀,···,i_q) Î N_p | i₀ > ··· > i_q }

| Q_p^q |

æ
è

q+1

p+1

ö
ø

where (

) is the usual binomial coefficient and | S | denotes the cardinality of a set S. Then, in particular, we see

Q₀¹

{ i₀ Î N₁ } = { (0), (1) }; | Q₀¹ | =

æ
è

ö
ø

Q₁¹

{ (i₀,i₁) Î N₁ | i₀ > i₁ } = { (1,0) }; | Q₁¹ | =

æ
è

ö
ø

Q₀²

{ i₀ Î N₂ } = { 0, , 1, 2 }; | Q₀² | =

æ
è

ö
ø

Q₁²

{ (i₀,i₁) Î N₂ | i₀ > i₁ } = { (1,0), (2,0), (2,1) }; | Q₁² | =

æ
è

ö
ø

Q₂²

{ (i₀,i₁,i₂) Î N₂ | i₀ > i₁ > i₂ } = { (2,1,0) }; | Q₂² | =

æ
è

ö
ø

Hence, we can rewrite C₂ C₁ C₀ as

C₂ C₁ C₀

I - b

i₀ Î Q₀²

i₀

+ b²

(i₀,i₁) Î Q₁²

i₀,i₁

i₀

i₁

- b³

(i₀,i₁,i₂) Î Q₂²

i₀,i₁

i₁,i₀

i₀

i₂

A simple induction argument shows that the general form of D is given by

C_S-1 C_S-2 ··· C₁ C₀

I - b

i₀ Î Q₀^S-1

i₀

S-1

k=1

(i₀,i₁,···,i_k) Î Q_k^S-1

(-1)^k+1 b^k+1 m

i₀,i₁

··· m

i_k-1,i_k

i₀

i_k

(5.11)

We now assume that the overlap between A_i and any other address A_j is a fixed percentage m_ij = p. In this case, the structure of D is much simpler. We have

I - b

S-1

i=0

A_i^T A_i +

S-1

k=1

(i₀,i₁,···,i_k) Î Q_k^S-1

(-1)^k+1 b^k+1 p^k A

i₀

i_k

(5.12)

5.3.3 The Structure of C_i:

We begin by analyzing the structure of a typical C_i, C_i = I-b A_i^T A_i. This LH × LH matrix has the structure shown in Table 5.3. In this table, for notational convenience, we let r_jⁱ denote the row jH + n_jⁱ, with n_i^j the index of the active sensor on level j in the CMAC architecture for input p_i and for ease of display, we use r^± to indicate r ± 1.

COL

ROW 0 ··· r₀^i,- r₀ⁱ r₀^i,+ ··· r_L-1^i,- r_L-1 r_L-1^i,+ ··· LH^-

0 1 0 0 0 0 ··· 0 0 0 0 0

: : ddots : : : : : : : : :

r₀^i,- 0 0 1 0 0 : 0 0 0 0 0

r₀ⁱ 0 0 0 1-b 0 : 0 -b 0 0 0

r₀^i,+ 0 0 0 0 1 : 0 0 0 0 0

: : : : : : ddots : : : : :

r_L-1^i,- 0 0 0 0 0 : 1 0 0 0 0

r_L-1ⁱ 0 0 0 - b 0 : 0 1-b 0 0 0

r_L-1^i,+ 0 0 0 0 0 : 0 0 1 0 0

: : : : : : : : : : ddots :

LH^- 0 0 0 0 0 : 0 0 0 0 1

Table 5.3: Structure of C_i

We make the following observations:

The matrix C_i is symmetric.
The inverse of C_i exists and is given by C_i^-1 = I + b/1-b A_i^T A_i.

Let W_i = { r₀ⁱ,···,r_L-1ⁱ } and let W_i^c denote the complement of this set in the set of all possible rows, { 0,1,···,LH-1 }. Then if j Î W_i^c, the row--column pair (j,j) is of identity form. That is, it has the form

	COL
ROW	0	···	j-1	j	j+1	···	LH^-
0				0
···				:
j-1				0
j	0	···	0	1	0	···	0
j+1				0
···				:
LH^-				0

We will henceforth simply say that row j Î W_i^c in C_i has identity form.

Let V_i denote the span of the vectors in the set W_i and V denote the span of the vectors in the union È_i=0^S-1 V_i. Then

C₀ has identity form for all j Î W₀^c
C₁ C₀ has identity form for all j Î { W₀ È W₁ }^c
C_S-1 ··· C₀ has identity form j Î { W₀ È W₁ ··· W_S-1 }^c

Consider D x^® for all vectors x^® in V. Note that

| D

| | C_S-1 | | ··· | | C₁ | | | C₀

Hence, we must obtain an estimate for the norm of the action of C₀ on x^® Î V. For an arbitrary sample index i, note that the (u,v) element of C_i can be written as u = a H + b and v = c H + d, for some choice of indices a, b, c and d; hence,

(C_i)_u,v

(C_i)_{a H + b,c H + d}

d_c^a d_d^b - b d

a H + b

r_aⁱ

c H + d

r_bⁱ

d_c^a d_d^b - b d

a H + b

a H + n_aⁱ

c H + d

c H + n_cⁱ

d_c^a d_d^b - b d

n_aⁱ

n_cⁱ

For arbitrary vector x^® in Â^LH, the component a H + b of C_i x^® is given by

(C_i

)_{a H + b}

L-1

c=0

H-1

d=0

d_c^a d

_d^b x_{c H + d} - b

L-1

c = 0

H-1

d = 0

n_aⁱ

n_cⁱ

x_{c H + d}

x_{a H + b} - b d

n_aⁱ

L-1

c = 0

c H + n_cⁱ

The rows aH+b which differ from some aH + n_aⁱ correspond to rows in W_i^c. For future use, we denote the set (È_k=0^S-1 W_k) by W. Hence the components of C_i x^® fall into three categories:

components (C_i x^®)_r, where r Î W_i
components (C_i x^®)_r, where r Î W Ç W_i^c; these are identity rows for C_i, but not necessarily for any other C_k.
components (C_i x^®)_r, where r Î W^c; these are identity rows for any C_k

Note that it follows from above that the elements (C_i x^®)_r with r Î W lie in V; hence, V is closed under the action of C_i restricted to the rows W. Hence, if x^® Î V, then all components from the third category can be ignored. The components of C_i x^® are then

C_i

é
ê
ê
ê
ë

x_k,

k Î W_i^c

x_k - b

j Î W_i

x_j,

k Î W_i

ù
ú
ú
ú
û

Let w^® be an eigenvector of C_i corresponding to eigenvalue 1. Then C_i w^® = w^® implies

é
ê
ê
ê
ë

w_k,

k Î W_i^c

w_k, - b

j Î W_i

w_j,

k Î W_i

ù
ú
ú
ú
û

é
ë

w_k,	k Î W_i^c
w_k,	k Î W_i

ù
û

It follows immediately that the basis vectors e_k, k Î W_i^c are eigenvectors of C_i with eigenvalue 1. In addition, the vector

é
ë

w_k	k Î W_i
0,	k Î W_i^c

ù
û

with å_{j Î W}_{_i} w_j = 0 is also an eigenvector for eigenvalue 1. Indeed, if å_{j Î W}_{_i} w_j ¹ 0, such w^® cannot be an eigenvector for eigenvalue 1. Hence, we can describe the set of such eigenvectors by W_i = {x^® Î Â^LH : A_i^T · x^® = 0 }.

Further, if w^® is an eigenvector of C_i corresponding to eigenvalue x ¹ 1, then C_i w^® = x w^® implies

é
ê
ê
ê
ë

w_k,

k Î W_i^c

w_k - b

j Î W_i

w_j,

k Î W_i

ù
ú
ú
ú
û

é
ë

x w_k,	k Î W_i^c
x w_k,	k Î W_i

ù
û

Since x ¹ 0 (C_i is invertible), we have w_k = 0 for k Î W_i^c and w_k - b å_{j Î W}_{_i} w_j = x w_k for all k in W_i. Hence,

(1-x) w_k

j Î W_i

w_j, " k Î W_i

and summing over W_i, we have

(1-x - b L)

j Î W_i

w_j.

Since the eigenvalue x ¹ 1, we must have å_{j Î W}_{_i} w_j ¹ 0 and hence x = 1 - b L = 1 - l.

We conclude that the eigenvalues of C_i are either 1 or 1 - l. Hence, the vector

é
ë

1,	k Î W_i
0,	k Î W_i^c

ù
û

A_i^T

is an eigenvector corresponding to eigenvalue x = 1 - l.

Also, the square of the norm of C_i x^®, for vectors x^® Î V is given by

| C_i

|²

j Î W_i^c

x_j² +

j Î W_i

æ
ç
ç
è

x_j - b (

p Î W_i

x_p)

ö
÷
÷
ø

j Î W_i^c

x_j² +

j Î W_i

x_j² + (L b² - 2 b )

æ
ç
ç
è

j Î W_i

x_j

ö
÷
÷
ø

N-1

j=0

x_j² + (L b² - 2 b )

æ
ç
ç
è

j Î W_i

x_j

ö
÷
÷
ø

1 - b (2 - b L)

æ
ç
ç
è

j Î W_i

x_j

ö
÷
÷
ø

Since b = l/L, for 0 < l < 1 and L ³ 1 we have b < 1 and 2 - b L > 0. Thus, on V, it is clear that the norm is less than or equal to one. From our discussions above, it is immediate that on the subspace V - W_i, the norm of C_i is actually 1 - l.

5.4 Convergence Analysis:

From the above section, it follows that if we restrict our attention to the subspace of Â^LH consisting of V - W₀, we have | | C₀ | | = 1 - l and

\| \| D \| \|	£	\| \| C_S-1 \| \| ··· \| \| C₁ \| \| \| \| C₀ \| \|
	<	1 ··· 1 · (1 - l) < 1.

Hence, D has norm less than one and the infinite series

(I + D + ··· + D^t + ··· )

converges to a matrix P as t ® ¥ as long as V^T lies out of the subspace W₀. This is equivalent to satisfying the condition

A₀ · V^T.

Moreover, it is clear that on V - W₀, I - D is invertible and

(I - D)^-1

Thus, the solution to the CMAC learning algorithm is given in closed form by (I - D)^-1 V^T, where the inverse is computed relative to the subspace V - W₀. Finally, if we calculate the difference between successive sweeps of the training algorithm, we see

^t+1,S-1 -

^t,S-1

b D^t V^T

^t+1,S-1 -

^t,S-1 |

b | | D | |^t | V |

(1 - l)^t | V |.

This implies that the rate of convergence of the training algorithm is approximately 1 - l.

5.4.1 The Structure of V^T:

It remains to study the condition that A₀ · V^T ¹ 0. Since V^T is defined as

V^T =

S-1

k=1

C_S-1 C_S-2 ··· C_k A_k-1^T b_k-1 + A_S-1^T b_S-1

we must have

S-1

k=1

A₀ C_S-1 C_S-2 ··· C_k A_k-1^T b_k-1 + A₀ A_S-1^T b_S-1

S-1

k=1

A₀ C_S-1 C_S-2 ··· C_k A_k-1^T b_k-1 + m_0,S-1 b_S-1.

Let V_p^T = å_k=1^p C_p C_p-1 ··· C_k A_k-1^T b_k-1 + A_p^T b_p. Consider

A₀ · V₁^T = A₀(C₁A₀^Tb₀ + A₁^Tb₁)

= A₀(I-b A₁^T A₁)A₀^Tb₀ + m₀₁b₁

= (A₀ - b m₀₁ A₁) A₀^T b₀ + m₀₁b₁

= (L - b m₀₁²)b₀ + m₀₁b₁

A₀ · V₂^T	=	A₀(C₂C₁A₀^Tb₀ + C₂A₁^Tb₁ + A₂^Tb₂)
	=	A₀(I-b A₂^T A₂)(I-b A₁^T A₁)A₀^Tb₀ + A₀(I-b A₂^T A₂)A₁^Tb₁ + m₀₂b₂
	=	(A₀ - b m₀₂A₂)(A₀^T - m₀₁ b A₁^T)b₀ + (A₀ - b m₀₂ A₂)A₁^Tb₁ + m₀₂b₂
	=	(L - b (m₀₁² + m₀₂²) + b² m₂₁m₀₂m₀₁)b₀ + (m₀₁ - b m₀₂m₁₂)b₁ + m₀₂b₂

A₃ · V₂^T	=	A₃(C₂C₁A₀^Tb₀ + C₂A₁^Tb₁ + A₂^Tb₂)
	=	A₃(I-b A₂^T A₂)(I-b A₁^T A₁)A₀^Tb₀ + A₃(I-b A₂^T A₂)A₁^Tb₁ + m₃₂b₂
	=	(A₃ - b m₃₂A₂) (A₀^T - m₀₁ b A₁^T) b₀ + (A₃ - b m₃₂ A₂)A₁^Tb₁ + m₃₂b₂
	=	(m₀₃ - b (m₀₁m₃₁+m₃₂m₂₀) + b² m₃₂m₀₁m₂₁)b₀ + (m₃₁ - b m₂₁m₃₂)b₁ + m₃₂ b₂

A₀ · V₃^T	=	A₀(C₃ V₂^T) + A₀ A₃^Tb₃
	=	A₀(I-b A₃^T A₃)V₂^T + m₀₃b₃
	=	A₀ V₂^T - b m₀₃ A₃ V₂^T + m₀₃ b₃
	=	(L - b (m₀₁² + m₀₂²+m₀₃²) + b² (m₂₁m₀₂m₀₁ +m₀₃m₀₁m₃₁+m₀₃m₃₂m₂₀)
		- b³ m₀₃m₃₂m₀₁m₂₁)b₀
		+ (m₀₁ - b (m₀₂m₁₂+m₀₃m₃₁) + b²(m₀₃m₂₁m₃₂))b₁
		+ (m₀₂ -b m₀₃m₃₂)b₂ + m₀₃b₃

Since b = l/L, A₀ · V₃^T can be rewritten as

A₀ · V₃^T

(1 - l (p₀₁² + p₀₂²+p₀₃²) + l² (p₂₁p₀₂p₀₁ +p₀₃p₀₁p₃₁+p₀₃p₃₂p₂₀)

- l³ p₀₃p₃₂p₀₁p₂₁)b₀

+ (p₀₁ - l (p₀₂p₁₂+p₀₃p₃₁) + l²(p₀₃p₂₁p₃₂))b₁

+ (p₀₂ -l p₀₃p₃₂)b₂ + p₀₃b₃.

Assume for the moment that there were just three samples, i.e., S = 3. Then the condition above for A₀ · V₃^T ¹ 0 determines the convergence of the chosen CMAC architecture. Let us assume that the overlap between A₀ and any other address A_i, for i ¹ 0, is a fixed percentage p. For example, it is reasonable to assume that p = L-2/L. Then we have

A₀ · V₃^T

(1 - 3 p²l + 3 p³ l² - p⁴ l³)b₀ + (p - 2 p² l + p³ l² )b₁

+ (p - p² l )b₂ + p b₃

(1 - 3 p µ + 3 p µ² - p µ³ )b₀ + p(1 - 2 µ + µ² )b₁ + p(1 - µ )b₂ + p b₃

(1-p)b₀ + p

(

(1 -3 µ + 3 µ² - µ³)b₀ + (1 - 2 µ + µ² )b₁ + (1 - µ )b₂ + b₃

)

(1-p)b₀ + p

j=0

(1-µ)^j b_3-j

where µ = p l. The convergence criterion is therefore

(1-p) b₀ + p

j=0

(1 - p l)^j b_3-j.

If we assume the uniform overlap condition that p_0i = p for all addresses other than the zeroth, a standard induction argument leads to the following convergence criterion:

(1-p) b₀ + p

S-1

j=0

(1 - p l)^j b_S-1-j.

This condition is easy to check numerically for a given hash, field width, level strategy and I/O data set; indeed, it is recommended that code to implement this sort of check be used routinely. There has never really been a problem with the CMAC training algorithm converging; the explanation is that the criterion above shows convergence is insensitive to the choice of hash size H, number of levels L, receptive field width w and I/O data set.

5.5 Quality of Solution:

The quality of the approximation is another question. Let x^® denote the converged solution to the CMAC training algorithm. Then the quality of this solution is determined by the error term

S-1

j=0

(A_j

- b_j)²

S-1

j=0

(b A_j (I - D

)

-1

| V- W₀

V^T - b_j)².

The first order approximation to the quality of this solution is found by choosing b and p so that

E₁

S-1

j=0

(b A_j (I + D) V^T - b_j)²

S-1

j=0

(b A_j V^T + b A_j D V^T - b_j)²

is minimized. Now consider terms of the form A_j^T V^T for the same uniform overlap condition; we have

A_j · V₁^T = A_j(C₁A₀^Tb₀ + A₁^Tb₁)

= A_j(I-b A₁^T A₁)A₀^Tb₀ + m_j1b₁

= (A_j - b m_j1 A₁) A₀^T b₀ + m_j1b₁

= (m_j0 - b m_j1m₁₀)b₀ + m_j1b₁

=

p [ (1-b p)b₀ + b₁ ]

A_j · V₂^T

A_j(C₂C₁A₀^Tb₀ + C₂A₁^Tb₁ + A₂^Tb₂)

A_j(I-b A₂^T A₂)(I-b A₁^T A₁)A₀^Tb₀ + A_j(I-b A₂^T A₂)A₁^Tb₁ + m_j2b₂

(A_j - b m_j2A₂)(A₀^T - m₀₁ b A₁^T)b₀ + (A_j - b m_j2 A₂)A₁^Tb₁ + m_j2b₂

(m_j0 - b (m_j1m₀₁ + m_j2m₀₂) + b² m_j1m₂₁m₀₁)b₀ + (m_j1 - b m_j2m₁₂)b₁ + m_j2b₂

[

(1 - 2b p + b² p²)b₀ + (1 - b p )b₁ + b₂

]

j=0

(1 - b p)^j b_2-j

A_j · V₃^T

A_j(C₃ V₂^T) + A_j A₃^Tb₃

A_j(I-b A₃^T A₃)V₂^T + m_j3b₃

A_j V₂^T - b m_j3 A₃ V₂^T + m_j3 b₃

(1 - p b)

é
ê
ê
ë

j=0

(1 - b p)^j b_2-j

ù
ú
ú
û

+ p b₃

j=0

(1 - b p)^j b_3-j

A standard induction argument then implies

A_j · V^T

S-1

j=0

(1 - b p)^j b_S-1-j.

Similary, the terms A_j D can be obtained from (5.13):

A_j D

A_j

æ
ç
ç
è

I - b

S-1

i=0

A_i^T A_i +

S-1

k=1

(i₀,i₁,···,i_k) Î Q_k^S-1

(-1)^k+1 b^k+1 p^k A

i₀

i_k

ö
÷
÷
ø

A_j - b

S-1

i=0

m_ji A_i +

S-1

k=1

(-1)^k+1 b^k+1 p^k

(i₀,i₁,···,i_k) Î Q_k^S-1

j,i₀

i_k

A_j - b p

S-1

i=0

A_i +

S-1

k=1

(-1)^k+1 b^k+1 p^k+1

(i₀,i₁,···,i_k) Î Q_k^S-1

i_k

Hence, A_j D V^T has the form

A_j D V^T

A_j V^T - b p

S-1

i=0

A_i V^T +

S-1

k=1

(-1)^k+1 b^k+1 p^k+1

(i₀,i₁,···,i_k) Î Q_k^S-1

i_k

V^T

æ
ç
ç
è

1- b p

S-1

i=0

S-1

k=1

(-1)^k+1 b^k+1 p^k+1

(i₀,i₁,···,i_k) Î Q_k^S-1

ö
÷
÷
ø

æ
ç
ç
è

æ
è

ö
ø

b p +

S-1

k=1

æ
è

k+1

ö
ø

(-1)^k+1 (b p)^k+1

ö
÷
÷
ø

k=0

æ
è

ö
ø

(-1)^k (b p)^k

D (1 - b p)^S

where, for convenience, we set A = å_k=0^S-1 (1 - b p)^k b_S-1-k and D = p A. Thus, the first order quality condition is obtained by choosing b and p so that we minimize

E₁

S-1

j=0

(

b D (1+ (1 - b p)^S) - b_j

)

S-1

j=0

(

b p A(1+ (1 - b p)^S) - b_j

)

Letting t = 1 - b p and B = å_k=1^S-1 k t^k-1 b_S-1-k, we see

E₁

S-1

j=0

(

b p A (1 + t^S) - b_j

)

S-1

j=0

(

(1-t^S+1) A - b_j

)

¶ E₁

¶ t

S-1

j=0

(

(1-t^S+1) A - b_j

)

æ
ç
ç
è

-(S+1)t^S A + (1-t^S+1)

¶ A

¶ t

ö
÷
÷
ø

S-1

j=0

(

(1-t^S+1) A - b_j

)

(

-(S+1)t^S A + (1-t^S+1) B

)

S-1

j=0

(

(1-t^S+1)² A B -(1-t^S+1)(S+1) A² + b_j (S+1) t^S A - b_j (1+t^S+1) B

)

æ
ç
ç
è

(1-t^S+1) A

ö
÷
÷
ø

(

S(1-t^S+1) B -S(S+1) t^S A

)

where b^_ denotes the average of the output data vector b^®. The first order extremum occurs when this derivative is zero. The simplest condition for a critical point is

æ
ç
ç
è

(1-t^S+1) A

ö
÷
÷
ø

æ
ç
ç
è

(1-t^S+1)

S-1

k=0

t^k b_S-1-k -

ö
÷
÷
ø

(5.13)

It is easy to see that at this critical t value, E₁ = .5 S s², where s is the standard deviation of the output data.

If we let the function g(t) = (1-t^S+1) å_k=0^S-1 t^k b_S-1-k - b^_, we see that g(1) = - b^_ and g(0) = b_S-1 b^_. Under reasonable conditions, there is a change in sign at these two values and hence by the intermediate value theorem, there is a root, t^*, satisfying g(t^*) = 0 with 0 < t^* < 1. Thus,

p b

= 1 - t^*

giving a design condition for the number of levels

p l

1-t^*

where the value of t^* must be obtained numerically. Thus, it is best if the condition (5.14) is approximated numerically at the beginning of the CMAC architecture initialization. Note also that this t^* value is only an approximate solution to our quality problem. We are only using the first two terms of the CMAC solution b å_j=0^¥ D^j V^T; inevitably, this will cause error. Numerical studies can give better insight, at the cost of increased computation. It seemed a reasonable tradeoff to use this simple approximation to obtain a ``ballpark'' qualtiy condition. Note that condition (5.14) also gives information about how to choose the overlap percentage p, which is closely related to the hashing strategy H and the sensor field width. If we choose to have an overlap of 80 % at all addresses, then p = .8 and we must choose the sensor field width w to achieve this overlap. Since the sensor field width is usually taken to be b-a/L, the ratio of the interval width to the number of levels, this gives additional constraints on our choices.

Finally, note that higher order quality criteria can, in principle, be found by including additional terms of the form D^t for t >1 in the error function approximation. While tedious, these conditions can be generated.

The analysis above looks carefully at the quality of the CMAC approximation to the original sample set { (p_i,b_i) : i = 0, S-1 }. The question of the quality of the generalization capabalities of the CMAC approximation has not been answered. Analysis similar in spirit to the arguments given above can be used to generate a variety of first order conditions for the generalization capacity of the CMAC model. We will report on these studies separately in a fuller study of local to global modelling using CMAC architectures.

5.6 Solution Magnitude and Range Estimates:

Let x denote the converged value of the weights in a particular CMAC architecture and p^® be an arbitrary input vector from Â^N. Associated to this input vector is an address vector A^T that consists of L blocks of length H; the values in each block are all zeroes, except a single 1 at some index within the block. As discussed in Section 5.2, the CMAC output is then given by g(p^®):

)

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë

·
·
·

position

n₀(

)

·
·
·

position

H + n₁(

)

·
·
·

position

(L-1)H + n_L-1(

)

·
·
·

ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û

where n_j(p^®) denotes the local address for level j. Then

| g(

b | A

t=0

D^t V^T |

b | A |

æ
ç
ç
è

t=0

| | D | |^t

ö
÷
÷
ø

| V |

sqrt(L) b

1-| | D | |

| V |

sqrt(L)

1-(1-l))

| |

æ
ç
ç
è

S-1

k=1

C_S-1 ··· C_k A_k-1^T b_k-1 + A_S-1^T b_S-1

ö
÷
÷
ø

| |

S-1

k=0

| b_k |.

Hence, the range of the CMAC function is the ball of radius r = å_k=0^S-1 | b_k |.

The magnitude of the converged solution to the CMAC training is also easily estimated from the argument above:

| x |

b |

t=0

D^t V^T |

sqrt(L)

S-1

k=0

| b_k |.

It is therefore clear that the magnitude of the converged solution is determined by the magnitudes of the elements in the training data set.

5.7 Conclusion:

We have shown that the CMAC training algorithm will converge with rate 1 - l as long as the condition A₀ · V^T ¹ 0 is satisfied. For the conceptually easier case of a uniform overlap percentage p, this condition for S samples becomes

(1-p) b₀ + p

S-1

j=0

(1 - p l)^j b_S-1-j.

We have also shown that, in the case of uniform overlap, a first order condition for a quality solution is given by

æ
ç
ç
è

(1-t^S+1)

S-1

k=0

t^k b_S-1-k -

ö
÷
÷
ø

Both of these conditions are best checked numerically during the usual CMAC initialization process. Finally, we have shown that the range of the CMAC architecture lies in the ball of radius r = å_k=0^S-1 | b_k | and that the magnitude of the solution is bounded by r/sqrt(L) .

Note that the analysis above is essentially unchanged; we merely use the average overlap p^{^} instead of assuming a uniform overlap. All first order conditions will then be phrased in terms of p^{^} instead of p.

The application of this methodology to local to global modelling issues and the determination of first order conditions for the quality of generalization will be discussed in separate work. We finish by noting these techniques are also useful in the study of more complex CMAC--based architectures. These include architectures which use analog rather than binary sensors with clustering strategies, as well as hierarchical structures involving multiple CMAC architectures at different levels of resolution.

C₁ C₀	=	I - b (A₀^T A₀ + A₁^T A₁) + b² A₁^T A₁ A₀^T A₀
	=	I - b (A₀^T A₀ + A₁^T A₁) + b² A₁ A₀^T (A₁^T A₀)
	=	I - b (A₀^T A₀ + A₁^T A₁) + b² m₁₀ (A₁^T A₀)

	COL
ROW	0	···	r₀^i,-	r₀ⁱ	r₀^i,+	···	r_L-1^i,-	r_L-1	r_L-1^i,+	···	LH^-
0	1	0	0	0	0	···	0	0	0	0	0
:	:	ddots	:	:	:	:	:	:	:	:	:
r₀^i,-	0	0	1	0	0	:	0	0	0	0	0
r₀ⁱ	0	0	0	1-b	0	:	0	-b	0	0	0
r₀^i,+	0	0	0	0	1	:	0	0	0	0	0
:	:	:	:	:	:	ddots	:	:	:	:	:
r_L-1^i,-	0	0	0	0	0	:	1	0	0	0	0
r_L-1ⁱ	0	0	0	- b	0	:	0	1-b	0	0	0
r_L-1^i,+	0	0	0	0	0	:	0	0	1	0	0
:	:	:	:	:	:	:	:	:	:	ddots	:
LH^-	0	0	0	0	0	:	0	0	0	0	1

A₀ · V₁^T	=	A₀(C₁A₀^Tb₀ + A₁^Tb₁)
	=	A₀(I-b A₁^T A₁)A₀^Tb₀ + m₀₁b₁
	=	(A₀ - b m₀₁ A₁) A₀^T b₀ + m₀₁b₁
	=	(L - b m₀₁²)b₀ + m₀₁b₁

Chapter 5: CMAC Convergence:

5.1 Introduction:

5.2 CMAC Training:

5.3 The Matrix Form:

5.3.1 The CMAC Training Generator Matrix:

5.3.2 The Structure of D:

5.3.3 The Structure of Ci:

5.4 Convergence Analysis:

5.4.1 The Structure of VT:

5.5 Quality of Solution:

5.6 Solution Magnitude and Range Estimates:

5.7 Conclusion:

5.3.3 The Structure of C_i:

5.4.1 The Structure of V^T: