Hopfield Networks

Content-Addressable Memory

A CAM is a system that can take part of a pattern, and produce the most likely match from memory. A CAM for instance would be able to interpret these:

intel__gent 
nueroscience 
War+++loo 
pa$sv0rd 
1,3, ,7, ,1

A CAM system can find an input’s closest match to a set of known patterns. It retrieves data by directly comparing input queries with stored memory locations. Hopfield networks mimic the behavior of CAM in a biologically inspired way using neural networks.

Hopfield Networks

Suppose we have a network of $N$ neurons, each connected to all the others.

• $W_{ij}$ is the connection strength from node $i$ to node $j$. We assume that $W_{ij}=W_{}ji$.

We want this network to converge to the nearest of a set of $M$ targets or inputs.

Each node in the network can be a $-1$ or $1$, such that $x_j\in \{-1,1\},j=1,\dots ,N$.

Suppose each node wants to change its state so that:

$$x_j=\{\begin{array}{ll}-1& \text{if }{\sum }_{j\ne i}{x}_i{W}_{ij}<b_j\\ 1& \text{if }{\sum }_{j\ne i}{x}_i{W}_{ij}\ge -b_j\end{array}$$

If we have a pattern that we would like the network to recall, we could set the weights such that:

• $W_{ij}>0$ between any two nodes in the same state
• $W_{ij}<0$ between any two nodes that are different

So we’ve seen that setting the weights is easy if we have one target. But what if we have a bunch of different targets that we want to encode?

Given $M$ target network states, $\{x^{(1)},\dots ,x^{(m)}\}$, each of length $N$:

$$\begin{array}{rl}X& =\{{\vec{x}}^{(s)}\in \{-1,1{\}}^N|s=1,\dots ,M\}\end{array}$$

where the $i$th component is calculated using the weights and biases as:

$$x_i=\{\begin{array}{ll}-1& \text{if }(\vec{x}W{)}_i+b_i<0\\ 1& \text{if }(\vec{x}W{)}_i+b_i\ge 0\end{array}$$

We then find the weights as:

$$\begin{array}{rl}{W}_{ij}& =\frac{1}{M}\sum _{s=1}^M{x}_i^{(s)}{x}_j^{(s)}i\ne j\\ W_{ii}& =0=\frac{1}{M}\sum _{s=1}^M{x}_i^{(s)}{x}_i^{(s)}-1\end{array}$$

• We call $W_{ij}$ the average co-activation between nodes $i$ and $j$. It is found by running through all the stored patterns and looking at the states of the nodes that the weight connects, and then connecting how many times they are in the same/opposite states and averaging.

Writing this in matrix form, we can write:

$$\begin{array}{rl}W& =\frac{1}{M}\sum _{s=1}^M{x}^{(s)}(x^{(s)}{)}^T-I\end{array}$$

• $x^{(s)}$ is a column vector, and $(x^s{)}^T$ is a row vector.

This method works best if the network states, $\{x^{(1)},\dots ,x^{(m)}\}$ are all mutually orthogonal.

Hopfield Energy

Hopfield recognized a link between these network states and the Ising model in physics.

• Ising model: Lattice of interacting magnetic dipoles, each of which can be “up” or “down”. The state of each dipole depends on its neighbors.

Hopfield energy is a scalar number that we compute for any network state $\vec{x}\in \{-1,1{\}}^N$. The dynamics are defined such that updating neurons makes $E$ decrease, so that the network falls into low-energy states, which correspond to the stored memories/patterns.

Hopfield energy is defined as:

$$\begin{array}{rl}E& =-\frac{1}{2}\sum _{j\ne i}{x}_i{W}_{ij}{x}_j-\sum _j{b}_j{x}_j\\ E& =-\frac{1}{2}{x}^{T}Wx-b^{T}x\end{array}$$

where $W_{ii}=0$.

Intution:

• If $x_i$ and $x_j$ are the same sign, their product is positive. Then, we want $W_{ij}$ to be positive. Since we have $-\frac{1}{2}$ at the front, the whole term will be negative, such that a good state corresponds to low energy.
• The ${\sum }_j{b}_j{x}_j$ term reflects that there is a cost to each node being on/off. If the node is on, it reduces the energy by $b_j$.

To minimize energy, we use gradient descent:

$$\frac{\partial E}{\partial x_j}=-\sum _{i\ne j}{x}_i{W}_{ij}-b_j$$

or

$$\begin{array}{r}{\nabla }_{\vec{x}}E=-\vec{x}W-\overline{b}\\ \\ ⟹{\tau }_x\frac{d\vec{x}}{dt}=\vec{x}W+b\end{array}$$

which is similar to the $(\vec{x}W{)}_i+b_i$ equation we saw earlier.

If $i\ne j$:

$$\frac{\partial E}{\partial W_{ij}}=-x_i{x}_j$$

If $i=j$:

$$\frac{\partial E}{\partial W_{ii}}=-x_i^2=-1$$

As a result, the gradient vector is:

$${\nabla }_{W}E=-{\vec{x}}^T\vec{x}+I_{N\times N}$$

where ${\vec{x}}^T\vec{x}$ is a rank-1 $N\times N$ matrix. We add the identity matrix to the right-hand side, so that the gradient of the diagonal weights is zero, to keep $W_{ii}=0$ for gradient descent.

Over all $M$ targets, we have:

$${\nabla }_{W}E=-\frac{1}{M}\sum _{s=1}^M({\vec{x}}^{(s)}{)}^T{\vec{x}}^{(s)}+I=-\frac{1}{M}{X}^{T}X+I$$

Thus:

$$W\leftarrow W+\kappa \left(\frac{1}{M}{X}^{T}X-I\right)$$

where $X^{T}X$ computes co-activation states between all pairs of neurons.

Because the input patterns $X$ are fixed, the co-activation matrix $\frac{1}{M}{X}^{T}X-I$ remains constant across iterations, so the gradient direction does not change, and repeated updates simply move $W$ linearly towards the steady-state solution, which is proportional to $W^{\ast }=\frac{1}{M}{X}^{T}X-I$.

Example

Let’s say we have $N=4$ neurons and $M=2$ target patterns.

$${\vec{x}}^{(1)}=[-1,1,1,-1],{\vec{x}}^{(2)}=[1,1,-1,-1]$$

Stacking them into the data matrix $X$:

$$X=\left[\begin{array}{cccc}1& -1& 1& -1\\ 1& 1& -1& -1\end{array}\right]$$

Now, we compute the coactivation states between all pairs of neurons:

$$X^{T}X=\left[\begin{array}{cccc}2& 0& 0& -2\\ 0& 2& -2& 0\\ 0& -2& 2& 0\\ -2& 0& 0& 2\end{array}\right]$$

Then:

$$\frac{1}{M}{X}^{T}X=\frac{1}{2}{X}^{T}X=\left[\begin{array}{cccc}1& 0& 0& -1\\ 0& 1& -1& 0\\ 0& -1& 1& 0\\ -1& 0& 0& 1\end{array}\right]$$

Using this to do weight update:

$$W\leftarrow W+\kappa \left(\frac{1}{M}{X}^{T}X-I\right)$$

Let’s start with $W=0$ and $\kappa =1$. Then:

$$W=\frac{1}{M}{X}^{T}X-I=\left[\begin{array}{cccc}0& 0& 0& -1\\ 0& 0& -1& 0\\ 0& -1& 0& 0\\ -1& 0& 0& 0\end{array}\right]$$

and we take biases $\vec{b}=0$.

Now, suppose we have a noisy cue:

$$\vec{x}=[-1,-1,1,-1]$$

• (the first bit should be $1$ for this to match ${\vec{x}}^{(1)}$)

Using the update rule:

$$x_i=\{\begin{array}{ll}-1& \text{if }(\vec{x}W{)}_i+b_i<0\\ 1& \text{if }(\vec{x}W{)}_i+b_i\ge 0\end{array}$$

Note that Hopfield networks are asynchronous, such that only one unit is updated at one time.

We have:

$$(\vec{x}W{)}_1=x_4\cdot W_{41}=(-1)\cdot (-1)=+1$$

Then:

$$h_1=1\ge 0⟶x_1=1$$

So the state is now $\vec{x}=[1,-1,1,-1]$ (the first bit flipped).

For the second one:

$$\begin{array}{rl}(\vec{x}W{)}_2& =x_3\cdot W_{32}=(1)(-1)=-1\\ h_2& =-1<0⟶x_2=-1\end{array}$$

The state stays as $\vec{x}=[1,-1,1,-1]$.

For the third one:

$$\begin{array}{rl}(\vec{x}W{)}_3& =x_2\cdot W_{23}=(-1)(-1)=+1\\ h_3& =1\ge 0⟶x_3=+1\end{array}$$

The state stays as $\hat{x}=[1,-1,1,-1]$.

Finally:

$$\begin{array}{rl}(\vec{x}W{)}_4& =x_1\cdot W_{14}=(1)(-1)=-1\\ h_4& =-1<0⟶x_4=-1\end{array}$$

Thus, after all the updates we have $[1,-1,1,-1]$, matching the input ${\vec{x}}^{(1)}$.