On Multi-Layered Connectionist Models: Adding Layers vs. Increasing Width

1 Introduction

For studying learning in the multi-layered connectionist models, It is important to understand the computational potential and limitations of the multi-layered connec­ tionist models. The single layered connectionist models have limited computational ability. For example, there is no single layered connectionist machine which can com­ pute the 'exclusive or' of two bits. But the 'exclusive or' problem can be solved by a 2-layer connectionist ma­ chine. However, the computational ability of2-layer con­ nectionist models depends on the width of the models. We define the width of a connectionist machine to be the maximum number of neurons in one layer of the connec­ tionist machine. The number of layers and the width are two crucial parameters for the multi-layered connection­ ist models. In this paper, we examine two extreme cases of the multi-layered connectionist models. In the first case, we fix the width of the multi-layered connectionist models and see what happen when the number of layers is increased. In the second case, we fix the number of layers to be two and see what happen when the width is increased. Our result is that in the first case, if each layer has the same size n and we increment the number of layers by 1, then the number of problems solved will increase O(nn 3 ) times; in the second case, when we in­ crement the width by 1, the number of problem solved will increase O(nn 2 ) times, where n is the input size.

2 Layered Connectionist models

A layered connectionist machine is a special case of con­ nectionist models. It has t layers and one input layer (layer zero) . The input (bottom) layer contains n input neurons. The last (top) layer contains m output neu­ rons. Each of the remainder layers contains w neurons. For i = 0, ... , t- 1, there are links connecting the neu­ rons in layer i to the neurons in layer ( i + 1); no other links exist. The following is a formal definition of layered connectionist machines.

Definition A layered connectionist machine is a 7-tuple (t, w, n, m, C, B, A), where

1. t is a positive integer defining the number of layers.
2. w is a positive integer defining the width of the model.
3. n is a positive integer defining the input size of the model.
4. m is a positive integer bounding the output size of the model.
5. C is a set of neurons. C = L0 U L1 U · · · U Lt where Lo = {Cot, Co2, .. . , Con} is the set of input neu­ rons, Lt = { Ctt, Ct2, .. . , Ctm} is the set of output neurons, and L; = { C;j : j = 1, . . . , w} is the set of neurons in layer i for i = 1, . .. , t - 1. We denote by JLd the number of elements in L; for i = 0, 1, ... , t. Clearly, JL0 J = n, ILtl = m and JL;J = w fori= 1, ... , t- 1.
6. B is a set of real numbers . 1, .. . ,t; and j = 1, ... ,JLd} the threshold of C;j. B = {b;i : i where b;j serves as
7. A is a set of matrices. A = {A1 , A2, . .. , At} where A; = ( aijk) is a matrix of real numbers whose entry aijk represents the connection weight with which ci-l,j affects ci ,k for i = 1, 0 0 0 't and j = 1, .. . , JL;-tl and k = 1, .. . , JL;J .

Each neuron C;j has a binary value Vij. Initially, the values Vot, vo2, .. . , Von are set to the input values. At time i, i = 1, . .. , t , the values of neurons in the ith layer are determined by the following formula :

for k = 1, 2, . .. , IL;I. Clearly, the computation time for a layered connectionist machine with t layers is t.

Example 1 The following is an example of layered con­ nectionist models with 3 input neurons, 2 output neu­ rons, 4 layers and width 5:

Let Hnm(t) denote a class of problems solved by lay­ ered connectionist machines with n input neurons, m output neurons, t layers and width w = max{ n, m }. We denote by IHnm(t)l the number of elements in Hnm(t).

We regards each problem in Hnm(t) as a mapping from {0, 1}n to {0, l}m. Thus, each problem in Hnm(t) can be represented as a function f(xl, x2, ... , Xn) = Yl···Ym where xl,x2·····Xn,Yl,Y2·····Ym E {0,1}. For j = 1, 2, ... , m, each Yi is a Boolean function in X!,x2, ... ,Xn. We write Yi = /j(x!,X2, ... ,xn)· f can be specified with m Boolean functions, It, h, ... , f m. There are 2n possible combinations of binary input val­ ues. Therefore, IHnm(t)l ~ 2m 2 n. As we know, the Boolean functions can be expressed in sum of products form. The product terms are AND terms and the sum denotes the ORing of product terms.

Example 2 f(x1,x2,x3) = X1X2X3 + X1X2X3 + X1X2X3 is the sum of products form off where Xj is the comple­ ment of x; for j = 1, 2, 3.

Lemma 1 Suppose the sum of products form of a Boolean function f(xl, x2, ... , Xn) contains single prod­ uct term. Then, f E Hn1(1). In other words, f can be computed by a single layered connectionist machine.

Proof In the product term, either x; or x; appears fori = 1, ... , n . Let U = { i : x; appears in the product term} and V = {j : Xj appears in the product term}. Suppose the number of elements in U is p and the number of elements in Vis q. Clearly, Uu V = {1,2, ... ,n} and p + q = n . We construct a single layered connectionist machine for computing f( x1 , ... , Xn) as follows:

The set of neurons C = La U L1 where La = { x1, x2, ... , Xn} is the set of input neurons and L1 = {y} is the set of the output neuron. Let b = p - 1 be the threshold of y. For i = 1, ... , n, suppose a; is the con­ nection weight with which x; affects y. We let a; = 1 if i E U; let a; = -1 otherwise. Clearly, y = 1 only when all x; (i E U) and x; (j E V) are equal to 1. Hence, this single layered connectionist machine computes f. 0

following single layered connectionist machine:

We don't know if there exists an integer to such that IHnm(to)l = 2m 2 n. However, the following lemma shows that any boolean function f(xl, ... , Xn) = Y1 · · · Ym can be computed by a layered connectionist machine M = (2n,w,n,m,C,B,A) ifw 2: n+m.

Lemma 2 Let Tnm(t) denote a class of problems solved by layered connectionist machines with n input neurons, m output neurons, t layers and width w = n + m. Then, ITnm(2n)l = 2m2 n ·

Proof It is equivalent to show that for an arbitrary func­ tion f : {0, l}n ~ {0, l}m there is a layered connection­ ist models M = (2n, n + m, n, m, C, B, A) which com­ putes f. Let t1 = 2n. f can be specified with m Boolean functions, ft,f2, .. . ,fm· Each/; (j = 1,2, ... ,m) can be represented by a sum of products form. The sum of products forms can be embedded in a layered connec­ tionist model M = (2n,n+ m,n,m,C,B,A) as follows:

The input values pass to neurons Gil, C;2 , ... , C;n at time i for i = 1, 2, ... , t 1 - 1. This can be achieved by setting weight a;kk = 1 and threshold b;k = 0 for k = 1, 2, ... , n . v; 1 , v;2 , ... , V;n serve as inputs to Ci+l,n+i for j = 1, 2, ... , m. The ith product term of /j is corresponding to the single layered subnetwork with nodes C;_11 , C;_1 2, ... , C;_1 n and C; n+i· For k = 1, 2, .. . , n, ~e set the weight 'aik,n+i (~ith which ci-l,k affects ci,n+j) and threshold bi,n+i by using the method described in Lemma 1 and Example 3. Now, for fixed j (1 ~ j ~ m), we need only to sum (OR) all of the values in C1,n+i, C2,n+i, ... , Ct,,n+i . This can be done by setting ai,n+ j,n+i = 2n for i = 2, ... , t1 . All the other weights and thresholds which haven't been men­ tioned are set to zero.

We have finished the description of the layered con­ nectionist model M. The number of product terms in /j (j = 1, 2, ... , m) can not be greater than 2n. Hence, M computes f. 0

Example 4 The following layered connectionist model for computing f = xy + xy is constructed by using the method described in Lemma 2. Note: all the thresholds are zero.

Next, we will separate Hnm(t + 1) from Hnm(t) . Let K = max{IHnm(t)l: t ~ 1}.

Then, clearly IHnm(t)l :5 K :52m 2 " fort~ 1.

Theorem 3 For t ~ 1, if IHnm(t)l < K, then IHnm(t)l < IHnm(t + 1)1.

Proof If IHnm(t)l < K and IHnm(t)l = IHnm(t+ 1)1, we will show that IHnm(t)l = IHnm(t + i)l fori ~ 1 which lead to a contradiction. Clearly, Hnm(t) ~ Hnm(t + 1) . If IHnm(t)l = IHnm(t + 1)1, then Hnm(t) = Hnm(t + 1). For showing Hnm(t) = Hnm(t+i) fori~ 1, we need only to show that Hnm(t + 1) = Hnm(t + 2). Let us consider the case oft+2. Obviously, Hnm(t+1) ~ Hnm(t+2) and IHnm(t+ 1)1 :5 1Hnm(t+2)1. For any f(xl, X2, ... , Xn) E Hnm(t + 2), we consider two cases:

Case 1, m > n : there exists a layered connectionist model M = (t + 2, m, n, m, C, B, A) which computes f. Each Vt+l,j (j = 1, 2, ... , m) in M can be represented as a Boolean function in x1, x2, ... , Xn. Since Hnm(t) = Hnm(t + 1), there is a layered connectionist model N = (t + 1, m, n, m, C', B', A') such that v~i = Vt+l ,j for j = 1, 2, ... , m, where v~i is the value of c;i . We can let A~+l = At+2 so that N also computes f.

Case 2, m < n : there exists a layered connec­ tionist model M = (t + 2,n,n,m,C,B,A) which com­ putes f. We can write f = g(vu,vl2·····Vln)· Since Hnm(t) = Hnm(t + 1), there is a layered connection­ ist model N' = (t + 1, n, n, m, C", B", A") such that f ( II II II ) h II · th 1 f C" = g v11 ,v12 , ... ,v1n, were v1i IS e vaue o lj for j = 1, 2, ... , n . We can let A~= A1 . Thus, v~'i = Vlj for j = 1, 2, ... , n; so that N' also computes f .

Thus, f E Hnm(H1); hence, Hnm(H2) ~ Hnm(t+1). Therefore, Hnm(t+1) = Hnm(t+2); and thusHnm(t) = Hnm(t + i) for i ~ 1. Let to be an integer auch that IHnm(to)l = K. If IHnm(t)l < K, then it is impossible that t ~to. However, ift <to, then we have Hnm(to) <

K. Contradiction. Hence, IHnm(t)l < IHnm(t+1)1. D Corollary 4 If IHnm(t)l < K then Hnm(t) C Hnm(t + 1).

Proof Clearly, Hnm(t) ~ Hnm(t + 1) . But, by Theorem 3, Hnm(t) =/; Hnm(t + 1). Hence, Hnm(t) C Hnm(t + 1). D

By Corollary 4, Hnm(t + 1) can be separated from Hnm(t) . There exists a function f E Hnm(t + 1) but f rf. Hnm(t).

Suppose M = (t,w,n,m,C,B,A) is a layered connec­ tionist machine. If we add one layer to M, we will add w2 links to M; and thus w 2 weights are added to M. The following theorem is due to [Hong, 1987].

Theorem 5 {Hong) Suppose r1, r2, .. . , rn are real numbers. There exists integers m1, m2, ... , mn such that the length of mi (j = 1, 2, .. . , n) is O(n log n) and for anyc1,c2, ... ,cn in {0,1}, we have

r1, r2, ... , rn are said to be simulated by m1, m2 , ... , mn .

By Theorem 5, each weights added can be simulated by an integer with binary length O(wlogw) . Thus, w 2 weights has total binary length 0( w 3 log w) . There­ fore, by adding one more layer to M, we can create 0( ww 3 ) different layered connectionist machines. Hence, ITnm(t + 1)1 is O((n + m)<n+m) 3 ) times of ITnm(t)l. But O((n + m)<n+m) 3 ) = 0(2(n+m) 4 ). Thus, ITnm(t)l = 0(2t(n+m) 4 ). We conclude that if ITnm(t)l =2m2" , then

If m = O(n), then t = 0{2" /n 3 ). It means that if w = O(n) then 0(2" /n 3 ) layers are needed for comput­ ing an arbitrary function with input size n and output size O(n).

3 2-Layer Connectionist models

Let M = (t, w, n, m, C, B, A) be a layered connectionist machine. If t = 2, we call M a 2-layer connectionist machine. A 2-layer connectionist machine is a special case of connectionist models. It has an input layer, an intermediate layer and an output layer. We denote by w the size of the intermediate layer. There are links con­ necting the neurons in the input layer to the neurons in the intermediate layer and there are links connecting the neurons in the intermediate layer to the neurons in the output layer; no other links exist. Clearly, the computa­ tion time for a 2-layer connectionist machine is 2.

Let Wnm(w) denote a class of problems solved by 2layer connectionist machines with input size n , output size m and width w . We denote by IWnm(w)l the number of elements in Wnm(w) .

Each problem in Wnm(w) can also be regarded as a function

where xl,X2, .. . ,Xn 1 Yl,Y2·····Ym E {0,1} . Moreover , each Yi (j = 1, 2, ... , m) is a Boolean function in x1, x2, ... , Xn. There are 2" possible combinations of binary input values. Therefore, we have IWnm(w)l :5 2m 2 " . In fact, for an arbitrary function f : {0, 1}" ~------+ {0, 1}m there is a 2-layer connectionist models M = (2, 2", n, m, C, B, A) which computes f. f can be spec­ ified with m Boolean functions, fl,f2, ... ,fm· Each fi (j = 1, 2, ... , m) can be represented by a sum of prod­ ucts form. Each n-digit input value has a corresponding product term such that the value will produce 1 for this product term. M can be constructed as follows:

Let vu , v12, ... , v1,2" represent 2n different product terms. This can be done by using the method described in Lemma 1 to set the weights alij(i = 1, ... , n; j = 1, ... , 2n) and thresholds b1i (j = 1, ... , 2n) to proper values. Then, for i = 1, .. . , 2n and j = 1, .. . , m, let a2;i = 1 if v1; is a product term in the sum of products form of /j ; let a2;j = 0 otherwise. Clearly, v2j = /j for j = 1, 2, . . . , m. Hence, M computes f. We thus proved the following lemma:

Theorem 7 For w 2:: 1, if IWnm(w)l < 2m 2 ", then Wnm(w) C Wnm(w + 1).

Proof Since IWnm(w)l < 2m 2 ", there exists a func­ tion f(xl, ... ,xn) ¢ Wnm(w). Suppose f is speci­ fied with m Boolean functions , ft , /2, .. . , fm· Let fi (j = 1, 2, ... , m) be represented as the sum of product form. We define

• S= {(d1, .. . , dm) : for j= 1,2, ... ,m, after delete dj product terms from fi, f will be in Wnm(w)}

Suppose (e1, ... ,em) E Sand there is ek , 1::; k::; m, such that d = ek . Let g(x1, ... , xn) E Wnm(w) be specified with m Boolean functions , Ul, g2, ... , Um such that gi is obtained by deleting ei product terms from /j for j = 1, ... , m. Suppose Pl, ... , Pd are the product terms deleted from fk . Let hk = Uk + p1 and let h be specified with gl , g2, ... , Uk-l· hk> Uk+l· ... , Um · Clearly, h ¢ Wnm( w), otherwise it will contradict to the defini­ tion of d. Suppose g is computed by a 2-layer connec­ tionist model M = (2, w, n, m, C, B , A) . We construct a 2-layer connectionist model N by adding one more neu­ ron C1 ,w+l to M such that i>1,w+1 = Pl (which can be done by using the method described in Lemma 1) and a2,w+l,k = LJ=l la2jkl + b2k + 1. Clearly, N computes h . Thus, h E Wnm(w + 1); but h ¢ Wnm(w). Hence Wnm(w) =f. Wnm(W + 1) . But Wnm(w) ~ Wnm(w + 1) . Hence, we have Wnm(w) C Wnm(w + 1). 0

Theorem 7 explains the space hierarchy of the 2-layer connectionist models. Suppose N = (2, w, n , m, C, B , A) is a 2-layer connectionist machine. If we add one neu­ ron to layer 1 of N, we will add (n + 1) links to N; and thus (n + 1) weights are added to N. By The­ orem 5 , each weight added can be simulated by an integer with binary length 0( n log n). Thus, ( n + 1) weights has total binary length O(n 2 logn) . Therefore, by adding one more neuron in layer 1 of N , we can , create O(nn ) different 2-layer connectionist machines. Hence, IWnm(w + 1)1 is O(nn') times of IWnm(w)l . But O(nn 2 ) = 0(2n 3 ). Thus, IWnm(w)l = 0(2wn 3 ), we con­ clude that if IWnm(w)l =2m 2 " , then

If m = O(n) , then w = S1(2n /n 2 ). It means that there exists a problem with input size nand output size O(n) which can only be solved by the 2-layer connectionist machines with width S1(2n fn 2 ).

4 Conclusion

Computational complexity for the connectionist models has not been studied much. In the complexity theory, we usually consider the uniform models. However, The connectionist models are non-uniform models. Little is known about the non-uniform models. [Hong, 1987] has proved the similarity between the connectionist models and other non-uniform models. Therefore, for the com­ plexity theory in the non-uniform models, we can just focus upon the connectionist models. In this paper, we presented time and space hierarchy in two extreme cases of the layered connectionist models. Open question: is there time and space hierarchy in the multi-layered con­ nectionist models?

If a function can not be learned by a 2-layer connec­ tionist model with width w = O(n), then, by Corollary 4 and Theorem 7, we may extend the 2-layer connec­ tionist model by adding layers or increasing width such that the extended model can learn this function . The total number of neurons in a connectionist machine is said to be the size of this machine. For computing any function with input size n and output size O(n), both 2-layer connectionist models and layered connectionist models with O(n) width need size S1(2n fn 2 ). But the 2-layer connectionist models always take time 2 whereas the layered connectionist models with O(n) width may take time S1(2n fn 3 ) . Therefore, for extending a 2-layer connectionist model, we suggest that increasing width is better than adding layers.

Acknowledgments

I thank Professor Jiawei Hong for many useful discus­ swns.