Biol. Cybern:52,141-152(1985)
Biological Cybernetics
9 Springer-Verlag1985
“Neural” Computation of Decisionsin Optimization Problems
Copyright By PowCoder代写 加微信 powcoder
J. J. Hopfield1’2 and D. W. Tank2
1 DivisionsofChemistryandBiology,CaliforniaInstituteofTechnologyP, asadenaC,A91125,USA 2 Departmenot fMolecularBiophysicsA, T&T BellLaboratoriesM, urrayHill, NJ 07974,USA
Abstract. Highly-interconnectednetworks of non- linear analog neurons are shown to be extremely effective in computing. The networks can rapidly provide a collectively-computedsolution (a digital output) to a problem on the basis of analog input information. The problems to be solved must be formulatedin termsofdesiredoptima,oftensubjectto constraints.The generalprinciples involved in con- structingnetworksto solvespecificproblemsare dis- cussed.Resultsofcomputersimulationsofanetwork designedto solvea difficult but well-definedoptimiza- tion problem- the Traveling-SalesmanProblem- are presentedand used to illustrate the computational powerofthenetworks.Goodsolutionsto this problem are collectively computedwithin an elapsedtime of only a few neuraltime constants.The effectivenessof the computationinvolves both the nonlinear analog responseof the neurons and the large connectivity among them. Dedicated networks of biological or microelectronicneurons could provide the compu- tational capabilities describedfor a wide class of problems having combinatorial complexity. The powerandspeednaturallydisplayedbysuchcollective networksmaycontributeto the effectivenessofbiolog- ical information processing.
I Introduction
A large class of logical problems arising from real world situations can be formulated as optimization problems,and thus qualitativelydescribedas a search for the best solution. These problems are found in engineeringand commerce,and in perceptualprob- lems which must be rapidly solved by the nervous systemsofanimals.Well-studiedproblemsfrom com- merceand engineeringinclude: Given a map and the problem of driving betweentwo points, which is the
best route? Given a circuit board on which to put chips,whatisthebestwaytolocatethechipsforagood wiring layout (Kirkpatrick et al., 1983)? Analogous, butonlypartiallycharacterizedproblemsin biological perceptionandroboticsinclude:~Givenamonocular picture,whatis the bestthree-dimensionadl escription of the locations of the objects?Indeed,what are the “objects”?In eachoftheseoptimizationproblems,an attemptcanbemadetoquantifythevaguecriterion “best”by the useofa specificmathematicalfunction to be minimized.
While a costfunctionmaybespecified,realworld data usedto evaluateit is generallynot precise.Also, complex cost functions usually involve somewhat arbitrary weightings and forms of the various contri- butions. From an engineeringviewpoint, thesecom- plications imply that little meaning can be attached to “best”. Often, what is truly desiredis a very good solution,which will be uniquelybestonly for simple tasks.In many situations,a very good answercom- putedon a time scaleshortenoughsothat the solution canbe usedin the choiceofappropriateactionis more iLmportant that a nominally-better “best” solution. This is especiallytrue in the biologicaland robotics tasks of perceptionand pattern recognition,because theseproblemstypically have an immensenumberof variablesand the taskof searchingfor the mathemat- ical optimum of the criterion can often be of consid- erable combinatorial difficulty, and hence time cons uming.
The computationalpowersroutinely usedby ner- vous systemsto solve perceptualproblems must be truly immense,given the massiveamount of sensory data continuouslybeing processed,the inherent dif- ficulty of the recognition tasks to be solved,and the shorttime (msec-secsi)n which answersmustbefound.
1 (PoggioandTorre,1985;Terzopoulos1,984;Ikeuchiand Horn, 1981iJulesz,1971;Marr, 1982;Sebestyn1,962)
Most generalpurposedigital computerswould fail to providethis combinationofpowerandspeed.Oneof the central goals of researchin neuroscienceis to understandhowthebiophysicalpropertiesofneurons and neural organizationcombine to provide such impressivecomputing power and speed.An under- standingof biologicalcomputationmay also lead to solutionsfor relatedproblemsin robotics and data processingusing non-biologicalhardwareand soft- ware.
It is clearfrom studiesin anatomy,neurophysi- ology, and psychophysicsthat part of the answerto how nervous systemsprovide computationalpower and speedis through parallelprocessing.The mam- malian visual systemcomputeselementaryfeature recognitionmassivelyin parallel(Julesz,1981;Ballard et al., 1983).At the level of neural architecture, a n a t o m y a n d n e u r o p h y s i o l o g yh a v e r e v e a l e d t h a t t h e broadcategoryofparallelorganizationis manifestin severaldifferentbut interrelatedforms. Parallelsen- s o r y i n p u t c h a n n e l s ,s u c h a s t h e i n d i v i d u a l r o d s a n d cones in the vertebrateretina, allow rapid remote sensingof the environmentand data transmissionto processingcenters.Likewise, paralleloutputchannels, forexamplein corticocorticalprojectionsin thecortex, connectdifferentprocessingmodules(see,for example Goldman-Rakic,1984).Anothermanifestationofpar-
alMism occursin the largedegreeoffeedbackandin- terconnectivityin the”localcircuitry”ofspecificpro- cessingareas(see,for exampleShepherd,1978).The ideathatthis largedegreeoflocalconnectivitybetween the simple processingunits (neurons)in a specific processingareaofthe nervoussystemis an important contributionto it’s computationapl owerhasledto the studyofthegeneralpropertiesofneuralnetworks2and also several”connectionist”theories in perception (Ballard, in press;Feldmanand Ballard, 1982).The connectionistheoriesemploylogicalnetworksoftwo- state neurons in a digital clocked computational framework to solve model pattern recognition problems.
There is a major feature of neuralorganization which is not included in connectionistmodels but which can act synergisticallywith parallel feedback and connectivityto greatly enhancecomputational power. This feature is that the biological system operatesin a collectiveanalo9mode,with eachneuron summingthe inputs of hundredsor thousandsof othersin orderto determineits gradedoutput.An analogsystemis madepowerfulin computationbyits ability to adjustsimultaneouslyand self-consistently manyinteractingvariables(Poggioand Koch, 1984; Jackson,1960;Huskey and Korn, 1962).Although
2 (Hopfield, 1984;Gelperin et al.,in press;Hopfield, 1982; Hinton and Sejnowski,1983;Arbib, 1975)
veryfast,analogsummationis inevitablylessaccurate than digital summation.This compromiseis not critical, however,in perceptualtasks formulated as optimization problems.The computationalload of rapidly reducing this sensoryinput to the desired “good”solutionis alreadyimmense;inaccuraciesand uncertaintiesare alreadypresentand the computa- tional load is meaninglesslyincreasedby high digital accuracyP. arallelanalogcomputationin a networkof neuronsis thus a natural way to organizea nervous systemto solve optimizationproblems.
In this paperwe quantitativelydemonstratethe c o m p u t a t i o n a lp o w e r a n d s p e e d o f c o l l e c t i v e a n a l o g networksofneuronsin solvingoptimizationproblems rapidly. We demonstratethat evenfor very difficult problems,makinga collectivedecisionis rapid,requir- ing anelapsedtime ofonlya fewcharacteristictimesof the “neurons”comprising the network. This speed, neededfor real-timeprocessingofsensoryinformation by a nervous system,can be provided by collective analog computationalcircuits becauseall of the neuronssimultaneouslyandcontinuouslychangetheir analogstatesin parallel.Whencomparedto modern digital generalpurpose computersconstructedwith conventionalsilicon integratedcircuits (VLSI), the “neural” computationalcircuits we describe have qualitatively different featuresand organization.In VLSI the usemadeofanalogcalculationsin minimal (Mead and Conway, 1980).Each logic gate will typicallyobtaininputsfromtwo orthreeothers,anda huge number of independentbinary decisions are m a d e i n t h e c o u r s e o f a c o m p u t a t i o n .I n c o n t r a s t , e a c h nonlinearneuralprocessor(neuron)in a collective analogcomputationalnetworkgetsinputs from tens or hundredsof others and a collective solution is computedonthebasisofthesimultaneousinteractions of hundredsof devices.
Recognizingthatthenatureofperceptuapl roblems is similarto otheroptimizationproblems( , 1985; Hinton and Sejnowski, 1983; Ter- zopoulos, 1984)and that computing power is best illustratedon a difficult but wellunderstoodproblem, we will showherehow to organizea computational networkofextensivelyinterconnectednonlinearana- log neuronsso that it will solve a well characterized, but non-biological,optimization problem. We have chosen as an illustration the “Traveling-Salesman Problem” (TSP), for which the computationaldif- ficultyhasbeenmuchstudied(Lawleretal.,in press; Gareyand Johnson,1979).The solution to the TSP problem,andindeed,the solutionto manyoptimi- zation problemsis a discreteanswer.However,the neurons in the networks we describe operate in an analog mode. Hence,unlike “connectionist”ap- proachesto solving perceptualproblemsin networks
whichusestrictlytwo-stateneurons,theformulation
ofproblemsto be solvedby an analogcomputational
networkrequiresembeddingwhat seemedto be dis-
creteproblemsin a continuousdecisionspacein which
the neuronalcomputationoperates.We demonstrate
herehowa continuousdecisionspaceandcontinuous
computationcan be relatedto discretecomputation
andwhya continuousspacecanimprovethequalityof
the solutions obtained by highly-interconnected However,like the input impedancecausedby the cell
neuralnetworks.
II Analog ComputationalNetworks
The generalstructure of the analog computational networkswhichcansolveoptimizationproblemsis shownin Fig. lb. Thesenetworkshavethethreemajor formsofparallelorganizationfoundin neuralsystems: parallelinputchannelsp, aralleloutputchannelsa, nda largeamountofinterconnectivitybetweentheneural processingelements.The processingelements,or “neurons”,are modelledas amplifiers in conjunction w i t h f e e d b a c kc i r c u i t s c o m p r i s e d o f w i r e s , r e s i s t o r s a n d capacitorsorganizedso as to modelthe most basic
membranein a biologicalneuron,eachamplifierj has an input resistorQjleadingto a referencegroundand an input capacitorCj. These componentspartially define(seebelow)thetimeconstantsoftheneuronsand provide for integrative analog summation of the synapticinput currentsfrom otherneuronsin the network.In orderto provide for both excitatoryand inhibitory synaptic connections between neurons while usingconventionalelectricalcomponents,each amplifieris giventwo outputs,a normal(+) output and an inverted (-) output. The minimum and maximumoutputsofthenormalamplifieraretakenas 0 a n d 1 , w h i l e t h e i n v e r t e d o u t p u t h a s c o r r e s p o n d i n g valuesof0 and – 1.A synapsebetweentwo neuronsis d e f i n e d b y a c o n d u c t a n c eT u w h i c h c o n n e c t s o n e o f t h e two outputs of amplifierj to the input of amplifier i. This connectionis made with a resistor of value Rij=1/[Tu[. If the synapseis excitatory(Tu>0), this resistor is connectedto the normal (+) output of amplifierj. For an inhibitory synapse(Tu<0), it is connectedto theinverted(-) outputofamplifierj.The m a t r i x Tu d e f i n e s t h e c o n n e c t i v i t ya m o n g t h e n e u r o n s . The netinput currentto anyneuroni (andhencethe input voltage ui) is the sum of the currentsflowing throughthe setofresistorsconnectingits input to the outputs of the other neurons.Thus the normal and invertedoutputforeachneuronallowfortheconstruc- tion of both excitatory and inhibitory connections using normal (positive valued) resistors;biological neuronsdo not requirea normalandinvertedoutput sinceexcitatoryandinhibitorysynapsesaredefinedby useofdifferentreceptor/ionchannelcombinations.As indicatedin Fig. lb, our circuits include an externally suppliedinputcurrentI~foreachneuron.Theseinputs canbeusedto setthegeneralevelofexcitabilityofthe network through constantbiases, which effectively shift the input-outputrelation along the ui axis, or to providedirectparallelinputs to drive specificneurons. Although this "neural" computationalcircuit is de- scribedherein termsofamplifiers,resistors,capacitors, etc.,we haveshown(Hopfield, 1984;Gelperinet al.,in press)thatnetworksofneuronswhoseoutputconsists of action potentials and with connectionsmodelled after biological excitatory and inhibitory synapses couldcomputein a similarfashionto this conventional electronichardware.
-u0 0 +Uo u
~_inputs....~
V amplifier
9resistorinTij network
Fig. la and b. a The input-output relation for the "neurons"or analogamplifiers,b The analogcircuit.The outputofanyneuron canpotentiallybeconnectedto theinputofanyotherneuron. Black circles at intersections representresistive connections (Tq's)betweenoutputsandinputs.Connectionsbetweeninverted outputs and inputs representnegative(inhibitory) connections
Vinverting amplifier
computationalfeaturesof neurons,namelyaxons, dendritic arborization,and synapsesconnectingthe differentneurons.The amplifiershavesigmoidmono- tonicinput-outputrelations,asshownin Fig. la. The function Vj=gj(uj) which characterizesthis input- output relation describes the output voltage of amplifier Vj due to an input voltage uj. The time constantsof the amplifiers are assumednegligible.
The equationofmotiondescribingthe time evo- lution of this circuit is:
minimizesthe function.We interpretthe solutionto the problem from the final stable state. For the problems consideredhere, the solutions are discrete (digital)andthegainis chosenhighenoughsothatin thefinalstablestateeachneuronhasa normal(+) o u t p u t V~ v e r y n e a r 0 o r 1 . T h e s e t o f o u t p u t s t h e n providesa digital answerwhich representsa solution the problem.
Before we considerthe form of a network which solves the TSP, it is instructive to considerhow a simpleroptimizationproblemcanbe solvedby one of these computationalnetworks. Although not inter- preted as an optimization problem at that time, an examplewas actuallyprovidedin earlierwork (Hop- field, 1984)whereit wasshownhowthe samecompu- tationalcircuit describedabovecould,with the proper choiceofconnectionstrengths,operateasa Content- Addressable-Memory(CAM). The normaloutputsof the N amplifers comprising the memory circuit - which for that applicationwere allowedthe range - 1 to + 1,insteadofthe 0 to 1rangedescribedabove- werealways- 1or 1in thehigh-gainlimit andthestate oftheseoutputsrepresenteda binaryword in memory. A memory,storedin the network by an appropriate choice of Tq elements,could be "retrieved"by setting theoutputsoftheamplifiersin thebinarypatternofthe recallkeyandthenallowingthe systemto convergeto a stablestate.This stablestatewasinterpretedasthe memoryword evokedby the key.Eachrecall"solved" the"problem"ofwhichofthestoredbinarywordswas "closest"to the key word.
We canunderstandhow to constructan appropri- ate computationalcircuit for the CAM, considered nowasasimpleexampleofanoptimizationproblem, by examiningthe E function.SinceE [Eq. (4)] deter- minesthe stablestatesofthe network,thenifwe wish the stable statesto be a particular set of m memory statesV~s={1,2, ...,m}we mustchoosethe connec- tion strengths(Tq)andtheinputbiascurrents(Ii) ofthe network suchthat Eq. (4) is a local minima when the systemisin eachoneofthestatesVLSinceEq.(4)is quadratica guessmight be:
E=- 1/2 ~ (Vs-V)2. (5) S=I
If the statevectorV(with componentsV~)is a random vector,theneachparenthesizedtermis verysmall.But ifVis oneofthememoriesV*,thenoneterminthesum is N z. Hence the network has an energyminima of depthapproximately- 1/2Nz ateachofthe assigned memories.Equation(5) can be rewritten in the stan- dardform [Eq.(4)] ofthe energyfunctionifallIi=0 and the T~jelementsare definedas:
6(duJdt)= Z T jVs-u,/Ri+Ii
Riis a parallelcombinationofr andthe R~j: N
= g j ( u j )
1/R~=I/o,+ Z 1/R,. (2) j=l
For simplicity, in the presentwork we have always chosengi=g, Ri=R,and C~= C, independentof i, though this is not necessary.Dividing by C and redefiningTq/CandI]C asTqandIi, theequationsof motion become:
dud&=-uJz + Z TijVj+[i (3) j=l
z=RC Vs= g (us ) .
For an "initial-value" problem, in which the input voltagesoftheneuronsaregivenvaluesu~attime t= 0, this equationof motion provides a full descriptionof thetimeevolutionofthestateofthecircuit.Integration of this equation in a digital computer allows any hypotheticalnetworkto be simulated.
In earlierwork (Hopfield, 1984)it was shownthat theequationsofmotionfora networkwith symmetric connections(Tis= Tii) alwaysleadto a convergenceto stable states, in which the outputs of all neurons remainconstant.Also,whenthewidthoftheamplifier gaincurveinFig.la isnarrow- thehigh-gainlimit- the stablestatesofa networkcomprisedofN neurons are the localminima ofthe quantity
e = - 1/2 E Z TqV~Vs- Z Vd~.
i=1 j=l i=l
The statespaceover which the circuit operatesis the interior ofthe N-dimensionalhypercubedefinedby V~= 0 or 1.However,in the high-gainlimit, the minima only occur at corners of this space.Hence the stable statesofthe networkcorrespondto thoselocationsin the discretespaceconsistingof the 2Ncornersof this hypercubewhich minimize [Eq. (4)].
Networks of neuronswith this basicorganization canbe usedto computesolutionsto specificoptimi- zation problems by first choosingconnectivities(Tq) andinputbiascurrents(I~)whichappropriatelyrepre- sentthe function to be minimized.The methodsin- volvedin this selectionare discussedbelow.Following thisconstructionor"programming"ofthenetwork,an initial setof input voltagesui are provided,and the analogsystemthen convergesto a stablestatewhich
This equationfor T~sis the storagealgorithmpresented earlier(Hopfield,1984)exceptforanadditiveconstant. It is derived above by thinking of the CAM as an optimizationproblem and then making a judicious choiceofthe representationofthe energyfunctionin termsofthe desiredmemories.In a practicalapplica- tion of a CAM, for examplea networkusedto store telephonenumbers,in addition to the storageal- gorithmabove,atransformationusedto codethereal- world informationinto the binaryword memorydata representationis required.Taken together,the data transformationandthealgorithmfortheT~scanbe c o n s i d e r e dt h e " m a p " o f t h i s p r o b l e m o n t o t h e a n a l o g computationalnetwork.
The basicpropertyof the analogcomputational networks describedabove is the minimization of E. The CAM exampleillustratesthat throughthe con- struction of an appropriateenergyfunction for the circuit,anda strategyforinterpretingthestateofthe outputsas a solution,a simple optimizationproblem maybe"mapped"ontothenetwork.We haverecently foundthatthesecircuitscanalsorapidlysolvedifficult optimizationproblemswhich haveboth contraintsin the possible solutions and also combinatorialcom- plexity.A networkdesignedto solvethe "Traveling- Saleman Problem" illustrates this computational power.
III The TSP Problem
The "Traveling-SalesmanProblem"(TSP)is a classic of difficult optimization. It is simple to describe, mathematicallywell characterizedand makesa good vehiclefordescribingtheusedofneuralanalogcompu- tationalnetworksto solve difficult optimizationprob- lems.A setofn cities A,B,C.... have(pairwise)dis- tances of separationdAB,dac..... dBc.... The prob- lem is to find a closedtour which visits eachcity once, returns to the starting city, and has a short (or minimum) total path length. A tour defines some sequenceB,F,E,G,..., W in which the cities are visited,andthetotalpathlengthd ofthis touris
d=d~v+dFE+... +dwB.
The actual best solution to a TSP problem is computationally very hard - the problem is np-complete(GareyandJohnson,1979),andthe time requiredto solvethis problemon anygivenc
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com