 |
Description  |
|
|
BACKGROUND OF THE INVENTION
A neural network is generally an electronic system (usually implemented in
software but may be a combination of hardware and software) for modeling
or simulating the brain. All neural networks can be completely and
uniquely specified by describing the four attributes of architecture,
propagation rules/equations, activation rules/equations and learning
rules/equations.
The architecture attribute specifies the organization of neurons or nodes
(the fundamental processing element or unit of a neural network) into
clusters, clusters into layers, and layers into the overall neural
network. For many neural networks, clusters are not used; hence, the
neurons are organized directly into layers. In addition, layers may be
arranged in a hierarchy. To that end, the architecture attribute also
describes the "permitted" flow of information or signals within the neural
network by specifying actual (or rules for) physical (specific) and
broadcast (non-specific) connectivity paths between layers, clusters,
and/or neurons (nodes).
Propagation rules/equations provide a detailed description, usually
mathematical, of information/signal flow for every permitted physical and
broadcast connectivity path specified in the architecture. This includes
initial conditions and evolution over time.
Activation rules/equations provide a detailed description, usually
mathematical, of how each neuron specified in the architecture processes
its information (signals) to produce output information (signals). This
includes initial conditions and evolution over time. In a so called
"winner take all" activation, for a given set of inputs to the network
neurons, one and only one neuron outputs a logical one and all other
neurons output a zero. In a "many-two-many" activation, several of the
network neurons generate a non-zero output.
Learning rules/equations provide a detailed description, usually
mathematical, of how each "persistent memory" in the network persists
and/or changes over time. "Persistent memories" (commonly called weights
or synapses) are those variables used in the propagation rules/equations
or activation rules/equations, whose values must be retained for proper
functioning of the neural network. This includes specification of all
initial conditions for these variables.
Through learning, a neural network is trained so that application of a
vector or set of inputs produces the desired (or at least consistent) set
of outputs. Both output sets as well as input sets are referred to as
vectors. Learning is usually accomplished by sequentially applying input
vectors, while adjusting network weights according to the learning
rules/equations. During learning, the network weights gradually converge
to values that enable each input vector to produce the desired output
vector.
Learning or training a neural network is said to be either "supervised" or
"unsupervised". In supervised learning, an external "teacher" evaluates
the behavior of the network and directs weight definitions accordingly.
This is typically implemented by each input vector being paired with a
target vector representing the desired output vector. Each pair of input
vector and target vector is called a training pair. An input vector is
applied, an output vector of the network is calculated and compared to the
corresponding target vector, and the difference (error) is fed back
through the network. As a result of this feedback, weights are changed
according to the learning rules/equations which generally minimize the
error. A sequence of such training pairs forms a training set. Each
training pair (i.e., the vectors thereof) is applied to the neural network
in sequence. The weights are adjusted for each applied vector until the
error for the entire training set is below a threshold.
In unsupervised learning, there is no teacher, i.e., there are no target
vectors and hence no comparison to predetermined outputs. Instead, the
training set consists solely of input vectors. The learning
rules/equations modify network weights (i.e., the network self-organizes)
to produce output vectors that are consistent. Specifically, application
of one of the training vectors produces the same output vector as
application of an input vector sufficiently similar to the training
vector. To that end, the learning process or training process extracts the
statistical properties of the training set and groups similar input
vectors into classes. Applying a vector from a given class to the network
input will produce a specific output vector.
SUMMARY OF THE INVENTION
Two goals of many-layered, hierarchical, self-organizing neural networks
are (i) unsupervised hierarchical clustering/categorization; and (ii)
enhanced performance over two and three layer neural networks. Two less
obvious but equally important goals are (iii) resource efficiency leading
to greater generalization and/or storage capacity; and (iv) exploitation
of potential connectivity schemes between layers within the hierarchy to
achieve:
spatiotemporal feature extraction/abstraction by using time delayed
connectivity schemes,
the ability to "mix" primordial spatiotemporal features with abstract
spatiotemporal features by using feed forward and/or feed back
connectivity schemes (that may skip one or more adjacent layers in the
hierarchy), and
practical, many layered, self-organizing systems by exploiting random
connectivity schemes (in lieu of full connectivity between layers).
The present invention provides a neural network that achieves the foregoing
goals. In particular, the present invention provides a neural network
formed of self-organizing, analog field layers (SOAFL) which learn
many-to-many (as opposed to winner-take-all) analog spatiotemporal
mappings. Each SOAFL is modular and mathematically self-contained,
allowing arbitrary (fully or random, and delayed or decayed) connectivity
between layers. Any number of SOAFLs can be combined, via user-specified
connectivity schemes, to create many layered, self-organizing hierarchical
neural networks that address specific problems. Thus the neural network of
the present invention is hierarchical, allowing unlimited layers for
spatiotemporal feature extraction/abstraction. Additional advantages of
the present invention neural network over networks of prior art will
become apparent by the following discussion.
In a preferred embodiment of the present invention, an unsupervised pattern
categorization system employs a plurality of input nodes, a plurality of
output nodes and modifying means, all arranged in a working layer. A
presentation field presents input signals defining an input pattern to the
input nodes. The input nodes are coupled, either fully or non-fully, to
the presentation field to receive the input signals. Each input node
categories patterns with respect to a plurality of categories. For each
input signal received by an input node, the input node generates a net
signal indicating similarity between the input pattern and patterns
categorized by the input node. To accomplish this, for each input signal
received by a input node, the input node has two adaptive long term memory
weights. The long term memory weights encode the plurality of patterns
categorized by the input node. In turn, the net signal is generated as a
function of the long term memory weights and input signals to the input
node.
The plurality of output nodes includes one output node for each input node.
To that end, a different input node is connected to a different output
node and each output node receives the net signal from the respective
input node. In response to the received net signal, each output node
selects a category of the corresponding input node. As a result, the
plurality of output nodes provide a mapping between plural parts of the
input pattern and plural categories. Each output node provides a short
term memory output signal indicative of category selection.
The modifying means dynamically modifies category selections of the output
nodes in a non-linear fashion such that sum of the output signals from the
output nodes is within a predefined range. Upon the sum of output signals
being within the predefined range, the output nodes provide categorization
of the input pattern from the mapping between plural parts of the input
pattern and plural categories of the input nodes. Preferably, the
predefined range is a real number from 0 to the number of input nodes,
non-inclusive.
In particular, the modifying means modulates the input nodes by
broadcasting a modulation signal from a modulation node to the input
nodes. In response to the modulation signal, each input node adapts the
respective long term memory weights from respective initial values to
respective final values. The final values are a function of the initial
values, the modulation signal, and the output signal from the output
nodes. The final values are determined as exact analytical values, as
opposed to iterative approximations.
According to one aspect of the present invention for each input node, one
of the long term memory weights of the input node controls generalization
of spatiotemporal parts of input patterns (i.e., unsupervised feature
learning). The other long term memory weight of the input node controls
strength of input signals to the input node (i.e., self-organization of
connectivity). In particular, strength of input signals to an input node
is indicated both as a degree of connectivity from the presentation field
to the input node, and as a shaping factor generalization of
spatiotemporal parts of the input pattern. Preferably the degree of
connectivity is in the range 0 to 1 inclusive. Zero indicates absence of
connection between the presentation field and the input node, and one
indicates relative strength between the presentation field and the input
node.
The output signals may be binary values generated by a STEP function.
Homeostasis occurs when the sum of the binary values equals a predefined
value. This results in a finite mapping, which may be many-to-many or
winner-take-all mapping depending on the predefined value. The choice for
the predefined number of 1 results in winner-take-all mapping. The
processing time to reach homeostasis is independent of both the predefined
value and the size of the input field.
In a particular preferred embodiment, an analog data processing system is
used to find the H highest-valued numbers from a set of N numbers. The set
of numbers is presented to a neural network or analog circuit as a set of
signals, each signal representing the magnitude of a respective number
from the set of numbers. Each signal is presented to a node on the neural
network. The node determines an output signal indicative of the relative
magnitude of the number within the set of numbers. The output signal from
each node is a binary value (i.e., either 0 or 1) obtained from a STEP
function. The output signals are processed to homeostasis. At
hemoeostasis, the sum of the output signals converge to H and the H nodes
having an output signal of 1 indicate the H highest-valued numbers.
BRIEF DESCRIPTION OF THE DRAWINGS
The foregoing and other objects, features and advantages of the invention
will be apparent from the following more particular description of
preferred embodiments of the invention, as illustrated in the accompanying
drawings in which like reference characters refer to the same parts
throughout the different views. The drawings are not necessarily to scale,
emphasis instead being placed upon illustrating the principles of the
invention.
FIG. 1 is a block diagram of a network employing self-organizing analog
field layers of the present invention.
FIGS. 2a and 2b illustrates a circuit for implementing each self-organizing
analog field layer of the network of FIG. 1.
FIGS. 3a-3i illustrate similarity metrics utilized in neural networks.
FIG. 4 is a graphic illustration depicting the modulation process within
the layer of FIG. 2.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
Referring to FIG. 1, a computer system embodying a neural network of the
present invention is generally shown at 11. The computer system employs a
host processor 13 in which the operation of a neural network 15 are
executed. Briefly, an input source such as on-line data from a workstation
terminal, a sensor system, stored data from memory, and the like provides
input to the computer system 11 at 17. The input is preprocessed by I/O
processing 19 which queues and/or formats the input data as needed. The
preprocessed input data is then transmitted to host processor 13 which
processes the data through neural network 15. In particular, neural
network 15 maps the input data to an output pattern and generates output
for either memory storage 21 or display through an I/O device, e.g., a
workstation display monitor, a printer, and the like. In the latter case
the output data is formatted through I/O processing 23 and transmitted
accordingly for display at a monitor or printing at a printer and the
like. The computer system according to the invention is useful in
applications including, but not limited to, speech recognition, language
recognition, character recognition, word recognition, user identification,
financial predictions, and market segmentation analysis.
In more particular terms, neural network 15 maps an analog input pattern to
an analog output pattern as illustrated in FIGS. 2a-2b and described next.
Referring to FIG. 2a, an analog input pattern is received by neural
network 15 at distribution nodes 25. Distribution nodes 25 are connected
to a first layer or field 29 of self-organizing nodes 27. Distribution
nodes 25 are connected to nodes 27 in a manner such that each input node
25 provides input to each node 27. This is called "fully connected,"
although arbitrary connectivity is also allowed as discussed below. In
response to this input, layer 29 of nodes 27 generates an output with
contributions from plural nodes 27. That is, layer 29 provides a
many-to-many mapping from the input pattern of distribution nodes 25 to
the output of nodes 27a-27n.
The output pattern is transmitted to a succeeding layer 31 of
self-organizing nodes 33 across transmission lines 35. Layer 31 similarly
maps the received input pattern (i.e., output pattern of first layer 29)
in a many-to-many fashion and produces an output pattern which
subsequently serves as input to another layer, and so on. One or more such
layers, like layer 29, are employed in a hierarchical or sequential
arrangement to form neural network 15. Transmission lines 35 between
layers may follow various connectivity schemes and in particular follow
user specified connectivity schemes to create a many layered hierarchical
neural network that addresses specific problems. Such connectivity schemes
are within the purview of one skilled in the art and include fully
connected, fully nonreflexive, random connectivity and/or receptive field
connectivity schemes.
A single layer such as first layer 29, is detailed in FIG. 2b. Each such
layer 29 is a self-organizing analog field layer to which the present
invention is directed. It is understood that the succeeding layers 31 of
FIG. 2a have similar architecture and defining equations as layer 29.
Layer 29 is N nodes wide and contains 2N+2 working nodes. Included in the
2N+2 working nodes are N nodes which form input column 39, N nodes which
form output column 41, inhibition node 43 and modulation node 45. Each of
these working nodes receives on input a signal having the value indicated
in the left hand third of the node, and generates a short term memory
output signal value indicated in the right hand third of the node.
Indicated in the central area of each of the working nodes are internal
long term memory values where applicable.
A receptive field 47 provides input data to each input column node j. The
portion of receptive field 47 that provides input to an input column node
j is denoted R.sub.j. The receptive field 47 may be of arbitrary size such
that each R.sub.j includes any number of nodes of receptive field 47. The
size of receptive field 47 is strictly a function of the connectivity
schemes used in the hierarchy of layer 29 and succeeding layers 31.
Because layer 29 has N receptive field inputs (one for each input column
node) and N activation outputs (one from each output column node), the N
node wide layer 29 may be treated as if it were a conventional neural
network layer with N neurons/nodes in it. Hence, an input pattern to layer
29 at time t is defined by the set of vectors I(t)={S.sub.j (t);j=1=N}.
S.sub.ij is then the input signal to input column node j from the ith node
in receptive field 47. S.sub.j is the total input from receptive field 47
to input column node j, the nodes producing signal S.sub.j defining
receptive field portion R.sub.j. Receptive field 47 may be a short term
memory serving as an input field. Processing of I(t) depends on the mode
of operation of layer 29. In training mode, a single input pattern
presentation to layer 29 lasts x PAML cycles, where PAML refers to
Propagate, Activate, Modulate and Learn equations/rules.
The Propagate equation/rules are as follows. A similarity metric equation
is given by
##EQU1##
where function RAND chooses a random number between the given arguments,
and
0.ltoreq..omega..sub.1 .ltoreq.0.5. (1h)
A vigilance equation is given by
##EQU2##
The Activate rules and equations are given by
##EQU3##
The Modulate rules and equations are as follows. The definition of
homeostasis is given by
(1-.alpha.)H.ltoreq.f.sup.all .ltoreq.(1+.alpha.)H (7a)
where
0<H<N (7b)
and
0<.alpha.<1. (7c)
Modulation node activation is given by
X(-1)=0,.epsilon..sub.M (-1)=.epsilon..sub.M (0) (8a)
where
##EQU4##
If homeostasis:
##EQU5##
If not homeostasis:
##EQU6##
The Learn rules and equations are as given by
##EQU7##
where the STEP function is as defined in Equation 6b;
##EQU8##
It is recognized that differential Equation 9a can be solved simultaneously
to yield an equality equation instead of a differential equation. Solving
the equation simultaneously speeds up the implementation of these
equations by orders of magnitude to produce a more theoretically correct
result. This occurs because equality equations implement faster than
iterative equations, and the simultaneous solution gives an exact
analytical answer rather than an approximate answer produced by the
iterative equations. It has been found that simultaneously solving the
equation improves performance by a factor of 50-1000 times. The resulting
equality equation is given by
##EQU9##
where .omega..sup.i is the initial value of .omega., and
.omega..sup.f is the final value of .omega..
An additional Learn equation is given by
##EQU10##
As discussed above regarding Equation 9a, differential Equation 10a can be
solved simultaneously to yield an equality equation. The resulting
equality equation is given by
##EQU11##
where .sigma..sup.i is the initial value of .sigma., and
.sigma..sup.f is the final value of .sigma..
Additional Learn equations are given by
##EQU12##
where function <z> is a time average of z. In addition,
##EQU13##
As discussed above regarding Equations 9a and 10a, Equations 11a and 11b
can be solved simultaneously to speed up processing to make the
implementation more theoretically correct. The resulting equality
equations are:
##EQU14##
where .eta..sup.i and .xi..sup.i are initial values, and
.eta..sup.f and .xi..sup.f are final values.
Referring back to FIG. 2b, an input pattern presentation takes one time
unit by definition, therefore each PAML cycle lasts 1/x time units. The
total number of input patterns presented to layer 29 in training mode is
denoted by .tau.. Training therefore takes .tau. time units. There is no
concept of "fast" or "slow" learning; .tau. represents a critical window
for self-organization much the same as is exhibited in the afferent
working nodes of early perceptual systems such as that of Knudsen. See
"The Role of Auditory Experience in the Development and Maintenance of
Sound Localization," by E. I. Knudsen, Trends in Neuroscience, 7, 1984,
pages 326-330.
The larger the time window, i.e., the more data one has to train on, the
more likely the training set, and associated layer 29
learning/generalization, will characterize the performance set providing
better results. Continuous and/or incremental learning after .tau. time
units is possible.
In performance mode, an input pattern is presented to layer 29 for as many
PAM (Propogate, Activate, Modulate) cycles as it takes to modulate the
layer 29 to homeostasis described below. It is when layer 29 is in
homeostasis that output column node activations (output in short term
memory) are "meaningful".
To achieve multi-layered, hierarchal self-organizing neural networks, each
layer 29 in the hierarchy must be able to produce and learn, unsupervised
(i.e., without a teacher), a "meaningful", many-to-many, analog mapping
from input space I(t) to output space f(y.sub.j):j=1 to N. This is in
contrast to popular unsupervised learning neural network architectures
that utilize many-to-one ("or winner take all") competitive mechanisms to
obtain their mappings without a teacher. This is also in contrast to
popular supervised learning neural network architectures which can learn
many-to-many analog mappings with a teacher because the teacher provides
detailed error analysis of the mapping, which is ultimately used in the
learning mechanism to gradually correct the errors and enhance the mapping
over the training period. In the present invention, good many-to-many
analog mappings are those that result in homeostasis. Homeostasis is
defined as the condition that exists when the sum of all output column
node activations, f.sup.all (Equation 6a), is within some homeostatics set
points (Equations 7a, 7b, 7c).
To that end, for any input pattern, I(t), N output column node activations,
f(y.sub.j), will be produced that sum to f.sup.all. If f.sup.all is
outside of homeostasis, the modulation node 45 detects this and rapidly
modulates layer 29 to homeostasis as described later. In homeostasis,
there exists many output column nodes with varying analog activation
values contributing to f.sup.all. Hence, a many-to-many analog mapping,
without a teacher is produced. Setting H in Equations 7a and 7b depends on
the hierarchy and problem domain.
The foregoing processing of input pattern I(t) is accomplished in the
preferred embodiment as follows. Referring to Equation 1a and FIG. 2b, the
input from receptive field 47 (and in particular from R.sub.j)) to input
column node j is net'.sub.j which is referred to as a similarity metric.
The similarity metric, net'.sub.j, reflects how well the input pattern
from receptive field 47 to input column node j, namely s.sub.j, compares
to or matches prior experience as embodied in the connections between
receptive field nodes i (where i=1 to .PSI..sub.j the size of R.sub.j) and
input column node j. In the present invention layer 29, two adaptive long
term memory weights .sigma..sub.ij and .omega..sub.ij are required per
connection. Topological self-organization is governed by .sigma..sub.ij.
Unsupervised feature learning is governed by .omega..sub.ij. Because the
number of receptive field 47 nodes connected to input column node j (i.e.,
the effective receptive field size, .PSI..sub.j, with respect to input
column node j) can be different from node to node in input column 39.
Equations 1e and 1f impose a "law of conservation of synaptic strengths"
on the initial values of .sigma..sub.ij. This allows the similarity metric
to be "fair" across different size receptive field inputs to nodes j in
input column 39.
FIGS. 3a-3i compare the present invention layer 29 similarity metric to
other known neural network metrics and statistical metrics. The shaded
area about a feature vector .omega..sub.j illustrates the decision volume
of the given similarity metric. FIGS. 3a-3d and 3g illustrate similarity
metrics of prior art while FIGS. 3e, 3f, 3h and 3i illustrate similarity
metrics of the present invention. It is noted that the similarity metric
of FIGS. 3a-3d do not depend on two adaptive long term memory weights
(.sigma. and .omega.) as in the present invention and the metric of FIG.
3g is extremely difficult to implement in a neural network.
Briefly, FIG. 3a illustrates a decision volume formed by an inner product
of feature vector .omega..sub.j and receptive field input s.sub.j. FIG. 3b
illustrates a decision volume formed by the inner product of vectors
.omega..sub.j and s.sub.j normalized. FIG. 3c illustrates a decision
volume formed by the inner product of feature vector .omega..sub.j
normalized and input s.sub.j normalized. FIG. 3d illustrates a decision
volume formed by a Euclidean similarity metric. FIG. 3g illustrates a
similarity metric from statistics.
FIGS. 3e and 3h illustrate a similarity metric of the present invention
layer 29 with equal, non-zero self-organization weights along the x and y
dimension (i.e., .sigma..sub.xj =.sigma..sub.yj .noteq.0). This results in
a decision volume (shaded area) that resembles the Euclidean similarity
metric shown in FIG. 3d. FIGS. 3f and 3i illustrate an alternative
similarity metric of the present invention layer 29 with a "don't care"
learning portion (for example along the y axis) incorporated in the
decision volume. "Don't care" usage and its incorporation in the
competitive and unsupervised learning/clustering process is a unique and
extremely powerful property of the present invention. Greater details
about long term memory and "don't care" learning are presented later.
However it is clear from Equation 1a and the architecture of layer 29
illustrated in FIG. 2b, that if .sigma..sub.ij goes to zero via learning,
the physical connection containing .sigma..sub.ij appears to atrophy.
Hence topological self-organization is governed by .sigma..sub.ij. Node
and connection atrophication is a prevalent phenomenon during early brain
development and critical windows of self-organization.
Referring back to FIG. 2b, every input column node j transforms its
received similarity metric, net'.sub.j, into another similarity metric
net.sub.j, according to Equation 2a. In Equation 2a the vigilance term,
.GAMMA., controls the discrimination/clustering potential of layer 29.
In a preferred embodiment per Equation 2a, vigilance effectively defines
the decision volumes discussed above and depicted in FIGS. 3e-3f. This can
be explained more easily by dropping .epsilon. in Equation 2a and
rewriting it as
##EQU15##
where <net'.sub.j >=.xi..sub.j /.eta..sub.j is a time-averaged similarity
metric. Equations A1 and 11a-b show how <net'.sub.j > learns a weighted,
time-average of the similarity metrics contributing to a nodes competitive
winning performance. Per Equation A1, one can see that if net'.sub.j
exceeds the time-averaged similarity metric for node j, its value is
passed directly to the corresponding output column node j (i.e., net.sub.j
=net'.sub.j e.sup.0 -net'.sub.j). However, if net'.sub.j is less than
<net'.sub.j >, and exponential fall off (governed by the ramping adaptive
vigilance term .eta..sub.j (t).GAMMA. and degree of mismatch) is applied
to the similarity metric net'.sub.j to obtain a smaller similarity metric,
net.sub.j, used by the output column nodes for competition and ultimate
output representation in homeostasis. This fall off has an effect of
defining an absolute decision volume (e.g., defined by e.sup.-1) about the
similarity metric as shown in FIGS. 3e-3 i. Actually, though e.sup.-z is a
"soft" delimiter, it allows outliers with extremely poor mismatches to
compete if and only if all other matches in layer 29 are relatively poor
and modulation is driving f.sup.all up to achieve homeostasis.
This absolute/relative phenomena is critically important to handle the
following duality during training without a teacher:
An "apparent" outlier is presented early in training but will eventually
become (or help develop) a cluster centroid. In this case, the appearance
of being an outlier is more strongly influenced by the random weight
initialization scheme which caused the poor mismatches than the statistics
of the training set. Both Equation A1 and modulation to homeostasis force
nodes with the smallest, in a relative sense, ramping adaptive vigilances,
.eta..sub.j (t).GAMMA., to activate and eventually learn pertinent
features associated with the non-outlier input pattern. This forces the
active and meaningful participation of all weight vectors, .omega..sub.j,
in the learning process independent of weight initialization or problem
domain.
An "actual" outlier is presented late in training and should not be learned
by layer 29. In this case, both Equation A1 and the drive to homeostasis
tend to "spread" activation across output column nodes thereby diluting
node activations f(y.sub.j) and associated learning rates according to
Equations 9a-10b and especially 9c. In addition, a single poor
contribution to the .eta..sub.j and .xi..sub.j learning equations
(Equations 11a-b) cannot effect <net'.sub.j > late in training. It should
also be noted that the effects of actual outliers presented early in
training tend to be washed away by the learning/generalization/clusteri | | |
