Introduction to Neural NetworksU. Minn. Psy 5038"Energy" and neural networksDiscrete Hopfield networkConstraint satisfaction problemsIntroductionThis notebook introduces the discrete two-state Hopfield net with an application to a constraint satisfaction problem--the random dot stereogram. In the next notebook, we will study the generalization to graded or continuous valued neural responses, which will lead us to stochastic models of neural networks.Discrete two-state Hopfield network‡BackgroundWe've seen how learning can be characterized by gradient descent on an error function e(W), in weight-space. We are going to study analogous dynamics for recall behavior, rather than learning.Hopfield (1982) showed that for certain networks composed of threshold logic units, the state vector evolves through time in such as way as to decrease the value of a function called an "energy function". Here we are holding the weights fixed, and following the value of the energy function as the neural activities evolve through time. This function is associated with energy because the mathematics in some cases is identical to that describing the evolution of physical systems with declining free energy. The Ising model of ferromagnetism developed in the 1920's is, as Hopfield pointed out, isomorphic to the discrete Hopfield net. We will study Hopfield's network in this notebook.One can define a function that depends on a neural state vector in almost any way one would like, e.g. E(V), where V is vector whose elements are the neural activites at time t. Suppose we could specify E(V) in such a way that small values of E are "good", and large values are "bad". In other words low values of E(V) tell us when the network is getting close to a right answer--as in the search game "you're getting warmer", but with the energy metaphor reversed. Then starting with this function, we could compute the time derivative of E(V) and set it equal to the gradient of E with respect to V. Then as we did for an error function over weight space, we could define a rule for updating V (but now in state space) over time such that we descend E(V) in the direction of the steepest gradient at each time step, and thus we'd go from "bad" to "better" to "good" solutions. But this gradient derived rule would not necessarily correspond to any reasonable neural network model. In two influential papers, Hopfield went the opposite direction. He started off with a model of neural network connectivity using the threshold logic units (TLU) for neurons, and posited an energy function for network activity. That is, he showed that with certain restrictions, state vectors for TLU networks descended this energy function as time progressed. The state vectors don't necessarily proceed in the direction of steepest descent, but they don't go up the energy surface. One reason this is useful, is that it shows that these networks converge to a stable state, and thus have well-defined properties for computation.Viewing neural computation in terms of motion over an "energy landscape" provides some useful intuitions. For example, think of memories as consisting of a set of stable points in state space of the neural system--i.e. local minima in which changing the state vector in any direction would only increase energy. Other points on the landscape could represent input patterns or partial data that associated with these memories. Retrieval is a process in which an initial point in state space migrates towards a stable point representing a memory. With this metaphor, mental life may be like moving from one (quasi) stable state to the next. Hopfield's paper dealt with one aspect: a theory of moving towards a single state and staying there. Hopfield showed conditions under which networks converge to pre-stored memories.We've already mentioned the relationship of these notions to physics. There is also a large body of mathematics called dynamical systems for which Hopfield nets are special cases. We've already seen an example of a simple linear dynamical system in the limulus equations with recurrent inhibition. In the language of dynamical systems, the energy function is called a Lyapunov function. A useful goal in dynamical system theory is to find a Lyapunov function for a given update rule (i.e. a set of differential equations). The stable states are called "attractors".Hopfield nets can be used to solve various classes of problems. We've already mentioned memory and recall. Hopfield nets can be used for error correction, as content addressable memories (as in linear autoassociative recall in the reconstruc-tion of missing information), and constraint satisfaction.Consider the latter case. Energy can be thought of as a measure of constraint satisfaction--when all the constraints are satisfied, the energy is lowest. Energy represents the cumulative tension between competing and cooperating constraints. In this case, one usually wants to find the absolute least global energy. In contrast, for memory applications, we want to find local minima in the energy. Below, we give an example of a Hopfield net which tries to simultaneously satisfy several constraints to solve a random dot stereogram. In this case, if E(V) ends up in a local minimum, that is usually not a good solution. Later we will learn ways to get out of local minimum for constraint satisfaction problems.2 Lect_18_HopfieldDis.nbHopfield nets can be used to solve various classes of problems. We've already mentioned memory and recall. Hopfield nets can be used for error correction, as content addressable memories (as in linear autoassociative recall in the reconstruc-tion of missing information), and constraint satisfaction.Consider the latter case. Energy can be thought of as a measure of constraint satisfaction--when all the constraints are satisfied, the energy is lowest. Energy represents the cumulative tension between competing and cooperating constraints. In this case, one usually wants to find the absolute least global energy. In contrast, for memory applications, we want to find local minima in the energy. Below, we give an example of a Hopfield net which tries to simultaneously satisfy several constraints to solve a random dot stereogram. In this case, if E(V) ends up in a local minimum, that is usually not a good solution. Later we will learn ways to get out of local minimum for constraint satisfaction problems.‡Basic structureThe (discrete) Hopfield network structure