Discontinuities in recurrent neural networks
Abstract
This paper studies the computational power of various discontinuous real computational models that are based on the classical analog recurrent neural network (ARNN). This ARNN consists of finite number of neurons; each neuron computes a polynomial net-function and a sigmoid-like continuous activation-function. The authors introduce
Full text
Discontinuities in Recurrent Neural Networks Ricard Gavalda Departmentof Software (LSI) Universitat Politecnica de Catalunya Barcelona 08034, Spain E-mail: gav[email protected] c.es Hava T. Siegelmann Faculty of Industrial Engineering and Management Technion, Haifa 32000, Israel E-mail: iehav[email protected]hnion.ac.il Revised, June 9th, 1998 Abstract This pap er studies the computational p ower of various discontinuous real computational mo dels that are based on the classical analog recurrent neural network (ARNN). This ARNN consists of nite numb er of neurons each neuron computes a p olynomial net function and a sigmoid-likecontinuous activation function. Weintro duce \arithmetic networks" as ARNN augmented with a few simple discontinuous (e.g., threshold or zero test) neurons. We argue that even with weights restricted to p olynomial-time computable reals, arithmetic networks are able to compute arbitrarily complex recursive functions. We identify manytyp es of neural networks that are at least as p owerful as arithmetic nets, some of which are not in fact discontinuous but they b o ost other arithmetic op erations in the net function, e.g. neurons that can use divisions and p olynomial net functions inside sigmoid-likecontinuous activation functions. These arithmetic networks are equivalent to the Blum-Shub-Smale (BSS) mo del, when the latter is restricted to a b ounded numb er of registers. With resp ect to implementation on digital computers, weshow that arithmetic networks with rational weights can b e simulated with exp onential precision but even with p olynomial-time computable real weights arithmetic networks are not sub ject to any xed precision b ounds. This is in contrast with the ARNN that are known to demand only precision that is linear in the computation time. When nontrivial p erio dic functions (e.g. fractional part, sine, tangent) are added to arithmetic networks, the resulting networks are computationally equivalenttoa 1
massively parallel machine. Thus, these highly discontinuous networks can solve the presumably intractable class of PSPACE-complete problems in p olynomial time. 1 Intro duction Mo dels of computation are in the heart of all algorithms b ecause they sp ecify the primitive op erators which are in use. Cho osing an appropriate mo del of computation is of great imp ortance, but it presents us with a challenge. The mo del should capture the essential realistic features, while still b eing mathematically tractable. In mo dels of real numb er computation, one thinks of real numb ers as the atomic data items. This is in contrast with mo dels of discrete computation which handle binary digits. In real-valued mo dels, one assumes innite precision registers rather than bit registers, and a collection of op erations on real numb ers that are executed in unit time. There are two main elds where formal mo dels of computation with real numb ers are necessary. The rst is the study of biological, or biologically inspired, computations. Here, one admits that some natural systems up date according to the values of their real parameters rather that their base 2 representation. Second, in areas such as computational geometry or numerical analysis, algorithms are naturally expressed in terms of real numb ers. This double origin is the reason whytwotyp es of real mo dels have b een prop osed: continuous and discontinuous ones. Continuous systems allow for continuous functionalityonly,which is b elieved to b etter describ e most of biologically motivated computations. Among the b est studied continuous mo dels are most neural networks with continuous/analog activation functions 9,10,12,7], in particular those with recurrentinterconnection pattern. Real computational mo dels with discontinuities usually include innite-precision tests of equality and inequality, which are discon tinuous by denition. Although such tests with innite precision are often considered physically implausible, they are routinely used in algorithms in computational geometry,numerical analysis, and algebra. Twowell-established mo dels of this kind are the real RAM of Preparata and Shamos 20] and the real Turing machine suggested by Blum, Shub, and Smale 5], now usually called the BSS mo del. Mo ore 16] has recently prop osed still another mo del (in fact, a family of mo dels) for real-time analog computation. Neural networks constitute a particular typ e of real-valued mo dels. In this eld as well we are faced with continuous neurons such as sigmoidal ones, as well as discontinuous neurons such as McCullo ch-Pitts neurons. In this pap er we ask what dierence do es it maketo the computational mo del if our neurons are all continuous or if discontinuous neurons are incorp orated as well. Wecho ose as a starting p oint the continuous mo del called analog recurrent neural network (ARNN), typically used to analyze computational capabilities of neural networks, and consider several discontinuous extensions. The ARNN mo del suggested by Siegelmann and Sontag 25, 26 ] consists of a xed number of neurons in a general interconnection pattern. Each neuron is up dated by x i ( t +1) = ( ( ! x u )) i =1 :::N (1) 2
where the net function is a p olynomial combination of its input (formed by the external input u and input from other neurons x ! denotes the vector of constant co ecients or weights). It lters the result through the linear-saturated (ramp) activation function = : ( x )= 8 > < > : 1if x 1 x if 0 x 1 0if x 0 : Such networks are sometimes classied as rst-order and high-order , according to the degree of the p olynomial constituting the net-function. It was previously proven that high order and rst-order networks are computationally equivalent, even if other sigmoid-like, continuous, and Lipschitz activation functions are allowed b esides 26]. Here we will consider highorder networks only. In this mo del, input app ears to the network as a string of digits that enters a subset of the neurons, output is generated as a string as well (an equivalentmodel considers initial and nal states and no inputs and outputs). This mo del is equivalen tin power to Turing machines for rational weights (constants), and b ecomes of a nonuniform (ab oveTuring) p ower when the weights are reals. As a rst stage of adding discontinuities to the analog networks weintro duce in Section 3 the class of arithmetic networks. The simplest expression of this class is obtained by incorp orating threshold neurons H ( x )= ( 1 if x 0 0 if x< 0 into the nite interconnection of analog neurons constituting the ARNN. Weshowintwo dierentways that arithmetic networks are computationally stronger than high-order (continuous) networks. For this we concentrate on networks whose weights b elong to a very simple and small subset of real numb ers called p olynomial-time computable reals. A real number r is called polynomial-time computable if there is a p olynomial p and a Turing machine M such that M on input n will pro duce the rst n digits of the fractional part of r in time p ( n ). All algebraic numb ers, constants suchas and e ,and many others are p olynomial-time computable. To emphasize how small this class is, we note that there are no more p olynomial-time computable real numb ers than Turing machines, hence there are countably many of them. Furthermore it can b e shown 3] that, when used as constants in ARNN, networks still compute the class P only, just like in the case where all constants are rational numb ers. As the rst evidence of the arithmetic networks' sup eriority,weprove that arithmetic networks can recognize some recursive functions arbitrarily faster than Turing machines and ARNN they recognize arbitrarily complex recursive functions in linear time. The second evidence concerns the amount of precision required to implement arithmetic networks on digital computers. We show that no xed precision function is enough to simulate all arithmetic nets running in linear time. This contrasts with ARNN even with arbitrary real weights (where linear precision in the computation time suces) and arithmetic nets with rational weights (where exp onential precision suces). Hence, we obtain an interesting computational class of neural networks that is p otentially more p owerful than the Siegelmann and Sontag's nets 26, 24]. Both multiplications and 3
discontinuities seem necessary to obtain this class: high-order nets with only continuous, Lipschitz activation functions have at most the p ower of rst-order nets { they are actually equivalent to them for the saturated-linear function 26]. And it follows from a more general result of Koiran 13 ] that adding the threshold function to rst-order nets do es not increase their p ower, either. If we consider nets running in p olynomial time, this complexity class of arithmetic nets lies between the classes P and PSPACE (P PSPACE). The rst corresp onds to the p ower of socalled rst class serial machine mo dels, of which the Turing machine is a prime example. The latter corresp onds to second class mo dels, with the p ower of massively parallel computers, in which time is p olynomially equivalentto Turing-machine (rst class) space (see Section 2 for denitions of these classes, and 29] for an exp osition of rst and second-class mo dels). For all we know our class could coincide with P,PSPACE, b oth, or form a third intermediate class. Yet, if weshow that adding threshold strictly increases the p ower of networks we have actually shown that P 6 = PSPACE. Recall, however, that the conjecture P 6 = PSPACE, although widely b elieved, is a long-standing and notoriously dicult op en problem. We show in Section 4 that many other networks share the same prop erties. We rst notice that the threshold gates can b e substituted with the gates computing the exact zerotest gates = ( x )= ( 1if x =0 0if x 6 =0 : There is a wide family of activation functions whichgives at least the same (and p ossibly more) p ower as threshold or zero-test gates. Weshow that this holds for any function containing what we call \jump discontinuities". Another family is that of \launching functions", which throwvalues that are close to zero exp onentially far away an example is the square ro ot. An alternativewayistostay with the saturated linear activation function in all neurons, and increase the computational capabilities of the network by enlarging the set of op erators in the net function. One case is to allow the net function to compute divisions in addition to p olynomials. In fact, weprove that nets with division or square ro ot are equivalent in computational p ower to threshold or zero-test (up to p olynomials in the running time). In Section 5, weshow that networks with thresholds (or divisions) and some pretty natural p erio dic functions | such as fractional part, sine, or tangent | compute up to the upp er b ound: PSPACE. Such p erio dic functions, combined with the threshold (or division), provide innitely many p erio dic discontinuities as opp osed to the single discontinuityof the threshold. Our pro of relies strongly on the theorem by Bertoni, Mauri, and Sabadini stating that unit-cost arithmetic RAMs can solve all of PSPACE 4]. This result can b e considered as complexity-theoretic evidence that it is unrealistic to assume p erio dic and discontinuous functions together with innite precision. Of course, the assumption of innite precision is physically unrealistic anyway. So far, however, there is no evidence (suchasaPSPACE-hardness or an NP-hardness result) that innite precision by itself is more helpful than p olynomial precision, even in a theoretical sense. It is interesting to compare this theorem with a recent of Mo ore 16 ] which also demonstrates, in another context, the computation p ower added by p erio dic functions. He exhibits 4
a language that can b e recognized in real time with dynamical systems with sinusoidal activation functions but cannot b e recognized in real time, for example, by p olynomial or sigmoidal functions. Some of our results are proved for nets with arbitrary real weights, while others apply only to nets with rational weights only.Invariably, the restriction to rational numb ers app ears where our pro of technique requires a reasonable b ound on the smallest real numb er that can app ear during the computation in a net. This b ound is easy to obtain for rational weights, but as weshowed in Section 3 it is not p ossible to nd such a b ound for general real weights. This do es not necessarily imply that our missing results for real numb ers are false, but shows at least that very dierent pro of techniques will b e necessary. Before starting the technical part of the pap er, let us discuss the relationship with biological neuron networks. One p opular argument of discrediting the signicance of computational complexity to biological mo deling claims that: Not only are the articial mo dels far removed from nature, they also emphasize functions which require a lengthy resp onse. In contrast, nature is likely to resp ond in real or at least linear time. Being endowed with the feature of arbitrary sp eedup in some cases, and combining analog functioning with discontinuities, our mo del is p erhaps somewhat attractive for computational mo deling of neuron networks. However our network carries a feature whichis very unlikely to exist in biology: it allows for no robustness. This we termed as the lack of precision b ound as opp osed to the linear b ound existing in the analog mo dels. Weleave as an op en question the existence of network that has the desirable feature of sp eedup while still b eing sub ject to precision b ounds. 2 Preliminaries: Computational Mo dels In this section we provide the preliminaries from the eld of computational complexity that are required to understand the previous results as well as our new ones. We also present some known results on the computational p ower two real-valued mo dels: the ARNN and the BSS mo del. 2.1 Alphab ets, Strings, Languages In classical computation theory, inputs are enco ded as nite strings over a nite alphab et . Most of the times we assume that = f 0 1 g , although any other alphab et with at least two letters could b e used. The set ? is the set of all nite strings over . For a string x 2 ? , we use j x j to denote the length (or numb er of letters) of x . We identify often natural numb ers and strings via an easy isomorphism. Also, we assume the existence of an easily computable and invertible pairing function h : : i : ? ? 7! ? enco ding uniquely two strings into a third string. For example, we can enco de binary strings x and y by rst duplicating every bit of x , then app ending 01 y .Thus, h 101 0010 i = 1100110100 10 . This function is extended to more than two arguments by comp osition: h x y z i = h x h y z ii . In any computation mo del taking strings as input, resources are usually measured as a function of the length of the input string. For example, wesay that the running time of any 5
device is t ( n ), or simply t , if the device makes at most t ( n ) steps on any input string whose length is n . Computational complexity theory has a technical name for the functions t ( n ) that are at all interesting to measure running times of algorithms. These are called time-constructible functions, although in this pap er we call them simply time bounds. A function t ( n ) 2 n is time-constructible if there is a Turing machine that, given n , computes t ( n ) in time O ( t ( n )). All functions that the reader may think of using as time b ounds for an algorithm are timeconstructible, including n log n , all p olynomials, and all exp onentials. See 1, 11, 18 ] for more details and motivation. A formal language L is any subset of ? . Equivalently, a language can b e seen as a function from ? to f true,false g or f 0 1 g , indicating memb ership in L . Languages and functions are classied in complexity classes according to the resources, such as running time or memory space, necessary to decide or compute them. Thus, the classes P and PSPACE is the class of all languages decided bya Turing machine in p olynomial time and p olynomial memory space, resp ectively. It is easy to argue that P is a sub class of PSPACE, but whether they are actually dierent is an op en problem. Let us recall that the well-known class NP falls in b etween P and PSPACE, and that it is also unknown whether it diers or coincides with either one. All logarithms in this pap er are taken in base 2. 2.2 The Power of Real-Valued Mo dels In principle, analog recurrent neural networks can compute functions over the real numb ers, We concentrate only on networks with discrete input/output and, more precisely, recognizing formal languages as dened ab oveover the alphab et = f 0 1 g .For this to make sense, we must rst dene an enco ding scheme for input and output. There are several, equivalent, ways of dening this enco ding, discussed for example in 26]. We explain only one for deniteness. A network has two input lines. The rst of these is a data line , used to carry a binary input stream of signals when no signal is present, it defaults to zero. The second is the validation line , and it indicates when the data line is active it takes the value \1" while the input is present there and \0" thereafter. Two output neurons, that takebinaryvalues only, are taken to represent the data and validation of the output. Then the computation time of a neural network is well dened and it makes sense to compare them with other real-valued mo dels suchas theBSS. For this discussion, let us consider only p olynomial running time. When all the constants are rational numb ers, the computational p ower of ARNN is known to b e exactly equal to P. For the BSS machine, the computational p ower is known to b e somewhere b etween P and PSPACE, but not exactly determined. Even for the b ounded-memory BSS, i.e., machines using only a constantnumb er of registers, the exact p ower is not known. When the constants are reals, the p ower of b oth mo dels b ecomes non-uniform: P/p oly for the ARNN, and somewhere b etween P/p oly and PSPACE/p oly for the BSS, these classes are dened, for example, in 1, 18]. 6
We will later use the fact that ARNN can implement most of the usual constructs in programming languages, such as arithmetic on integer variables, assignments, conditional statements, and lo ops, the most imp ortant exception b eing equality and inequality tests on real variables. Some examples of ARNN programming can b e found in 23]. 3 The Arithmetic Networks From now on, we will dene several generalizations of the ARNN mo del dened in the Intro duction. Each generalization can b e sp ecied byapair( ), where is the set of net functions allowed and is the set of activation functions allowed. Let \ Q-p oly" and \IR-p oly" b e the set of all multivariate p olynomials with rational and real co ecients, resp ectively.By\poly"we mean either Q-p oly or IR-p oly,and we use this notation when the choice is either clear or irrelevant for the discussion. We dene high-order networks as these with ( ) = (p oly, ), and arithmetic networks (or threshold networks) as these computing with ( )=(poly, f H g ). For discrete input, arithmetic networks are p olynomial-time equivalent to BSS machines in which only a constantnumb er of registers are used. The pro of is not dicult and we omit it in order to keep fo cused on neuron-based mo dels. In many cases, real weights are muchmore powerful than rational ones. For example, p olynomial-time high-order nets with rational weights accept only languages in P while those with real weights accept all of P/p oly,which contains even non-recursive languages. At rst sight, one might think that this is due exclusively to the fact that there are uncountably many real weights, so most of them are highly non-computable, while all rational weights are easily computable in any reasonable sense. In this section we show that, when wemove from rst-order to higher-order threshold nets, or arithmetic nets, this simple explanation is wrong. Indeed, we show that taking p olynomial-time computable real numb ers as weights increases the computational complexity of arithmetic nets in at least twoways. Note that the results in this section are absolute, not dep ending on any unproven conjecture suchasP 6 = PSPACE. Recall that it was shown in 26] that, for rst-order nets, \linear precision O ( t ( n )) suf- ces", meaning that it is enough to have the rst O ( t ( n )) bits of the real weights and activation values to achieve a correct result after t ( n ) steps. Similarly,wewillshow in Lemma 4.2 that \precision 2 t 2 ( n ) suces" to simulate all ( Q-p oly, f H g ) nets running in time t ( n ). As an evidence of the p ower of discontinuity,weshow that no result of this kind is p ossible for arithmetic nets with even very simple weights. Theorem 3.1 There is no computable precision function r ( n )such that \precision O ( r ( t ( n ))) suces" to simulate all (IR-p oly, f H g ) nets running in time t ( n ). This is true even if only p olynomial-time computable weights are used. This theorem sp eaks of precision functions dep ending on the input size n only. It is clear that, for each set of weights, there is some amount of precision depending on the weights that suces to simulate any net having these particular weights and discrete input. 7
As a second evidence, weshow that arithmetic nets, even with simple weights, can recognize some recursive languages arbitrarily faster than Turing machines. Theorem 3.2 There are (IR-p oly, f H g ) nets that run in p olynomial time, have p olynomialtime computable weights, and yet they accept recursive languages of arbitrarily high time complexity (in the Turing machine sense). Again, this is in contrast with the rst-order case and the rational-weight case. Firstorder nets with p olynomial-time computable weights accept only languages in P 3], and arithmetic nets with rational weights can b e simulated in PSPACE, so in exp onential time. Theorems 3.1 and 3.2 are b oth consequences of the following theorem. Theorem 3.3 For every time-constructible function t ( n ) there is a net N in (IR- p oly, f H g )suchthat: 1. The weights in N are computable in time O ( n ) 2. N runs in time 2 n 3. The language T accepted by N is recursive but not decidable in time O ( t ( n )) byany Turing machine. 4. Precision O ( t ( n )) do es not suce to simulate N , that is, if N is simulated with precision O ( t ( n )) a language dierentfrom T is accepted, even in the soft acceptance sense. Proof .We rst give a rough idea of how N is built. Wetake a recursive but hard language T 1 ? where \hard" means that it cannot b e decided in time close to t ( n ). Webuilda weight w in a way that the predicate \1 i 2 T " is equivalent to \the r ( i )-th bit of w is 1", where r ( i ) is function suciently larger than t ( i ). Under some additional conditions on the set T , the r ( i )-th bit of w is computable in time O ( r ( i )) to satisfy part (1) of the theorem. Under the same conditions, N can access this bit using the threshold in time O ( i ), hence it can decide T in linear time to satisfy conditions 2 and 3. On the other hand, if N is simulated with precision O ( t ( n )) r ( n ), then there is no time to access the r ( i )-th bit of w . Then, the net cannot correctly decide whether 1 i 2 T , unless wecontradict the assumption that T is not decidable in time close to t ( n ). Nowwe provide the details. For a real number a 2 0 1] with binary expansion 0 :a 1 a 2 a 3 ::: ,we denote by a j the j th bit in its binary expansion, and by a # j the number 0 : 00 ::: 00 |{z } j ; 1 a j a j +1 ::: . Given function t ( n ), dene functions s ( n )and r ( n )as: s (1) = 1 r ( i )= t 5 ( s ( i )) s ( i +1) = r 2 ( i ) : (Here, for example, t 5 ( n ) denotes the fth p ower of t ,not t iterated 5 times.) It is routine to checkthat s and r are time constructible if t is. We assume w.l.o.g. that r ( i +1) >r ( i )+1. Nowwetake the hard set T mentioned ab ove: Claim. There is a set T with the following prop erties: 8
1. T contains only strings of the form 1 s ( i ) . 2. T is decidable bysomeTuring machine in time t 5 ( n ) but is not decidable byanyTuring machine in time O ( t 4 ( n )). The existence of this T follows from a basic theorem in computational complexity theory called the Time Hierarchy Theorem. See for example 1, 11, 18 ] for exp ositions of this theorem. Now dene a pair of weights u w 2 0 1]. Weight w is an enco ded version of T and u is a supp ort weight useful to nd the enco ding bits: u j = 1 if, for some i , j = r ( i ) 0 otherwise and w j = 1 if, for some i , j = r ( i ) and 1 s ( i ) 2 T 0 otherwise. Observe that, for every i ,1 s ( i ) 2 T ifandonlyif w r ( i ) = 1, and we claim that this happ ens if and only if w # r ( i ) ( u= 2) # r ( i ). This is so b ecause all bits b efore the r ( i )-th are the same in b oth w # r ( i ) and ( u= 2) # r ( i ) (namely, 0). Furthermore, ( u= 2) r ( i )+1 = u r ( i ) = 1 for sure, and, b ecause r ( i +1) >r ( i )+1, w r ( i )+1 = 0, and similarly ( u= 2) r ( i ) = 0. So the bit w r ( i ) decides which of the twonumb ers is larger. But all the bits of u and w in b etween r ( i ; 1) + 1 and r ( i ) are 0, so this is equivalentto w # ( r ( i ; 1) + 1) ( u= 2) # ( r ( i ; 1) + 1). This prop erty can b e used to decide T if weights u= 2 and w are available. More precisely, the net N decides T as follows: 1. input 1 n 2. checkthat n = s ( i )forsome i , and compute j = r ( i ; 1) + 1 3. from the weights w and u= 2, compute w 0 = w # j and u 0 =( u= 2) # j 4. output H ( w 0 ; u 0 ). This net accepts T by the observation ab ove, so it satises part (3) of the theorem. Getting the input takes time n .Notethat r ( i ; 1) is o ( s ( i )) by denition of r ( n ). Then, computing i and j takes time o ( s ( i )) by the time-constructibilityof r , and obtaining u 0 and w 0 can b e done in time O ( j )= o ( s ( i )) with essentially the net in Lemma 4.1. This says that N works in time s ( i )+ o ( s ( i )) 2 n , as stated in the theorem, part (2). To see part (1) of the theorem, see that all the weights in N are the rationals used for controlling the execution ow, u , and w .For u , note that checking whether u j = 1 is deciding whether j = r ( i )forsome i ,which can b e done in time O ( j )by denition of r deciding whether w j =1,for j = r ( i ) is p ossible b ecause T is decidable in time t 5 ( n ), so deciding 1 s ( i ) 2 T takes time t 5 ( s ( i )) = r ( i )= j . 9
such that the range (0 B ] is linearly mapp ed onto ( a a + ] and the range ; B 0] is mapp ed to a .Now, z 2 a a + ], and wethenhaveto simulate the threshold at a (rather than at 0) on this range. Wenow dene v ( z )= 1 f ( z ) ; f ( a )] so that the range is v ( z )= 8 > < > : 1 f ( a ) <f ( z ) ; 1 f ( a ) >f ( z ) =0 z = a and we are to simulate any function that computes 1 for the rst two cases and 0 for the last case. Wecho ose a particular function k ( v )= (2 v ; 1) + ( ; 2 v ; 1) which computes as required. To summarize, the threshold at 0 can b e simulated by a neural network having b oth and f activation functions, using the equation: k ( v ( z ( x ))) = f 2 f ( a + ( x B )) ; f ( a )] ; 1 g + f 2 f ( a ) ; f ( a + ( x B ))] ; 1 g : 4.2 Launching Parts Simulate Discontinuities As mentioned in the Intro duction, it is known that a very large class of net functions and activation functions are equivalent to high-order networks 26]. That theorem applies to all activation functions which are b ounded and Lipschitz. Recall that f is Lipschitz if for every there is a c such that, for all x and y satisfying j x ; y j , it holds j f ( x ) ; f ( y ) j c j x ; y j . The Lipschitz condition, on a compact domain, is stronger than b eing continuous and is weaker than having derivatives. A non-Lipschitz function f is similar to a discontinuous one in the following sense: at some parts of the function, a small change in x may pro duce a large change in f ( x ). These very fast changes are precisely what makes discontinuous functions hard to compute by rst-order nets. We show an example of non-Lipschitz function, the square ro ot, for which this similarit y can b e made precise: adding square ro ot activation functions makes high-order networks computationally equivalent to threshold networks. Later wesketchhow similar results can b e proved for many other non-Lipschitz functions. Theorem 4.6 For nets that use only rational weights, time in the following mo dels is p olynomially related: 1. Networks ( )=( f Q-p oly, p : g , ). 16
2. Networks ( )=(Q-p oly, f H g ). Proof . 2 simulates 1 .Fix a ( f p oly, p : g , )-net N thatrunsintime t and contains only rational weights. We can showthatsuch a net only requires 2 ct bits of precision, for some constant c . This follows by an analysis of the accumulated numerical error, similar to that in the pro of of Lemma 4.2, part (2). We obtain an equivalentnet N 0 replacing each pro cessor computing p a by a subnet running in time t O (1) which computes an approximation to p a correct up to 2 ct bits. The subnet approximates p a by the Newton-Raphson metho d: to nd a solution to x 2 ; a =0, iterate the mapping x + := x ; x 2 ; a 2 x which converges to x = p a . The following well-known fact ensures that converge is fast enough (see, e.g., 6, 14 ], for pro ofs). Here x ( i ) stands for the numb er that results from iterating i times the mapping starting from x . Prop osition 4.7 Let f b e a real function, and a b ]an interval suchthat f is innitely dierentiable in a b ], f ( a ) f ( b ) < 0, and f 0 and f 00 do not change sign in a b ]. Then Newton-Raphson converges quadratically inside a b ], this is, there is a constant C for f such that j f ( x ( i ) ) j C j f ( x ( i ; 1) ) j 2 . Then, inductively, at least 2 t correct bits are obtained in O ( t ) iterations. This subnet uses division, so N 0 do es. But by Theorem 4.3, there is a net equivalentto N 0 using H instead of division. 1 simulates 2 . By Theorem 4.3, we only havetoshowhowtosimulate (p oly, f = g ) nets. Fix one such net, and assume it runs in time t .Let c b e the constantgiven by Lemma 4.2, part (1), this is, all activation values of this net are either 0 or else greater than 2 ; 2 ct . Replace each pro cessor computing = ( a )by a subnet that do es the following: Square a to make sure a 0 note that = ( a )= = ( a 2 ). Set x (0) := a . Then, iterate ct times the mapping x ( i ) := ( p x ( i ; 1) ), so that x ( ct ) = a 2 ; ct . If a = 0, then x ( i ) =0 for every i . Otherwise, a> 2 ; 2 ct , and then x ( ct ) > 2 ; 2 ct 2 ; ct = 1 = 2. All in all, we obtain = ( x )as (2 x ( ct ) ). Generalizing the second part of this pro of, one can see that the square ro ot op erator in Theorem 4.6 can b e substituted byany \launching" function. Say that a function f has launching degree (0 << 1) if for every there is a constant c such that, for every x and y with j x ; y j < , j f ( x ) ; f ( y ) j >c j x ; y j and is the supremum of the values satisfying this prop erty. The launching condition is opp osite of the H!older condition, where > is substituted by it can be interpreted as b eing \strongly" non-Lipschitz. For the following prep osition we can relax the launching condition to o ccur only for the xed value y = 0 to get j f ( x ) j >c j x j . Prop osition 4.8 Let f b e a launching function, then for nets that use only rational weights, the networks ( f Q-p oly, f g , ) simulate ( Q-p oly, f H g ) with at most p olynomial slow-down. 17
5 Perio dic Discontinuities In this section we consider only networks that use rational numb ers as weights and run in p olynomial time. Consider again threshold networks. It is easy to see that these nets can compute at least all functions in P: they prop erly include high-order networks, that are known to compute in p olynomial time exactly the class P 25]. It is also p ossible to show that threshold nets only compute functions included in PSPACE: for example, the unit-cost RAMs to b e dened b elow can simulate threshold networks with a p olynomial overhead, and it is known that unit-cost RAMs are at most as p owerful as Turing machines working in p olynomial space 22, 27 ]. Hence, the p ower of threshold networks, having a broad class of discontinuous activation functions, is lo cated in b etween (or on) P and PSPACE. Recall that the inequalityP 6 =PSPACE, although widely b elieved, is a long-standing op en problem in the eld of computer science. We do not resolve the exact complexity of threshold nets, but we show that some activation functions suciently more complex than the threshold do increase the p ower of neural networks up to their upp er b ound, PSPACE. Hence, these periodic networks b ecome so-called second-class computing mo dels, those in which time is p olynomially equivalentto Turing-machine space. Second-class machines are usually intro duced as mo dels of massively parallel computation. Parallelism can b e explicit, that is, the mo del explicitly uses exp onentially many pro cessors, or implicit, in that it sequentially executes op erations involving exp onentially large ob jects. The rst happ ens, for example, with the Parallel RAM or PRAM mo del. The second case is true, for example, for the vector machines of Pratt and Sto ckmeyer 21]. See 29] for more information on second-class mo dels. In 2], it was shown that networks with p olynomials, division, and bitwise-AND op erations on rational numb ers constitute a second-class machine. The pro of consisted essentially of an ecient simulation of a vector machine by suchanetwork, with the bitwise-AND used to simulate the b o olean op erations on vectors. Bitwise-AND is admittedly an unnatural op eration in the context of neural networks and, in general, of arithmetic mo dels. Wethus lo ok for a computational equivalence which is more natural for this context. Bertoni, Mauri, and Sabadini 4] proved the surprising and nontrivial result that bitwise op erations are not necessary to obtain second-class p ower. They used the following mo del of RAM op erating on unb ounded integers. Denition 5.1 A Random Access Machine (RAM) consists of an innite numb er of registers, R 0 , R 1 , R 2 ,... Each register can contain any nonnegativeinteger numb er. Register R 0 is used as an accumulator, and contains the input at the start of the computation. The program of the RAM can contain the following op erations: R 0 := k /* constant load */ R 0 := R i /* direct load */ R 0 := @( R i ) /* indirect load */ 18
R i := R 0 /* direct store */ @( R i ):= R 0 /* indirect store */ ADD R i /* add R i to R 0 */ SUB R i /* subtract R i from R 0 if R i >R 0 , set R 0 to 0 */ MUL R i /* multiply R 0 by R i */ DIV R i /* integer divide R 0 by R i */ JZERO lab el /* jump if R 0 =0 */ HALT /* result is in R 0 */ In a unit-cost RAM, each instruction is executed in one unit of time, regardless of the size of the op erands. The running time of a unit-cost RAM is thus the numb er of instructions it executes until it halts. Bertoni, Mauri, and Sabadini proved that every problem in PSPA CE is solved by a unitcost RAM in p olynomial time. In fact, their work, together with a padding argument, shows the following. Theorem 5.2 4]For any time b ound t ( n ) n , the following two mo dels are equivalent: 1. Turing machines running in space p oly( t ( n )). 2. Unit-cost RAMs running in time p oly( t ( n )). For our pro ofs, it is convenient to use RAMs that do not abuse the p ower of indirect addressing. We use the following folklore lemma. Lemma 5.3 Let M b e a unit-cost RAM working in time t ( n ). Then there is an equivalent unit-cost RAM working in time O ( t ( n ) log t ( n )) that only reads and writes registers with index numbers O ( t ( n )). The idea of the pro of is to organize the memory as a dictionary of pairs ( i v i ), where v i is the last value written into R i . When the original RAM tries to read from or write to R i , rst search the table lo oking for an entry with i , then read or up date the v alue of v i . If the dictionary is organized as a sequential table, each access costs time O ( t ( n )), as there are never more than t ( n ) pairs in the table. Implementing the dictionary as, say, a balanced tree, the cost for eachaccessis O (log t ( n )), and the memory overhead is a small multiplicative constant. We next showtwo theorems. Theorem 5.4 states the second class p ower of p erio dic networks, i.e., those with p olynomials, division, and the fractional part op eration. Fractional part is used b oth to enco de and deco de a unit-cost RAM memory and to simulate integer division. Then in Theorem 5.6 we show that a large variety of other p erio dic functions, such as the sine, can simulate fractional part eciently.Solet F :IR 7! 0 1) denote fractional part. 19
Theorem 5.4 For time b ounds t ( n ) n , time in the following mo dels is p olynomially related: 1. Networks ( )=( f Q-p oly,division g , f F g ). 2. Unit-cost RAMs. Proof .To simulate 2 by 1, x a unit-cost RAM program that runs in time t ( n ). We describ e a division net using also F -neurons that simulates it in time O ( t 2 ( n )). First we give some notation for a xed input length n . Let R b e the numb er of registers used by M on inputs of length n .We can assume w.l.o.g. that R = O ( t ( n )) by Lemma 5.3. Fix any D suchthat2 D is greater than the contents of any register of the RAM on any input of length n (we will give an explicit value for D in a moment). For anyinteger m , let code ( m )be m 2 ; D . Notethatif m is stored in a register of the RAM, then code ( m ) 2 0 1). We simulate the memory of the RAM in a xed pro cessor Mem of the net, such that at any moment: Mem = R X i =0 code ( R i ) 2 ; iD : We can imagine each register of the RAM enco ded in blo cks of D binary digits inside Mem , something like Mem =0 : code ( R 0 ) | {z } D bits code ( R 1 ) | {z } D bits ::: code ( R R ) | {z } D bits We describ e now some basic op erations of the net. Computing 2 ; D . It is easy to verify by induction that for every unit-cost RAM there is a constant c such that the numb ers it builds in time t havevalue at most ( n + c ) 2 t . Let D b e log ( n + c ) 2 t ( n ) = O (2 t ( n ) log n ). Then, the arithmetic net can compute 2 ; D in time O ( t ( n ) + log log n )= O ( t ( n )) by rep eatedly squaring from 1 = 2. Extracting a eld from Mem . Given i and the memory of the RAM enco ded in Mem ,we want to compute code ( R i ) to do some op eration using R i . Observethat code ( R i )= F ( Mem 2 ( i ; 1) D ) ; F ( Mem 2 iD ) 2 ; D ] The rst fractional part gets rid of the co de of registers R 0 ... R i ; 1 ,thenwe subtract the co de of registers R i +1 ... R R ,so we are left with the co de of R i . Clearly, an arithmetic net can compute this in constanttimegiven 2 ; D ,if i is constant. (Note: numb ers suchas 2 iD cannot b e stored in a pro cessor however, in expressions as ab ovewe write \ Mem 2 iD " meaning \ Mem = 2 ; iD " for clarity.) Inserting a eld in Mem . Given i , Mem ,and a value x = code ( m ), wewant to up date Mem so that R i = m i.e., wewant to replace the current code ( R i ) with x . This is done as follows: Mem + = Mem ; F ( Mem 2 ( i ; 1) D ) 2 ; ( i ; 1) D + x 2 ; iD + F ( Mem 2 iD ) 2 ; iD ] 20
The rst line gives the co des of registers up to R i ; 1 , the second line adds x , the new co de for R i , and the third line adds the co des for registers R i +1 on. With these two op erations on elds, the net can simulate b oth direct and indirect access to register R i . Indeed, we only have to compute numb ers suchas 2 ; iD , and this can b e done in time O ( t ( n )) given i , b ecause we assume that the RAM never reads or writes registers R i with indices i>O ( t ( n )). Simulating arithmetic instructions. For natural numb ers a and b , code ( a + b )= code ( a )+ code ( b ) code ( a b )= code ( a ) code ( b ) 2 D code ( a DIV b )= 2 ; D code ( a ) code ( b ) ; 2 ; D F code ( a ) code ( b ) ! : Test for zero. The expression ( code ( R i ) 2 D ) is 0 if R i = 0, and 1 otherwise. Putting it al l together. With the building blo cks ab ove, each unit instruction of the unitcost RAM can b e simulated in time O ( t ( n )). Using some hardware to control the owof the program, the arithmetic net: 1) reads the input in time O ( n ) 2) computes 2 ; D and related numb ers in time O ( t ( n )) 3) simulates the program, each instruction adding a cost of O ( t ( n )) 4) when the RAM halts, the net outputs the contents of R 0 . Hence, the running time is O ( n + t 2 ( n )). The converse simulation of an arithmetic net by a unit-cost RAM is much easier. As the net has only rational weights, all the states in the computation are rationals. The unit-cost RAM keeps the state of each pro cessor as a pair (numerator, denominator), and this allows to simulate each step of the net in constant time in a straightforward manner. Note only that function F is simulated by means of DIV. We next show that many other p erio dic functions can substitute F in Theorem 5.4, together with division or threshold. One sucient condition is the following. Denition 5.5 Let f b e a p erio dic function f with p erio d P .Wecall f weakly invertible if there is a nonemptyinterval a b ) 0 P )such that: i) f is innitely dierentiable in a b ] ii) for every x 2 a b ), f ( x ) has exactly one preimage in 0 P ). Theorem 5.6 Let f be anyweakly-invertible p erio dic function. Then, for time b ounds t ( n ) n , unit-cost RAMs are p olynomially simulated by networks ( )=( f IR- p oly,division g , f f g ) and by networks ( )= (IR-p oly, f H f g ). Note that the constants in the simulating networks are either rational or else constants dep ending on f only. Proof . By Theorem 5.4, we only have to showhowtocompute F using f . In fact, bythe usual analysis of error propagation, it is enough if we can approximate F with 2 O ( t ( n )) bits of precision in time p olynomial in t ( n ). Let a b )be the interval given by the assumption that f is weakly invertible. Takea subinterval c d ] with the following prop erties: 21
a<c<d<b . The period P is an integral multiple of d ; c , i.e., for some natural number k wehave k ( d ; c )= P . f , f 0 and f 00 have constant sign inside c d ], and in particular they are not zero there. (This will b e used to apply Newton-Raphson in the conditions of Prop osition 4.7). Note that if the interval c d ] cannot b e chosen then, b ecause of the third condition, every subinterval of a b )must contain a zero of either f , f 0 ,or f 00 . By the assumption that f is innitely dierentiable, f has to b e either constant or linear in a b ). If it is constant, then a b ) cannot witness that f is weakly invertible. If it is linear, the function h built as b elow is a linear transformation of F so we are done with the pro of. Hence we can assume for the argumentthat c d ] exists. Wenow do some surgery on f so that it can b e used to compute F . See Figure 1 for an example. ((((Figure 1 here)))) Dene function g by g ( x )= f ( x ) if f ( x ) 2 c d ] 0 otherwise and then function h by h ( x )= k ; 1 X i =0 g ( x + i ( d ; c )) : Now h has the following prop erties: it is a p erio dic function of p erio d d ; c consisting of rep eated copies of f ( c ) :::f ( d ) inside their p erio d, neither h 0 nor h 00 change sign, and they are never zero it can b e computed by a net of constant size containing f and H pro cessors H can b e replaced with division as wesaw in Theorem 4.3. For simplicity,we assume from now on that h has p erio d 1 it is enough to always divide the argumentto h by its true p erio d. To compute F ( z ), do as follows: 1. Compute y := h ( z ) observethat h ( F ( z )) = y . 2. Solve the equation h ( x )= y in the interval c d ) with precision 2 ; 2 ct in x . 3. Output this x as an approximation to F ( z ). 22
To solve the equation h ( x )= y , use Newton-Raphson metho d. By Prop osition 4.7, the distance from x to the ro ot after O ( t ) Newton iterations is at most 2 ; 2 ct ,as we need. Finally, to implement Newton's iteration x + := x ; h ( x ) ; y h 0 ( x ) we compute a small and use ( h ( x + ) ; h ( x )) = instead of h 0 ( x ). Wehave to show that there is an computable in time p olynomial in t such that the error intro duced bythis approximation of h 0 do es not aect the overall result of the computation. Assume for simplicity that y =0sowewant to solve h ( x )=0. Let f x ( i ) g i be the sequence obtained by iterating x ( i +1) := x ( i ) ; h ( x ( i ) ) h 0 ( x ( i ) ) and f y ( i ) g i b e the one obtained by iterating y ( i +1) := y ( i ) ; h ( y ( i ) ) h ( y ( i ) + ) ; h ( y ( i ) ) from the same initial p oint y (0) = x (0) .We will set up a recurrence b ounding j x ( i ) ; y ( i ) j . Since the initial p oint is the same, j x (0) ; y (0) j = 0. In general, j x ( i +1) ; y ( i +1) j j x ( i ) ; y ( i ) j + h ( x ( i ) ) h 0 ( x ( i ) ) ; h ( y ( i ) ) h ( y ( i ) + ) ; h ( y ( i ) ) : To b ound the second term we use that, for all u , v , s ,and t , u v ; s t max( j u j j s j ) 1 v ; 1 t max( j u j j s j ) min 2 ( j v j j t j ) j v ; t j : Here, h 0 ( x ( i ) ) ; h ( y ( i ) + ) ; h ( y ( i ) ) h 0 ( x ( i ) ) ; h 0 ( y ( i ) ) + h 0 ( y ( i ) ) ; h ( y ( i ) + ) ; h ( y ( i ) ) : Wehave j h 0 ( x ( i ) ) ; h 0 ( y ( i ) ) j k 1 j x ( i ) ; y ( i ) j for a constant k 1 b ecause h 00 is b ounded. Furthermore, by the mean value theorem, there is a ' 2 0 ]suchthat h 0 ( y ( i ) + ' )= h ( y ( i ) + ) ; h ( y ( i ) ) : ( ) On the one hand, this implies that min j h 0 ( y ( i ) ) j h ( y ( i ) + ) ; h ( y ( i ) ) ! =min j h 0 ( y ( i ) ) j j h 0 ( y ( i ) + ' ) j 23
is b ounded from b elowby a constant, b ecause h 0 is not zero in c d ]. Therefore, as also h is b ounded ab oveby a constant, max( j h ( x ( i ) ) j j h ( y ( i ) ) j ) min 2 j h 0 ( y ( i ) ) j h ( y ( i ) + ) ; h ( y ( i ) )) is b ounded ab oveby a constant k 2 . On the other hand, ( ) also implies that h 0 ( y ( i ) ) ; h ( y ( i ) + ) ; h ( y ( i ) ) = j h 0 ( y ( i ) ) ; h 0 ( y ( i ) + ' ) j k 3 ' k 3 for some constant k 3 , b ecause h 00 is b ounded. All in all, h ( x ( i ) ) h 0 ( x ( i ) ) ; h ( y ( i ) ) h ( y ( i ) + ) ; h ( y ( i ) ) k 2 ( k 1 j x ( i ) ; y ( i ) j + k 3 ) : The recurrence b ecomes j x (0) ; y (0) j =0 j x ( i +1) ; y ( i +1) jj x ( i ) ; y ( i ) j (1 + k 2 k 1 )+ k 2 k 3 that certainly satises j x ( i ) ; y ( i ) j ( k 4 ) i for a constant k 4 dened from k 1 , k 2 ,and k 3 . The analog of Lemma 4.2 works for ( f Q-p oly,division g , f F g ) nets, so we can tolerate an error in the approximation of F of 2 ; 2 ct ,for c aconstant. Tohave j x ( t ) ; y ( t ) j 2 ; 2 ct , it is enough to have 2 ; 2 ct k ; t 4 ,a numb er that can b e computed in time O ( t )by rep eated squaring. It remains to showthatwe can use H instead of division { recall that our pro of of Theorem 4.3 did not show that this can always b e done when arbitrary functions f are added. Note that division exists in the network given by Theorem 5.4, and that it is intro duced in the preceding construction by Newton's metho d. Because we start from a net using only rational numb ers, we are now guaranteed that whenever wewant to compute u=v , then j v j > 2 ; 2 ct for some constant c . By some easy scaling we can also assume that 0 <v < 1. Then u=v canbeapproximated very well as follows: 1. Compute the unique integer p suchthat2 p v 2 1 = 2 1), and dene z =1 ; 2 p v . Since p must b e in the interval 0 2 ct ], it can b e found by binary searchin time O ( ct ). Threshold is used to do the binary search. 2. Use the series u v = 2 p u 1 ; z =2 p u (1 + z ) (1 + z 2 ) (1 + z 4 ) (1 + z 2 i ) 24
Since 0 <z 1 = 2, it is enough to use O ( ct ) terms of the series to approximate u=v with 2 O ( ct ) bits of precision. And by the same argument as b efore, this precision is enough for the whole simulation to b e correct. Observe that F satises Denition 4.4, so by Theorem 4.5, it can simulate H . Hence, an immediate corollary to Theorem 5.6 is that division is not necessary in Theorem 5.4. Corollary 5.7 For time b ounds t ( n ) n , time in the following mo dels is p olynomially related: 1. Networks ( )=( f Q-p oly,division g , f F g ). 2. Networks ( )=(Q-p oly, f F g ). 2 Functions suchas F and tangent are easily seen to b e weakly invertible. Sine is not b ecause all p oints in the range havetwo preimages in the p erio d, except for = 2and 3 = 2. But the following variant of sine is weakly invertible. half-sine( x )= sin( x )if sin( x + = 2) 0 0 otherwise. In words, half-sine lters out the parts of the sine with negativeslope. Furthermore, it can b e computed with a < gate and a sine gate, and < can b e replaced by division with the technique in Theorem 4.3. Note that all weakly invertible functions must b e discontinuous, to have an injective part. If the discontinuity is of the \jump" typ e, we can apply Theorem 4.5 and get rid of H .This is the case, for example, for the tangent function, b ecause (tan) has a jump discontinuity. The fact that it is not dened at the discontinuity is not problematic: it is easy to ensure that the function is never evaluated at undened p oints by osetting its argumen t with a suciently small numb er. All in all, wehave for example the following corollaries: Corollary 5.8 Unit-cost RAMs are p olynomially simulated by ( f poly,division g , f sin g )networks, (p oly, f H sin g ) networks, and (p oly, f tan g )networks. Therefore, these nets are second class machines, and in particular they can solve all PSPACE problems in p olynomial time. 2 Note that the trickusedtoobtainaweakly invertible function from sine is likely to work for many other natural functions, though we do not attempt to formalize when. 25