{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HAL, ramped and asymmetric\n",
    "\n",
    "The ramped window, the matrix it fills, and why the matrix is not symmetric.\n",
    "\n",
    "From chapter 7, [Count Vectors, PPMI, and SVD](https://nlp.jcrlabz.com/book/countvectors/), of the course notes.\n",
    "\n",
    "Source: `book/code/worked_examples/hal.py`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What you need\n",
    "\n",
    "Nothing. This example uses only the Python standard library."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Nothing to install: this example uses only the Python standard library.\n",
    "import sys; print(sys.version.split()[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The script\n",
    "\n",
    "Everything the example defines, in one cell. Run it and the definitions\n",
    "are live in the notebook."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "\"\"\"HAL, the Hyperspace Analogue to Language, traced as Chapter 7 traces it.\n",
    "\n",
    "Two scans over the corpus, a ramped window, and an asymmetric matrix. Run this\n",
    "and you get the same matrix the book prints for\n",
    "\n",
    "    the horse raced past the barn fell\n",
    "\n",
    "    python3 hal.py                      # the book's corpus, window 5\n",
    "    python3 hal.py --window 3           # watch the ramp shorten\n",
    "    python3 hal.py --corpus \"a b a c\"   # your own text\n",
    "    python3 hal.py --vectors            # concatenated row+column vectors\n",
    "\n",
    "The one idea to hold on to: M[a][b] counts b occurring BEFORE a, so M[b][a]\n",
    "counts something different. The matrix is asymmetric on purpose, because word\n",
    "order carries grammar.\n",
    "\n",
    "Install:  nothing, the Python standard library is enough\n",
    "\"\"\"\n",
    "\n",
    "import argparse\n",
    "from collections import Counter\n",
    "\n",
    "CORPUS = \"the horse raced past the barn fell\"\n",
    "\n",
    "\n",
    "def ramp(window, distance):\n",
    "    \"\"\"Weight for a neighbour `distance` words away. Equation 7.1.\"\"\"\n",
    "    return window - distance + 1\n",
    "\n",
    "\n",
    "def build(tokens, window):\n",
    "    \"\"\"M[a][b] = summed weight of b occurring BEFORE a, within the window.\n",
    "\n",
    "    This single matrix holds both scans. Reading across a row gives you the\n",
    "    left-to-right information (what preceded this word). Reading down a column\n",
    "    gives you the right-to-left information (what followed it).\n",
    "    \"\"\"\n",
    "    vocab = list(dict.fromkeys(tokens))   # first-appearance order, as the book\n",
    "    M = {a: {b: 0 for b in vocab} for a in vocab}\n",
    "    for i, target in enumerate(tokens):\n",
    "        for j in range(max(0, i - window), i):\n",
    "            M[target][tokens[j]] += ramp(window, i - j)\n",
    "    return vocab, M\n",
    "\n",
    "\n",
    "def show_scan(tokens, window):\n",
    "    \"\"\"The ramp as the lectures draw it, one key word per row.\"\"\"\n",
    "    print(f\"\\nTHE RAMP  (window {window}: nearest neighbour scores {window},\"\n",
    "          f\" furthest scores 1)\\n\")\n",
    "    print(\"       \" + \"\".join(f\"{t:>7}\" for t in tokens))\n",
    "    for k in range(min(2, len(tokens))):\n",
    "        cells = []\n",
    "        for i in range(len(tokens)):\n",
    "            if i < k:\n",
    "                cells.append(\"\")\n",
    "            elif i == k:\n",
    "                cells.append(\"K\")\n",
    "            else:\n",
    "                d = i - k\n",
    "                cells.append(str(ramp(window, d)) if d <= window else \"0\")\n",
    "        print(f\"  from {tokens[k]:<3}\" + \"\".join(f\"{c:>7}\" for c in cells))\n",
    "    print(\"\\n  K marks the key word. Each following word gets a smaller weight.\")\n",
    "\n",
    "\n",
    "def show_matrix(vocab, M, tokens):\n",
    "    print(f\"\\nTHE MATRIX  M[row][col] = weight of COLUMN word before ROW word\\n\")\n",
    "    print(\"            \" + \"\".join(f\"{b:>11}\" for b in vocab))\n",
    "    for a in vocab:\n",
    "        print(f\"  {a:<10}\" + \"\".join(f\"{M[a][b]:>11}\" for b in vocab))\n",
    "\n",
    "    # The cell where a repeated context word accumulates twice.\n",
    "    repeats = [w for w, n in Counter(tokens).items() if n > 1]\n",
    "    if repeats:\n",
    "        r = repeats[0]\n",
    "        best = max(vocab, key=lambda a: M[a][r])\n",
    "        if M[best][r]:\n",
    "            print(f\"\\n  '{r}' occurs {Counter(tokens)[r]} times, so it can\")\n",
    "            print(f\"  contribute more than once. Row '{best}' collects\"\n",
    "                  f\" {M[best][r]} from it.\")\n",
    "\n",
    "\n",
    "def show_asymmetry(vocab, M):\n",
    "    print(\"\\nWHY IT IS ASYMMETRIC\")\n",
    "    print(\"  M[a][b] counts b BEFORE a.  M[b][a] counts a BEFORE b.\")\n",
    "    print(\"  Different events, so the two cells disagree.\\n\")\n",
    "    pairs = []\n",
    "    order = sorted(vocab)\n",
    "    for i, a in enumerate(order):\n",
    "        for b in order[i + 1:]:\n",
    "            if M[a][b] != M[b][a]:\n",
    "                pairs.append((abs(M[a][b] - M[b][a]), a, b))\n",
    "    pairs.sort(reverse=True)\n",
    "    print(f\"  {'pair':<22}{'M[a][b]':>9}{'M[b][a]':>9}\")\n",
    "    for _, a, b in pairs[:5]:\n",
    "        print(f\"  {a + ', ' + b:<22}{M[a][b]:>9}{M[b][a]:>9}\")\n",
    "    if not pairs:\n",
    "        print(\"  (none: this corpus happens to be symmetric)\")\n",
    "\n",
    "\n",
    "def vectors(vocab, M):\n",
    "    \"\"\"A word's full HAL vector: its row, then its column. Length 2|V|.\"\"\"\n",
    "    return {a: [M[a][b] for b in vocab] + [M[b][a] for b in vocab]\n",
    "            for a in vocab}\n",
    "\n",
    "\n",
    "def minkowski(x, y, r=2):\n",
    "    \"\"\"Equation 7.5. r=2 is ordinary Euclidean distance.\"\"\"\n",
    "    return sum(abs(p - q) ** r for p, q in zip(x, y)) ** (1 / r)\n",
    "\n",
    "\n",
    "def main():\n",
    "    ap = argparse.ArgumentParser(description=__doc__)\n",
    "    ap.add_argument(\"--corpus\", default=CORPUS)\n",
    "    ap.add_argument(\"--window\", type=int, default=5)\n",
    "    ap.add_argument(\"--vectors\", action=\"store_true\",\n",
    "                    help=\"print the concatenated row+column vectors\")\n",
    "    a = ap.parse_args()\n",
    "\n",
    "    tokens = a.corpus.split()\n",
    "    print(f\"\\nCORPUS  {a.corpus}\")\n",
    "    vocab, M = build(tokens, a.window)\n",
    "    show_scan(tokens, a.window)\n",
    "    show_matrix(vocab, M, tokens)\n",
    "    show_asymmetry(vocab, M)\n",
    "\n",
    "    if a.vectors:\n",
    "        V = vectors(vocab, M)\n",
    "        print(f\"\\nFULL VECTORS  row then column, {2 * len(vocab)} dimensions\")\n",
    "        for w in vocab:\n",
    "            row = \" \".join(f\"{x:>2}\" for x in V[w][:len(vocab)])\n",
    "            col = \" \".join(f\"{x:>2}\" for x in V[w][len(vocab):])\n",
    "            print(f\"  {w:<10}[{row}] + [{col}]\")\n",
    "        print(\"\\n  The row is what preceded the word. The column is what\")\n",
    "        print(\"  followed it. A symmetric model would have nothing to join.\")\n",
    "\n",
    "        print(f\"\\n  Minkowski distance (r=2) between a few pairs:\")\n",
    "        for x, y in [(vocab[0], vocab[1]), (vocab[0], vocab[-1])]:\n",
    "            print(f\"    {x:<8} to {y:<8} {minkowski(V[x], V[y]):.2f}\")\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running it\n",
    "\n",
    "The script is a command line tool, so each run below sets the arguments\n",
    "and calls `main()`. The heading shows the equivalent shell command."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "def run(*args):\n",
    "    sys.argv = [\"hal.py\", *args]\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 hal.py`\n",
    "\n",
    "The matrix, and the pairs whose two cells disagree most."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `python3 hal.py --vectors`\n",
    "\n",
    "M[a][b] counts b before a, so a word needs its row and its column. Here they are, concatenated."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "run(\"--vectors\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Read the chapter this comes from: [Count Vectors, PPMI, and SVD](https://nlp.jcrlabz.com/book/countvectors/)."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "hal.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}