Gradient calculation for dynamic recurrent neural networks: a survey <s> III. Computing the Gradient Without Assuming a Fixedpoint <s> One way to achieve viewpoint-invariant shape recognition is to impose a canonical, object-based frame of reference on a shape and to describe the positions, sizes and orientations of the shape's features relative to the imposed frame. This compulation can be implemented in a parallel network of neuron-like processors, but the network has a tendency to make errors of a peculiar kind: When presented with several shapes it sometimes perceives one shape in the position of another. The parameters can be carefully tuned to avoid these "illusory conjunctions" in normal circumstances, but they reappear if the visual input is replaced by a random mask before the network has settled down. Treisman and Schmidt (1982) have shown that people make similar errors. <s> BIB001 </s> Gradient calculation for dynamic recurrent neural networks: a survey <s> III. Computing the Gradient Without Assuming a Fixedpoint <s> This chapter contains sections titled: Parallel Distributed Processing, Examples Of PDP Models, Representation and Learning in PDP Models, Origins of Parallel Distributed Processing, Acknowledgments <s> BIB002
Now w e get to the heart of the matter|the computation of r w E, the gradient of the error E with respect to the vector of free parameters w, where the error is not de ned at a xedpoint but rather is a function of the network's detailed temporal behavior. The techniques we will discuss here, like those of section II, are quite general purpose: they can accommodate hidden units as we l l a s v arious architectural embellishments, such as second-order connections BIB001 The xedpoint learning procedures discussed above a r e unable to learn non-xedpoint attractors, or to produce desired temporal behavior over a bounded interval, or even to learn to reach their xedpoints quickly. Here, we t u r n to a learning procedure suitable for such non-xedpoint situations. This learning procedure essentially converts a network evolving through time into a network whose activation is owing through a numb e r o f l a yers, translating time into space, as shown in gure 5. Backpropagation then becomes applicable. The technique is therefore called Backpropagation Through Time, or BPTT. Consider minimizing E(y), some functional of the trajectory taken by y between t 0 and t BIB002 In this derivation, we take the conceptually simple approach of unfolding the continuous time network into a discrete time network with a step of t, applying backpropagation to this discrete time network, and taking the limit as t approaches zero to get a continuous time learning rule. The derivative in (3) can be approximated with dy i dt (t) y i (t + t) ; y i (t) t which yields a rst order di erence approximation to (3), Tildes are used throughout for temporally discretized versions of continuous functions. Let us de ne e i to be the rst variation of E with respect to the function y i (t), In the usual case E is of the form so e i (t) = @f(y(t) t )=@y i (t). Intuitively, e i (t) measures how m uch a small change to y i at time t a ects E if everything else is left unchanged. As usual in backpropagation, let us de nẽ where the @ + denotes the ordered derivative of 97], with variables ordered here by time and not unit index. Intuitively, z i (t) measures how m uch a small change toỹ i at time t a ects E when this change is propagated forward through time and in uences the remainder of the trajectory, as in gure 7. Of course, z i is the limit ofz i as t ! 0. This z is the of the standard backpropagation \generalized rule." We can use the chain rule for ordered derivatives to calculatez i (t) in terms of thez j (t+ t). According to the chain rule, we add all the separate in uences that varyingỹ i (t) has on E. It has a direct contribution of te i (t), which comprises the rst term of our equation forz i (t). Varying y i (t) b y dỹ i (t) has an e ect onỹ i (t+ t) o f dỹ i (t) ( 1 ; t), giving us a second term, namely (1 ; t)z(t + t). Each w eight w ij makesỹ i (t) i n u e n c ẽ y j (t + t), i 6 = j. Let us compute this in uence in stages. Varying y i (t) b y dỹ i (t) v ariesx j (t) b y dỹ i (t) w ij , which v aries (x j (t)) by dỹ i (t) w ij 0 (x j (t)), which v ariesỹ j (t + t) by dỹ i (t) w ij 0 (x j (t)) t. This gives us our third and nal term, P j w ij 0 (x j (t)) tz j (t + t). Combining these, z i (t) = t e i (t)+(1; t)z i (t+ t)+ X j w ij 0 (x j (t)) tz j (t+ t): (21) If we put this in the form of (16) and take the limit as t ! 0 w e obtain the di erential equation with boundary condition z(t 1 ) = 0. Thus we h a ve derived appropriate adjoint equations to (1). They are similar to the analogous discrete-time backwards error equations, z(t ; 1) = df(y w I) where the error to be minimized is E. If this error is of the usual form of an integral E = R E 0 (y(t) t )dt then we get the simple form E= y= dE 0 =dy.  For boundary conditions note that by (18) and (20) z i (t 1 ) = te i (t 1 ), so in the limit as t ! 0 w e h a ve z i (t 1 ) = 0 . Consider making an in nitesimal change dw ij to w ij for a p e r i o d t starting at t. This will cause a corresponding in nitesimal change in E of y i (t) 0 (x j (t)) tz j (t)dw ij . Since we wish to know the e ect of making this in nitesimal change to w ij throughout time, we i n tegrate over the entire interval, yielding @E @w ij = Z t1 t0 y i 0 (x j )z j dt:  One can also derive (26),  and (37) using the calcul u s o f v ariations and Lagrange multipliers, as in optimal control theory 98], 99]. In fact, the idea of using gradient descent to optimize complex systems was explored by control theorists in the late 1950s. Although their mathematical techniques and algorithms are identical to those reviewed here, and thus handled hidden units, they refrained from exploring systems with so many degrees of freedom, perhaps in fear of local minima. It is also interesting to note that the recurrent b a c kpropagation learning rule (section II-C) can be derived from these. Let I i be held constant, assume that the network settles to a xedpoint, and let E be integrated for one time unit before t 1 . A s t 1 ! 1 , (26) and  reduce to the recurrent backpropagation equations (9) and (8), so in this sense backpropagation through time is a generalization of recurrent backpropagation. There are two w ays to go about nding such derivations. One is direct, using the calculus of variations 98]. The other is to take the continuous time equations, approximate them by di erence equations, precisely calculate the adjoint equations for this discrete time system, and then approximate back to get the continuous time adjoint equations, as in 76]. An advantage of the latter approach i s that, when simulating on a digital computer, one actually simulates the di erence equations. The derivation ensures that the simulated adjoint di erence equations are the precise adjoints to the simulated forward di erence equations, so the computed derivatives contain no approximation errors.