The ramped window, the matrix it fills, and why the matrix is not symmetric.
The notebook carries the source, the install step and every run below, so nothing has to be on your machine. Open it, then choose Runtime › Run all.
Colab opens it read only. Click Copy to Drive to keep
your changes. You can also download
hal.ipynb, or run it
locally: python3 hal.py.
python3 hal.py
The matrix, and the pairs whose two cells disagree most.
python3 hal.py --vectors
M[a][b] counts b before a, so a word needs its row and its column. Here they are, concatenated.
python3 hal.py --contributions
Why the raw numbers work: every cell is one question put to two words, and the distance is the tally of their disagreements.
python3 hal.py --canteen
The same argument on canteen bills instead of words: two drinks that never share a bill, and the rare one the raw counts get wrong.
Download hal.py
· served verbatim at https://nlp.jcrlabz.com/code/hal.py
"""HAL, the Hyperspace Analogue to Language, traced as Chapter 7 traces it.
Two scans over the corpus, a ramped window, and an asymmetric matrix. Run this
and you get the same matrix the book prints for
the horse raced past the barn fell
python3 hal.py # the book's corpus, window 5
python3 hal.py --window 3 # watch the ramp shorten
python3 hal.py --corpus "a b a c" # your own text
python3 hal.py --vectors # concatenated row+column vectors
python3 hal.py --contributions # what each cell contributes to distance
python3 hal.py --canteen # the same idea on canteen bills, not words
The one idea to hold on to: M[a][b] counts b occurring BEFORE a, so M[b][a]
counts something different. The matrix is asymmetric on purpose, because word
order carries grammar.
Install: nothing, the Python standard library is enough
"""
import argparse
import itertools
from collections import Counter
CORPUS = "the horse raced past the barn fell"
# A second corpus, for the section on why the raw numbers work. Two words are
# used in exactly the same way here, so their vectors have to agree. The book
# uses window 2 on this one, which keeps the contribution table readable.
PARALLEL = "the dog barked the puppy barked the dog slept the puppy slept"
# One morning of canteen bills, each item in the order it was served, with the
# number of times that exact bill was rung up. The chapter uses this to make
# the point without words: chai and coffee never share a bill, yet the matrix
# places them together, because the same things are served around both.
BILLS = [
("idli chutney chai", 6), ("idli chutney coffee", 5),
("dosa chutney chai", 4), ("dosa chutney coffee", 4),
("vada sambar chai", 3), ("vada sambar coffee", 3),
("samosa chutney chai", 2), ("samosa chutney coffee", 2),
("idli chutney greentea", 1), ("dosa chutney greentea", 1),
]
def ramp(window, distance):
"""Weight for a neighbour `distance` words away. Equation 7.1."""
return window - distance + 1
def build(tokens, window):
"""M[a][b] = summed weight of b occurring BEFORE a, within the window.
This single matrix holds both scans. Reading across a row gives you the
left-to-right information (what preceded this word). Reading down a column
gives you the right-to-left information (what followed it).
"""
vocab = list(dict.fromkeys(tokens)) # first-appearance order, as the book
M = {a: {b: 0 for b in vocab} for a in vocab}
for i, target in enumerate(tokens):
for j in range(max(0, i - window), i):
M[target][tokens[j]] += ramp(window, i - j)
return vocab, M
def show_scan(tokens, window):
"""The ramp as the lectures draw it, one key word per row."""
print(f"\nTHE RAMP (window {window}: nearest neighbour scores {window},"
f" furthest scores 1)\n")
print(" " + "".join(f"{t:>7}" for t in tokens))
for k in range(min(2, len(tokens))):
cells = []
for i in range(len(tokens)):
if i < k:
cells.append("")
elif i == k:
cells.append("K")
else:
d = i - k
cells.append(str(ramp(window, d)) if d <= window else "0")
print(f" from {tokens[k]:<3}" + "".join(f"{c:>7}" for c in cells))
print("\n K marks the key word. Each following word gets a smaller weight.")
def show_matrix(vocab, M, tokens):
print(f"\nTHE MATRIX M[row][col] = weight of COLUMN word before ROW word\n")
print(" " + "".join(f"{b:>11}" for b in vocab))
for a in vocab:
print(f" {a:<10}" + "".join(f"{M[a][b]:>11}" for b in vocab))
# The cell where a repeated context word accumulates twice.
repeats = [w for w, n in Counter(tokens).items() if n > 1]
if repeats:
r = repeats[0]
best = max(vocab, key=lambda a: M[a][r])
if M[best][r]:
print(f"\n '{r}' occurs {Counter(tokens)[r]} times, so it can")
print(f" contribute more than once. Row '{best}' collects"
f" {M[best][r]} from it.")
def show_asymmetry(vocab, M):
print("\nWHY IT IS ASYMMETRIC")
print(" M[a][b] counts b BEFORE a. M[b][a] counts a BEFORE b.")
print(" Different events, so the two cells disagree.\n")
pairs = []
order = sorted(vocab)
for i, a in enumerate(order):
for b in order[i + 1:]:
if M[a][b] != M[b][a]:
pairs.append((abs(M[a][b] - M[b][a]), a, b))
pairs.sort(reverse=True)
print(f" {'pair':<22}{'M[a][b]':>9}{'M[b][a]':>9}")
for _, a, b in pairs[:5]:
print(f" {a + ', ' + b:<22}{M[a][b]:>9}{M[b][a]:>9}")
if not pairs:
print(" (none: this corpus happens to be symmetric)")
def vectors(vocab, M):
"""A word's full HAL vector: its row, then its column. Length 2|V|."""
return {a: [M[a][b] for b in vocab] + [M[b][a] for b in vocab]
for a in vocab}
def minkowski(x, y, r=2):
"""Equation 7.5. r=2 is ordinary Euclidean distance."""
return sum(abs(p - q) ** r for p, q in zip(x, y)) ** (1 / r)
def contributions(vocab, V, x, y, r=2):
"""Split the distance between two words into one term per cell.
Minkowski distance sums |x_i - y_i|^r over the cells. Every term is
non-negative and depends on that cell alone, so the distance is a plain
tally of disagreements. A cell where the two words agree adds nothing,
whatever number it holds. That is the whole mechanism.
"""
labels = [f"row {b}" for b in vocab] + [f"col {b}" for b in vocab]
terms = [(L, p, q, abs(p - q) ** r)
for L, p, q in zip(labels, V[x], V[y])]
return terms, sum(t for _, _, _, t in terms)
def show_contributions(vocab, V, x, y):
terms, total = contributions(vocab, V, x, y)
print(f"\n {x} against {y}")
print(f" {'cell':<14}{x:>10}{y:>10}{'(diff)^2':>10}")
for L, p, q, t in terms:
mark = " <-- disagrees" if t else ""
print(f" {L:<14}{p:>10}{q:>10}{t:>10}{mark}")
print(f" {'total':<14}{'':>10}{'':>10}{total:>10}")
print(f" distance = sqrt({total}) = {total ** 0.5:.3f}")
def show_why(window=2):
"""Why a column of raw numbers finds similar words at all."""
tokens = PARALLEL.split()
vocab, M = build(tokens, window)
V = vectors(vocab, M)
print(f"\nWHY THE RAW NUMBERS WORK")
print(f"\n CORPUS {PARALLEL}")
print(f" WINDOW {window}\n")
show_matrix(vocab, M, tokens)
print("\n VECTORS row then column")
for w in vocab:
row = " ".join(f"{v:>2}" for v in V[w][:len(vocab)])
col = " ".join(f"{v:>2}" for v in V[w][len(vocab):])
print(f" {w:<8}[{row}] + [{col}]")
print("\n EVERY CELL IS ONE QUESTION PUT TO BOTH WORDS.")
print(" Agreement costs nothing. Disagreement costs the squared gap.")
show_contributions(vocab, V, "dog", "puppy")
show_contributions(vocab, V, "dog", "slept")
print("\n EVERY PAIR RANKED BY DISTANCE")
ranked = sorted((minkowski(V[x], V[y]), x, y)
for x, y in itertools.combinations(vocab, 2))
for d, x, y in ranked:
print(f" {x + ', ' + y:<20}{d:>8.3f}")
print("\n 'dog' and 'puppy' are used identically, so almost every")
print(" question gets the same answer and the two vectors nearly")
print(" coincide. 'dog' and 'slept' answer differently everywhere.")
print(" No cell knows any meaning. The agreement is the meaning.")
def build_bills(bills, window):
"""The HAL matrix over receipts instead of running text.
A bill is a short sentence. Its items are the words, in the order they were
served, and the window never reaches across from one bill to the next. Each
bill is counted as many times as it was rung up.
"""
vocab = list(dict.fromkeys(i for b, _ in bills for i in b.split()))
M = {a: {b: 0 for b in vocab} for a in vocab}
for bill, times in bills:
t = bill.split()
for i, item in enumerate(t):
for j in range(max(0, i - window), i):
M[item][t[j]] += times * ramp(window, i - j)
return vocab, M
def cosine(x, y):
"""Compares shape and ignores size, which is the whole point below."""
dot = sum(p * q for p, q in zip(x, y))
nx = sum(p * p for p in x) ** 0.5
ny = sum(q * q for q in y) ** 0.5
return dot / (nx * ny) if nx and ny else 0.0
def show_canteen(window=2):
"""Why the raw numbers work, argued on receipts rather than on text."""
vocab, M = build_bills(BILLS, window)
V = vectors(vocab, M)
print("\nTHE CANTEEN BILL")
print(f"\n WINDOW {window}: the item served just before scores {window},"
f" the one before that scores 1\n")
for bill, times in BILLS:
print(f" {bill:<24}{times:>3}")
print("\n M[row][col] = weight of COLUMN item served before ROW item\n")
print(" " + "".join(f"{b:>10}" for b in vocab))
for a in vocab:
print(f" {a:<8}" + "".join(f"{M[a][b]:>10}" for b in vocab))
print("\n EMPTY ROWS ARE NOT EMPTY WORDS.")
print(" A tiffin opens the bill, so nothing is ever served before it and")
print(" its row is all zeros. Its evidence sits in its column instead.")
tiffins = [w for w in vocab if not any(M[w].values())]
R = {a: [M[a][b] for b in vocab] for a in vocab}
print(f"\n {'pair':<20}{'row only':>10}{'row+column':>12}")
for x, y in itertools.combinations(tiffins, 2):
rowonly = sum((p - q) ** 2 for p, q in zip(R[x], R[y])) ** 0.5
print(f" {x + ', ' + y:<20}{rowonly:>10.2f}"
f"{minkowski(V[x], V[y]):>12.2f}")
print("\n On the row alone every tiffin collapses onto every other one.")
print(" The concatenated vector separates them again.")
print("\n NEAREST PAIRS, MINKOWSKI r=2")
ranked = sorted((minkowski(V[x], V[y]), x, y)
for x, y in itertools.combinations(vocab, 2))
for d, x, y in ranked[:5]:
print(f" {x + ', ' + y:<24}{d:>8.2f}")
print(f"\n chai and coffee never share a bill:"
f" M[chai][coffee] = {M['chai']['coffee']},"
f" M[coffee][chai] = {M['coffee']['chai']}")
print(" and they are still the closest pair in the canteen.")
show_contributions(vocab, V, "chai", "coffee")
print("\n WHERE RAW COUNTS FAIL")
print(f" chai to coffee {minkowski(V['chai'], V['coffee']):8.2f}")
print(f" chai to greentea {minkowski(V['chai'], V['greentea']):8.2f}")
print(f" greentea to sambar {minkowski(V['greentea'], V['sambar']):8.2f}")
show_contributions(vocab, V, "chai", "greentea")
print("\n Green tea keeps the company chai keeps. It was ordered twice.")
print(" Every disagreement above is volume, not shape.")
print("\n THE SAME MATRIX, COMPARED BY SHAPE ALONE (cosine)")
for x, y in [("chai", "coffee"), ("chai", "greentea"),
("chutney", "sambar")]:
print(f" cos({x}, {y})".ljust(28) + f"{cosine(V[x], V[y]):8.3f}")
print("\n Green tea moves next to chai on two orders, once size stops")
print(" drowning out shape. That is the argument for a normalised count.")
def main():
ap = argparse.ArgumentParser(description=__doc__)
ap.add_argument("--corpus", default=CORPUS)
ap.add_argument("--window", type=int, default=5)
ap.add_argument("--vectors", action="store_true",
help="print the concatenated row+column vectors")
ap.add_argument("--contributions", action="store_true",
help="split a distance into one term per cell")
ap.add_argument("--canteen", action="store_true",
help="the same argument on canteen bills instead of words")
a = ap.parse_args()
if a.contributions:
show_why()
print()
return
if a.canteen:
show_canteen()
print()
return
tokens = a.corpus.split()
print(f"\nCORPUS {a.corpus}")
vocab, M = build(tokens, a.window)
show_scan(tokens, a.window)
show_matrix(vocab, M, tokens)
show_asymmetry(vocab, M)
if a.vectors:
V = vectors(vocab, M)
print(f"\nFULL VECTORS row then column, {2 * len(vocab)} dimensions")
for w in vocab:
row = " ".join(f"{x:>2}" for x in V[w][:len(vocab)])
col = " ".join(f"{x:>2}" for x in V[w][len(vocab):])
print(f" {w:<10}[{row}] + [{col}]")
print("\n The row is what preceded the word. The column is what")
print(" followed it. A symmetric model would have nothing to join.")
print(f"\n Minkowski distance (r=2) between a few pairs:")
for x, y in [(vocab[0], vocab[1]), (vocab[0], vocab[-1])]:
print(f" {x:<8} to {y:<8} {minkowski(V[x], V[y]):.2f}")
print()
if __name__ == "__main__":
main()