Optimization network for the decomposition of signals

A network comprising analog amplifiers with a resistive interconnection matrix that connects each amplifier output to the input of all other amplifiers. The connections embodied in the matrix are achieved with conductances whose values are computed in accordance with the set of decomposition functions for which the solution is sought. In addition to the specified connectivity implemented. Further included is a second matrix that connects externally applied voltages to the amplifier inputs via resistors whose values are also computed in accordance with the set of decomposition functions for which the solution is sought. Still further and in accordance with another aspect of the invention, means are included for varying the amplifier gains from an initial low value to an ultimately high value in the process of arriving at a solution to an applied problem.

BACKGROUND OF THE INVENTION 
This relates to apparatus for parallel processing of signals, and in 
particular, to apparatus for highly parallel computation leading to the 
decomposition of signals into component signals. 
Digital computers are ubiquitous and quite powerful, but that is not to say 
that digital computers do not exhibit certain limitations in problem 
solving. Many practical problems, in fact, take such an enormous amount of 
computation that a solution in real time is not possible. Such 
difficulties are experienced, for example, in programs that aim to select 
from memory the information that best satisfies known characteristics or 
descriptors (which may be referred to as "clues") when the clues are 
insufficient to completely define the information. Pattern recognition is 
another example of where the computational problem is just too great for 
digital computers. 
Most artisans either suffer the limitations of general purpose digital 
computers or develop special purpose digital computers to solve their 
particular problems more efficiently. 
In a copending application entitled "Electronic Network For Collective 
Decision Based On Large Number Of Connections Between Signals", by J. J. 
Hopfield, a generalized circuit was disclosed having N amplifiers of high 
gain and an N.times.N interconnection matrix having N input conductors and 
N output conductors. The amplifiers exhibit a sigmoid input-output 
relation, with a minimum and a maximum possible output which can be 
thought of as a "0" and a "1". Each input conductor of the matrix is 
connected to the input of a separate one of the amplifiers, and each 
amplifier has its output terminals (positive and negative) connected to a 
separate one of the matrix output conductors. Each amplifier has in 
addition an input capacitance C.sub.i and an input resistance .rho..sub.i. 
Within the interconnection matrix each input conductor i is connected to 
an output conductor j through a resistor R.sub.i,j. In the disclosed 
circuit each amplifier satisfies the circuit equation of motion: 
##EQU1## 
u.sub.i is the input voltage to amplifier i, V.sub.j is the output voltage 
of an amplifier j, and I.sub.i is the current into the input terminal of 
amplifier i (e.g., from a high impedance source). 
The motion of the disclosed circuit (as specified by the above equation) 
drives the network to one of a set of predetermined stable states which 
presents an output pattern of binary 1's and 0's (since the amplifiers 
have a high gain). 
When used for accessing information in a associative memory, the input 
voltages of amplifiers i are set in correspondence with the individual 
bits of the input word for each clue (descriptor) known for the 
information desired. Alternatively, a constant current I.sub.i can be 
applied to each input in proportion to the confidence that the voltage 
V.sub.i should be at "1" in the final answer. Once started, the amplifiers 
drive to a stable state, producing at the output a unique word that 
represents the information itself, which could include the address of a 
location in another memory which may then yield a block of words that 
comprise the information defined by the descriptor used to store and 
retrieve the unique word from the associative memory. 
When used for problem solutions, all inputs may be set approximately equal, 
such as to zero, or held in a pattern representing input information, and 
the output pattern of bits "1" and "0" define the solution. In either 
application, problem solving or information retrieval, the output in 
binary form is a very good solution to the given problem. 
Although the disclosed circuit quickly and efficiently reaches a stable 
solution state, it is not guaranteed that the optimal solution to a given 
problem is obtained. This is because the topology of the solution space is 
very rough, with many local minima, and therefore many good solutions are 
similar to the optimal solution. In difficult robotics and biological 
problems of recognition and perception, very good solutions that are 
rapidly calculated may provide sufficient information to be of practical 
use, but in some applications it is the exact, or best, solution that is 
desired. 
It is an object of this invention to employ a network of analog processors 
in connection with decomposition processes. 
SUMMARY OF THE INVENTION 
These and other objects are achieved with a highly interconnected analog 
network that is constructed to implement a specific decomposition process. 
The network comprises analog amplifiers that are connected with a 
resistive interconnection matrix which, like the prior art network, 
connects each amplifier output to the input of all other amplifiers. The 
connections embodied in the matrix are achieved with conductances whose 
values are computed in accordance with the set of decomposition functions 
for which the solution is sought. In addition to the specified 
connectivity implemented with the interconnection matrix, the analog 
network of this invention includes a second matrix that connects 
externally applied voltages to the amplifier inputs via resistors whose 
values are also computed in accordance with the set of decomposition 
functions for which the solution is sought. In accordance with another 
aspect of our invention, our circuit is caused to reach its solution by a 
process of simulated annealing, whereby the amplifier gains are initially 
set at low values and then slowly increased to their ultimate high value. 
This process inhibits the circuit from being directed to a local minima.

DETAILED DESCRIPTION 
FIG. 1 is a schematic diagram of a computational multi-processor network 
disclosed in the aforementioned co-pending application. It comprises 
amplifiers 10 which provide positive gain and, optionally, negative gain, 
whose inputs and outputs are interconnected via interconnection network 
20. A physical embodiment of an amplifier would necessarily include some 
impedance at the input that is primarily resistive and capacitive. It is 
represented in FIG. 1 by resistors 11 (.rho..sub.i) and capacitors 12 
(C.sub.i). Each node in interconnection matrix 20 is represented by a 
heavy black dot 21 and it comprises a resistor R.sub.ij which connects a 
path of matrix 20 that is connected to an output of amplifier i, e.g. path 
22, with a path of matrix 20 that is connected to an input of amplifier j, 
e.g. path 23. In addition, the FIG. 1 circuit allows for externally 
applied currents to be fed into paths 23 that connect to inputs of 
amplifiers 10. Current I.sub.i represents the input current to path 23 
that connects to amplifier i. The voltage V.sub.i represents the output 
voltage of amplifier i. 
The equation of motion describing the time evolution of the FIG. 1 circuit 
is: 
##EQU2## 
where u.sub.i is the input voltage of amplifier i, g.sub.i is the transfer 
function of amplifier i, i.e., 
##EQU3## 
It has been shown in the aforementioned co-pending application that when 
the equation 
##EQU4## 
is considered, and when the terms T.sub.ij and T.sub.ji are equal and the 
gain of the amplifiers is very large, then the time derivative of equation 
(3) reduces to 
##EQU5## 
The parenthetical expression in equation (3) is equal to the right hand 
side of equation (1). That means that the change (with time) of input 
voltage at amplifier i multiplied by the change (with time) of the output 
voltage at amplifier i, summed over all the amplifiers, is equal to the 
dE/dt of equation (3), and is equal to: 
EQU dE/dt=-.SIGMA.C.sub.i [dg.sub.i.sup.-1 (V.sub.i)/dV.sub.i 
](dV.sub.i/dt).sup.2. (4) 
Since each of the terms in equation (4) non-negative, dE/dt is negative, 
and approaches 0 (stability) when dV.sub.i /dt approaches 0 for all i. 
The above analysis means that a presented problem that meets the conditions 
set forth for the above equations can be solved by the circuit of FIG. 1 
when the values of T.sub.ij and the input currents I.sub.i are 
appropriately selected, an initials set of the amplifier input voltages is 
provided, and the analog system is allowed some time to converge on a 
stable state. 
One class of problems that can conveniently be solved in this manner is the 
class of decomposition problems where it is sought to represent an input 
signal with a "best fit" set of other non-orthogonal signals. One example 
is the A/D conversion problem. Another example is the decomposition of a 
complex signal (as represented by a sequence of voltage samples) into a 
set of preselected functions. 
To more clearly describe our invention, the following describes the 
approach taken in accordance with the principles of our invention to solve 
the A/D conversion problem. Thereafter, the concepts described are 
expanded to cover the entire class of decomposition problems. 
In connection with the A/D conversion process it is known that conversion 
of a signal from analog representation to digital representation means 
that an analog signal x is approximately equal to the weighted sum of the 
developed digital signals {V.sub.1, V.sub.2, . . . V.sub.N } that are 
supposed to represent x. That is, a signal x', which is an approximation 
of the signal x can be expressed as: 
##EQU6## 
One conventional measure of "goodness" of x' is the square of the 
difference between the signal x and the signal x'. That concept is 
embodied in the following equation: 
##EQU7## 
Equation (6) states that the optimum value of x' results in a minimized 
value of E. Expanding equation (6) and rearranging it results in a form 
similar to that of equation (1), plus a constant, and that indicates that 
an A/D converter might indeed be implemented with a circuit not unlike 
that of FIG. 1. 
Unfortunately, the minima of the function defined by equation (6) do not 
necessarily lie near enough to 0 and 1 to be identified as the digital 
logic levels that an A/D converter must develop. In accordance with the 
principles of this invention, we circumvent this problem by adding an 
additional term to the energy function of equation (6). We chose the term 
##EQU8## 
because it favors digital representation since it reduces to zero when all 
of the V.sub.i terms are restricted to 0 or to 1. When equation (7) is 
combined with equation (6) and rearranged, the equation 
##EQU9## 
results, which is also in the form of equation (1), if we identify the 
connection matrix elements and the input currents as: 
EQU T.sub.ij =-2.sup.(i+j) 
and 
EQU I.sub.i =(-2.sup.(2i-1) +2.sup.i x). 
FIG. 2 depicts a four bit A/D converter circuit in accordance with the 
principles of our invention that is constructed with a connection matrix 
that satisfies equation (8). It comprises inverting amplifiers 10 having 
input lines 22 and output lines 23, a connection matrix 20 which connects 
lines 23 to lines 22 via nodes 21, and a connection matrix 30 which 
connects a reference voltage -V (e.g., -1 volt) on line 31, and an input 
signal x on line 32. Both signals -V and x communicate with lines 22 via 
nodes 33. 
In accordance with the specification of equation (8), each T.sub.ij element 
takes the value 2.sup.i+j (except where i=j--where T.sub.ij does not 
exist). These are the connection strengths depicted in FIG. 2. Also in 
accordance with the specification of equation (8), each input current 
I.sub.i takes on the value -2.sup.2i-1 +2.sup.i x. Matrix 30 realizes 
these currents via the depicted connection strengths which represent 
conductances of specified value. 
As indicated earlier, the A/D conversion process is presented herein for 
illustrative purposes only and that, in accordance with the principles of 
our invention, many decomposition processes can be achieved with a circuit 
like the one of FIG. 2. 
If, for example, .epsilon..sub.k represents a set of basic functions (such 
as, for example, gaussian functions) which span the signal space x (signal 
samples), then the function 
##EQU10## 
describes a network which has an energy minimum when the "best fit" 
digital combination of the basic functions are selected (with V.sub.i =1) 
to describe the signal. The term .epsilon..sub.k 
.multidot..epsilon..sub.k, by the way, means the dot products of the 
signal .epsilon..sub.k with itself. Equation (9) can be expanded and 
rearranged to assume the form 
##EQU11## 
and equation (10) is in the form of equation (1), plus a constant. That 
is, as with equation (8), the T.sub.ij terms and I.sub.i terms can be 
defined to make equation (10) appear identical to equation (1), thereby 
yielding a correspondence between the elements in the equation and the 
physical parameters of the FIG. 2 network. Specifically for equation (10), 
EQU T.sub.ij =-(.epsilon..sub.i .multidot..epsilon..sub.j) where i.noteq.j (11) 
and 
EQU I.sub.i =[(x.multidot..epsilon..sub.i -1/2(.epsilon..sub.i 
.multidot..epsilon..sub.i)]. (12) 
An example may be in order. 
Consider the problem of decomposing a time sequence of analog signals which 
result from the linear summation of temporally disjoint gaussian pulses of 
differing widths. A typical summed signal is shown in FIG. 3 and the 
different gaussian pulses of which it is comprised are shown in FIG. 4. 
The decomposition process must determine this particular subset of all the 
possible basis functions that, when added together, recreate the signal of 
FIG. 3. As indicated by dots 100 on the curve of FIG. 3, a plurality of 
samples are available from the signal of FIG. 3, and those samples 
comprise the analog data x.sub.i, where 1=1,2, . . . , N. The basis set, 
defining all possible "pulses" are the gaussian functions of the form 
EQU .epsilon..sub..sigma.t =e.sup.-[(i-t)/.sigma.].spsp.2 (13) 
where the width parameter, .sigma., takes on a finite number of values, 
while the peak position of the pulse t, can be at any one of the N 
instances where the samples of the FIG. 3 signal are taken. Since the 
basis set is specified by the two parameters, width and peak position, the 
amplifiers used in the decomposition network can be conveniently indexed 
by the double set of indices, .sigma.,t. In describing the decomposition, 
each of these basis functions will have digital coefficient 
(V.sub..sigma.t) which corresponds to the output of an amplifier in the 
network and which represents the presence or absence of this function in 
the signal to be decomposed. That is, a V.sub.20,10 =1, for example, means 
that a gaussian function with a peak at the time of sample 20 and a width 
of 10 is present in the solution set. 
With the above in mind, the energy function which describes an analog 
computational network that will solve this particular decomposition 
problem is: 
##EQU12## 
with the basis function as defined in equation 12. This expression defines 
a set of connection strengths T.sub..sigma.t,.sigma.'t' and input currents 
I.sub..sigma.t, with: 
##EQU13## 
A computational network for implementing the above processing is 
essentially identical to the network shown in FIG. 2. The only difference 
is that instead of a single input signal x, there is a plurality of input 
signal samples x.sub.i, and each is connected to a line 32 which, through 
connection matrix 30, feeds currents to amplifiers 10 in accordance with 
equation (16). This circuit is shown in its general form in FIG. 5, with 
lines 32-1 through 32-4 comprising the plurality of input lines, to each 
of which a signal sample is connected and through which each signal sample 
is connected to all amplifiers. 
As demonstrated, our circuit seeks a minimum stable state, but it has a 
number of other stable states which constitute local minima. This 
condition is depicted in FIG. 6 by curve 100, where the lowest stable 
state occurs at circuit state 54, at point 104, and local minima exist at 
states 51, 52, 53, 55, 56, 57, 58, and 59, corresponding to points 101-109 
(exclusive of 104) on curve 100, respectively. 
We have discovered that the gain of amplifiers 10 in our circuit exhibits 
control over the shape of curve 100 in a manner that is not dissimilar to 
the process of annealing. As in some spin glass problems where the 
effective field description followed continuously from high temperatures 
to lower temperatures is expected to lead to a state near the 
thermodynamic ground state, in our circuits we start with low amplifier 
gains and slowly increase the gains to their ultimate levels. This yields 
better computational results. 
This behavior can heuristically be understood by observing that curve 110 
in FIG, 6, which corresponds to the circuit energy function when the gain 
is low, has discontinuities in the slope of the curve at points 
corresponding to states 51 through 59 (corners), but the curve is still 
monotonically increasing or decreasing on either side of point 114 which 
is the minimum point of curve 110. The other corners in the curve are not 
local minima and, therefore, when we set the gains at a low value our 
circuit will not come to rest at those points but would move to point 114. 
When the gain is increased, our circuit easily and quickly settles at the 
minimum point, i.e., point 104. 
Beginning a computation in a low gain state initializes the circuit. In a 
situation with changing inputs, as for example the A to D converter 
measuring a fluctuating voltage, the best operation of the circuit may 
require re-initializing the gain for each new decision. 
The gain control feature, which can be implemented in a conventional 
manner, is illustrated in FIG. 5 by a line 40 that is connected to a gain 
control point on all amplifiers 10. Changing the voltage on line 10 
changes the gain of amplifiers 10, yielding the desired "annealing" action 
or re-initializing.