US 5,249,259 AGrant
Genetic Algorithm Technique for Designing Neural Networks
Issue Date:1993-09-28
•15 Claims
•26 Drawing Sheets
Abstract
A generic algorithm search is applied to determine an optimum set of values (e.g., interconnection weights in a neural network), each value being associated with a pair of elements drawn from a universe of N elements, N an integer greater than zero, where the utility of any possible set of said values may be measured. An initial possible set of values is assembled, the values being organized in a matrix whose rows and columns correspond to the elements. A genetic algorithm operator is applied to generate successor matrices from said matrix. Matrix computations are performed on the successor matrices to generate measures of the relative utilities of the successor matrices. A surviving matrix is selected from the successor matrices on the basis of the metrics. The steps are repeated until the metric of the surviving matrix is satisfactory.
Metadata
Assignee
- Massachusetts Institute of Technology
Inventor
- Robert L. Harvey
Application Information
Application Number:US 8924015
Filing Date:1992-05-28
Priority Date:1990-01-23
Art Unit:238
Classifications
IPC:
G06F 1518
Field of Search:
39513;24;27;23
Patent Drawings (26 sheets)
Description
Background of the Invention
The invention relates to genetic algorithms, and to the use of genetic algorithms in designing neural networks (NNs).
One aspect of NN design is the specification of the interconnections among a NN's neurons to achieve a desired input-output (I/O) relationship. In particular, for the class of long term memory (LTM) time invariant NNs, the NN is programmed for a particular I/O relationship by choosing the weight of each interconnecting trace between a pair of neurons.
Conventional NN design techniques make simplifying assumptions so that the problem of determining the trace weights is tractable. Examples of these simplifying assumptions are that the neurons are arranged in layers within which no lateral connections are made or that a neuron can be simultaneously excitatory and inhibitory, i.e., the weights of traces from a particular neuron to others in the NN can be positive to some and negative to others.
Summary of the Invention
In general, the invention features applying, in a program controlled computer, a genetic algorithm search to determine an optimimum set of values, each value being associated with a pair of elements drawn from a universe of N elements, N an integer greater than zero, where the utility of any possible set of said values may be measured. An initial possible set of values is assembled, the values being organized in a matrix whose rows and columns correspond to the elements. A genetic algorithm operator is applied to generate successor matrices from said matrix. Matrix computations are performed on the successor matrices to generate measures of the relative utilities of the successor matrices. A surviving matrix is selected from the successor matrices on the basis of the metrics. The steps are repeated until the metric of the surviving matrix is satisfactory.
Preferred embodiments of the invention include the following features. The method may be adapted for determining, for neurons of a neural network, a set of interconnection weights which will enable the network to approximate a prespecified output when presented with a predetermined set of input data. In that adaptation, the initial possible set of interconnection weights is assembled, and matrix computations are performed on the input data and on the successor matrices to generate an output of each successor matrix. A metric is computed corresponding to the difference between each generated output and the prespecified output, and the successor matrix is selected based on the metrics.
The interconnection weights in the matrices are forced to comply with constraints that correspond to the architecture of the neural network. The interconnection weights in the matrices are organized so that the interconnection weights leading to a given neuron all appear in a single row (or a single column) of each matrix, and the interconnection weights leading from a given neuron all appear in a single column (or a single row) of the matrix. The constraints include requiring that the interconnection weights between a neuron and itself be zero. The constraints also include requiring that the interconnection weights leading from a given neuron all be of the same sign. The neural network comprises a layer of input neurons, a layer of hidden neurons, and a single output neuron. The step of applying a genetic algorithm operator comprises applying a mutation operator by randomly changing a portion of the interconnection weights in a given matrix. No other genetic algorithm operator is applied, other than mutation. The interconnection weights are organized in more than one matrix based on layers of neurons in the neural network. The input data sets include binary values which represent edges of an image. The step of selecting a successor matrix on the basis of the metrics may include either testing whether a metric lies within a band between upper and lower bounds, or testing whether metrics with respect to predetermined input data sets lie above a passband or below a stopband.
Use of matrix representations enables simple and rapid design of a neural network. The meanings of the interconnection weights may be easily interpreted because of the manner in which they are arrayed in the matrix. Simplifying assumptions required in some other techniques may be avoided. Complex, fully interconnected networks an be designed for implementing user specified, input output functions.
Other advantages and features will become apparent from the following description of the preferred embodiment and from the claims.
Description of the Preferred Embodiment
We first briefly describe the drawings.
FIG. 1 is a functional block diagram of a pattern recognition system.
FIGS. 2A, 2B, 2C, and 2D are a diagram of edges in images.
FIG. 3 is a diagram of the layers of one kind of neural network.
FIG. 4 is a diagram of neurons and interconnections within the network.
FIGS. 5A through 5D are equations relating to the invention.
FIGS. 6A and 6B are matrices of interconnection weights.
FIG. 7 is a diagram of constaints imposed on the interconnection weights arrayed in a matrix.
FIG. 8 is a flow chart of a method of designing the interconnection weights.
FIG. 9 is a set of input data matrices for testing the neural network.
FIG. 10 is a diagram of horizontal feature detector response.
FIG. 11 is a diagram of the generational history of metrics during the design process.
FIGS. 12A through 12D set forth matrices of interconnection weights for a horizontal edge detector.
FIG. 13 is a graph of numbers of generations required for various numbers of hidden neurons.
FIG. 14 is a curve of sensitivity to number of copies per generation.
FIG. 15 is a diagram of diagonal feature detector response.
FIG. 16A through 16D set forth matrices of interconnection weights for a diagonal edge detector.
The LTM, time-invariant class of NNs is particularly suited for applications such as preprocessors, feature detectors, and feedback control modules in larger processing systems. Referring to FIG. 1, in a pattern recognition system of the kind described in copending patent application, U.S. Ser. No. 07/784,634, filed Oct. 28, 1991, assigned to the same assignee and incorporated herein by reference, patterns of an input image are analyzed to classify objects represented by patterns within the image. The output of the system is an indication of the categories, or names, of the objects located within the input image.
Each of the modules within the system of FIG. 1 mimics a particular function of the biological vision system. The system includes a pattern edge strength module 10 and a perimeter edge strength module 12 which mimic the functions of the biological vision system's visual cortex areas called visual area 1 and visual area 2, respectively. Together, these two edge strength preprocessors provide edge strength information to the classifier module 14 for final classification of objects located within an input image.
The system of FIG. 1 also includes a digitizer unit 18 which digitizes the input image data 16, and a locate/focus/adjust unit 20 which locates patterns within the input image data 16, provides control to the digitizer unit, and receives feedback from the classifier module 14.
The pattern edge strength module 10 generates a measure of the visual strength of the edges within a pattern in the input image data 16. For binary images, the module measures the visual strength of the pattern's orientations in the horizontal, vertical, and two 45 degree diagonal directions. For gray-scale images, the module generates measures of the magnitude of the luminance gradient in the four directions. These orientation measurements of luminance lines and gradient magnitudes model similar processing that occurs in biological vision systems.
The perimeter edge strength module 12 measures the visual strength of a pattern's perimeter in the northern, southern, eastern, and western directions. Thus, the module's output indicates the orientational strength of a pattern's edges.
In measuring the edge strengths of a pattern, both the perimeter and pattern edge strength modules evaluate an edge's magnitude with no special regard for the edge location within an image. To illustrate this rationale, consider the image blocks A, B, C, and D of FIG. 2, which could be evaluated for their horizontal edge strengths. The images labeled A and B would produce the same edge strength, because lines A and B, although at different image locations, are of the same length. In contrast, image C would produce a higher strength value than image D because image C includes more and longer lines than image D.
To implement either of the edge strength preprocessors described above with a LTM NN, the NN would ideally model the orientation sensitive biological NN found in the human primary visual cortex. Thus, the implemented NN might measure, for example, the edge strength of a binary pattern in the horizontal direction. Design constraints implied by this biological-like function of the NN, as discussed below, dictate considerations of both the NN's architecture and interconnections.
The network architecture suggested by the biological design constraints, as shown in FIG. 3, consists of a layer of M input neurons 16 which receive the input pattern, a network of N neurons located within the network, called hidden neurons 18, and a single output neuron 20. This architectural framework allows direct correlation between the neurons of the artificial and biological networks. The network input layer is composed of, for example, a 7.times.7, 2-dimensional array of neurons, for a total of M=49 input neurons. Connected to the input layer, the hidden neuron network may include N=25 interconnected neurons, with some subset of those neurons being connected to the output neuron.
Considering the network architecture in more detail, FIG. 4 illustrates a subset of some possible network interconnections for the network. The input neurons, labeled A-D in the figure, are configured in an array so that each may accept one piece, or pixel, of an input pattern. This capability mimics the process by which a visual image would be defined on the input layer of the human primary visual cortex. The output connection of each input neuron is specified to connect it with some set of hidden neurons, labeled E-J in the figure, and possibly the output neuron, labeled O in the figure. Within the hidden neuron network, each neuron may be connected to some set of input neurons, some set of hidden neurons, and the output neuron, but all three types of connections are not required for any given neuron.
In operation, the activation state of each neuron determines whether or not it "fires", i.e., whether or not it sends an output signal to the other neurons connected to it. This activation is determined by all of the input signals received by each neuron, i.e., a neuron's activation depends on the activation of the neurons connected as inputs to it. Arrows in the figure indicate the direction of input and output for each connection between a pair of neurons. If a neuron's activation is smaller than a design threshold, the neuron will not send any output signals. If the neuron's activation reaches or passes the design threshold, it will "fire" by sending an output signal along each of its output connections.
When a neuron "fires", its output signals act to affect the activation states of the neurons to which it sends signals. There are two possible conditions, called types, of neuron output signals. A neuron's output signal may be excitatory (type 1), meaning that it is trying to "turn on" a succeeding neuron by raising that neuron's activation state. Alternatively, the neuron's output may be inhibitory (type 2), meaning that it is trying to "turn off" a succeeding neuron by lowering that neuron's activation state.
Each neuron is specified as being either excitatory or inhibitory by assigning a multiplication factor, called a weight, to each of its output connections. When a neuron "fires", sending multiple output signals, each of those signals is multiplied by the weight of the particular connection it has been sent through. A positively weighted signal acts to increase a succeeding neuron's activation, while a negatively weighted signal acts to decrease a succeeding neuron's activation. This custom weighting of each output signal is what enables a neuron to increase or decrease the activation of a succeeding neuron. The particular assigned weight determines the degree to which one neuron's output signal contributes to the next neuron's activation.
The connections of each neuron in the example NN are further defined such that when any of the hidden neurons or the output neuron "fires", it does not send an output signal back to the input layer. However, output signals of each hidden neuron may be sent to other hidden neurons as feedback within the hidden neuron network.
These activation and connection design rules are supplemented by design constraints, based on experimental physiology, which are applied to the network architecture to model the behavior of the biological NN of the visual cortex. The additional design constraints include:
(1) A neuron has no feedback connection to itself.
(2) Each of the neurons is excitatory or inhibitory, but not both simultaneously.
(3) All input neurons are excitatory, and all hidden neurons are inhibitory.
Constraint (3) defines the example NN to be of the ON-Center/OFF-Surround architecture. Operationally, this implies that the input neurons are always trying to turn on the hidden neurons they are connected to, as well as the output neuron, while the hidden neurons are all trying to turn off the other hidden neurons they are connected to, as well as the output neuron.
The output neuron does not send any signals backward to the hidden or input neurons; its only output signal is, in the example, the NN's horizontal edge strength measure for an input pattern. This output signal is a real analog number, with the range of the signal determined by the NN interconnection design and training, as discussed below.
Given all of the design rules and assumptions discussed above, the last remaining NN design specification is the choice of interconnections between all of the NN neurons. This interconnection choice may be considered as the selection of the NN interconnection weights, as an interconnection weight of zero implies that no interconnection exists, while a positive weight causes an interconnection to be excitatory and a negative weight causes an interconnection to be inhibitory.
Each interconnection weight, and the NN set of weights together, is chosen to enable the NN to provide a desired relationship between a set of input patterns and the output horizontal edge strength measures the NN would generate for the set. In particular, the NN weight set is chosen to define the range of the output signal and the correspondence between values in the range and strength of a given horizontal edge. Thus, the weight set selection acts to calibrate the NN for a design specified input-output (I/O) relationship.
In the invention, a trial and error approach is used to select the NN interconnection weights. The inventive method eliminates the need for certain simplifying assumptions required in known techniques for designing interconnection weights for a NN. Furthermore, the resulting NN may require fewer neurons and fewer interconnections than a corresponding NN designed using other methods. Also, the resulting NN may be easier to implement than a corresponding NN designed by known methods.
The particular trial and error strategy employed by the current invention is a form of the general search strategy called the genetic algorithm (GA). The GA is a known search procedure, inspired by evolution and heredity, for locating high performance structures in a complex task domain. It is an iterative technique for exploring large search spaces and complex problems of the kind that lack convenient closed forms. For NN design purposes, it is a search method for finding a good set of interconnection weights in a high-dimensional, non linear weight space.
Note that the weight space, or set of possible NN interconnection weights in our example, is large enough (there are 49 input neurons and 25 hidden neurons) to discourage simple trial and error search procedures. In a traditional unstructured search, the interconnection weights would be selected by random, the performance of the newly defined NN computed, the result evaluated, and the process repeated until a satisfactory result is obtained. This is equivalent to numeration because each weight selection trial is unaffected by the outcome of previous selection trials. For any but the simplest cases it is easy to show that this is not a practical technique because of the large number of trials required before a satisfactory set of weights is achieved.
In general, the GA principle gives guidelines for constructing practical search techniques when the number of possible trials is extremely large. The fundamental requirements for solving a trial and error problem with the GA are that the problem must be capable of being represented by some data structure and that the problem's solutions be capable of being evaluated.
The general GA procedure is defined as follows: A set of structures, called a generation, is created, which attempts to solve a particular problem. The structures, generally known as schemas, are manipulated by one or more genetic operators to create a new set of structures. These new structures are evaluated on how well they solve the problem and the best are saved, thereby creating a new generation. A requirement for constructing further generations is that the advances already made must be retained and that the retained advances be used to increase the population of fit structures. This evolutionary process is repeated until a structure produces an acceptable solution to the problem.
To choose the optimum set of NN interconnection weights, the GA procedure is implemented as follows:
(1) An initial set of interconnection weights is formed by randomly choosing a value for each of the weights in the whole NN.
(2) The weight set is manipulated by a genetic operator to create a new generation of weight sets.
(3) Each weight set which is a member of the new generation of weight sets is evaluated on how well its corresponding NN responds to a set of test, or training, input patterns in generating a horizontal edge strength measure for each of the training patterns.
(4) Steps (2) and (3) are repeated until a set of interconnection weights produces a NN with an acceptable relationship between input patterns and output horizontal edge strength measures.
In step (1) of the design procedure, the set of NN interconnections must be represented in a manner that can be easily mapped to a representation that can be subjected to a GA operator. This mapping is achieved by formulating a mathematical representation of the activations of each of the neurons in the NN to be designed. This formulation is called the short-term memory (STM) equation, and describes the activation of a neuron by all of the inputs to that neuron. The most general STM is shown as Eqn. 1 of FIG. 5.
Z.sub.ji, defined in Eqn. 1 as the LTM trace from the j-th neuron to the i-th neuron, is the weight value assigned to the interconnection between the j-th neuron and the i-th neuron. Thus, the matrix of coefficients includes the complete set of Z.sub.ji s for all i and j that we seek. The function f(x.sub.j), called a sigmoid function, is defined to set the threshold for activation of a neuron. Thus, for example, using a simple step function as the sigmoid function would cause a neuron with an activation below the step never to "fire", and would cause a neuron with an activation above the step to always to "fire".
Interpreted literally, the STM equation shows that any changes in the activation of a neuron are determined by the sum of any external inputs to that neuron (I.sub.i), all of the weighted signals received from other neurons (Z.sub.ji), and the current activation of the neuron. This equation is the cornerstone of NN design and is adequate for an initial NN design. If desired, it can be replaced with the shunting STM Equation for a better model.
Given the desired NN architecture described above and in FIG. 3, the STM equation can be customized to specifically describe the activations of neurons in the input layer, hidden layer, and output of the NN. Since neurons in the input layer have no interconnections between themselves, Eqn. 1 simplifies to Eqn. 2 of FIG. 5 for the input layer neurons, showing that input neurons only receive inputs from the pattern defined on them.
Neurons located within the hidden neuron network may receive inputs from any of the input neurons and any of the other hidden neurons, so that the STM equation for the hidden neurons simplifies to Eqn. 3 of FIG. 5.
Likewise, the output neuron may receive inputs from any of the input or hidden neurons, so its STM equation simplifies to Eqn. 4 of FIG. 5.
In Eqn. 3, the interconnection weights may be grouped between those associated with connections between the input layer and a hidden neuron and those associated with connections between two hidden neurons. This new hidden neuron STM equation, as shown in Eqn. 5 of FIG. 5, delineates the weight interconnections within the hidden network as Z.sub.ji and interconnections between the input layer and hidden network as Z'.sub.ki.
In the steady-state, each of the input neuron activations will approach the external inputs applied to them, i.e., x.sub.k will approach I.sub.k, where k=1, . . . , M. For this case, the steady state hidden system STM equation becomes Eqn. 6 of FIG. 5.
To map the interconnection weights to a structure which may be manipulated by a GA operator, matrix notation is introduced as shown in Eqn. 7 of FIG. 5. Each element of matrix X represents the activation of the corresponding neuron in the hidden neuron network. Using this matrix notation, the hidden neuron STM equation (Eqn. 5) becomes that of Eqn. 8 of FIG. 5.
Using this matrix notation, each element of matrix A represents the corresponding interconnection weight between two of the hidden neurons. As an example, FIG. 6(a) illustrates what the elements of matrix A would be for the simplified NN of FIG. 4. The first element of matrix A, Z.sub.EE, is the weight coefficient of the interconnection from hidden neuron E back to itself. Although, as was discussed above, this interconnection is not actually allowable by the design rules, it, like every other theoretically possible interconnection from neuron E, is included in the general matrix.
Similiarly, the second element of the first row, Z.sub.EF, describes the weight of the connection from hidden neuron E to hidden neuron F. Thus, the first row of matrix A includes the interconnection weights for all possible connections from neuron E and all of the other hidden neurons. Likewise, all of the other rows and columns of matrix A represent each of the other possible connections between the hidden neurons.
As shown in FIG. 6(a), matrix B represents all of the possible interconnections between the input layer neurons and the hidden layer neurons. Thus, each element of matrices A and B may be directly correlated to a physical interconnection of the NN being designed.
Continuing with the matrix notation and considering the output neuron activation, the steady-state output is denoted simply as Z, i.e., x.sub.O approaches Z in the steady-state. Then the output neuron's STM equation may be grouped to delineate which interconnections are coming from the input layer and which are coming from the hidden layer, the sets of interconnections being represented in Eqns. 9 and 10 of FIG. 5.
FIG. 6(b) illustrates what matrices C and D would look like for the example NN of FIG. 4. Matrix C includes all of the possible connections between hidden neurons and the output neuron. Matrix D includes all of the possible connections between input layer neurons and the output neuron.
Given this matrix formulation of the NN activations, the design rules and constraints discussed above can be efficiently and understandably imposed as the GA is used to determine an optimum set of interconnection weights. Further, and more importantly, the A, B, C, and D matrices can be directly manipulated by the GA procedure to solve the weight search. Indeed, each GA interconnection generation is simply a new copy of the interconnection matrices, so that each matrix element coefficient (weight) plays a role analogous to a DNA molecule in biological evolution.
To begin the GA interconnection weight search procedure using the weight matrix notation, the activation, connection, and physiological design rules discussed above must be imposed on the interconnection weights, and thus on the interconnection weight matrix elements. With these constraints, the weight matrices for the ON-Center/Off Surround NN being designed have the following properties:
(1) A has zero diagonal components,
(2) A and C have only negative or zero elements,
(3) B and D have only positive or zero elements,
(4) The rows of A give the lateral inhibition to other hidden neurons.
While these constraints are difficult to include in standard design techniques, it will be seen that they can be easily accommodated using the GA search technique. FIG. 7 summarizes the constraints on the system matrices for the biological-like NN.
With these constraints in place, the computational steps for the NN design procedure (see FIG. 8) are as follows:
(1) Form (40) a parent initial matrix set A, B, C, and D of interconnection weights which satisfy the design constraints.
(2) Make copies of the parent set of matrices, and for each copy (42), randomly select a number of the matrix elements to be changed, subject to maintaining the above matrix properties, to produce successor matrices (offspring). In GA terminology, a mutation operator is used to construct new generations.
(3) Apply a set of input patterns (44) to each NN corresponding to one of the copies and solve (46) for each NN's edge strength output for each pattern. (Note that a solution may not always exist.)
(4) Compute (48) a metric to quantify the discrepancy between each of the NN outputs of (3) and the prespecified solution (50).
(5) Select (52) the copy of the A, B, C, and D matrix set which provides the best NN I/O relationship (i.e., has the smallest discrepancy metric). Make this copy the survivor.
(6) Use the survivor as the parent for the next generation and repeat steps (2)-to-(5).
(7) Continue until the selection criterion is met (54).
(8) The surviving matrix set A, B, C, D determines the interconnection weights for the final NN design.
The example NN edge strength preprocessing modules to be designed using the above procedure contain, as described previously, 49 input neurons, 25 hidden neurons, and one output neuron. This NN requires 1924 interconnection coefficients to be specified. For simplicity, the sigmoid function defined in the activation equation is a unit step. The model is a "sum of sigmoids" not the usual simplifying approximation of "sigmoid-of-sums".
To implement step (1) of the design method, a random number generator is used to specify the matrix elements, thus establishing an initial parent set of interconnection weight matrices. Although the elements of the parent matrix set are chosen randomly, the interconnection constraints described above are followed in the choice. The random selection of initial matrix elements increases the likelihood that some portion of initial weights will be adequate immediately, thus decreasing the required computation of new generations.
Using the GA mutation operator, each new generation is created by first making 10 copies of the parent matrix set A, B, C, D. Then, for each copy, one-third of the weight elements of each matrix are randomly changed, subject to the given interconnection constraints, over the search range 0, +/-1, +/-2, . . . , +/-10. While other GA operators may be feasibly used with the current inventive NN design method, the mutation operator is most easily applied to the schema defined by the matrix notation and has been found to be sufficient.
The choice of 10 copies (or offspring) per generation and one third changes per copy is purely logistical and may be chosen differently without affecting the efficiency of the method. Similarly, the search range limit of -10 to +10 places a boundary on the search space to speed up the calculations, and may be chosen differently.
To implement step (3) of the design procedure, the 12 training patterns illustrated in FIG. 9 are input to each of the NN offspring of the current generation, and each of the NN offspring's responses is calculated. The arrangement of 1's on a background of 0's in each training pattern represents a possible edge. A desired output is specified for each input training pattern, and a metric is defined to measure the distance, or error, of the NN response from the desired output. Many metrics are possible. One possible metric specifies that for each input pattern, the NN output response Z should lie within a bank of upper and lower bounds. This HI-LO metric, described below, is used to calibrate the desired NN output measurement for each training program. The metric defines the acceptable NN output to be in the range 50-100 for the "high response" training patterns, and -100-10 for the "low response" training patterns.
As shown in FIG. 9, training patterns 1, 2, and 3 are examples of input patterns with horizontal lines, and so should elicit a high response from the NN, with pattern 1 generating the highest response. Training patterns 4-12 of FIG. 9 have little or no horizontal components in them, and so should elicit varying degrees of low responses.
FIG. 10 illustrates the mapping of acceptable output responses, or Zs, for each of the 12 training patterns, to the response ranges. The first dot, labeled 1 in FIG. 10, is the output Z for the first training pattern. For this case, Z surpasses the HI band limit of 100 because of its maximum horizontal strength. The dots 2 and 3 lie above the HI pass band minimum of 50 because they have a high degree of "horizontalness". The dots corresponding to patterns 4-12 are expectedly located between -100 and 10, indicating their degree of horizontal edge strength.
The HI-LO metric is formulated by summing the error of the NN output for each training program. Thus, for N.sub.p training patterns, the error, d, of the NN output is given by Eqn. 11 of FIG. 5. As shown by Eqn. 12 of FIG. 5, if the NN correctly calls a "high pattern" "high" or a "low pattern" "low", d=0 for that pattern. If the NN incorrectly measures a pattern's horizontal edge strength, d=1 for that pattern.
Another type of metric would require that the output be above a passband threshold for certain patterns and be below a stopband threshold for the other patterns. This PASS-STOP criterion is formulated as follows:
For N.sub.1 PASS patterns and N.sub.2 STOP patterns, with N.sub.p =N.sub.1 +N.sub.2, the error, d, of the NN output is given by Eqn. 13 of FIG. 5. As shown in Eqn. 14 of FIG. 5, if the NN correctly identifies a pattern, d=0 for that pattern, while d=1 if the pattern is not identified correctly.
For both metrics, the inequality of Eqn. 15 of FIG. 5 holds true. The condition d=N.sub.p means that the NN satisfies none of the selection criteria (maximum error); the condition d=0 means that the NN satisfies all the selection criteria and that a solution has been reached. In the design procedure the metric, d, starts at N.sub.p (or smaller) and monotonically decreases to zero.
To compute the error d for each NN copy and pattern, Eqn. 8 of FIG. 5 must be solved for the steady state activation matrix X with that copy and pattern. Once X is known, the NN output Z is computed directly with Eqn. 10 of FIG. 5. This Z is then compared to the HI-LO metric to determine the error d. Recasting Eqn. 8 of FIG. 5 to reflect a particular NN, given the matrices A.sub.NXN and B.sub.NXM and an input pattern I.sub.MX1, it is required to solve Eqn. 16 of FIG. 5.
Assume for illustration that I.sub.MX1 is binary. It is easily shown that for some choices of {A,B,I} no solutions may exist, a single solution may exist, or multiple solutions may exist.
The solution of non linear matrix equations such as Eqn. 16 of FIG. 5 may be achieved using many different methods. The method used for the inventive design procedure is a combination of operator decomposition followed by recursion based on a fixed point theorem. The first two terms of the operator decomposition solution, X.sub.0 and X.sub.1, are given by Eqns. 17 and 18 of FIG. 5. The recursive form used to solve for a final.times.matrix is given as Eqn. 19 of FIG. 5, with X.sub.1 being the initial value. The recursion is continued until X(+)=X(-).
The above recursion scheme will converge to a solution if and only if the operator defined by the right-hand side of Eqn. 19 of FIG. 5 is a contraction operator. In practice, an operator may be a contraction in some subspaces and not in other subspaces. For the horizontal edge strength NN, the initial values generated by operator decomposition will be in a contraction subspace for more than 90% of the choices of the A and B matrices. It typically requires 7 to 10 recursions to reach the final solution of the activation equation.
To complete steps (4), (5), and (6) of the design procedure, the metric d of each of the 10 different offspring NNs is compared with the metric d of the parent NN. If an offspring metric is below the parent metric, then the offspring replaces the parent NN for the next generation. When two or more offspring NNs all are more satisfactory than a parent NN, one of the offspring is randomly chosen to become the new parent.
To summarize the system variables chosen for the inventive design method, Table 1 lists together all of the design rules chosen to complete the 5-step procedure outlined above.
FIG. 11 illustrates the time history of the metric d as the GA design procedure evolves a set of interconnection weight matrices to an acceptable solution. The acceptable solution is achieved after about 600 NN generations. The one remaining error at the 600th generation corresponds to the response above the high threshold from the first training pattern, which is acceptable. FIGS. 12A through 12D illustrate the final A, B, C, and D matrices that the example GA design procedure produces. These matrix values are used to implement the NN interconnections so that the resulting NN measures edge strength values within the output range defined by the training patterns.
In practice, one would like to minimize the computation time required to reach an acceptable generation of NN interconnection weights. Two of the critical parameters to be chosen for this consideration are the number of hidden neurons in the NN and the number of copies made per generation of the GA procedure. The relationship between these parameters follows a power law, as shown by Eqn. 20 of FIG. 5.
To illustrate this relationship, the effect of changing these parameters is shown for a fixed cooperative-competitive (C--C) NN. In a C--C NN, the hidden neurons maybe of both types 1 and 2 (excitatory and inhibitory, respectively). Therefore, in applying the matrix constraints to a C--C NN, the system matrix properties for ON-Center/OFF-Surround NNs are modified as follows: property (1) still holds while properties (2) and (3) are changed such that the corresponding columns of matrices A&C and C&D have the same sign.
FIGS. 13 and 14 illustrate the number of generations required to find an acceptable interconnection weight set as a function of the number of hidden neurons and the copies made per generation, respectively. As shown for this C--C case, .alpha.=1 and .beta.=-3/2. Since the total computer design time is proportional to the total number of copies, i.e., to NG.times.NC, to first order the computational time varies as N/NC.sup.1/2. Because the mutation process is random, the number of generations required for solution is also random. The brackets indicate the range over which solutions were determined.
The design method of the invention may be generally applied to any NN design which can be mathmatically formulated to allow for manipulation by a GA operator. For example, a diagonal, rather than horizontal, feature detector may be designed. FIG. 15 illustrates the NN output response Z of a diagonal edge strength NN measurer using the same training set described above. This NN is designed using the same method described above, but with different HI-LO bands so that a 45 degree diagonal detector NN is achieved. FIGS. 16a through 16D show the final matrices for the diagonal detector.
As a second example, the method may also be employed to design a NN analyzing gray input images, rather than binary images. A summary of this design method is as follows: The gray input pixel values are scaled to lie in the interval [0,1] using a digitizing preprocessor. To preserve the grayness of the input image, a piecewise linear sigmoid function with saturation is used in the activation equations so that a neuron's "firing" threshold is analog like, rather than digital. With this definition, the X matrix (hidden neuron activations), and NN output response Z are given by Eqns. 21 and 22 of FIG. 5. Here f.sub.1 () may be a unit step as before and f.sub.2 () is a piecewise-linear sigmoid with saturation such as given by Eqn. 23 of FIG. 5. This set of equations is used in the above design procedure to achieve a NN which is sensitive to edge gradient measurements of gray, rather than binary, images.
The method may also be used to design a NN with multiple outputs, rather than a single output neuron, or with other I/O properties. The method may be extended to generally provide a design framework for constructing any type of NN to have a desired network performance.
The method may be implemented by software. An example of code that implements the method is set forth in Appendix A. The code in Appendix A is written in the APL language, and may be run and compiled on the IBM-AT computer. Appendix A is subject to copyright protection. The copyright owner has no objection to the reproduction of Appendix A as it appears in the United States Patent and Trademark office, but otherwise reserves all copyright right whatsoever.
Other embodiments are within the claims. ##SPC1##
Claims
I claim:
1. A computer method for implementing a neural network for use in a selected application, said neural network being implemented to effect a desired relationship between inputs representing real world phenomena and outputs corresponding to the inputs, said neural network having neurons and neurons interconnections each of said neurons possibly having an interconnection to any other of said neurons, each of said interconnections characterized by an associated weight value, said weight values having potentially any value including zero, positive, or negative, the method comprising (a) by computer, searching possible sets of weight values and selecting a set of weight values for use in the neural network, said step of searching and selecting comprising (i) picking an initial set of weight values; (ii) organizing said initial set of weight values in rows and columns, so the weight values in each of said rows all are associated with interconnections to the same one of said neurons, and the weight values in each of said columns all are associated with interconnections from the same one of said neurons; (iii) generating successor sets of weight values from said initial set of weight values; (iv) for each of said successor sets of weight values, determining test outputs of a neural network having those weights, when activated by predetermined inputs; (v) analyzing the merits of each of said successor sets of weight values based on how well the test outputs conform to predetermined outputs; (vi) selecting a single surviving set of weight values from among said successor sets of weight values based on the relative merits of said surviving set of weight values, said surviving set of weight values serving as an initial set; and (vii) if the merits of said surviving set of weight values meet a threshold, treating said surviving set of weight values as a final set of weight values; otherwise repeating steps (iii)-(vi) using said surviving set of weights as a new initial set of weight values; and (b) implementing said neural network with said final set of weight values.
2. The method of claim 1 further comprising constraining said interconnection weight values to comply with constraints that correspond to said selected application.
3. The method of claim 2 wherein said constraints include requiring that the interconnection weight values between a neuron and itself be zero.
4. The method of claim 2 wherein said constraints include requiring that the interconnection weight values leading from a given neuron all be of the same sign.
5. The method of claim 1 wherein said step of organizing said interconnection weight values comprises organizing said weight values with the interconnection weights leading to a given neuron all appearing in a single row (or a single column), and the interconnection weight values leading from a given neuron all appearing in a single column (or a single row).
6. The method of claim 5 wherein said rows and columns of interconnection weight values are organized in a number of matrices based on layers of neurons in said neural network.
7. The method of claim 6 wherein said neural network comprises a layer of input neurons, a layer of hidden neurons, and a single output neuron.
8. The method of claim 1 wherein said predetermined input comprises binary values which represent edges of an image.
9. The method of claim 1 wherein said step of generating successor sets of weight values comprises applying a genetic algorithm operator to said initial set of weight values.
10. The method of claim 9 wherein said step of applying a genetic algorithm operator comprises applying a mutation operator.
11. The method of claim 10 wherein applying said mutation operator comprises randomly changing a portion of said interconnection weight values.
12. The method of claim 1 wherein said step of analyzing the relative merits of the successor sets of weight values comprises computing a metric corresponding to the difference between said test outputs and said predetermined outputs.
13. The method of claim 12 wherein said step of selecting a surviving matrix comprises testing whether said metric lies within a band between upper and lower bounds.
14. The method of claim 12 wherein said step of selecting a surviving matrix comprises testing whether said metric lies above a passband or below a stop band.
15. The method of claim 1 wherein said predetermined input comprises gray gradient values which represent edges of an image.
Patent Citations (7)
Non-Patent Literature (23)
- Symbolic Schemata in Connectionist Memories: Role Binding and the Evolution of Structure; Technical Report UCLA-AI-87-11; Dolan and Dyer; pp. 1-23; Apr. 1987.
- Designing Neural Networks using Genetic Algorithms; International Conference on Genetic Algorithms, ICGA '89, George Mason University, Fairfax, Va.; Miller, Todd, and Hedge; pp. 379-384; Jun. 4-7, 1989.
- Towards the Genetic Sythesis of Neural Networks; International Conference on Genetic Algorithms, ICGA '89, George Mason University, Fairvax, Va.; Harp, Samad, and Guha; pp. 360-369; Jun. 4-7, 1989.
- Training Feedforward Neural Networks Using Genetic Algorithms; International Joint Conference on Artificial Intelligence, IJCAI '89, Machine Learning; Montana and Davis; pp. 763-767; Aug. 20-25, 1989.
- Applying Genetic Algorithms to Neural Network Learning; Proceedings of the Seventh Conference of the Society for the Study of Artificial Intelligence and Simulation of Behavior; Whitley; pp. 137-144; Apr. 1989.
- Parametric Connectivity: Feasibility of Learning in Constrained Weight Space; T. Caudell; IJCNN; Jun. 18-22, 1989; vol. 1; pp. 667-675.
- Calibration of Neural Networks Using Genetic Algorithms, with Application to Optimal Path Planing; Smith et al.; First Annual Workshop on Space Operations, Automation, and Robotics (SOAR '89); Aug. 5-7, 1987; pp. 519-526.
- Schaffer et al., "Using Genetic Search to Exploit the Emergent Behavior of Neural Networks", Physica D, vol. 42, Jun. 1990, Nos. 1-3, pp. 244-248.
- Montana et al., "Training Feedforward Neural Networks Using Genetic Algorithms", IJCAI-89, Proceedings of The Eleventh International Joint Conference on Artificial Intelligence, vol. 1, Aug. 20-25, 1989.
- L. Davis and S. Coombs, "Genetic Algorithms and Communication Link Design: Theoretical Considerations", Proc. Second Int. Conf. on Genetic Algorithms and Their Applications, Jul. 28-31, 1987, (pp. 252-260).
- S. Coombs and L. Davis, "Genetic Algorithms and Communication Link Speed Design: Constraints and Operators", Proc. Second Int. Conf. on Genetic Algorithms and Their Applications, Jul. 28-31, 1987, (pp. 257-260).
- Smith et al., "Calibration of Neural Networks Using Genetic Algorithms, with Application to Optical Path Planning", NASA Conference Publication 2491, Aug. 5-7, 1987, pp. 519-526.
- Grossberg, "Nonlinear Neural Networks: Principles, Mechanisms, and Architectures", Neural Networks, vol. 1, pp. 17-61, 1988.
- McClelland et al., "Explorations in the Microstructure of Cognition", Parallel Distributed Processing, pp. 333-371, 1988.
- Holland, "Adaption in Natural and Artificial Systems", ISBN 0-472-08460-7, Oct. 11, 1988, pp. v-vii.
- Adomian, "A Global Method for Solution of Complex Systems", Mathematical Modelling, vol. 5, pp. 251-263, 1984.
- Deimling, "Nonlinear Functional Analysis", Index, AMS Subject Classification, 1980.
- De Jong, "On Using Genetic Algorithms to Search Program Spaces", Computer Science Department, George Mason University, pp. 210-216.
- Bickel et al., "Tree Structured Rules in Genetic Algorithms", Abstract, Department of Compute and Information Systems, Florida Atlantic University.
- Booker et al., "Classifier Systems and Genetic Algorithms", Elsevier Science Publishers B.V., 1989, pp. 235-282.
- Dolan et al., "Towards the Evolution of Symbols", UCLA AI Laboratory, pp. 123-131.
- Schaffer et al., "An Adaptive Crossover Distribution Mechanism for Genetic Algorithms", Philips Laboratories, North American Philips Corporation, Briarcliff Manor, New York, pp. 36-58.
- Fujiki et al., "Using the Genetic Algorithm to Generate LISP Source Code to Solve the Prisoner's Dilemma", Department of Computer Science, University of Idaho, Moscow, Id., pp. 236-240.