{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Serial order in a Hopfield network\n",
    "\n",
    "*NEUR0016, Lecture 4: Learning, performing and remembering serially ordered actions (Prof. Caswell Barry, UCL)*\n",
    "\n",
    "How can a network of neurons remember a **sequence**, not just a single pattern? Here 400 simple neurons (each is either on or off) learn to step through four letters in order: **P → R → O → F**. This is the model of Sompolinsky & Kanter (1986) and Kleinfeld (1986).\n",
    "\n",
    "The idea in one sentence: *one set of connections holds the current letter in place, and a second, delayed set of connections pushes the network on to the next letter.*\n",
    "\n",
    "Run each cell in turn with **Shift + Enter** (or use Run → Run All Cells). You don't need to understand the code to follow the notebook, but you can change the numbers in the \"Try it yourself\" section."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# SETUP: run this cell first. You don't need to read it.\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.path import Path\n",
    "from matplotlib.textpath import TextPath\n",
    "from matplotlib.font_manager import FontProperties\n",
    "import io\n",
    "import warnings\n",
    "import PIL.Image                                          # comes with Matplotlib; used to make the movies\n",
    "\n",
    "plt.rcParams.update({\"font.size\": 14, \"axes.titlesize\": 15, \"axes.labelsize\": 15,\n",
    "                     \"axes.spines.top\": False, \"axes.spines.right\": False})\n",
    "\n",
    "LETTERS = \"PROF\"                                          # the sequence to learn\n",
    "COLOURS = [\"#2a78d6\", \"#eb6834\", \"#1baf7a\", \"#eda100\"]    # one colour per letter\n",
    "\n",
    "\n",
    "def letter_image(letter, side):\n",
    "    # Draw a letter on a side x side grid: +1 = ink (neuron on), -1 = background (neuron off).\n",
    "    path = TextPath((0, 0), letter, size=1, prop=FontProperties(weight=\"bold\"))\n",
    "    outlines = path.to_polygons()                           # the letter's outlines (the hole in P, R, O is a second outline)\n",
    "    box = path.get_extents()\n",
    "    size = 1.15 * max(box.width, box.height)\n",
    "    x0 = (box.x0 + box.x1) / 2 - size / 2\n",
    "    y0 = (box.y0 + box.y1) / 2 + size / 2\n",
    "    image = -np.ones((side, side))\n",
    "    for row in range(side):\n",
    "        for col in range(side):\n",
    "            x = x0 + (col + 0.5) / side * size\n",
    "            y = y0 - (row + 0.5) / side * size\n",
    "            inside = sum(Path(o).contains_point((x, y)) for o in outlines)\n",
    "            if inside % 2 == 1:                             # inside an odd number of outlines = ink\n",
    "                image[row, col] = 1\n",
    "    return image\n",
    "\n",
    "\n",
    "def show_letter(ax, state, side, colour=\"grey\"):\n",
    "    # Show a network state as a picture, with a coloured frame.\n",
    "    ax.imshow(state.reshape(side, side), cmap=\"Greys\", vmin=-1, vmax=1)\n",
    "    ax.set_xticks([])\n",
    "    ax.set_yticks([])\n",
    "    for edge in ax.spines.values():\n",
    "        edge.set_visible(True)\n",
    "        edge.set_color(colour)\n",
    "        edge.set_linewidth(4)\n",
    "\n",
    "\n",
    "def show_run(states, overlap, side):\n",
    "    # Main figure: snapshots of the network state (top) and overlap with each letter (bottom).\n",
    "    steps = len(states) - 1\n",
    "    fig = plt.figure(figsize=(12, 6))\n",
    "    times = (steps * np.array([0, 0.1, 0.3, 0.55, 0.8, 1])).astype(int)   # six moments in time\n",
    "    grid = fig.add_gridspec(2, len(times), height_ratios=[1, 1.4], hspace=0.3, wspace=0.15)\n",
    "    for k, t in enumerate(times):\n",
    "        ax = fig.add_subplot(grid[0, k])\n",
    "        best = overlap[t].argmax()\n",
    "        colour = COLOURS[best] if overlap[t, best] > 0.8 else \"grey\"   # coloured when it is a clean letter\n",
    "        show_letter(ax, states[t], side, colour)\n",
    "        ax.set_title(\"t = %d\" % t, fontsize=14)\n",
    "    ax = fig.add_subplot(grid[1, :])\n",
    "    for i, letter in enumerate(LETTERS):\n",
    "        ax.plot(overlap[:, i], color=COLOURS[i], linewidth=3, label=letter)\n",
    "    for t in times:\n",
    "        ax.axvline(t, color=\"lightgrey\", linestyle=\":\", zorder=0)\n",
    "    ax.set_xlim(0, steps)\n",
    "    ax.set_ylim(-0.6, 1.15)\n",
    "    ax.set_xlabel(\"time (steps)\")\n",
    "    ax.set_ylabel(\"overlap with letter\")\n",
    "    ax.legend(title=\"letter\", loc=\"center left\", bbox_to_anchor=(1.01, 0.5), frameon=False, fontsize=16)\n",
    "    plt.show()\n",
    "\n",
    "\n",
    "def find_loop(overlap):\n",
    "    # For a looping run: find the last two complete P -> R -> O -> F cycles (each starts when P comes back).\n",
    "    best = overlap.argmax(axis=1)\n",
    "    clean = overlap.max(axis=1) > 0.8\n",
    "    starts = [t for t in range(1, len(best)) if best[t] == 0 and clean[t] and best[t - 1] != 0]\n",
    "    if len(starts) < 2:\n",
    "        return None                                         # not even one full cycle: just show the whole run\n",
    "    return starts[max(0, len(starts) - 3)], starts[-1]\n",
    "\n",
    "\n",
    "def show_animation(states, overlap, side, loop=False, every=2):\n",
    "    # Play the run as a movie: the network state (left) and the overlap with each letter (right).\n",
    "    # loop=True: shows two whole cycles and repeats them seamlessly, so each restart is just the next P.\n",
    "    # every: use every 2nd (or 3rd ...) time step, to keep the movie quick to make.\n",
    "    steps = len(states) - 1\n",
    "    window = find_loop(overlap) if loop else None\n",
    "    if window is None:\n",
    "        times = np.arange(0, steps + 1, every)\n",
    "        first, last = 0, steps\n",
    "    else:\n",
    "        first, last = window                                # 'last' is where the next cycle starts, so leave it out\n",
    "        times = np.linspace(first, last, round((last - first) / every), endpoint=False).astype(int)\n",
    "        last -= 1\n",
    "    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4), dpi=72, gridspec_kw=dict(width_ratios=[1, 2]))\n",
    "    show_letter(ax1, states[times[0]], side)\n",
    "    image = ax1.images[0]\n",
    "    lines, dots = [], []\n",
    "    for i, letter in enumerate(LETTERS):\n",
    "        lines += ax2.plot([], [], color=COLOURS[i], linewidth=3, label=letter)\n",
    "        dots += ax2.plot([], [], \"o\", color=COLOURS[i], markersize=10)\n",
    "    if loop:                                                # looping movie: the whole stretch is drawn, a dot shows \"now\"\n",
    "        for i in range(len(LETTERS)):\n",
    "            lines[i].set_data(range(first, last + 1), overlap[first:last + 1, i])\n",
    "            lines[i].set_alpha(0.5)\n",
    "    ax2.set_xlim(first, last)\n",
    "    ax2.set_ylim(-0.3, 1.15)\n",
    "    ax2.set_yticks([0, 0.5, 1])\n",
    "    ax2.set_xlabel(\"time (steps)\")\n",
    "    ax2.set_ylabel(\"overlap with letter\")\n",
    "    ax2.legend(loc=\"upper left\", bbox_to_anchor=(1.01, 1.0), frameon=False, fontsize=16)\n",
    "    fig.tight_layout()\n",
    "\n",
    "    pictures = []\n",
    "    for t in times:                                         # draw each frame and keep it as a picture\n",
    "        best = overlap[t].argmax()\n",
    "        clean = overlap[t, best] > 0.8                      # coloured frame when it is a clean letter\n",
    "        image.set_data(states[t].reshape(side, side))\n",
    "        for edge in ax1.spines.values():\n",
    "            edge.set_color(COLOURS[best] if clean else \"grey\")\n",
    "        ax1.set_title(\"t = %d:  %s\" % (t, LETTERS[best] if clean else \"?\"))\n",
    "        for i in range(len(LETTERS)):\n",
    "            if not loop:\n",
    "                lines[i].set_data(range(first, t + 1), overlap[first:t + 1, i])\n",
    "            dots[i].set_data([t], [overlap[t, i]])\n",
    "        frame = io.BytesIO()\n",
    "        with warnings.catch_warnings():                     # the in-browser Matplotlib prints a harmless warning here\n",
    "            warnings.simplefilter(\"ignore\", DeprecationWarning)\n",
    "            fig.savefig(frame, format=\"png\")\n",
    "        pictures.append(PIL.Image.open(frame).convert(\"RGB\"))\n",
    "    plt.close(fig)                                          # show only the movie, not an extra still picture\n",
    "\n",
    "    # Join the pictures into an animated GIF that repeats forever (a normal run pauses 2 s on its last frame).\n",
    "    some = np.concatenate([np.asarray(p) for p in pictures[::4] + pictures[-1:]])\n",
    "    palette = PIL.Image.fromarray(some).quantize(colors=256)   # one shared set of colours for every frame\n",
    "    colours = np.array(palette.getpalette()).reshape(-1, 3)\n",
    "    colours[colours.min(axis=1) >= 245] = 255                    # keep the background pure white\n",
    "    palette.putpalette(colours.astype(np.uint8).flatten().tolist())\n",
    "    pictures = [p.quantize(palette=palette, dither=PIL.Image.Dither.NONE) for p in pictures]\n",
    "    durations = [120] * len(pictures)\n",
    "    if not loop:\n",
    "        durations[-1] = 2000\n",
    "    gif = io.BytesIO()\n",
    "    pictures[0].save(gif, format=\"GIF\", save_all=True, append_images=pictures[1:], duration=durations, loop=0)\n",
    "    try:\n",
    "        from IPython.display import Image, display\n",
    "    except ImportError:                                     # plain Python, not Jupyter: nothing to show it in\n",
    "        return gif.getvalue()\n",
    "    display(Image(data=gif.getvalue(), format=\"gif\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. The four letters to remember\n",
    "\n",
    "Each letter is a picture made of a 20 × 20 grid of pixels, and each pixel is one neuron: **black = neuron on (+1)**, **white = neuron off (−1)**. So the network has 20 × 20 = 400 neurons, and each letter is one *pattern* of activity across them."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "side = 20                                   # the grid is side x side, so there are side * side neurons\n",
    "\n",
    "# Each row of 'patterns' is one letter, written out as a list of 400 numbers (+1 or -1)\n",
    "patterns = np.array([letter_image(letter, side).flatten() for letter in LETTERS])\n",
    "\n",
    "fig, axes = plt.subplots(1, 4, figsize=(9, 2.8))\n",
    "for i in range(4):\n",
    "    show_letter(axes[i], patterns[i], side, COLOURS[i])\n",
    "    axes[i].set_title(\"stored letter \" + LETTERS[i])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Build the connections (the \"learning\")\n",
    "\n",
    "Two sets of connections are built from the letters:\n",
    "\n",
    "* **Holding connections** (`Ws`, symmetric): link neurons that are on together in the *same* letter. They make each letter a stable state, so the network stays on a letter once it is there.\n",
    "* **Pushing connections** (`Wa`, asymmetric): link each letter to the *next* letter (P→R, R→O, O→F; with `cyclic=True` also F→P, see section 5). They are scaled by a strength **λ (lambda)**. Later we will make them act with a **delay**, so they only kick in once the network has been on a letter for a while.\n",
    "\n",
    "(The picture of the connections below is just to show what they look like: red = excitatory, blue = inhibitory. It isn't meant to be readable by eye.)\n",
    "\n",
    "The letters share many pixels, so the helper below uses a standard correction (the *pseudo-inverse*) to stop the letters being confused with each other."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def build_weights(patterns, lam, cyclic=False):\n",
    "    # 'duals' is a corrected copy of the patterns (pseudo-inverse), so that similar-looking letters don't get confused.\n",
    "    duals = np.linalg.pinv(patterns.T)\n",
    "    n = patterns.shape[1]\n",
    "    Ws = np.zeros((n, n))                                   # holding connections\n",
    "    Wa = np.zeros((n, n))                                   # pushing connections\n",
    "    for i in range(len(patterns)):\n",
    "        Ws += np.outer(patterns[i], duals[i])               # letter i -> letter i  (hold)\n",
    "        if i < len(patterns) - 1:\n",
    "            Wa += lam * np.outer(patterns[i + 1], duals[i]) # letter i -> letter i+1 (push)\n",
    "        elif cyclic:\n",
    "            Wa += lam * np.outer(patterns[0], duals[i])     # last letter -> first letter (F -> P), so it loops\n",
    "    return Ws, Wa, duals\n",
    "\n",
    "\n",
    "lam = 1.5                                                   # strength of the pushing connections\n",
    "Ws, Wa, duals = build_weights(patterns, lam)\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=(10, 4.5))\n",
    "for ax, W, name in [(axes[0], Ws, \"Holding connections (Ws)\"), (axes[1], Wa, \"Pushing connections (Wa)\")]:\n",
    "    biggest = np.abs(W).max()\n",
    "    image = ax.imshow(W, cmap=\"RdBu_r\", vmin=-biggest, vmax=biggest)   # red = excitatory, blue = inhibitory\n",
    "    ax.set_title(name)\n",
    "    ax.set_xlabel(\"from neuron\")\n",
    "    ax.set_ylabel(\"to neuron\")\n",
    "    plt.colorbar(image, ax=ax, label=\"connection strength\", shrink=0.8)\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Run the network: P → R → O → F\n",
    "\n",
    "We start the network in a *noisy* version of P (10% of the neurons are flipped) and let it run. At every time step each neuron adds up its inputs and switches **on** if the total is positive, **off** otherwise. The pushing connections listen to a **slow memory trace** of the activity (`trace`, which lags behind with time constant **τ (tau)**). That is the delay: the push grows the longer the network sits on a letter, until it beats the holding connections and the network moves on.\n",
    "\n",
    "**How to read the figure:** the top row shows the network's state at six moments in time. The frame is coloured when the picture is a clean letter. The bottom plot shows the *overlap* with each letter over time: 1 means the network is exactly that letter, 0 means unrelated. One line per letter."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def run_network(start, Ws, Wa, tau, noise, steps):\n",
    "    state = start.copy()\n",
    "    trace = np.zeros(len(state))                            # slow memory of recent activity\n",
    "    states = [state.copy()]\n",
    "    for t in range(steps):\n",
    "        total_input = Ws @ state + Wa @ trace               # holding input + delayed pushing input\n",
    "        total_input += noise * np.random.randn(len(state))  # random noise on every neuron\n",
    "        state = np.where(total_input > 0, 1.0, -1.0)        # on if the input is positive, off otherwise\n",
    "        trace += (state - trace) / tau                      # trace slowly follows the state\n",
    "        states.append(state.copy())\n",
    "    return np.array(states)\n",
    "\n",
    "\n",
    "np.random.seed(1)                                           # same random numbers every time\n",
    "start = patterns[0].copy()                                  # begin on the letter P ...\n",
    "flipped = np.random.rand(len(start)) < 0.1                  # ... but flip 10% of the neurons\n",
    "start[flipped] = -start[flipped]\n",
    "\n",
    "states = run_network(start, Ws, Wa, tau=20, noise=0.1, steps=100)\n",
    "overlap = states @ duals.T                                  # how much does each time step look like each letter?\n",
    "show_run(states, overlap, side)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Watch it run\n",
    "\n",
    "The same run as a movie (it pauses on the last frame, then starts again). The frame turns the letter's colour when the network is showing a clean letter."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "show_animation(states, overlap, side)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Loop back: P → R → O → F → P → ...\n",
    "\n",
    "At the moment nothing pushes on from F, so the network stops there. With `cyclic=True` the pushing connections also link the last letter to the first (F → P), so the sequence goes round and round. The movie below loops by itself: just watch it cycle (the faint lines show two whole cycles; the dots show \"now\")."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "Ws_loop, Wa_loop, duals = build_weights(patterns, lam, cyclic=True)\n",
    "\n",
    "np.random.seed(1)\n",
    "states = run_network(start, Ws_loop, Wa_loop, tau=20, noise=0.1, steps=320)\n",
    "overlap = states @ duals.T\n",
    "show_animation(states, overlap, side, loop=True, every=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Try it yourself\n",
    "\n",
    "Change the numbers below, then run **both** cells underneath (this one and the next). The second cell draws the figure and then plays the movie. Each parameter has a comment saying what it does. The three experiments after the figure are suggestions."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# PARAMETERS: change these numbers, then run this cell and the next one.\n",
    "lam = 1.5        # strength of the pushing connections (lambda). Bigger = pushes harder.\n",
    "tau = 20         # delay of the pushing connections (tau), in time steps. Bigger = each letter lasts longer.\n",
    "noise = 0.1      # random noise on each neuron. Bigger = messier.\n",
    "side = 20        # grid is side x side neurons. 20 = 400 neurons; 6 = only 36 neurons.\n",
    "steps = 100      # how many time steps to run for\n",
    "cyclic = False   # True = F pushes back to P, so the sequence loops (use steps = 320 to see it go round twice)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "patterns = np.array([letter_image(letter, side).flatten() for letter in LETTERS])\n",
    "Ws, Wa, duals = build_weights(patterns, lam, cyclic)\n",
    "\n",
    "np.random.seed(1)\n",
    "start = patterns[0].copy()\n",
    "flipped = np.random.rand(len(start)) < 0.1\n",
    "start[flipped] = -start[flipped]\n",
    "\n",
    "states = run_network(start, Ws, Wa, tau, noise, steps)\n",
    "overlap = states @ duals.T\n",
    "show_run(states, overlap, side)\n",
    "show_animation(states, overlap, side, loop=cyclic, every=3 if cyclic else 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Three experiments\n",
    "\n",
    "1. **Weak push.** Set `lam = 0.5` and run both cells again. The push is too weak to beat the holding connections, so the network gets **stuck on P**. (Try `lam = 0.8` too: the push is still not enough to move past R.)\n",
    "2. **Change the delay.** Set `tau = 8`, then `tau = 40` (with `steps = 200`). How long does each letter last? The time on each letter is set by how long the slow trace takes to build up.\n",
    "3. **Fewer neurons plus noise.** Set `side = 6` (only 36 neurons) and `noise = 0.8`. The sequence **breaks**: the order is scrambled, letters are skipped or repeated. With few neurons the push is averaged over too few connections to beat the noise. Now set `side = 20` again with the same noise: 400 neurons are much more reliable. This is why serial order is thought to be stored by *populations* of neurons.\n",
    "\n",
    "Each run is followed by its movie. To make any of these loop, set `cyclic = True` and `steps = 320`.\n",
    "\n",
    "**References.** Sompolinsky, H. & Kanter, I. (1986) Temporal association in asymmetric neural networks. *Physical Review Letters* 57, 2861. Kleinfeld, D. (1986) Sequential state generation by model neural networks. *PNAS* 83, 9469."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python",
   "display_name": "Python (Pyodide)",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}