Hopfield Nets | Haobin Tan

Hopfield Nets

Binary Hopfield Nets

Single layer of processing units
Each unit $i$ has an activity value or “state” $u\_i$
- Binary: $-1$ or $1$
- Denoted as $+$ and $–$ respectively
Example

Processing units fully interconnected
Weights from unit $j$ to unit $i$ : $T\_{ij}$
No unit has a connection with itself
$\forall i : \qquad T\_{ii} = 0$
Weights between a pair of units are symmetric
$T\_{ji} = T\_{ij}$
- Symmetric weights lead to the fact that the network will converge (relax in stable state)
Example

Unit vector:

U = (+1, -1, -1, +1)^T

Weight matrix:

T=\left(\begin{array}{cccc} T\_{11} & T\_{12} & T\_{13} & T\_{14} \\\\ T\_{21} & T\_{22} & T\_{23} & T\_{24} \\\\ T\_{31} & T\_{32} & T\_{33} & T\_{34} \\\\ T\_{41} & T\_{42} & T\_{43} & T\_{44} \end{array}\right) = \left(\begin{array}{cccc} 0 & -1 & -1 & +1 \\\\ -1 & 0 & +1 & -1 \\\\ -1 & +1 & 0 & -1 \\\\ +1 & -1 & -1 & 0 \end{array}\right)

u\_i = \operatorname{sign}(\sum\_{j} T\_{ji} u\_j) = \begin{cases} +1 & \text{if }\sum\_{j} T\_{ji} u\_j \geq 0 \\\\ -1 & \text {otherwise } \end{cases}

Network state is initialized in the beginning
Update
- Asynchronous: Update one unit at a time
- Synchronous: Update all nodes in parallel
Continue updating until the network state does not change anymore

$> u\_4 = \operatorname{sign}(+1 \cdot (-1) + (-1) \cdot 1 + (-1) \cdot 1) = \operatorname{sign}(-3) = -1 >$
So the new state of unit 4 is $-$

Could be sequentially
Random order (Hopfield networks)
- Same average update rate
- Advantages in implementation
- Advantages in function (equiprobable stable states)
Randomized asynchronous updating is a closer match to the biological neuronal nets

Assign a numerical value to each possible state of the system (Lyapunov Function)
Corresponds to the “energy” of the net
$\begin{aligned} E &= -\frac{1}{2} \sum\_{j} \sum\_{i \neq j} u\_{i} T\_{j i} u\_{j} \\\\ &= -\frac{1}{2}U^T TU \end{aligned}$

Each updating step leads to lower or same energy in the net.

Let’s say only unit $j$ is updated at a time. Energy changes only for unit $j$ is

E\_{j}=-\frac{1}{2} \sum\_{i \neq j} u\_{i}T\_{j i} u\_{j}

Given a change in state, the difference in Energy $E$ is

\begin{aligned} \Delta E\_{j}&=E\_{j\_{n e w}}-E\_{j\_{o l d}} \\\\ &=-\frac{1}{2} \Delta u\_{j} \sum\_{i \neq j} u\_{j} T\_{j i} \end{aligned}

\Delta u\_{j}=u\_{j\_{n e w}}-u\_{j\_{o l d}}

Change from $-1$ to $1$ :
$\Delta u\_{j}=2, \Sigma T\_{j i} u\_{i} \geq 0 \Rightarrow \Delta E\_{j} \leq 0$
Change from $1$ to $-1$ :
$\Delta u\_{j}=-2, \Sigma T\_{j i} u\_{i}<0 \Rightarrow \Delta E\_{j}<0$

Not all memories are remembered with same emphasis (attractors region is not the same size)

Retrieval States
Reversed States
Mixture States: Any linear combination of an odd number of patterns
“Spinglass” states: Stable states that are no linear combination of stored patterns (occur when too many patterns are stored)

In a net of $N$ units, patterns of length $N$ can be stored
Assuming uncorrelated patterns, the capacity $C$ of a hopfield net is
$C \approx 0.15N$
- Tighter bound $$ \frac{N}{4 \ln N}

Last updated on 2024-09-05