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

    截屏2020-08-18 16.52.56

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

    V_1 = +1
    V_2 = -1
    V_3 = -1
    V_4 = +1
    -1
    -1
    +1
    +1
    -1
    -1
    Viewer does not support full SVG 1.1

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} $$
  1. Evaluate the sum of the weighted inputs
  2. 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

截屏2020-08-18 17.19.17 截屏2020-08-18 17.23.26
$$ > 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 $-$

截屏2020-08-18 17.23.29 截屏2020-08-18 17.23.32 截屏2020-08-18 17.23.34 截屏2020-08-18 17.23.37 截屏2020-08-18 17.23.39 截屏2020-08-18 17.23.42

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

截屏2020-08-18 22.36.03

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)

截屏2020-08-18 22.39.28

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}

Reference