Dynamically Stable Associative Learning Neural Network System

The present invention relates to a dynamically stable associative learning neural network system involving neuron circuits and networks and, more particularly, to a neuron circuit employing a novel learning rule which enables associative learning, including correlations and anti-correlations, with decreased computational time and complexity.

Efforts have been made to use neural networks to emulate human-like performance in the areas of pattern recognition including pattern-recognition applications in speech or image recognition, classification systems, and adaptive control systems. The basic computational element of a neural network is the neuron circuit which typically has multiple input lines and a single output line. The output response of a neuron circuit is generally a nonlinear function of the sum of the signal amplitudes on its input lines, with an output response being triggered when the sum of the input signal amplitudes exceeds a threshold value. The output of a neuron circuit may be coupled to the input of more than one other neuron circuit.

A neural network is formed by interconnecting the neuron circuits through synapses, each of which has an associated weight for modifying any signal passing through it. The amplitude of a signal exiting a synapse is thus the product of the weight associated with that synapse and the amplitude of the signal entering the synapse. A synapse may be either excitatory, that is, its weight is positive because it contributes to production of a signal by the associated neuron circuit, or inhibitory, that is, its weight is negative.

The output end of each synapse terminates at an input line to a neuron circuit, with the other end connected to either the output line of another neuron circuit or to a primary input (i.e., the receptor) to the neural network. The primary outputs of a neural network are each derived from a single output line of one of the neuron circuits in the system. With such loose restrictions, a large number of differently configured neural networks can be formed by simply varying the synaptic connections between neuron circuits.

The two major classes of artificial neural networks developed are (1) single layer networks in which a set of neuronal elements are fully interconnected with each other and which function well as associators, and (2) multilayer perceptrons in which all interconnections are feed-forward connections between layers and which function well as pattern classifiers. For the networks in these two classes, the basic neuronal models used are variants of a concept in which (1) "synaptic" inputs to an element are summed and the element fires if a threshold is exceeded, and (2) the weight or strength of a synaptic junction is increased only if both the presynaptic and post-synaptic elements fire. Essentially, all of the currently popular neural network designs implicitly or explicitly use the element to be formed in the adjustment of the weights on its input. In most implementations, a nonlinear optimization or relaxation algorithm is used for setting weights. These algorithms are all computationally intensive, since for each set of inputs to be learned many iterations are required before convergence is achieved and the network has learned the input patterns. Depending on the details of the implementation, the computational complexity of these algorithms (reflected in the number of iterations needed to achieve convergence) is between O(N.sup.2) and O(N.sup.3) where N is the number of weights (connections) to be determined. Consequently, the total computational effort per connection increases as the number of connections is increased. A survey of neural networks can be found in R. P. Lippmann, "An Introduction to Neural Nets," IEEE ASSP Magazine, Pgs. 4-21, April, 1987.

Neural networks are taught by successive presentation of sets of signals to their primary inputs with each signal set derived from a pattern belonging to a class of patterns, all having some common features or characteristics. Each time a set of signals is presented to the primary inputs, the synaptic weights must be adapted in order for the neural network to learn from this input.

The primary disadvantages associated with prior art neural networks result from their methods of adapting synaptic weights when the neural networks are in the training mode. Essentially, conventional neural network designs implicitly or explicitly use the output response of a given neuron circuit in adjusting the weights of the synapses connected to its input lines (see, for example, U.S. Pat. No. 3,950,733 issued Apr. 13, 1976 to Cooper et al). The use of the output response requires nonlinear optimization or relaxation algorithms which are computationally intensive; for a relatively small network of neuron circuits, thousands or ten of thousands of iterations are typically required before convergence is achieved and the network is said to have learned a set of input patterns. As the number of neuron circuits increase, the computational time to achieve convergence increases at a polynomial rate.

Additionally, most neural networks require a noise free external teacher that provides the neural network with a desired set of output values chosen to represent the class of patterns being learned. Sets of signals representing the exemplary input patterns are successively applied to the primary inputs and propagate through the neural network to the output. The differences between the actual and desired output vales, determined by the external teacher, are calculated to arrive at an error signal that is employed, typically with a nonlinear algorithm, throughout the network to adjust synaptic weights. This process is repeated in a recurring manner and typically requires a large number of iterations to reduce errors appearing at the primary outputs to an acceptable level.

To overcome some of the limitations of the art, a neural network has been developed which has many advantageous properties including the ability to learn, store and recall associations among vast numbers of noisy patterns. This network is qualitatively different from sum-of-weighted input models proposed by others. Also, other image understanding/object recognition systems are not based on associative learning.

This invention relates to a neural network system characterized by levels of increasing complexity that represent improvements and enhancements in the ability of the system to function, for example, in the context of pattern recognition and classification. A hierarchy builds from a basic architectural unit, comprised of input and output elements with so-called "patches" (see definition below) interposed, by improving and expanding that basic unit to a multilayered (multi-subnetworked) system based on a concatenation of the basic unit.

Thus, in accordance with the present invention, the input presented to a basic neural network architectural unit comprises a first input signal comprising a set of conditioned stimuli (CS), and a second input (UCS) signal comprising an unconditioned stimulus. In some embodiments of the invention, CS arise from a pattern to be classified and UCS represents a classification category.

A signal is a detectable physical quantity or impulse (such as a voltage, current, or magnetic field strength) by which information can be transmitted; a physical representation of data. Input signals may be generated by an optical scanner for example, by scanning a visual image, such as a photograph or a handwritten set of numbers, a "chipped" digital image wherein images are digitally extracted from photos into image chips, or an analog output from an instrument, such as an oscilloscope showing a voice waveform. Input signals may be continuous or discrete (binary).

These input signals generate or modify the "patches," which are storage and processing areas interposed between the input and output elements of the system. The use of patches in the present invention is an improvement over systems that employ indirect connections, called "interneurons," between input and output, and over competitive learning networks.

More specifically, patches are created initially by signals input to the system. Patches are storage areas in whatever physical apparatus is used to implement a neural network of the present invention, and are important elements where signals interact and are modified according to the training set developed for a particular application and the network training rules. In particular, patches are the sites of local learning in the immediate vicinity of paired stimuli (conditioned and unconditioned) where component signals are aggregated and simplified so that network association learning is made efficient.

Patches are dynamic areas which respond to conditioned and unconditioned stimuli in accordance with various rules and methods, as presently disclosed, so as to organize signals into classes and/or features and to process the signals, thereby to condense or modify information to achieve goals of particular applications of the network.

A training or learning rule is a set of relationships that determine how the CS and UCS interact to modify the patches. In Example 1 herein, for example, weights of the most similar patch to a new input signal, and of all other patches are determined according to prescribed Equations 3 and 4.

An overall goal of the present invention is training a network so that it performs a given task. A trainable network may be trained by input of a training set. The task is defined by the training set presented to the network.

Recent neurobiological research strongly suggests that long-term storage of learned associations occurs in post-synaptic dendritic patches. An increase in responsitivity of a dendritic patch results from repeated stimulation of the patch by a series of similar signals presented in the same temporal relationship to each other. Increased responsivity is essentially a local phenomenon, independent of whether the output neuron responds to input or not. A local learning rule that is independent of neuron output is useful, since it requires neither error correction nor feedback.

Associative learning in the present invention is facilitated by storing the associations in the dendritic patches. In this scenario, the firing of the neuron is a readout of the UCS associated with the active patches. The result is a network with combinatorial specificity, where the pattern of neuron firings is the information-bearing code.

Significant advantages of the network are realized with the implementation of dendritic patches which model the local interaction of unconditioned stimuli and conditioned stimuli pathways into two separate input streams. The pathway for the unconditioned stimuli pattern is separate and distinct from the pathway for the conditioned stimuli pattern. Also, in order to induce associative learning, the unconditioned stimuli pattern is presented together with the conditioned stimuli pattern (each to their own input neurons). After the association has been learned, presentation of the conditioned stimuli input alone will elicit, as the output of the network, that unconditioned stimuli with which that conditioned stimuli has previously been associated.

The basic architectural unit of the network also includes an output neuronal element with a receptive field. This field comprises i) a subset of the conditioned stimuli and ii) a component of the unconditioned stimuli associated with the CS subset. Output may occur in the form of reconstructed, processed or classified images, depending on the problem presented to the network. For example, a goal may be to recognize an individual face despite different views of the face being presented as input. The present invention also relates to various modifications, extensions and expansions of the basic architectural unit, said unit defined as signals input to the system, patches, and output signals.

In embodiments that modify and extend the network, there may be a plurality of patch elements, each of which connects a plurality of input stimuli with an output neuronal element. Patches are each capable of learning an association.

Patch elements occupy positions in a hyperspace volume in the system which may be created, deleted or modified by various procedures disclosed herein. The purpose of these patch-creation, -deletion and -modification procedures is to improve the performance of the system by increasing efficiency and/or accuracy.

As disclosed herein, in the fixed threshold model of patch creation (constant size), the closest patch for the stored UCS which is the same as that of the CS is found by the use of the similarity between a conditioned stimulus and preexisting patches. If the computed similarity falls below some threshold, a new patch is created whose patch vector equals the input pattern. If the similarity is larger than the threshold, the patch is updated. This threshold ensures that all patches will cover a similar "size" or area in n-space (hyperspace).

An aspect of the present invention is to use patches more effectively by allowing patches to vary in area within predefined thresholds. Variable size patches facilitate efficiency because new patch creation is limited to where patches are needed, for example, to refine boundaries, which addresses the limitation that the more patches created, the larger is the network and the slower its operation on a serial computer.

A term used interchangeably with "variable size" patches is "variable radius" patches, where a radius may be considered as a threshold in n-space. In this method, the closest patch is selected regardless of its UCS. The UCS is then considered and if it does not match, a new patch is created, regardless of the similarity between the CS and the patch.

The "variable radius" method provides a means for controlling resolution of the definition of boundaries between adjacent classes in a neural network. There may be different architectural units, each with different rules for creating and altering patches--some fixed, some variable. In the multilayered (multi-subnetworked) network disclosed in subsequent sections, different layers (subnetworks) may have different rules. This allows for great flexibility in the system.

There are generally two thresholds for the variable-radius- patch-creation method. These thresholds may be designated T.sub.H and T.sub.L. To illustrate the use of these thresholds, if T.sub.H defines a boundary in hyperspace, and T.sub.L defines a boundary beyond T.sub.H, if an input CS value falls within the boundary defined by T.sub.H for the patch with the most similar patch vector, that the patch will be updated. If the value lies beyond T.sub.L, a new patch will be created even if it has the same UCS.

Variable size patch creation thus is a method of creating patches that more efficiently cover the hyperspace formed by the set of the input patterns. It allows the system to create many "small" patches where needed to distinguish similar CS patterns that have different UCS values associated with them, but use a few "large" patches where all similar patterns have the same UCS value. This results in fewer patches needed for most problems and is directed toward better results where patterns of different kinds have subtle differences.

Another aspect of the present invention is to provide enhancements that permit a patch to modify its own receptive field. A receptive field includes those components of the conditioned stimuli input that are connected to an output neuron.

One modifying method to effectively reduce the size of the receptive field is by "pruning." The effect of "pruning" is to allow patches to have a customized receptive field. In general, if a connection to a patch varies significantly while the patch is active, relative to the variability of the input value overall, that connection is removed from the patch's receptive field. Subsequent comparisons for matching of patches ignore the incoming signal on that connection. Advantages of "pruning" include savings in computational time and improved classification accuracy, assuming the pruned connections represented noise rather than information.

Another aspect of the present invention is "budding," a method of optimizing the number of connections to a patch. Basically, conditioned and unconditioned stimuli enter the receptive fields of the output neurons. If the receptive fields are considered without "budding," the entire receptive field is active. With budding, a subset of the field is designated as "active" and is used to calculate the similarity measure; the inactive portion being passive for calculating the similarity measure, but is updated for calculation of the running average. For example, 10% of the entire signal input may be selected as the active receptive field. The selection criteria for the "active" field will depend on the nature of the problem, for example, the active section may be chosen at random or selected based on some aspect of the problem or classification, perhaps a geographic area, a Gaussian data conversion, or the like.

Some input values will have low variance overall and therefore will contain no information. Similarly, if the within-class variance approximates the among-class variance, those connections will be of little use as classifiers. Conversely, small intraclass and larger interclass variances characterize good discriminators. Methods designated as "pruning" and "budding" may remedy these limitations and, depending on the circumstances, may be used simultaneously. Budding is useful when there is a sparse receptive field and addition connections are helpful. Pruning is a method for removing connections that appear to contribute little, if anything, to classification and pattern recognition from a large receptive field. For use of these methods, it is necessary to keep track of the variances of the patches.

Another aspect of the present invention relates to a multilayered (multi-subnetworked) network, that is, a concatenation of single subnetworks (wherein a subnetwork is equivalent to a basic architectural unit) to improve feature recognition capabilities of a neural network system and to permit the combination of outputs of subnetworks operating in parallel.

In a two-subnetwork embodiment of a neural network, the first subnetwork is structured either by eliminating the UCS inputs or by setting all UCS inputs to the same value, irrespective of the class of training exemplars. Initial CS input is received by the system as defined for a single subnetwork. Patches that are formed in this embodiment reflect only similarity of CS patterns, independent of their classification.

If the receptive fields represent only a portion of the complete input pattern, then the patches will record and respond to similarities in the portion of the input field to which they are attached, that is, to the similarity of "features" within that portion of the field. Consequently, the output neurons of this first layer transmit, as the input to the second subnetwork not the product of the most similar UCS with the similarity measure, as in the basic network, but rather the identification of each patch and, optionally, the similarity value as a pair of numbers for the most similar patches.

In one embodiment of a two-subnetwork neural network, the first subnetwork propagates a relatively small number of patch numbers and (optionally) their associated similarity to the second subnetwork. That number can be chosen either by stipulating a threshold similarity that must be exceeded by the patch to be considered, or a numerical limit (e.g., the five patches with the greatest similarity, or a combination, those patches with a similarity in excess of a threshold, but no more than the top five of these). Appropriate similarity measures are chosen from those disclosed herein. Use of correlation coefficients, normalized dot products, power-divergence statistics and the like divide the input hyperspace into cones. The classifying UCS is presented to the UCS input of the second subnetwork.

The basic structure of input elements, patches and output elements in a two-subnetwork can be extended further to a multilayered (multi-subnetworked) neural network, which comprises n subnetworks, wherein the first subnetwork is defined as having an input conditioned stimuli and output neurons that are connected to the input neurons through patches. The output of the first subnetwork provides the input to the second subnetwork, said second subnetwork input being transmitted to the second output neurons through patches in the second subnetwork, wherein each of said patches may receive input from a plurality of output neurons of subnetwork 1. Further, each successive subnetwork is linked to subnetwork n-1 by the output of the n-1 subnetwork, the output of n-1 serving as the input of n, and wherein unconditioned stimuli are input to the nth (final) subnetwork. The bigger the n the greater the abstraction or compression of information that is achievable.

In this network, the input to each successive layer (or subnetwork) comes from a multiplicity of outputs from a previous subnetwork. CS inputs in the first subnetwork are as described for the basic architectural unit, but input to subsequent layers are output elements representing patch identifiers from the previous subnetwork. The final subnetwork receives UCS as in the simpler embodiments, one component to each patch of the final subnetwork. Accordingly, there must be at least as many output neuronal elements in the final layer as there are components to the UCS. An advantage to the multi-subnetworked system is the abstraction of information from signals as subsequent layers (subnetworks) are encountered.

Layers (or subnetworks) may have different patch creation rules, that is, they may use pruning and/or budding or neither. The basic criterion for a multilayered (multi-subnetworked) network is that the output of subnetwork n-1 is the input of the nth subnetwork.

In view of the foregoing, it is an object of the present invention, among others, to provide a dynamically stable, associative learning neural network system which is capable of signal classification, pattern recognition, and other feats. The system associatively learns both correlations and anti-correlations.

It is another object of the present invention to provide a dynamically stable, associative learning neural network system that can be configured to classify or to restore patterns simply by changing the number of output units.

It is a further object of the present invention to provide a dynamically stable, associative learning neural network system in which neither global nor local feedback connections are required during learning, thus eliminating the need for any non-linear optimization or iteration.

In view of these and other objects, the present invention provides a dynamically stable, associative learning neural network system which in its general form provides for the separation of UCS and CS pathways into two separate input streams, and which entails the implementation of dendritic "patches" which model the local interaction of USC and CS pathways during associative learning.

For neurons with binary outputs, 50 neurons are capable of encoding 2.sup.50 noise free messages. If b different firing intensities can be differentiated, b.sup.N different messages are possible where N is the number of output neurons sharing common inputs, and b is the number of distinguishable gray levels.

An advantage of the network algorithm exploited in accordance with the present invention is that it has a computational effort that scales linearly in complexity with the number of connections, i.e., O(N). For example, on a completely parallel computer, learning time is constant regardless of the size of the network. The number of pattern-set presentations is small compared to other systems and does not change with pattern size or complexity.

A network of the present invention exhibits monotonic convergence, reaching equilibrium values after being fully trained, without oscillating. Neural networks are machine independent, that is, a neural network can be implemented in hardware, software, or a combination of both. Many different types of hardware or software may be employed for the operation of the system. Those of skill in the art will select the appropriate hardware, software, or combination thereof, appropriate to a particular application. For example, some aspects of the system are readily implemented on a VLSI chip.

The present invention eliminates the need for, but does not preclude, a noise-free, external teacher. In addition, there is no need for feedback of some output parameter or error measure in order for the network to learn an association.

Still another advantage of the present invention is the minimal constraints on architecture when it is embodied in neural networks. Because changes in synaptic weights are based solely on the signal history of synapses within the same receptive field of a neuron circuit, either feedback or lateral connections can be made between layers of neuron circuits or within the same layer of neuron circuits without changing the method of teaching the neural network. Thus, the learning rule does not restrict the global connections of the network.

The explicit inclusion of time within the learning rule enables neural networks constructed with neuron circuits according to the present invention to associate arbitrary patterns. In the prior art, some external error measure was needed to guide the learning process.

It has been found that neural networks constructed of neuron circuits employing the learning rule of the present invention learn more quickly than those of the prior art. The typical neural network of the prior art requires many times more iterations than the present invention to learn an association.

Other objects and further scope of applicability of the present invention will become apparent from the detailed description to follow, taken in conjunction with the accompanying drawings, in which like parts are designated by like reference characters.

The present invention is further described by way of examples and drawings wherein:

FIG. 1 is a schematic diagram illustrating a single neuron circuit including variable synapses in accordance with an embodiment of the present invention;

FIG. 2 is a flow diagram illustrating, in schematic form, the synaptic-weight training rule for the adaptive weight circuit of FIG. 1;

FIG. 3 is a schematic diagram illustrating a single neuron circuit including two types of connections flowthrough and collateral in accordance with an embodiment of the present invention;

FIG. 4A is a, conceptual illustration of a receptive field of a k.sup.th layer inputting to a flow-through synapse of a k+1 layer in which each flow-through synapse is shown in perspective as a solidly filled ellipse and each non-flow-through synapse is shown in shaded ellipse;

FIG. 4B is a conceptual illustration of a combination of flow-through and collateral neuronal elements but with collateral connections only at x.sub.j, k+1;

FIG. 4C illustrates the learning rule for neural combinations of flow-through and collateral connections for permitting weight increases;

FIG. 5 is a partial schematic diagram of the architecture of a neural network according to the present invention with flow-through synapses shown and collateral synapses omitted for clarity;

FIG. 6 is a sectional view taken along lines 6--6 of FIG. 5 with collateral synapses shown as open circles to illustrate the flow-through and collateral synapses connecting the layers of neuron circuits;

FIG. 7 illustrates the receptive fields of a neuron circuit with a flow-through synapse connection;

FIG. 8 illustrates the receptive fields of a neuron circuit without a flow-through synapse connection;

FIG. 9 is an illustration of the basic architectural unit of a preliminary version of the present network for learning both correlations and anticorrelations;

FIG. 10 illustrates the basic architectural unit of a generalized network with two conditioned stimuli inputs, and unconditioned stimuli and output neuron, and showing 1, n patches in which the interneuron of FIG. 9 has been subsumed into patches;

FIG. 11 is a flow diagram of the operation of a single neuronal element in the neural network system.

FIG. 12 is a decision space for variable size patch creation using thresholds. If the similarity (S.sup.m) of the incoming CS pattern to the most similar patch with a matching UCS value (P.sup.m) exceeds T.sub.H then that patch is updated. If S.sup.m is less that T.sub.L then a new patch is created. If S.sup.m is between the two thresholds, then a new patch is created if p.sup.m is not most similar patch overall, p.sup.mo.

FIG. 13 is a schematic representation of a single output neuron and its associated patches. Each patch consists of the patch vector, the expected value of one component of the UCS, and a frequency of use based weight. Each output neuron has many patches and the CS and UCS inputs are connected to the output neuron via the patches.

FIG. 14 is a schematic illustration of a multilayered (multi-subnetworked) neural network.

A neural network is constructed of a plurality of interconnected neuron circuits with various types of such interconnections known in the art. The neural network operates by receiving one or more input signals and transforming these input signals into one or more output signals through the interconnected neuron circuits. In the related art, the weights of the various synapses control the response of each neuron circuit and hence the overall response of the neural network. Typically, the various weights are adjusted during a learning process to provide the desired network response. In the prior art, this learning process involves the application of various exemplary inputs for comparison of the actual outputs with the desired outputs. This feedback process may not converge quickly and equilibrate at the weights required for the desired network response. In addition, this technique requires the use of global parameters, namely the network outputs, for the adjustment of each individual synapse. The present invention represents substantial difference and improvements over other networks.

In an illustrative embodiment, the present invention provides a plurality of synapses, each synapse having a synaptic weight for producing a signal proportional to the product of the input signal and the weight, and a non-linear function circuit, such as a step, threshold, or sigmoid function circuit, for summing the outputs of each synapse and producing a nonlinear summation output. An adaptive weight circuit is provided for adjusting the weight of each synapse based upon the current signal, and at least one prior signal applied to the input of the particular synapse and the current signal and at least one prior signal applied to the input of a predetermined set of other synapses.

The weight of a synapse is increased if and only if that particular synapse and a predetermined set of other synapses all receive nonzero signals on their respective synaptic inputs for both the current time and the immediately preceding time. The weight of a synapse is unchanged and thus retained if and only if the particular synapse receives nonzero signals on its inputs for both the current time and the immediately preceding time and the predetermined set of other synapses do not all receive nonzero signals on their respective synaptic inputs for both the current time and the immediately preceding time. In all other cases the adaptive weight circuit reduces the weight of the particular synapse.

In an illustrative embodiment, the synapses have a maximum weight value and a minimum weight value. When the weight is increased, the amount of the increase is proportional to the difference between the prior weight and the maximum weight value, and, when the weight is decreased, the amount of the decrease is proportional to the difference between a prior weight and the minimum weight value.

Another illustrative embodiment of the present invention includes a flow-through synapse, that is, a synapse having a predetermined fixed weight near the maximum weight value, which flow-through synapse is not coupled to the adaptive weight circuit.

A network is formed employing neuron circuits of the adaptive and flow-through types and includes a plurality of input terminals and an equal number of output terminals. At least one layer of neuron circuits are connected between the input terminals and the output terminals. Flow-through neuron circuits are connected by flow-through synapses to form separate and direct paths between each input terminal and a corresponding output terminal. The collateral neuron circuits are connected to synapses with adjustable weights connected to the outputs of other neuron circuits to permit correlative learning.

The neural network is initialized by setting the adjustable weight synapses at some value near the minimum weight with each fixed weight of each flow-through synapse set near the maximum value, for example, 0.91. This value is set so that the inputs will not propagate to the outputs without additional stimulation from collateral neuron circuits, that is, neuron circuits not on the flow-through path. The neural network is taught by successive application of sets of input signals to the input terminals until a dynamic equilibrium is reached in which the sum of the weight increases and the weight decreases over a set of input presentations is zero or near zero.

In still further and preferred embodiments, each output element has a dynamically allocated number of memory storage devices known as "patches." Each patch stores a single association between (1) the portion of the conditioned stimuli (CS) input in the output element's receptive field; and (2) that element of the associated unconditioned stimuli (UCS) input related to that output. The memory of an entire CS pattern is distributed over many patches and output neurons, each of which learns a portion of the pattern.

A patch is composed of: (1) a patch vector, which is the average value of the CS input patterns that it has matched (each component of the patch vector is real-valued and receives input from a single CS input element); (2) the expected value for the UCS component associated with this CS and output neuron; and (3) a weight that reflects the frequency of use of the patch. Every patch of a given output neuronal element is connected to the same subset of CS inputs. Thus, each patch learns an association between a CS input sub-pattern and a component of the UCS input by storing both the vector of CS input values and the value of the UCS input component. One of the ways patches differ from prior art network components is that the latter calculate output by (weight x signal) algorithms in which each individual input is multiplied by a weight associated only with that input connection.

In an extension of the network suitable for gray-scale pattern recognition, patch information is stored as multi-bit values and the similarity between patch vectors and input pattern is computed using a geometrically specific function of the stored patch vector. The input signal pattern is transmitted by the direct connection. A suitable function includes Pearson's R which provides a range between -1 and +1 (inclusive) that provides a measure of correlation, with +1 indicating complete correlation, a -1 indicating negative anti-correlation, and a zero representing no correlation. Because the similarity-computation uses the input signal transmitted by the CS connections, interneurons and indirect connections are not needed. The signal propagated is a function of the computed similarity between the patch vector and the input pattern, and all patches above a computed-similarity threshold participate in signal propagation. In the extended network, the learning rule for calculating the weight on the patch includes storing a moving average of CS signals, and storing a moving average of the unconditioned stimuli signal to allow gray scale values to be learned, distinguished and reproduced. Additionally, the frequency of use of each patch is determined and, where the frequency of use is below a certain value, that patch is removed.

FIG. 1 illustrates a neuron circuit 100 in accordance with one embodiment of the present invention. The neuron circuit 100 includes input lines X.sub.1, X.sub.2, . . . , X.sub.i, . . . X.sub.n ; synapses 22, 24, 26, and 28; function circuit 20; and output line 30 and an adaptive weight circuit 150. The adaptive weight circuit 150 receives signals from each of the input lines X.sub.i, X.sub.2,. . . , X.sub.i, . . . , X.sub.n and includes outputs connected to the synapses 22, 24, 26, and 28 for adjustment of the respective weights W.sub.1, W.sub.2,. . . , W.sub.i,. . . , W.sub.n. The adjustment of each weight depends upon current or present input to that synapse, the prior history of inputs to that synapse, and the current and prior inputs to at least one other synapse of the same neuron circuit.

The preferred synaptic-weight training rule for the adaptive weight circuit 150 for modifying the synaptic weights is shown in flow chart form in FIG. 2. The adaptive weight circuit 150 considers each synaptic weight once each time period, i.e., a predetermined sensing or operating time period. The weight of a particular synapse may be either increased, retained at the same level, or decreased. The weight of a particular synapse is increased if, and only if, that synapse received a nonzero input during both the current time period and the immediately prior or preceding time period and each synapse of a predetermined set of at least one synapse of the same neuron circuit also received a nonzero input during both the current and immediately prior time periods. The weight of a particular synapse is retained at the same level if, and only if, that synapse received a nonzero input during the current and immediately prior time periods and not all synapses of the predetermined set of synapses received a nonzero input during both the current and immediately prior time periods. Otherwise the weight of that synapse is reduced. By nonzero input, the above synaptic-training rule refers to a signal greater than the minimum output signal Y.sub.min with Y.sub.min =zero in the preferred embodiment.

When a weight W is modified, the rate of change is proportional to the difference between the current value W and the extreme allowed value in the direction of change. These extremes may be, for example, 0 or 1 for an excitatory synapse and -0.5 or 0 for an inhibitory synapse. The constants of proportionality for increasing and decreasing the values of collateral synapse weights are a and b, respectively. Thus, if a weight W is to be increased, the new value W' is given by:

If the weight W is to be decreased, then the new value W' is given by:

where, for example: a=0.33; b=0.005: W.sub.max =1.0; and W.sub.min =0.0 for excitatory synapses; and W.sub.max =-0.5 and W.sub.min =0.0 for inhibitory synapses.

FIG. 3 illustrates a neuron circuit 110 in accordance with an illustrative embodiment of the present invention utilizing two types of connections: flowthrough connections, which serve to define a set of principal pathways, and collateral connections. These two types of connections differ in that the weights (synaptic strengths) of flow-through connections are always set at a constant high value and the collateral connections are initially set at a low value and are modified according to the abovementioned synaptic training or learning rule.

The neuron circuit 110 of FIG. 3 is similar to neuron circuit 100 of FIG. 1 with the addition of a flowthrough synapse 122 (having a cross-hatched pattern). The flow-through synapse 122 has an input 112 connected to receive the input on line X.sub.ft, an output 132, and a predetermined fixed weight W.sub.ft. The adaptive weight circuit 150 is connected to input line X.sub.ft to receive the input signal to the flow-through synapse 122 so that the presence or absence of a signal on the input line X.sub.ft may influence the adjustment of the respective weights W.sub.1, W.sub.2, . . . , W.sub.i, . . . , W.sub.ft, if the signal on input line X.sub.ft is selected as being within the inputs influencing the weight of a particular synapse. In this regard the signal on input line X.sub.ft is no different than the signal on any other input line within the selected set for a particular synapse. The adaptive weight circuit 150 is not connected to flow-through synapse 122 to change its weight W.sub.ft and the weight W.sub.ft remains a predetermined constant which may be, for example, 0.91.

As illustrated in FIG. 4A, a receptive field RF utilizing a flow-through synapse in which each flow-through synapse is shown in perspective as a solidly filled ellipse and each non-flow-through connection, i.e., a `collateral` connection, is shown in shaded ellipse. In FIG. 4A, the flow-through pathway is shown as a thicker, darker pathway W.sub.ffk while the collateral connections are shown in lighter lines. As shown, the flow-through pathway W.sub.ffk extends directly from one flow-through neuronal element in the kth layer to the next flow-through neuronal element in the k+1 layer while the collateral connections in the k.sup.th layer in the exemplary illustration extend from the neuronal element to the flow-through neuronal element.

In contrast, FIG. 4B illustrates a combination of flow-through and collateral neuronal elements of a receptive field in the k.sup.th layer providing collateral connections only to an adjustable collateral neuronal element in the k+1 layer; for the receptive field of the element with collateral connections only, any number of connections from neurons with flow-through connections may exist. Thus, a neuron with a flow-through connection receives connections from input (receptive) fields of arbitrary size (either all positive, or center-on/surround-off) but only a single connection from a neuron with a flow-through connection. A neuron with only collateral connections also has an arbitrary size receptive field but may include many neurons with flow-through connections. Conceptually, the flow-through connections are analogues of pathways for unconditioned stimuli (UCS), and the collateral connections are analogues of pathways for conditioned stimuli (CS) because the weights for the synapses of the collateral connections can be varied in accordance with the learning rules illustrated herein. For pattern classification, the CS are the components of the pattern to be classified, the UCS are the desired classification.

The learning for a single architectural unit is illustrated in graphical form in FIG. 4C. As shown, the architectural unit includes a neuron with a fixed weight flow-through connection (FIG. 4) connected to a post-synaptic neuron through either a flow-through or a collateral connection and a neuron connected to the post-synaptic neuron through a collateral connection. At the synapse, the collateral connection knows the temporal relationships of the other connections synapsing on the same neuron, but has no information about any other connections or neurons, including the neuron upon which it synapses. As such, the learning rule does not depend on the firing history of the post-synaptic neuron. The connection weights of the collaterals are modified by the following rule: the weight of a collateral connection to a post-synaptic neuron is increased if, and only if, the collateral and the connections to that same post-synaptic neuron from neurons with a flow-through connection have both carried a signal two consecutive times (Time=t-.DELTA.t and time=t). The weight is not changed if the collateral connection has carried a signal twice successively and the connections to the same post-synaptic neuron from neurons with flow-through connections have not. Under all other combinations of circumstances, the weight associated with the collateral connection is decreased (i.e., the collateral neuron has not carried a signal twice successively). The rate of weight change is proportional to the difference between the current value of the weight and the extreme allowed values (usually 1 and 0) in the direction of the change, as described above.

FIGS. 5 to 8 illustrate an example of a neural network constructed of neuron circuits according to the present invention as illustrated in FIGS. 1 and 3. The neuron circuit 100 as illustrated in FIG. 1 is referred to hereinafter as a collateral neuron circuit, and the neuron circuit 110 as illustrated in FIG. 3 is referred to hereinafter as a flow-through neuron circuit. For simplicity, in the illustration of the neural network of FIGS. 5 to 8, each neuron circuit will be depicted as a circle; collateral neuron circuits 100 will be illustrated as shaded circles and flow-through neuron circuits 110 will be illustrated as filled circles. The associated connections between neuron circuits will be represented by lines terminated with arrows showing the direction of signal flow.

The neural network example of FIGS. 5 to 8 includes: a 3.times.3 array 210 of inputs: two 7.times.7 arrays of neuron circuits indicated at 220 and 230, each including both collateral neurons 100 and flow-through neurons 110; and one 3.times.3 array 240 of outputs. A simplified view of the overall structure of this example is illustrated in cross-section in FIG. 6 which shows the collateral and flow-through synapse connections between neuron circuits for the cross section marked 6--6 in FIG. 5. FIGS. 7 and 8 further illustrate the synaptic connections of the collateral and flow-through neuron circuits, respectively.

As shown in the partial perspective of FIG. 5, the architecture of the neural network, generally designated at 200, includes the array 210 of 3 rows and 3 columns of individual primary inputs 215. The input to neural network 200 is applied via this set of primary inputs 215. Output signals from the neural network are produced by the output array 240 which includes 3 rows and 3 columns of individual primary outputs 245. Two arrays 220 and 230 of neuron circuits 100 and 110 are interposed between the input array 210 and the output array 240. The arrays 220 and 230 each include 7 rows and 7 columns of neuron circuits. Each array 220 and 230 contains: nine flow-through neuron circuits 110, shown as solid circles: and 40 collateral neuron circuits 100, as represented by the shaded circles. The flow-through neuron circuits 110 are disposed in a 3.times.3 array which is embedded within the 7.times.7 combined array.

Flow-through neuron circuits 110 are connected via flow-through synapses (FIG. 5) to form continuous signal paths directly linking each input 215 to a corresponding output 245. Thus each flow-through neuron circuit 110 of array 220 has an input connected via a flow-through synapse to a corresponding input 215 of input array 210. In addition, each flow-through neuron circuit 110 of the second array 230 is connected via a flow-through synapse to a corresponding neuron circuit 110 of array 220. Lastly, the outputs of the flow-through neuron circuits 110 of the array 230 are connected to a corresponding output 245 of output array 240. Thus separate paths, including flow-through synapses and flow-through neuron circuits, links each input 215 to a corresponding output 245. For clarity, only connections via flow-through synapse arrays 210, 220, 230, and 240 are shown, with all collateral connections omitted.

A cross-sectional view of the neural network 200 taken along line 6--6 of FIG. 5 is shown in FIG. 6. The connections between neuron circuits via the flow-through synapses are denoted by relatively thick lines as also illustrated in FIG. 5. The remaining connections within the neural network 200 are via collateral synapses and are represented by the relatively thinner lines. Collateral synapses connect primary inputs 215 to input lines of collateral neuron circuits 100 in the first array 210. Collateral synapses connect the output lines of both collateral neuron circuits 100 and flow-through neuron circuits 110 in the first array 220 to single input lines of both collateral neuron circuits 100 and flow-through neuron circuits 110 in the second array 230, respectively.

The typical receptive field of a flow-through neuron circuit 110 is illustrated in FIG. 7. The receptive field consists of a 3.times.3 array 310 of neuron circuits located in a previous array (within the dashed squares). A single connection via a flow-through synapse is provided from the output of a flow-through neuron circuit 110 of the prior layer: all other links are via collateral synapses. All collateral synapses linking the neuron circuits in the receptive field are excitatory, i.e., their weights have positive values preferably within the range from 0.0 to 1.0. As indicated above, the flow-through synapse has a predetermined fixed weight near the maximum allowable weight, i.e., 0.91.

The typical receptive field of a collateral neuron circuit 100 is illustrated in FIG. 8. The receptive fields consist of a 3.times.3 array 300 of neuron circuits located in a previous array (within the dashed squares) with all connections made via collateral synapses. All these collateral synapses are excitatory, i.e., their weights have positive values preferably within the range from 0.0 to 1.0 with the set point for the weight determined during training.

In this embodiment of the invention, both the flow-through neuron circuits 110 and the collateral neuron circuits 100 within the second array 230 (FIGS. 5 and 6) each have receptive fields containing sixteen additional neuron circuits disposed adjacent to the outside border of the dashed squares as shown in FIGS. 7 and 8; these additional connections are via inhibitory collateral synapses. FIGS. 7 and 8 each illustrate only two such connections for reasons of clarity. The weights of the inhibitory collateral synapses are negative and range in value from 0.0 to a "maximum weight" of preferably -0.5. In the preferred embodiment of the present invention, the extra connections via inhibitory synapses have been found to increase the training efficiency of the neural network 200, but in this and other embodiments having larger arrays of neuron circuits, there is no requirement that extra connections via inhibitory synapses be included.

The typical use of a neural network of the type 200 disclosed is for recognizing whether a pattern belongs to a class of patterns having common characteristics. The first step in training initializes the weights of all the collateral synapses to values near their minimum. In the preferred embodiment, excitatory collateral synapses are given initial values of 0.10, while inhibitory collateral synapses are given initial values of -0.10. All the flow-through synapses have fixed weights near the maximum weight, for example, 0.91. This value is set so that the inputs will not propagate to the outputs without additional stimulation from the to-be-trained collateral neuron circuits, that is, neuron circuits not on the flow-through path. After initialization is completed, the neural network 200 is ready for training.

Training takes place by successively applying to the primary inputs 215 sets of signals derived from patterns having common characteristics. These sets of signals can be groups of either analog or binary values derived from patterns belonging to a class having common characteristics. Examples include sets of binary values representing the black and white pixel levels from pictures of the same object taken at slightly different angles or corrupted by noise, and sets of analog values sampled from voice waveforms obtained from different persons speaking the same work or group of words. For each application of a signal set to the primary inputs 215, the weight of each collateral synapse is modified by the adjustable weight circuit 150 for the neuron circuit. This successive application of the signal sets takes place for a sufficiently long period of time for the collateral synapse weights to converge towards and achieve relatively stable values. These relatively stable values will be dynamically stable, i.e., changing with the presentation of the set of input signals without any net change over the whole of the set.

A plot of the value of a weight for a typical excitatory collateral synapse as a function of the number of successive signal sets presented to the primary inputs was obtained from a computer simulation of a neural network representing the example described above in relationship to FIGS. 5-6. The set of signals sequentially presented to the primary inputs consisted of three input sets. The first two sets were identical and were derived from an image having 3.times.3 pixels, each pixel having a value ranging from 0 to 1, while the third set was a null set containing 3.times.3 pixels, all having values of 0.0. when these three input signals sets were continuously and sequentially presented to the primary inputs, the weight of a typical collateral synapse in the neural network converged towards and reached dynamic equilibrium in which weight increases and weight decreases over the set of patterns are equal, and no net weight change occurs. When the weights of all collateral synapses in the neural network reach this dynamically stable equilibrium state, the neural network is said to be trained to recognize the patterns represented by the set of input signals successively presented to the primary inputs. At equilibrium, the weights fluctuate between limits that are determined by three system parameters: (1) the maximum allowed weight (W.sub.MAX), (2) the learning increment, a, and (3) the weight decrement, b, together with the specific images and their order of presentation, i.e., their temporal association. The set of responses on the primary outputs 245, then represent the mean pattern of the collective group of patterns used in training.

Use of neuron circuits with a training rule of the present invention results in several advantages over the prior art. Firstly, the training rule is local to each neuron circuit, requiring no global error signal or measure for training. This results in improved learning performance of the neural network. If the neural network is embodied in a computer simulation, then the amount of computation required expands linearly with the number of synapses needed to connect the network. Computer simulations of neural networks employing learning rules in accordance with the prior art scale at a rate greater than linearly with the number of synapses. Similarly, for neural networks embodied in parallel hardware the number of interconnections required for teaching the network increases linearly with the number of synapses. This greatly reduces the number of interconnections as compared to the prior art. Thus the present invention enables increasing the size of the neural network with a lesser degree of additional effort. Because many problems require neural networks of hundreds or thousands of neuron circuits, this scaling factor can be a significant advantage in many applications.

The embodiments described above in the context of FIGS. 1-8 are effective in learning correlations; a further progression of embodiments, referred to herein as the generalized embodiments, is developed in FIGS. 9-14.

The generalized version of the neural network incorporates (1) the separation of the unconditioned stimuli and conditioned stimuli pathways into two separate input streams, (2) `interneurons` that allows the system to learn anti-correlations as well as correlations among input signals, and (3) the implementation of dendritic "patches" that model the local interaction of unconditioned stimuli (UCS) and conditioned stimuli (CS) pathways during associative learning.

In order to implement these features, the pathway for the unconditioned stimuli pattern is separate and distinct from the pathway for the conditioned stimuli pattern, and, in order to induce associative learning, the unconditioned stimuli pattern is presented together with the conditioned stimuli pattern (each to their own input neurons). After the association has been learned (and in exact parallel with Pavlovian conditioning), presentation of the conditioned stimuli input alone will elicit, as the output of the network, that unconditioned stimuli with which that conditioned stimuli has previously been associated.

The basic architectural unit of the preliminary generalized network, consisting of the separate unconditioned stimuli and conditioned stimuli pathways along with the indirect connection, is illustrated in FIG. 9. As shown, the relatively thicker vertical connection from neuron 1 to the output neuron 4 represents a flow-through connection from the unconditioned stimuli input (neuron 1); the relatively thinner lines represent collateral connections from the conditioned stimuli input (neuron 2); neuronal elements 3 and 4 have spontaneous firing activity. The arrow-tipped lines represent excitatory connections, the circle-terminated lines represent inhibitory connections, and the squares represent `patches` whose sign is determined during training by the signal in the flow-through (unconditioned stimuli) connection from the unconditioned stimuli input. This apparent ambiguity of sign is a computationally effective method of restricting attention to active patches, as described below, and does not imply or represent a change in function of an existing synapse.

To permit the network to learn the patterns of its input signals, rather than learning the signals from each individual input, "patches" on the "dendritic membrane" have been introduced with each patch reflecting a pattern of activity on the input neurons. Patches are where synapses are located. Weights are generally associated with each patch rather than with each connection and represent how often the patch has been used. Interneurons are deleted in more sophisticated embodiments.

To illustrate the differences between the original network of FIGS. 1-8 and the generalized version of the network (FIGS. 9 and 10) and present the concept of patches, a generalized network with two conditioned stimuli inputs, neurons 2a and 2b is shown.

The introduction of patches permits recognition, and therefore separation, of the patterns of incoming signals, i.e., recognition of which independent combination is being activated. These independent patterns have been termed herein as a "patch" as an analogy to the synaptic patches believed to be formed on branches of the dendritic tree of vertebrate neurons. Consequently, the weight associated with learning is now assigned to the patch as a whole, rather than to each incoming connection. By explicitly defining patches, the input signal is compared to all possible patch patterns, and the patch whose stored pattern is most similar to the input signal carries the signal.

An illustrative method is used for determining the patch that carries the signal when indirect connections are used (FIG. 9) where each patch i is described by a binary vector P.sub.i (n), where n is the index on the neurons that provide input to the patch, and

P.sub.i (n)=1 if the signal came from the direct connection, and

P.sub.i (n)=-1 if the signal came from the indirect connection.

The input signal is represented by the continuous-valued vector x(n) where n is the index on the neurons providing input to the patch and x(n) may be any value between 0 and 1. If x(n) is small, then the spontaneously active interneuron is not inhibited and the signal on the indirect connection is large. The signal on the indirect connection is represented as S(x(n)) or s(n). If SF is the level of spontaneous firing activity and g(Z) is as defined above, then

To calculate the degree of mismatch, a binary representation, D(n), of the input signal must be calculated:

D(n)=1 if x(n)>s(n) (the direct connection carries the signal), and

D(n)=-1 if x(n)<s(n) (the indirect connection carries the signal).

The degree of mismatch for a patch i may be calculated as the Hamming distance between D(n) and P.sub.i (n) and the most similar patch i, and thus the patch that carries the signal is that patch with the smallest degree of mismatch. In the event of a tie, the sum of (x(n)-s(n)).sup.2, for those n for which D(n).noteq.P(n), is calculated and the patch with the smallest value is selected as the most similar.

An alternative method of determining the most similar patch is to calculate a value termed herein as the degree of match, DM, as follows: ##EQU1##

The degree of match is a function of the absolute difference between s(n) and x(n). For each n, if D(n)=P.sub.i (n) then the absolute difference between s(n) and x(n) is added to the total, if D(n).noteq.P.sub.i (n) then the absolute difference is subtracted from the total. Pearson's r, a correlation coefficient well known to those of skill in the art, may be used as a similarity measure for gray scale inputs. When indirect connections are not used (FIG. 10) the degree of match and degree of mismatch may be calculated directly, without computing a binary representation of the input.

A computational simplification is introduced by not storing all possible 2N patches (where N is the upper limit of n, the number of neurons providing input to the patch); instead, only patches that are needed (whose number is a function of the specific unconditioned stimuli and conditioned stimuli inputs) are stored by the network. When a new signal is presented on the input, the pattern of activation is compared to existing patches. If the new signal is similar to an existing patch (the degree of mismatch is smaller than the "patch creation threshold"), then the signal is carried by that patch and its weight is changed. If the new signal is not similar to an existing patch, a new patch is stored. Repeated presentations of the same (or a similar pattern) causes the weight associated with the patch to increase. Patches which carry signals frequently have high weights, whereas weights are low on patches which carry signals rarely. An additional far-reaching consequence of the introduction of patches is that, without any additional complications, it eliminates both of the problems associated with memory capacity that plagues other artificial neural networks. It permits the storage of very large number of patterns, and these patterns need not be orthogonal.

The network of FIG. 10 can be expanded to learn to associate images, because the number of conditioned stimuli inputs is independent of the number of unconditioned stimuli inputs, allowing the network to associate a large image with a much smaller representation or vice versa.

Additionally, the network can be trained as an auto-associator, by presenting the same pattern to both the unconditioned stimuli and conditioned stimuli pathways, or as a hetero-associator, by presenting different patterns to the unconditioned stimuli and conditioned stimuli pathways. In both auto- and hetero-association, both the conditioned stimuli and unconditioned stimuli inputs may be noisy. By configuring the unconditioned stimuli input appropriately, a network trained as a hetero-associator can be made to function as a pattern classifier.

An improvement on the basic patch concept, is to vary the radius (size) of patches. Variable radius patch creation, is a method of creating patches that more efficiently covers the hyperspace formed by the set of input patterns. It allows the system to create more "small" patches where needed to distinguish similar CS patterns that have different UCS values associated with them, but use a few "large" patches where all similar patterns have the same UCS value. This means fewer patches for most problems and the potential for better results where patterns of different kinds have subtle differences.

As discussed in previous sections, the simplest form of variable radius (convoluted boundaries) patches employs no thresholds. When a pattern is presented, the CS values are compared with the stored CS values for all patches and the most similar patch (P.sup.mo) is determined. If the UCS value of that patch (U.sup.mo) matches the input UCS value, that patch (P.sub.mo) is updated. Otherwise, a new patch is created. (FIG. 11)

To allow for finer control over the maximum and minimum sizes of patches, two thresholds are introduced. The most similar patch (P.sup.M) with a matching UCS value is determined. The similarity (S.sup.M) between the incoming pattern and P.sup.M is calculated. One threshold (T.sub.C) limits the maximum size a patch can have. This ensures that a new patch is created if the input pattern is not sufficiently similar to any existing patch. That is, if S.sup.M <T.sub.L, a new patch is created. The other threshold (T.sub.H) prevents overcrowding of patches. It prevents a patch from being created if it is almost identical to an existing patch with a matching UCS If S.sup.M >T.sub.H, P.sup.M will be updated rather than creating a new patch. If the similarity lies between the two thresholds, patch creation depends on U.sup.mo. A patch is created only if the expected value of the most similar patch does not match the incoming UCS. FIG. 12 illustrates this relationship. By setting these thresholds to the same value, the neural network system would behave as if without variable size patches (with a patch creation threshold T.sub.c equal to the thresholds' value: T.sub.c =T.sub.L =T.sub.H ) as illustrated in FIG. 11. A general patch structure is shown in FIG. 13.

Other enhancements to a neural network, that permit a patch to modify its own receptive field, are "pruning" and "budding." An output neuron has associated with it a receptive field, i.e., those components of the CS input that are connected to the output neuron. In a simpler embodiment disclosed herein, when a patch is created, it inherits the neuron's receptive field and is unable to modify its receptive field. As described in subsequent paragraphs, receptive fields may be altered.

"Pruning," is a method of eliminating unnecessary connections to a patch. This effectively reduces the size of the receptive field for patches and allows patches to have a customized receptive field. If a connection to a patch varies significantly while the patch is active (relative to the variability of the input value overall), that connection is removed from the patch's receptive field. Thus, future determinations of whether there is a match for a patch will ignore the incoming signal on that connection. The idea is that a connection which varies considerably while a pattern is matched is not part of the distinguishing characteristics of that pattern. It is more likely some sort of noise. In some cases, inputs that would result in multiple patches without pruning may be combined into one pruned patch (which ignores the noise that previously forced the network to create multiple patches). Thus, ignoring these inputs saves computation time and is expected to improve network performance by avoiding the noise which might cause an inaccurate classification.

"Budding" is another method of optimizing the number of connections to a patch. While pruning requires an initial large number of connections which can then be reduced, budding allows the initial number of connections to be small and causes connections to be added as appropriate. With budding, a patch is defined as having an "active area" of its receptive field. The active area is the group of connections which are compared with the patch values to determine whether a patch is matched (in other embodiments, the comparison was made on the entire receptive field, in this alternative embodiment comparison is made on a subset thereof). When each pattern is presented, an active area of the input pattern is selected.

Methods for choosing the active area include using the bright, unusual, or recently changed areas of the inputs, depending on the nature of the input and the goal of operating the system. It may be desirable to limit the active areas to the spatially connected areas in the input pattern. A patch with this active area is created if there is not already a similar patch (similar both in which locations of the input pattern make up the active area and in the CS values in the active area, as well as UCS value). In addition, each patch is compared with the incoming pattern of CS values. This comparison uses only the connections in the patch's active area. This may cause one or more patches to be updated and/or a new patch to be created.

Whenever a patch is matched, the variability measure (the same value used in pruning above) is updated for all connections in the receptive field (not just in the active area). If a connection outside a patch's active area has a low enough variability, it becomes part of the active area. "Budding" could be combined with "pruning" to remove any connections accidentally left in the active area. Pruning could remove connections from the active area. By allowing the active areas to form entirely dependent on the input data, more useful views of the data may be formed (such as feature detectors).

In a preferred embodiment, FIG. 14 shows a multilayered (multi-subnetworked) network. The first subnetwork is constructed such that UCS inputs are eliminated or, equivalently, all UCS inputs are set to the same value irrespective of the class of training exemplars. When patches are formed as described herein, the patches will reflect only the similarity of CS patterns, independent of their classification. If the receptive fields are chosen in such a way that each receptive field is but a portion of the complete input pattern, then the patches will record, and respond to, similarities in the portion of the input field to which they are attached, that is similarity of "features" within that portion of the field. Consequently, the output neurons of the first layer 403 transmit not the product of the most similar UCS with the similarity measure, but rather a pair of numbers: the identification of some subset of patches (depending on their associated similarity measure), and, optionally, the similarity measure, as input to the second layer 404.

The second subnetwork of the network has, in this embodiment, an input field large enough to equal the total number of output elements on all the neurons in the subnetwork below, and a number of output elements equal to the number of components in the input UCS. The input to the second subnetwork will consist of the identification of each sufficiently well matched patch of the preceding subnetwork and, optionally, value of the similarity measure for each patch, presented on the input line corresponding to that patch; the classifying UCS is presented to the UCS input of the second subnetwork. The advantages of this two layer (two subnetwork) network include:

1. The first layer generates fewer patches because similar CS inputs do not form different patches. Similar features are sought across classes. This is a particularly significant advantage when the application to which the method is directed contains a large number of classes (such as the identification of 4000 different hand-written Japanese Kanji characters).

2. The second layer, which performs the actual classification function, classifies not on the basis of the entire image or components thereof, but rather on the basis of features clustered by the patches generated in the first layer. Thus, common features among classes can be identified by examination of the first layer clusters and which features group to identify specific classes can be determined by examining the clusters of the second layer.

The size of the receptive field on the second layer may be too large for efficient operation if it is constructed according to the principles outline above. If problems occur, the following remedies may be applied:

1. If temporally mixed training and testing are not required (i.e., in a temporally stationary environment), the first layer can be trained first without training the second layer. Thus, when training of the first layer is complete, the distribution of patches among the first layer output neurons and their numbering is known, as is the similarity measure with respect to the training set. A decision can then be made to limit the connections to the second layer to some subset of the first layer patches with the highest similarity measures across the training set.

2. A preferred, modification consists of using the pruning option disclosed herein. In this implementation, connections from the first layer to the second are pruned on the basis of their variance with respect to the UCS-specific signal. Thus, an appropriate number of unnecessary connections between the layers is removed.

3. Alternatively, budding (as disclosed herein) may be employed to start the development of second layer patches with only those connections reflecting the least variance with respect to the UCS, and adding additional, higher variance connections, as needed to improve classification performance.

Another view of FIG. 14 is that it illustrates the extension of the system shown in FIG. 13 to a multi-subnetworked system wherein there is an input 400 in the first layer (or subnetwork) from conditioned stimuli, and that input is transmitted to a series of patches 402 which, as in the basic layer unit of FIG. 13, connect to output neurons 403. A difference between the multilayered system and the simpler system at the entry layer is that there are either no unconditioned stimuli or that they are all set to the same value so that, in effect, the processing is independent of unconditioned stimuli.

The output of the first subnetwork is used as the input layer of the successive layer (subnetwork). The output 403 of the first layer is the input of the second layer. This input may be transmitted to patch elements 404 of the second layer. However, the patches may be linked to a plurality of output neurons from the first layer 403. Viewing the system from the output neurons of the second subnetwork, there may be signals from a plurality of output neurons in subnetwork 1 to patches connecting to an individual neuron output of subnetwork 2.

This pattern of interconnecting subnetworks may extend for n subnetworks, where n is determined by the particular circumstances of the problem being addressed. Not only can n subnetworks be placed in series, but m of such series networks (each with a different n, if desired) can be placed in parallel, finally converging on the nth (final) output layer, with its associated USC 405.

At the nth subnetwork, input from unconditioned stimuli 405 is also provided in the usual way as shown in the basic network of FIG. 13, i.e., one component of unconditioned stimuli is provided to each patch. The final output of the nth output neurons is shown as 408 in FIG. 14, the final patches as 407. Multi-subnetworked systems may be connected in series and/or parallel.

The present invention advantageously provides a dynamically stable associative learning neural network system that associatively learns both correlations and anti-correlations, that can be configured to classify or restore patterns simply by changing the number of output units, in which the computational effort scales linearly in complexity with the number of connections, and in which neither global nor local feedback connection are required during learning.

As will be apparent to those skilled in the art, various changes and modifications may be made to the illustrated dynamically stable associative learning neural network system of the present invention without departing from the spirit and scope of the invention as determined in the appended claims and their legal equivalents.

The following examples illustrate various applications of the neural network system:

For either fixed or variable method of patch creation, the patch, , P.sup.m, whose similarity, , S.sup.m, is greatest is "activated" and all three parts of the patch (vector, expected UCS and weight, FIG. 13) are modified. The patch vector is modified to increase its resemblance to current CS pattern by calculating a running average of all the CS inputs that are similar to the patch: ##EQU2## where t is the number of patterns that have activated the patch and P.sub.i.sup.m (0)=0. For a new patch, t=1; thus the patch vector for a new patch equals the CS input. As t increases, the effect that a novel CS input pattern has on the patch decreases. Therefore, patch movement eventually ceases for stationary distribution of inputs. The final patch vector is the average of similar valued CS inputs.

The expected value of the UCS, U.sup.m (t), is also a running average of UCS inputs associated with similar valued CS inputs: ##EQU3## where U.sup.m (0)=0. For a new patch, t=1; thus the expected value of the UCS for a new patch equals the UCS input. The weight, W.sup.m, reflects the frequency of utilization of the patch. The weight of the most similar patch is incremented according to learning rules:

where a is the learning increment and W.sup.m (0)=0. The weight of all other patches is decremented according to those same learning rules:

where b is the learning decrement. The weights exhibit a monotonic convergence to their equilibrium value. Furthermore, it follows from equations 1 and 2, respectively, that the patch vector and expected value of the UCS also reach steady state values.

The output of a neuronal element equals the product of S.sup.m, the similarity between the CS and the most similar patch, and U.sup.m, the expected value of the UCS of the most similar patch:

N generally ranges from -0.5 to +0.5. If there is negative correlation between the CS and the patch (S.sup.m <0, a condition that may occur during testing), then the neuronal output has a value of 0. Note that, unlike other networks, the weight is not used in the computation of the output of a neuronal element. The weight is used in patch merging and patch deletion, two mechanisms whose function is to reduce the number of existing patches.

The system incorporates two ad hoc mechanisms, patch merging and patch deletion, designed to reduce the number of patches retained by each neuronal element. These are computational mechanisms whose purpose is to reduce the storage requirements of the network.

Patch merging combines two similar patches into a single patch. Two patches may become similar as a result of two dissimilar patches "moving" toward one another. The similarity between two patches is determined in the same fashion as the similarity between a patch and the CS input: ##EQU4## Two patches are considered similar if S.sup.jk is greater than some patch merging threshold, T.sub.m, and if the UCS associated with the patches are similar (e.g., the difference between the two UCSs is less than half their range). Patches are merged by replacing the two patches with one patch which has

(a) a weighted average of the two patch vectors: ##EQU5## (b) a weighted average of the two UCS values: ##EQU6## (c) and a weight approximating the sum of the frequency of use of the patches. A power law approximately relates the frequency of use (f) to the weight (f=W.sup..alpha., where .alpha. is a function of the learning increment and decrement.) Therefore, the new weight is given by:

The second mechanism, patch deletion, removes patches whose frequency of use is very low. All patches whose weight, W.sup.j, is greater than a patch retention threshold, T.sub.R, are retained; all patches whose weight has decayed (Equation 4) to less than the patch retention threshold, are removed.

This example demonstrates the pattern completion capabilities of the neural network system. Pattern completion is a special case of classification in which the number of input units are equal to the number of output units, and an input/output relationship is defined on a pixel by pixel basis.

A training set consisted of the letter E, A, O, Q, each letter in four different fonts.

Each letter consisted of a 19.times.19 pixel binary array. The receptive field to each of the output neurons was a 13.times.13 pixel subset of the input field.

Training consisted of presenting one exemplar of one of the four letters chosen at random to the CS input, and another random exemplar of the same letter to the UCS. Using this training paradigm repeatedly, the network learned to generalize across fonts.

A testing set was generated by adding multiplicative noise, that is randomly changing bits in the input patterns. Flipping 30 percent of the bits produces patterns with a signal-to-noise ratio of 1.75:1 (note that flipping 50 percent of the bits results in a completely random pattern). The output is not a representation of any one of the four fonts, but rather the generalized characteristics of each letter as learned by the neural network system. In tests where human observers were not shown the neural network system output corresponding to the test set, none could correctly identify more than six of the eight test letters, and most could identify correctly less than four of the eight, yet the network can reconstruct universally recognizable letters from each of the eight inputs.

This example illustrates the use of the neural network system of the present invention to classify segmented, rectified, hand-written digits. It also includes a comparison of the variable size versus the constant size patch creation.

Hand-written ZIP codes were segmented into single digits and scaled to fill a 22.times.16 array. The scaled digits were rotated to all be in approximately the same orientation.

The small set of digits was randomly divided into a training set containing 976 digits and a testing set containing 943 digits. The large set of ZIP code digits was divided into a training set of 2000 digits (200 of each kind) and a testing set of the remaining 8964 digits. Some of the experiments used the 22.times.16 bit-mapped digit. For other experiments, the CS data set was transformed using principal component analysis [Rubner et al., 1990; Hyman et al., 1991] to demonstrate the neural networks system's performance on continuous-valued inputs. For all experiments, the UCS pattern was a 10 bit classification vector in which the nth bit (n=0, . . . 9) was 1 for digit n and all other bits were 0.

A decision rule is required to evaluate the continuous-valued output vector and determine the neural network system's performance. The value 0.5 is added to the output of each neuronal element, to force the range of output values between 0 and 1. Thus, the value of 0.5 results when there is no similarity (S.sup.M =0) between the CS input and a patch. If the value of only one of the output elements was greater than 0.5, the pattern was considered classified by the network, otherwise (i.e., no value over 0.5 or more than one value over 0.5) the pattern was considered un-classified because the output was not similar to any UCS presented to the network during training. The pattern was considered correctly classified if the nth output element was the only element with an output above 0.5 when digit n was presented is the input, otherwise a pattern was classified incorrectly.

The first experiment used the small set of bit-mapped digits and a method of constant size patch creation. For this experiment the neural network system was configured using random receptive field connections. The CS input field was a 22.times.16 array; the UCS input field was a 1.times.10 array and the output field was a 1.times.10 array of neuronal elements. Each output neuronal element was connected to a randomly chosen subset of the inputs. Because of the size of the input field, the CS connections to only a single patch on one output element are shown, and the patch structure is not illustrated. However, as shown in FIG. 13, the inputs are actually to patches on either output element. The number of randomly chosen inputs connected to each output neuronal element is varied to evaluate the effect of the number of connections on performance. The patch vectors are stored as 4 bit approximations to the real value to reduce storage requirements.

The network was trained by presenting each pattern in the training set once (increasing the number of pattern presentations did not change performance.) The order of pattern presentation was random. Each presentation of the CS pattern was accompanied by the presentation of the appropriate UCS pattern. After training, the neural network system was tested on the disjoint set of digits in the testing set. The neural network system's performance variation was measured as a function of several network parameters: (1) number of connections between each output neuronal element and the input field, (2) patch creation criterion value (T.sub.c), (3) patch merging threshold (T.sub.m) and (4) patch retention threshold (T.sub.R). Regression analysis was used to determine which of the parameters most affected each of the performance measures.

The percent correct plotted as a function of patch creation criterion value (T.sub.c) and the patch retention threshold (T.sub.R) showed performance is best for intermediate values of T.sub.c and T.sub.R, but is relatively high for most of the range of values. Except for the case when both T.sub.c and T.sub.R are high simultaneously, percent correct remains within five percent of its maximum value.

The percent of patterns the network is able to classify (percent classified) is a function of To, the number of connections, and the patch merging threshold, T.sub.m. Over most of the range of parameters, performance is relatively constant, although predictably, performance for 150 connections is a few percentage points higher than performance with 75 connections. Only for low values of both T.sub.c and T.sub.m does percent classified drop below ten percent of the maximum value, demonstrating that the network is robust to changes in global parameters.

The number of patches created by the network is a function of T.sub.c, T.sub.R and T.sub.m. As expected, the number of patches increases with increasing T.sub.c and T.sub.m and decreasing T.sub.R. When a more stringent matching requirement between the patch and the CS input is applied (increased T.sub.c), more patches are needed. Similarly, a low T.sub.R implies that even infrequently used patches are retained. There is a low correlation between the number of patches and the performance of the neural network system. As a first order approximation, as the number of patches increases, performance improves; deviations from this general rule are attributed to the decrease in ability to generalize as the number of patches increases.

The best performance on ZIP code digits of a neural network system that creates constant size patches is 96 percent correct. As described in the section on variable size patches, covering the input space more efficiently using variable size patches results in a performance of 98 percent correct.

The second experiment used the small set of preprocessed digits and a method of constant size patch creation to demonstrate the ability of a neural network system to learn, store, and recall associations based on continuous-valued inputs (gray shades). As these experiments demonstrate, preprocessing significantly reduces the computational burden, but not the ultimate performance.

The digits in the training set are preprocessed [Hyman et al., 1991] using the self-organizing network of Rubner and Schulten [1990] that performs principal component analysis (PCA). The PCA network is trained using an equal number of digits of each class, all of which are taken from the training set. After training the PCA preprocessor, each test digit is then preprocessed, and the continuous-valued outputs of the first 20 (out of 352) PCA outputs are chosen to represent each digit as the input to the neural network system. This 94% reduction in the dimensionality of the input patterns is possible because most of the variation of the training set is represented by the first 20 components. Using more than the first 20 outputs does not improve the classification performance of the network.

The architecture and training of a neural network system that learns the preprocessed digits is almost identical to the neural network system that learns bit-mapped digits. The only difference is in the CS input field (one input for each of the 20 outputs from the preprocessor) and that each neuronal element is fully connected to all 20 inputs. Both neural network systems are identical as the UCS input field (a 1.times.10 array) and the output field (a 1.times.10 array of neuronal elements). For both neural network systems, the patch vectors are stored as 4 bit approximations to the real value to reduce storage requirements. The network is trained in exactly the same way as the network that learned the bit-mapped digits. Each pattern in the training set is presented only once and the order of presentation is random. Each presentation of the CS pattern is accompanied by the presentation of the appropriate UCS pattern as described for the earlier experiment. After training, a neural network system is tested on the preprocessed set of digits in the testing set. The output of the network to each input pattern is evaluated using exactly the same rules applied when the network was tested on the bit-mapped digits. As with bit-mapped digits, regression analysis is used to identify which of the parameters most affected each of the performance measures.

The variation in performance as a function of network parameters on the preprocessed inputs is very similar to the variation in performance on the bit-mapped digits. The percent of patterns the network is able to classify (percent classified) is a function of patch creation criterion value (T.sub.c), and patch merging threshold (T.sub.m). For both the bit-mapped digits and the preprocessed digits, performance generally increases as T.sub.c and T.sub.m increase. The percent of preprocessed digits that the network unambiguously, but not necessarily correctly, classified ("percent classified" ) is near 100% (compared to 95% for the case of bit-mapped images) and relatively constant for higher values of T.sub.c and T.sub.m.

The percent correct for the preprocessed digits is a function of T.sub.c and T.sub.R. Percent correct is relatively constant, within five percent of maximum for a large range of T.sub.R and T.sub.c, but decreases when both T.sub.c and T.sub.R take on high values simultaneously. Thus for both bit-mapped and preprocessed digits, percent correct for constant size patch creation is 95%-96% for optimal parameter values. This demonstrates that preprocessing reduces the computational load by decreasing the number of inputs to the classifier, but does not alter the performance of the neural network system as a classifier.

The number of patches created by the network trained on preprocessed inputs is a function of T.sub.c, T.sub.R and T.sub.M. The number of patches created by the network increases with increasing T.sub.c and decreasing T.sub.R. The effect of changes in T.sub.c and T.sub.R on the number of patches is the same whether the network is trained on preprocessed or bit-mapped digits.

The third set of experiments used the larger set of PCA preprocessed digits. Both variable size patch creation and constant size patch creation were evaluated in order to compare and contrast the performance of these two methods of patch creation. As in the previous experiments, only a single presentation of the training set is required to train a neural network system. The performance of the neural network system with respect to the method of patch creation is robust. Percent correct remains within 5 percent of the maximum value over most of the parameter space. An analysis of the number of patches created by the neural network system reveals that variable size patches more efficiently cover the pattern space. Performance on ZIP code digits is higher (97.8% vs. 96.5%) and fewer patches are created when the neural network system is trained using variable size patches.

This example illustrates the use of the neural network system of the present invention to classify hand-printed Japanese Kanji characters.

The data consisted of hand-printed Japanese Kanji characters. A database of 160 exemplars (each written by a different person) of 956 Japanese Kanji characters (ETL8B2) was obtained through the courtesy of Drs. T. Mori and K. Yamamoto of the Electrotechnical Laboratory (ETL), Tsukuba, Japan. For the purpose of testing the neural network system, the first 40 exemplars of each character are designated the training set and the remaining 120 characters the test set. Thus different people wrote the training set and the test set. To reduce the dimensionality of the data the 63.times.64 binary pixel characters are preprocessed using a principal components (PCA) network [Rubner et al., 1990; Hyman et al, 1991] that is trained on each of the 40 exemplars of the 956 characters in the training set.

Results of the performance of the neural network system on preprocessed Kanji as a function of the number of characters and the number of PCA components used to describe each character decreases linearly with the number of different characters and increases with the number of PCA components.

An alternate test of the neural network system is to consider the training set as representing 40 different fonts of printed characters (or trained on the handwriting of the same people, possibly the staff in a particular office, whose handwriting is to be read at a future time) and use the training set as the testing set. For this task, the neural network system was tested on 40 to 320 different Kanji characters, with a data compression near 99%. Under these somewhat artificial conditions, that roughly correspond to reading 40 different fonts of printed text, the performance of the neural network system is constant, ranging between 100% and 99.7% correct identification, with a slowly increasing number of exemplars that the neural network system categorizes as "unknown" as the number of different characters to be recognized increases. In reading fonts, printing variations will introduce multiplicative noise. Because the neural network system is very robust to multiplicative noise, excellent performance on printed Kanji in multiple fonts is expected. It is noteworthy, and indicative of the power, stability, and robustness of the neural network, that close to optimum performance can be obtained on all of the problems described above (and on others) using exactly the same global parameters.

The references listed below are incorporated herein by reference to the extent that they supplement, explain, provide a background for, or teach methodology, techniques, and/or compositions employed herein.

S. D. Hyman, T. P. Vogl, K. T. Blackwell, G. S. Barbour, J. Irvine, D. L. Alkon (1991), Classification of Japanese Kanji using principal component analysis as a preprocessor to an artificial neural network, Proceedings of the IJCNN'91, In Press.

J. Rubner, K. Schulten (1990), Development of feature detectors by self-organization. A network model, Biological Cybernetics 62, 193.