Consider the following scenario. You are at a party when you hear a short snippet of your favorite song.

Almost instantly, your brain recalls the lyrics of that song and many related memories, such as attending a recent concert featuring that artist.

It seems very natural and unimpressive. After all, people can recall information all the time. However, if you think about it, this problem is computationally non-trivial.

Let's put ourselves in the shoes of evolution and try to come up with an algorithm for the brain to solve it.

The first approach that comes to mind is to actually store some kind of a database of all the songs you have heard a sufficient number of times, along with related information, like the title and lyrics.

When an audio fragment of an unknown song is received, we can scan through all the songs in our database, find the one that has a close enough match, and retrieve its lyrics.

However, the search space of every sound I've ever heard is astronomically large, and it's even larger when considering every single memory you have formed since childhood.

Performing an exhaustive search would be simply impossible. Yet, you seem to have no problem instantly recognizing familiar stimuli and finding associations between them.

So how does the brain accomplish this so quickly? In this video, we will lay the foundation for a new paradigm of information storage and retrieval, which is more in line with biology, and actually build one of the simpler models of this process known as Hopfield networks, developed by John Hopfield in 1982, who laid an important groundwork for many ideas in both neuroscience and machine learning.

If you are interested, stay tuned. Just to reiterate, we need a way to somehow query what we know and find associations between existing memories and new inputs.

without explicitly checking individual entries for a match, which seems like an impossible problem. However, we can draw insights from a seemingly unrelated field of molecular biology and in particular, a concept known as Levinthal's paradox of protein folding.

As you might know, proteins are long chains of amino acids that fold into specific 3-dimensional structures which determine their function.

The number of possible structural configurations a protein can take, considering all the different ways you can arrange the atoms of an amino acid chain in 3-dimensional space, is absolutely enormous.

Given the number of possibilities, it seems like it would take an astronomical amount of time for a protein to search through all the possible structures to find its correct folded state.

In fact, there are computations showing that even if the protein samples its different conformations at a nanosecond scale, it would still require more time than the age of the universe to arrive at the correct configuration.

Yet, in reality, proteins fold into their native structures in a matter of milliseconds.

So how do they accomplish this? When I first heard this paradox in high school, it seemed to me like an ill-posed question.

After all, the protein molecule is not a computer, so it doesn't do any sort of search. It just folds into the most stable and favorable configuration according to physical laws.

This is similar to how when you throw a ball, the ball doesn't search through all the possible trajectories to select the optimal parabolic one.

It simply follows that path, because... well, physics works this way. But how can we think about this folding into a favorable configuration?

Favorable for what, exactly? Let's introduce the concept of energy, as it will come in handy in future videos as well.

If you think back to your high school physics days, you may recall something along the lines of "energy is a quantitative property that describes the state of a system." "namely the capacity to do work or cause change." Energy can be stored in a variety of different forms, and for the case of proteins, we will be interested in potential energy stored in the interactions between the atoms in the protein chain.

Each possible configuration of the protein chain has a specific potential energy level determined by the sum of all of these atomic interactions.

In other words, we can assign a positive number to each state equal to its energy, which is a function in some very high-dimensional space where different dimensions correspond to degrees of freedom you need to uniquely describe a configuration, for example, all possible dihedral angles of peptide bonds.

Let's abstractly visualize it as having just two dimensions.

Then the energy function can be thought of as a surface where each point on it represents a possible protein configuration and the height of the point represents the potential energy of that configuration.

This is what we are going to refer to as "energy landscape." For a protein, it could be a complex, rugged surface with many peaks and valleys.

Now, here's the key point: a protein molecule, like any physical system, tends to minimize its potential energy guided by the second law of thermodynamics.

It will naturally seek out the configuration that has the lowest possible energy level, as this represents the optimal arrangement of its atoms, and this in fact corresponds to the native, correctly folded state.

When a protein is folding, it is essentially rolling downhill on the energy landscape following the steepest path towards the valley.

This is why proteins can fold so quickly. They don't need to search through all possible configurations.

They simply follow the natural tendency of physical systems to minimize their potential energy. The protein's folding process is guided by the shape of the energy landscape, which in turn, is determined by the interaction between its atoms, and the descent along the surface is essentially driven by the underlying physical process of energy minimization.

Now, the core idea is to achieve something similar for the case of associative memory. Suppose we have a system that can encode information in its states and each configuration has a specific potential energy determined by the interaction between the states.

Then we need to first somehow sculpt the underlying energy landscape so that memories or state patterns we want to store correspond to local minima, these wells in the energy surface.

Second, we need something that would play the role of the second law of thermodynamics and would drive the changes in the states directing the system towards the nearest local minimum.

Once these two things are achieved, retrieving a memory that is most similar to the input pattern is done by configuring the system to encode the input pattern initially and then let it run to the equilibrium, descending into the energy well from which we can read out the stored memory.

So let's get into building it. Let's consider a set of neurons which we can think of as abstract units that can be in one of two possible states, plus one or minus one.

This is a simplified analogy of how nerve cells in the brain encode information through patterns of firing.

They either generate an electrical impulse at a given point in time or remain silent. We'll focus on the fully connected network where each neuron has connections to every other neuron.

These connections have weights associated with them, real numbers that signify the strength of coupling between the corresponding pair of neurons.

For a pair of units i and j, we denote the connection weight between them as w-ij.

and the states of neurons themselves as x-i and x-j. In the brain, connections between neurons or synapses have a well-defined direction.

A pair of neurons is connected asymmetrically, meaning that the synapse from neuron A to neuron B is physiologically separate from the synapse that connects B to A if that one exists at all, and so they can have different weights.

While we could generalize a Hopfield network to account for asymmetric connections, it would introduce complications and potentially unstable behavior.

For simplicity, here we will stick to the original formulation of the Hopfield network, which assumes symmetric weights.

In other words, neurons i and j are connected by the same weight in both directions. Now that we have a set of neurons symmetrically linked with each other through weighted connections, let's explore what these weighted connections represent.

If w-ij is greater than zero, the connection is said to be excitatory and favors the alignment between the two neurons.

We can think of each connection as being happy or unhappy depending on the states of its neurons. For example, if w-ij is a large positive number, it means that neurons i and j are closely coupled and one excites the other.

In this case, when one neuron is active, the other tends to be active as well, and when one is silent, the other one is more likely to be silent.

These configurations, where both x-i and x-j are either one or minus one, agree with the connection weight.

However, if we observe, for example, that x-i is equal to one and x-j is equal to minus one, it conflicts with the excitatory nature of the connection, making such a configuration less likely.

Conversely, when w-ij is negative, the connection promotes misalignment between the weights.

This alignment between the signs can be expressed more concisely using the product x-i times x-j.

This product will be positive when both neurons have the same sign and negative when they have different signs. By multiplying this product further by the connection weight, we obtain an expression for the happiness of that connection.

For a positive W-ij, happiness will be positive when the product of the two states is positive.

But this is just one edge. We can extend this idea and compute the happiness of the entire network as a whole by summing this quantity across all edges.

The larger that number is, the more overall agreement there is between connection weights and pairwise states of neurons. Ultimately, we will search for a set of weights that maximize this quantity, and maximizing happiness is equivalent to minimizing it with a minus sign, which you can think of as the measure of overall conflict between the actual configuration of states and what's favored by the connection weights.

This total conflict between the weights and the pairwise states is exactly what we are going to define to be the energy of the system.

As we discussed previously, we want the Hopfield network to be able to gradually evolve towards energy minima. But looking closely at the formula, we can see that the energy value depends both on the states and the weights.

So, there are a lot of things the system can tweak to change it.

What exactly is getting adjusted? As we will see further, there are essentially two modes of network updates that nicely map to the two aspects of associative memory, namely adjusting the weights corresponds to shaping the energy landscape, defining which configurations are stable by digging energy wells around them.

This is the act of "learning" when we are writing new memories into the network.

Once the weights are fixed, tweaking the states of neurons to bring them into greater agreement with the weights corresponds to descending along the energy surface.

This is the act of "inference" when we are recalling the memory that is at the bottom of the energy well which is nearest to the configuration of the input pattern.

Let's take a look at inference first. Suppose for a second, someone has already set the weights W and hands us the backbone of the network (the neurons themselves with all the connection weights).

However, the exact configuration of states (which neurons are active and which are silent) is unknown.

The question then becomes, "How do we find the state pattern that would minimize the total energy?" As we discussed, simply checking all possible states is not an option.

So, we will start with some initial state, which could be either a partial or a noisy version of one of the memories, or a random configuration altogether.

Once the initial condition is set, we will iteratively try to lower the energy value by focusing on updating one neuron at a time.

Let's denote the neuron we're currently considering as neuron i. We will calculate the total weighted input to it from all other neurons in the network.

This input, which we'll denote as h-i, is the sum of the states of all other neurons multiplied by their respective connection weights.

If h-i is positive, it means that the weighted sum of the other neurons' states is in favor of neuron i being in the plus one state.

Conversely, if h-i is negative, it suggests that neuron i should be in the minus one state to minimize the conflict with the other neurons.

So, we will update the state of neuron i based on the sign of h-i. Notice that this update is guaranteed to decrease the energy of the network because from the two candidate states, we are selecting the more energetically favorable one.

You can think of this as a kind of a voting process.

Each neuron looks at the states of all other neurons, weighted by the strength of their connections, and decides whether to be active or silent based on the majority vote.

We'll go through this process for each neuron in the network one by one, chosen in random order, updating their states based on the input from all other neurons.

Once we've updated all neurons, we will have completed one iteration of the network inference and decreased the system's energy by a little bit.

We'll keep repeating this process, doing these sweeps through all neurons, updating them one at a time based on the current configuration.

As we do this, the network will gradually evolve towards a configuration that minimizes the overall energy. At some point, however, we will reach a configuration where flipping any neuron would lead to an increase in energy, so no further adjustments would be necessary.

At that point, the network has converged to a stable configuration where each neuron state agrees with the majority vote. This stable configuration represents a local minimum in the energy landscape.

Now you might be wondering, is the network guaranteed to reach such a stable configuration? Could we possibly stumble into a particularly unlucky set of states and get stuck in a never-ending loop of flipping neurons back and forth?

In other words, is such iterative flipping of one neuron at a time equivalent to doing a descent along the energy surface?

This is where we come back to the point about symmetric weights. It turns out that there is a mathematical proof that I am not going to cover here, stating that as long as your weights are symmetric, this simple majority vote single neuron update rule is guaranteed to eventually converge to a stable configuration if you do it enough times.

To restate it, the Hopfield network can settle into different local minima based on its initial conditions.

These local minima in the energy landscape correspond to distinct memories stored in the network. When we initialize the network with a pattern, that is similar to one of these memories in some way and let it evolve, it will fall into the nearest local minimum, effectively recalling the complete stored memory, thus performing pattern completion or noise correction.

But so far, we haven't talked about how we come up with this set of connection weights that encode specific memories in the first place.

So, let's explore the learning process. Before we move to storing several memories, let's consider memorizing a single pattern of states.

That means the network would have a single global minimum, one energy well, and would converge to the same pattern every time, no matter where you initialize it.

While it has little practical use, it provides a nice starting point to describe the learning procedure. Let's denote the template pattern that we'd like to store as "psi", which is a vector packing the states of all neurons, and "psi-i" will denote the 'i'th component, the "psi" state of the 'i'th neuron encoding the memory, while x-i refers to the state of the 'i'th neuron in the network in general, which could be tweaked.

Revisiting our definition of energy, we want to set w-ij so that this quantity would be at its minimal value for the memory pattern.

If we plug x-i equal to "psi-i", we get the equation for the energy of the reference pattern as a function of weights, which we want to turn into a global minimum.

Notice that we don't really care about the absolute value of that energy as long as the energy of the desired memory pattern is less than the energy of any other configuration.

Now, intuitively, the lowest possible energy is obtained when all the connection weights fully align with the state pairs. But when we have just a single pattern, this is very easy to do.

All we need is to set the weight, w-ij, to be the product of the corresponding pair of states in the memory pattern.

This way, every connection is satisfied, and the energy of the network when it's in the state "csi" becomes the negative of the total number of edges.

When the network is in the state "csi", any single flip of a neuron would increase the energy, thus making it a stable state.

I want to reiterate a crucial point here. If we want to come up with a set of weights that would dig an energy well around some pattern, then all we need to know are the pairwise relationships between states in that pattern.

If the two neurons are active together in the source memory, strengthening the connection between them lowers the Hopfield energy of that memory, effectively storing it in the weights for associative recall.

A Brain-Inspired Algorithm For Memory

Scripts