Hopfield Nets
Binary Hopfield Nets
Basic Structure: Binary Unit
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
Connections
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) $$Update Binary Unit
$$ 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} $$- Evaluate the sum of the weighted inputs
- Set state $1$ if the sum is greater or equal $0$, else $-1$
Update Procedure
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
Example
$$ > 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 $-$
Order of updating
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
Energy function
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} $$
Proof on Convergence
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 $$
Stable States
Stable states are minima of the energy function
- Can be global or local minima
Analogous to finding a minimum in a mountainous terrain
Applications
Associative memory
Optimization
Limitations
Found stable state (memory) is not guaranteed the most similar pattern to the input pattern
Not all memories are remembered with same emphasis (attractors region is not the same size)
Spurious States
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)
Efficiency
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}
- Tighter bound
$$
\frac{N}{4 \ln N}