US 5,046,020 AGrant
Distributed Parallel Processing Network Wherein the Connection Weights Are Generated Using Stiff Differential Equations
Issue Date:1991-09-03
•12 Claims
•5 Drawing Sheets
Abstract
A parallel distributed processing network of the back propagation type is disclosed in which the weights of connection between processing elements in the various layers of the network are determined in accordance with the set of steady solutions of the stiff differential equations governing the relationship between the layers of the network.
Metadata
Assignee
- E. I. du Pont de Nemours and Company
Inventor
- David L. Filkin
Application Information
Application Number:US 2855348
Filing Date:1988-12-16
Priority Date:1988-12-16
Art Unit:238
Classifications
IPC:
G06F 1518
Field of Search:
364513;900;200
Patent Drawings (5 sheets)
Description
BACKGROUND OF THE INVENTION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates to a distributed parallel processing network of the form of a back propagation network having an input layer, an intermediate (or hidden) layer, and an output layer, and in particular, to such a network in which the interconnection weights between the input and hidden layers and between the hidden and the output layers are determined by the steady state solutions of the set of stiff differential equations that define the relationships between these respective layers.
2. Description of the Prior Art
A parallel distributed processing network is a computational circuit which is implemented as a multi-layered arrangement of interconnected processing elements. In a typical arrangement of a parallel distributed processing system, known as the back propagation network, the network architecture includes at least three layers of processing elements: a first, or "input", layer; a second, intermediate or "hidden", layer; and a third or "output", layer. Each processing element has an input and an output port, and operates on an input applied thereto to transform that input in accordance to a predetermined transfer function. The transfer function usually takes the form of a sigmoid function having a predetermined threshold associated therewith that is operable to produce an output bounded between zero and one.
The input port of each processing element in the input layer is connectible to at least one input signal while the output port of each of the processing elements in the input layer is connected to at least one, and typically to a plurality, of the processing elements in the intermediate layer. Similarly, the output port of each of the processing elements in the intermediate layer is connectible to at least one, and typically to a plurality, of the processing elements in the output layer.
The connection lines between the elements in the input layer and those in the intermediate layer and the connection lines between the elements in the intermediate layer and those in the output layer each have a "connection weight" associated therewith. Generally speaking, with respect to the elements in the hidden and the output layers, the magnitude of any signal at the input of a processing element in these layers is the summation over all of the inputs of the inner vector product of the activation strength of each input signal and the connection weight of the corresponding connection line on which it is carried plus the threshold of the processing element.
A network such as that described is trained using a learning rule known as the "Generalized Delta Rule" described in Rumelhart, Hinton and Williams, "Learning Internal Representations by Error Propagation", Parallel Distributed Processing, Volume 1, Foundations, Rumelhart and McClelland, editors, MIT Press, Cambridge, Mass. (1986). This rule is generalization of the "Delta Rule" given by Widrow, "Generalization and Information Storage in Networks of ADELINE Neurons", Self Organizing Systems, Yovitts, editor, Spartan Books, New York (1962).
Using such a training rule the network is presented sequentially with a number of "training patterns" relating the activation strengths of the input signals at the input elements to the corresponding values at the output ports of the elements in the output layer. All the connection weights are then varied together to minimize the error in the network's predicted outputs. To change the weights in accordance with the method of steepest descent the gradient of the error with respect to the weights is found and the weights changed to move the error toward smaller values. The weights are changed iteratively, in accordance with the following relationship: ##EQU1## where .DELTA.W[gd] represents the weight changes for gradient or steepest descent,
.DELTA.W.sup.n represents the weight change applied at iteration number n,
.DELTA.W.sup.n-1 represents the weight change from the previous iteration,
eta represents the "learning rate" of the network and
alpha represents the "momentum" term.
Training occurs in discrete steps or iterations, each requiring one presentation of all the training patterns to the network. In order to assure convergence of the iterative algorithm the learning rate eta must be chosen small enough so that oscillations and instabilities do not occur. The momentum term alpha is provided to increase the convergence rate and to help avoid the problem of being trapped in local minima of the least-squares surface.
It is well known in the art that although the training rule gives a finite-step change in the weights that corresponds approximately to the direction of gradient or steepest descent, it does not always converge. Perhaps more problematic, the training is initially fairly rapid, but eventually training becomes extremely slow, especially as the network becomes more accurate in predicting the outputs. Training to great accuracy can take thousands or even millions of presentations of the training set. The number of training presentations required grows rapidly with the size of the network, usually more rapidly than the square of the number of connections.
During the IEEE International Conference on Neural Networks, San Diego, Calif., in July 24-27, 1988, a number of papers were presented on techniques to increase the training speed of a back propagation network. These papers are available in the proceedings of the conference as published for the IEEE by SOS Printing of San Diego, Calif. The paper by Kung and Howard, at pages 363 to 370, describes a method to predict the optimal number of hidden layer elements needed. By using only the minimum number, the training rate can be optimized. In the paper by Kollias and Anastassiou, at pages 383 to 390, the Marquhardt-Levenberg least squares optimization technique is used to improve convergence. The paper by Gelband and Tse, at pages 417 to 424, describes a method of generalizing the threshold logic function to a "selective" function thereby effectively reducing the multilayer network to a single layer and thus increasing the learning rate. The paper of Hush and Salas, at pages 441 to 447 describes a method called the "Gradient Reuse Algorithm" which speeds the training rate.
Accordingly, in view of the foregoing it is believed to be advantageous to provide a back propagation network which is more expeditiously trained.
SUMMARY OF THE INVENTION
The present invention relates to a multilayered parallel distributed processing network using the architecture of the back propagation network. Such a network includes at least three layers of processing elements. The first, or input, layer, has a set of at least one to i processing elements, each of which has an input port and an output port and each of which operates on an input in accordance with a predetermined transfer function to produce an activation signal Al(i) at the output port. The second or intermediate layer has a set of at least one to k processing elements, each having an input port and an output port. Each processing element in the intermediate layer operates on an input in accordance to a predetermined transfer function to produce an activation signal A2(k) at the output port thereof. The third, or output layer, has a set of at least one to j processing elements. Each output processing element also has an input and an output port. Each processing element in the output layer operates on an input in accordance to a transfer function to produce an activation signal A3(j) at its output port.
The output port of each of the processing elements in the input layer is connected by a line having a connection weight W1 to the input of at least one of the processing elements of the intermediate layer. Similarly, the output port of each of the processing elements of the intermediate layer is connected by a line having a connection weight W2 to the input of at least one of the processing elements of the output layer. The network is trained by applying at the input port of the input layer a training signal producing activation signals A1, A2 and A3. Each training signal has a desired output signal V associated therewith.
In accordance with the present invention the weight W1 and W2 are determined by solving the set of stiff differential equations relating the various layers of the network:
BRIEF DESCRIPTION OF THE DRAWINGS
The invention will be more fully understood from the following detailed description, taken in connection with the accompanying drawings, which form a part of this application and in which:
FIG. 1 is a stylized diagram of a generalized parallel distributed processing network in accordance with the present invention;
FIG. 2 is a generalized representation of a processing element used in the parallel distributed processing network of the present invention;
FIG. 3 is a diagram of a parallel distributed processing network in accordance with the present invention used in the specific example discussed herein;
FIGS. 4 and 5 are flow diagrams of a program used to determine the interconnection weights and the thresholds between processing elements in the network shown in FIG. 3 in accordance with the present invention, specifically, with FIG. 4 being a flow diagram of the computer program to train a back propagation network using a stiff differential equation solver, and FIG. 5 being a flow diagram showing the interaction of the main program with the subroutine DGEAR: and,
FIG. 6 shows the results of a distributed parallel processing network prediction of accept/reject versus training data for the specific example discussed herein.
A listing of a program in Fortran-77 source language (pages A-1 to A-20, inclusive) whereby the program shown in the flow diagrams of FIGS. 4 and 5 is implemented is attached to and forms part of this application.
DETAILED DESCRIPTION OF THE INVENTION
Throughout the following detailed description similar reference numerals refer to similar elements in all figures of the drawings.
With reference to FIG. 1 shown in a stylized diagram of a generalized distributed parallel processing network generally indicated by reference character 10 in accordance with the present invention. The network 10 is configured as a back propagation network and comprises individual processing elements 12 configured into at least three layers 14, 16 and 18. Of these layers the layer 14 is termed the "input layer", the layer 18 the "output layer", and the intermediate layer 16 the "hidden layer". The processing network 10 is organized such that the input layer 14 contains a set of at least one to i processing elements, the hidden layer 16 has a set of at least one to k processing elements, and the output layer 18 has a set of at least one to j processing elements therein. When implementing the network an operator would specify the values i, k and j.
FIG. 2 is a generalized representation of a processing element 12 used throughout the network 10. Each processing element 12 has an input port P.sub.in and an output port P.sub.out. The processing element is responsive to one or a plurality of excitation signal(s) I.sub.1 though I.sub.m presented at the input port P.sub.in and is operative to produce an activation signal Q.sub.out carried on a line L.sub.out connected at the output port P.sub.out. Each of the excitations I.sub.1 though I.sub.m is connected to the input port P.sub.in of the element 12 over a respective line L.sub.1 though L.sub.m that has a predetermined respective connection weight W.sub.1 through W.sub.m. The activation signal Q.sub.out that is produced on the line L.sub.out at the output port P.sub.out of the processing element 12 is, as a general rule, a function of the input signal Q.sub.in applied at the input port P.sub.in. The input signal Q.sub.in is the summation, over all of the input lines to the processing element, of the inner product of the strength of a given excitation signal I and the connection weight W of the line L carrying that signal to the processing element, scaled by the squashing function S for that processing element. Symbolically, the activation signal Q.sub.out at the output port P.sub.out functionally related to the input signal Q.sub.in
wherein ##EQU3## where T is the threshold of the processing element 12. The threshold T can be considered as an additional weight from an input line (m+1) having a constant excitation signal of one (1), similar to the prior art. Throughout this application, the squashing function S takes the form of the sigmoid function,
although any other desired monotonically nondecreasing squashing function may be used. If some other squashing function is used the detailed forms of the Equations (6), (7), (6a) and (7a) would, of course, be different from those set forth herein. However, the teachings of the present invention would have equal applicability thereto.
As may be seen from FIG. 1 each of the processing elements 14-1 through 14-i in the input layer 14 is connected to at least one of a predetermined number i of network input signals on a respective input line 22. Each of the lines 22 may have a predetermined weight associated therewith, similar to the situation discussed above in the case of the generalized processing element. It should be understood that a given processing element in the input layer 14 may be connected to more than one of the input signals, if desired. Each of the processing elements in the input layer 14 is operative, in a manner similar to that described above for the generalized processing element, to produce a respective activation signal A1[1] through A1[i] at the output port thereof.
The output port of each of the i processing elements in the input layer 14 is connected to at least one of the k processing elements 16-1 through 16-k in the intermediate layer 16 of processing elements by a respective line 24. In a typical case, the output port of each of the processing elements in the input layer 14 is connected to the input port of each of the processing elements in the intermediate layer 16. Each such interconnection line 24 has a connection weight W1[i,k] associated therewith.
In a fashion similar to that discussed above the processing elements in the intermediate layer 16 respond to the inputs applied thereto to produce an activation signal A2[k] at the output port thereof. In similar fashion, the output port of each of the k processing elements in the intermediate layer 16 is connected to the input port of at least one of the j processing elements in the output layer 18 of processing elements on a line 26. In the preferred case the output port of each element in the intermediate layer 16 is connected to the input port of one of the processing elements in the output layer 18. The lines 26 each have a connection weight W2[k,j] associated therewith.
The processing elements in the output layer 18 respond to the inputs thereto to produce an activation signal A3[j] at the output port thereof. These output signals are carried over respective output lines 28.
To train the network shown in the FIG. 1, a training set comprising an array containing from one to p sets of input signals is applied to the input lines 22 of the network 10. Associated with each of the applied inputs p is a predetermined desired value for the j-th output V[j,p] at the output 28 of the network 10. At any stage in the training of the network the error E to be minimized is the squared difference between the desired output V[j,p] and the actual output A3[j,p] when the input pattern p is presented to the network. Thus ##EQU4##
If training of the network 10 is done using the conventional Generalized Delta Rule for the changes in weights given by the method of steepest descent (the term .DELTA.W[gd] in Equation (1), above) ##EQU5## The sum p is over all training patterns and that of j over all output elements. As discussed earlier this training rule gives a finite-step change in the weights that corresponds approximately to the direction of steepest descent but it does not always converge. Despite initially fairly rapid training, training eventually becomes extremely slow and, as noted, can take thousands or even millions of presentations of the training set.
The present invention revolves upon the recognition that the training of a back propagation network using the conventional training rule described above is closely analogous to systems which are governed by stiff differential equations. Such systems are characterized by time constants which vary greatly in magnitude. In the case of a back propagation network this corresponds to the fact that some weights reach a near steady state value very rapidly while others change only very slowly. Moreover, sometimes a weight will remain unchanged for a large number of iterations and then suddenly change to another quasi-steady state value. This is a common occurrence for variables in a stiff differential system. Finally, prior art solution schemes for neural networks involve heuristics for adjusting the values of the constants eta and alpha (from Equation (1)) to try to obtain rapid but stable convergence.
The fundamental training concept of the back propagation network is to change the weights in accordance with the Generalized Delta Rule given by the method of steepest descent in such a way as to decrease the total squared error E. However, in accordance with the present invention, instead of the usual back propagation training schemes in which one thinks of the training as taking place in discrete steps labeled n, the training in accordance with the present invention is presumed to take place as a continuous time evolution of the weights W. However, it can be shown that the conventional discrete-step iterative scheme of Equation (1) is a fixed-time-step forward-Euler method for solving the underlying differential equations which is both inefficient and potentially unstable when applied to a system of stiff differential equations.
Thus, Equations (6) and (7) relating the various layers of the network can be written as differential equations ##EQU6##
Equations (6a) and (7a) are a set of coupled nonlinear ordinary differential equations for the continuous variables W1[i,k] and W2[k,j]. The initial conditions are small random weights. This system of equations may be integrated numerically to solve the equations, such that, as time increases, the weights converge to steady state values corresponding to those giving a local minimum least-squares prediction error. In the preferred instance, the equations are numerically solved using the stiff integration package DGEAR from the IMSL Library, sold by IMSL, Inc. Houston, Tex. The original version of the algorithm used in the package DGEAR is disclosed in Gear, C. W., Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Englewood Cliffs, N.J. (1971).
Because the differential Equations (6a), (7a) are formulated to decrease the mean square prediction error, in the direction of steepest descent the prediction error will always decrease. Convergence is absolute in all cases, with no need to adjust fitting parameters, such as eta or alpha, as in the prior art. As a further advantage, the solution of the equations and thus, the valuation of the weights, is achieved in a more rapid manner than in the prior art.
It should be understood that in accordance with the present invention the network 10 may be implemented in any of a variety of forms. In one aspect the network may be formed as the interconnection of discrete analog components in the manner indicated in the Figures. In an alternate implementation the network may be formed as an integrated circuit in which the layers of processing elements and the interconnection lines between them are integrated onto a suitable substrate by any appropriate integration process (in FIG. 1 the plane of the paper can be considered the substrate). In both these implementations the interconnection weights between the processing elements would preferably take the form of resistances in the connection lines. As another alternative an optical (holographic) implementation can be used. In the most preferred case the network is implemented using a programmed digital computer, either in the form of a mainframe (such as a CRAY X-MP), a mini computer (such as a Digital Equipment Corporation VAX) or in the form of one or more microcomputers or one or more boards having a microprocessor thereon.
It should be specifically understood that the terms in the claims "means for defining a first, input, set of from one to i processing elements", "means for defining a second, intermediate, set of from one to k processing elements", and "means for defining a third, output, set of from one to j processing elements", is not meant to imply that three discrete sets of electrical circuit structures are required to simultaneously coexist in order to implement the network. It should be appreciated that, as pointed out above, the distributed parallel processing network can be implemented using one or more digital computer(s) having a traditional von Nuemann architecture (of whatever size or power desired) in which each processing element in each layer is configured during one or more instruction cycles of the computer(s).
It should also be clearly understood that although the computation of the values of the connection weights W1, W2 for the back propagation network 10 is accomplished using a mathematic algorithm, such as the numerical integrator, the weights themselves are not mathematical in nature but represent physical connections between processing elements. Moreover, the network 10 as a whole is nonalgorithmic in nature. Stated alternatively, although a mathematical algorithm may be used to solve the underlying continuous differential equations and specify the values of the weights, the network having the processing elements connected by lines having those weights is not an algorithmic network.
EXAMPLE
An Inspection Problem
A specific example of a parallel distributed processing network trained in accordance with the present invention is now presented. FIG. 3 is a schematic diagram of the parallel distributed processing network utilized in this example and configured to process information relative to a specific pattern recognition problem while FIGS. 4 and 5 are flow diagrams of a program used to determine the weights W1, W2 and the thresholds for the specific network shown in FIG. 3. The specific details of the problem involved the classification of electronic parts as either being accepted or rejected. The listing of a program, in Fortran-77 source language, for programming a CRAY X-MP supercomputer which effected the training of a back propagation network shown in FIG. 3 and determined the thresholds of the processing elements and the values of the weights W1 and W2 by solving (i.e., converging to a solution of) the underlying set of stiff differential equations associated with that network (in the form of Equations (6a) and (7a)) is attached as an Appendix to this application and is hereby made part thereof.
The parallel distributed processing network of the back propagation type as described heretofore is well suited for solving a wide variety of formulation, classification and pattern recognition problems. As discussed above, the network "learns" how to match a training set of inputs to outputs by adjusting the weights of the connections from the input processing elements to the intermediate processing elements and from the intermediate processing elements to the output processing elements.
The advantage of using such a network for formulation problems is that it is self-teaching. It is not necessary to specify an a priori functional form for the relationship between inputs and outputs, as in non-linear least squares statistical models. Also, the network is implicitly non-linear, giving a useful generalization over often applied linear techniques like multiple linear regression. Such networks do no require the discovery of an exhaustive set of formulation "rules", as in rule-based artificial intelligence (AI) systems. The network implicitly builds into its internal structure the rules and relationships that exist between inputs and outputs in the training data base. For this, given a sufficiently complete data base, the creation of a distributed parallel processing network model for formula prediction and pattern recognition can usually be completed more quickly and easily than statistical or rule-based models.
For a pattern recognition problem, the training data set determines the number of input and output processing elements that are used. A pre-processing step is normally used, scaling the inputs and outputs individually in both the training data set and the prediction data set to lie in the range 0.1 to 0.9. As will be developed, the training data set is used to determine the values of the thresholds and weights of the interconnections in accordance with the present invention. (It is again noted that the thresholds may be treated as weights.) The prediction data set is used to verify and to validate the operation of a network having the weights as determined in accordance with the present invention. When scaling, usually a linear scaling is done, with 0.1 corresponding to the lowest value of a particular variable in the set and 0.9 corresponding to the highest. In the example to be discussed, the data from eleven physical measurements of an electronic part was to be related to a visual inspector's classification into the categories REJECT [coded as 0.1] or ACCEPT [coded as 0.9 ]. The training set consisted of forty two (42) samples, of which thirty six (36) samples were accepted and six (6) rejected. The network of the example had eleven input processing elements (i=11), one for each of the physical measurements, two intermediate processing elements (k=2) and one output processing element (j=1), whose value designated acceptance or rejection.
In the present example, a user had only two choices to make in setting up the training of the network. First, the accuracy of convergence in the output data was specified. Two convergence criteria were used and the acceptance of either one caused the training to stop. First, if the root-mean-square (RMS) error in predicting the outputs was less than the user-specified tolerance TOLER (in scaled units), convergence was declared. Second, if none of the individual output errors exceeded three times the error tolerance (3*TOLER), the solution was also considered converged. For the classification of electronic parts example, an error tolerance of 0.01 was chosen, as shown in the listing of the input parameter file for training of the network (ELEC.PRM on page A-1 of the Appendix).
The second user-adjustable parameter was the number of internal or hidden processing elements (k) used in the network. For n.sub.i input elements, n.sub.k hidden elements, and n.sub.j output elements, the total number of adjustable weights and thresholds is given by the equation:
If n.sub.total is small compared with the number of training samples, the network is "interpolative" in nature, the subtle variations in the input data cannot be mapped to output changes. If n.sub.total is large, the network approaches the "pattern recognition" mode in which it is memorizing each input pattern. If a few more internal elements are specified than needed, the network often tends to a solution in which several elements are either "on" or "off" for all the training patterns. These redundant elements can be removed from the network. If, on the other hand, too few hidden elements are specified, the network converges very slowly, and it tends to misclassify some of the members of the training set.
In the example here presented the training of the network and the determination of the thresholds and weights was implemented using a CRAY X-MP supercomputer operating in accordance with a program. The Cray Job Control Language (JCL) file ELEC.JOB given on page A-1 of the Appendix supervised the execution of the job on the CRAY X-MP supercomputer. The complete source listing of the Fortran-77 main program FORMUL, stored in file ELEC.CFT, is shown on lines 1 to 227 appearing on pages A-7 to A-11 of the Appendix.
The program input was read from two files, ELEC.PRM (on the input/output device identified in the listing as Fortran logical unit 15) and QSM.DAT (on the input/output device identified in the listing as Fortran logical unit 18). As may be seen from the listing of the file ELEC.PRM, page A-1 of the listing, there were eleven input nodes, one output node, and two hidden (internal) nodes. The RMS error tolerance (TOLER) for the training was specified as 0.01 (i.e., one percent), and the maximum number of effective training presentations (NMAX) was specified as one hundred thousand (100,000) thereby to provide an exit from the program. Any suitable error tolerance for a problem at hand may be specified, and any suitable number of training presentations may be selected.
The set of training data is set forth in the file QSM.DAT on page A-2 of the listing. The eleven inputs, labeled TRINA 1 through TRINA 11, to correspond to the variable name used in the program, for each of the forty two training patterns are shown one per line in the listing of the file QSM.DAT. On page A-3 of the listing are the forty two outputs TROUTA (also given the variable Y in the listing), with the values of 0.1 and 0.9 corresponding to REJECT and ACCEPT, respectively. The sets of input signals TRINA corresponds to the sets input signals INPUT(i) shown in FIG. 1 and to the inputs I shown in connection with FIG. 2.
Two files received the output from the main routine FORMUL. Information written to the input/output device identified in the listing as Fortran logical unit 6 appears in the output file NEURAL.CPR on page A-4 of the Appendix. The weights and thresholds are written to file ELEC.W on the input/output device identified in the listing as Fortran logical unit 28. The flow diagram for the training routine FORMUL is shown in FIG. 4. The major elements of the program are given in the boxes, with line numbers corresponding to those in the source listing of file ELEC.CFT shown along the right.
After variable and common declarations, the program FORMUL called subroutine INCONT and GETPAT to input the training parameters and the data, respectively. Subroutine INCONT (lines 446 to 459) read the information stored in file ELEC.PRM from the input/output device identified in the listing as Fortran logical unit 15. Subroutine GETPAT (lines 460 to 482) read the training patterns in the file QSM.DAT from Fortran logical unit 18, storing them in variables named TRINA (eleven inputs per training pattern) and TROUTA (one output per training pattern). In a new run (IRSTRT=0 in the file ELEC.PRM) the weights and thresholds were randomly assigned in lines 74 to 100. If the training was to be restarted (IRSTRT=1 in the file ELEC.PRM), lines 103 to 116 on page A-9 of the Appendix would read the file ELEC.W containing previously calculated weights and thresholds from the input/output device identified in the listing Fortran logical unit 29. In the example here discussed the training was started from random initial conditions, which along with control parameters for the subroutine DGEAR are set in lines 117 to 159 (page A-9).
Lines 160 to 205 in the main routine FORMUL were a loop in which the subroutine DGEAR was called repeatedly (lines 164-165), with increasing ending time TEND, which was initially one hundred. DGEAR solves the differential equations shown as Equations (6a), (7a) herein from time t (initially t=0) through time TEND, calling the subroutine DIFFUN (lines 228 to 435) which evaluated the right-hand side of Equations (6a) and (7a).
After DGEAR advanced the solution of the differential equations from t to TEND the weights and thresholds were written to file ELEC.W (the input/output device identified in the listing as Fortran logical unit 28) in lines 185 to 198. Some monitoring information was also written to file NEURAL.CPR (page A-4 of the listing) (the input/output device identified in the listing as Fortran logical unit 6) in lines 179 to 184. The time endpoint was then doubled (line 202) and, unless the time reached exceeded the maximum number of iterations (NMAX) specified in file ELEC.PRM, the loop was continued at line 160. The maximum program loop (lines 160 to 205) was also stopped if either of the two above discussed convergence criteria were met: a root-mean-squared prediction error in the outputs less than TOLER, or all of the prediction errors less than three times tolerance (3*TOLER). If convergence or NMAX was reached, program control was passed to line 206, and the final monitoring printout (lines 209 to 210) and writing of ELEC.W (lines 211 to 221) were done before the program stopped (line 223).
The interaction between the main routine FORMUL and the subroutine DGEAR is shown in the flow diagram of FIG. 5. On each call DGEAR began with the variables Y at the initial time and integrated Equations (6a) and (7a) through the time t by repeated calls to the subroutine DIFFUN which evaluated the right-hand side of these equations. DGEAR internally monitored the time step DT being used in the integration, increasing or decreasing it as necessary. It should be understood that since the program DGEAR is commercially available, the details thereof are depicted in the flow diagram in only a generalized fashion.
The subroutine DIFFUN (lines 228 to 435) took as input the values Y (representing the weights W1 and W2 and the thresholds THETA1 and THETA2 of the network being trained) and computed the instantaneous time rate of change of these values. DY=dY/dt. Again, it is noted that the thresholds were treated as weights. In lines 258 to 307 the input values Y were stored in the appropriate weight and threshold variables, and temporary storage variable for the weight changes are initialized. The DO loop in lines 308 to 390 evaluated the gradient-descent weight changes given in Equations (6a) and (7a). These quantities were stored in the appropriate locations of the output vector DY in lines 397 to 417.
The printout NEURAL.CPR on page A-4 of the listing shows the output for the example data set QSM.DAT (with explanatory material being added). The example had forty two training patterns and twenty seven adjustable weights and thresholds. The routine FORMUL converged to better than 0.01 RMS prediction error in a time of 25,600 effective training iterations. The FLOWTRACE (page A-4), specific to CRAY computer systems, show how many times each routine was called. The training weights and thresholds obtained are given in the printout of the file ELEC.W (page A-5). Because computers generated machine specific random number sequences, the details of the results shown in NEURAL.CPR and ELEC.W will not be the same on other computers.
The final listing provided with this example is the routine PREDCT.FOR, given on pages A-17 to A-20 of the Appendix. This is a VAX Fortran program which implements a distributed parallel processing network trained in accordance with the present invention. The routine PREDCT.FOR utilized the prediction set of data to verify and validate that a distributed parallel processing network in which the values of the weights between the input layer and the intermediate layer and between the intermediate layer and the output layer were adjusted in accordance with the steady state solution sets of the differentials equations as given in Equations (6a) and (7a) would accurately result in the appropriate classification of electronic parts as either REJECT or ACCEPT. The network was implemented on a Digital Equipment Corporation VAX.
The VAX, operating in accordance with the routine PREDCT.FOR, read the files ELEC.PRM, QSM.DAT and ELEC.W. It then used the weights found as the steady state solutions of the stiff differential equations set forth in Equations (6a) and (7a) to predict the outputs for the prediction set of patterns in QSM.DAT. The file ELEC.OUT shows the result of this computation for the weights and thresholds given in the file ELEC.W. As may be readily seen from inspection of the output Y[j] for the prediction set (the left-hand column on page A-6 of the Appendix) with the output produced by the network 10 in accordance with the invention as implemented by the VAX operating in accordance with the routine PREDCT.FOR, the network correctly classified each of the forty two (42) samples in the prediction set.
The accuracy of the network predictions listed in the file ELEC.OUT on page A-6 of the Appendix is graphically illustrated in FIG. 6. Since there were 42 training patterns, and from Equation (8) the number of adjustable weights and thresholds was 27, there are still fifteen (15) degrees of freedom. Nevertheless the network, with only two hidden elements, was able to correctly classify all 42 accept/reject decisions.
In the example discussed, as may be seen from the FLOWTRACE set forth on page A-4 of the Appendix, training of the network to a convergence having a tolerance of 0.01 required less than seven seconds of execution time (actually 6.741 seconds) on a CRAY X-MP/24 computer, using 25,600 time steps, well within NMAX. The actual solution of the Equations (6a) and (7a), which determines the values of the weights) required 6.629 seconds, and required execution of the routine DIFFUN 1505 times. In a traditional sequential-update scheme, where the weights are determined in accordance with the first term of the right hand side of Equation (1), training would have required at least 25,600 effective training presentations of all the training patterns to achieve this convergence, since the training rate eta is usually less than 1. That is, traditional training of the network would have required 25,600 iterations wherein .DELTA.W[gd] would have been calculated. Stated alternatively, the number of iterations n in Equation (1) to train the network would have been 25,600 (with eta equal one and alpha equal zero). But, training done in accordance with the present invention resulted in one call to the subroutine DIFFUN, which is shown in the FLOWTRACE output as calling the routine DIFFUN 1505 times. For this example, therefore, the computational speedup due to using the training scheme in accordance with the invention is a factor of at least seventeen (17, 25,600 divided by 1505).
Moreover, the uniform convergence of the RMS prediction error is illustrated in the file NEURAL.CPR shown at Appendix page A-4, along with the rapid buildup of the computation step size being used. Toward the end of the training, in accordance with the present invention the network is learning at a rate hundreds of times faster than the traditional iteration scheme.
Distributed parallel processing network methods such as those outlined here can be a useful complement to traditional statistical methods, particularly when the underlying interactions are complex and nonlinear. Compared with multiple least squares regression, the network can accommodate a more complex (i.e., nonlinear) relationship between inputs and outputs. The underlying principle of minimizing the least squares prediction error is the same, but the back propagation network is more general. The network is model-free, in contrast with nonlinear least squares fitting procedures, since no assumption is made about the inherent functional form relating inputs to outputs; the accuracy of the representation is limited only by the quality of the data, not by the adequacy of the model.
Those skilled in the art, having the benefit of the teachings of the present invention may impart numerous modifications thereto. It should be understood, however, that such modifications lie within the contemplation of the present invention, as defined by the appended claims. ##SPC1##
Claims
What is claimed is:
1. In a parallel distributed processing network implemented in hardware alone or in a digital computer operating in accordance with a program, the network being of the type having: a first, input, set of from one to i processing elements, each input processing element having an input port and an output port, each of the i input processing elements being connectible to an input signal at the input port thereof and each being operable to produce an activation signal A1[i] at the output port thereof; a second, intermediate, set of from one to k processing elements, each processing element having an input port and an output port, each of the k intermediate processing elements being operable to produce an activation signal A2[k] at the output port thereof; a third, output, set of from one to j processing elements, each processing element having an input port and an output port, each of the j output processing elements being operable to produce an activation signal A3[j] at the output port thereof; each of the i processing elements in the input set of processing elements being connected to at least one of the k processing elements in the intermediate set of processing elements with each such interconnection having a connection weight W1[i,k] associated therewith, each of the k processing elements in the set of intermediate processing elements being connected to at least one of the j processing elements in the set of output processing elements with each such interconnection having a connection weight W2[k,j] associated therewith, the network being arranged such that a set of p training signals, applied at the input ports of the input processing element produces activation signals A1[i,p], A2[k,p] and A3[j,p], each of the p training signals being associated with a predetermined one of a set of V predetermined desired output signals, wherein the improvement comprises: the activation signals A1, A2, and A3 and the connection weights W1, W2 of the interconnections between the input processing elements and the output processing elements being related by a first set of stiff differential equations ##EQU7## the activation signals A2 and A3 and the connection weights W2 of interconnections between the intermediate processing elements and the output processing elements are related by a second set of stiff differential equations ##EQU8## and wherein the weights W1 and W2 are, respectively, calculated by converging to the steady state solutions of the first and second sets of stiff differential equations.
2. The parallel distributed processing system of claim 1 wherein the output port of each of the i input processing elements is connected to the input port of each of the k intermediate processing elements and wherein the output port of each of the k intermediate processing elements is connected to the input port of each of the j output processing elements.
3. The parallel distributed processing system of claim 2 wherein the means defining the first, second and third sets of processing elements comprises at least one digital computer operating in accordance with a program.
4. The parallel distributed processing system of claim 2 wherein the means defining the first, second and third sets of processing elements comprises interconnected discreet analog components.
5. The parallel distributed processing system of claim 2 wherein the means defining the first, second and third sets of processing elements comprises an integrated circuit having a substrate, the input, intermediate and output layers of processing elements and the interconnection lines therebetween being formed on the substrate.
6. The parallel distributed processing system of claim 1 wherein the means defining the first, second and third sets of processing elements comprises at least one digital computer operating in accordance with a program.
7. The parallel distributed processing system of claim 1 wherein the means defining the first, second and third sets of processing elements comprises interconnected discrete analog components.
8. The parallel distributed processing system of claim 1 wherein the means defining the first, second and third sets of processing elements comprises an integrated circuit having a substrate, the input, intermediate and output layers of processing elements and the interconnection lines therebetween being formed on the substrate.
9. A method for training a parallel distributed processing system of the type having a first, input, set of from one to i input processing elements, each input processing element having an input port and an output port, each of the i input processing elements being connectible to an input signal at the input port thereof and each being operable to produce an activation signal A1[i] at the output port thereof; a second, intermediate, set of from one to k intermediate processing elements, each processing element having an input port and an output port, each of the k intermediate processing elements being operable to produce an activation signal A2[k] at the output port thereof; a third, output, set of from one to j processing elements, each processing element having an input port and an output port, each of the j output processing elements being operable to produce an activation signal A3[j] at the output port thereof; each of the i input processing elements being connected to at least one of the k intermediate processing elements with each such interconnection having a connection weight W1[i,k] associated therewith, each of the k intermediate processing elements being connected to at least one of the j output processing elements with each such interconnection having a connection weight W2[k,j] associated therewith, the network being arranged such that a set of p training signals, applied at the input ports of the input processing elements produces activation signals A1[i,p], A2[k,p] and A3[j,p], each of the p training signals being associated with a predetermined one of a set of V predetermined desired output signals, the method comprising the steps of: (a) defining the relationship between the activation signals A1, A2, A3 and the weights W1 and W2 in the form of a first and a second set of stiff differential equations ##EQU9## (b) solving the sets of differential equations to find the values of the weights W1 and W2; and (c) adjusting the weights of the network such that the weights W1 and W2 correspond to the solution sets of the first and second sets of stiff differential equations.
10. The method of claim 9 wherein the solving step (b) is performed using a digital computer operating in accordance with a program.
11. The parallel distributed processing system defined by the process of claim 10.
12. The parallel distributed processing system defined by the process of claim 9.
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US4773024 | 1988-09-01 | Faggin et al. | |
| WOXW08807234 | 1988-09-01 |
Non-Patent Literature (6)
- Widrow, "Generalization and Information Storage in Networks of ADELINE Neurons," Self Organizing Systems, Yovitts, Editor, Spartan Books, NY (1962), pp. 435-461.
- Rumelhart et al., "Learning Internal Representations by Error Propagation," Parallel Distributed Processing, vol. 1, Foundations, pp. 318-362.
- Kung et al., "An Algebraic Projection Analysis for Optimal Hidden Units Size and Learning Rates in Back-Propagation Learning," IEEE International Conf. on Neural Networks, pp. I-363 to I-370.
- Kollias et al., "Adaptive Training of Multilayer Neural Networks Using a Least Squares Estimation Technique," IEEE, pp. I-383 to I-399.
- Gelband et al., "Neural `Selective` Processing and Learning," IEEE, pp. I-417 to I-424.
- Hush et al., "Improving the Learning Rate of Back-Propagation with the Gradient Reuse Algorithm", IEEE, pp. I-441 to I-446.