FINDING NEEDLES · CHAPTER 05
To TF-IDF, “pear” and “apple” are as different as “pear” and “ladder”. Give each word a point in space, placed by the words around it, and the fruit end up together.
You search an orchard log for “pear”. A note that says “sweet apple juice” is not a hit. The index from chapter 1 only knows exact words, and the TF-IDF vectors from chapter 2 give “pear” and “apple” separate axes that never touch.
Now look at what sits next to each word. Apples and pears are both sweet, both blossom, both end up as juice. A ladder stands by the tree too, but it has rungs and you climb it. You never read a definition. The neighbours told you.
Words that appear in similar places tend to mean similar things. That is the distributional hypothesis. A word embedding is a list of numbers that records a word’s usual neighbours, so that words with the same neighbours get nearby vectors.
The orchard log uses ten words: apple, pear, plum, ladder, and six neighbours. The simplest vector for a word is one-hot. It has ten slots, a 1 in the word’s own slot, and 0 everywhere else.
company · window · cosine · type
Any two different one-hot vectors share no slot, so their dot product is 0. The cosine of apple and pear is 0. The cosine of apple and ladder is also 0. One-hot vectors can tell words apart. They can never say two words are alike.
two different words never share a slot, so every pair is equally far apart.
Each note is a few words with the stop words already removed. Two words “keep company” if they share a note.
| Word | Its three notes |
|---|---|
| apple | apple tree blossom · sweet apple tree · apple juice |
| pear | pear tree blossom · sweet pear tree · pear juice tree |
| plum | sweet plum tree · plum blossom tree · sweet plum juice |
| ladder | ladder tree rung · climb ladder tree · ladder tree |
Count, for each word, how many times each neighbour shares a note with it. Each row is now that word’s vector, with one axis per neighbour.
| Word | sweet | juice | blossom | tree | rung | climb | Row total |
|---|---|---|---|---|---|---|---|
| apple | 1 | 1 | 1 | 2 | 0 | 0 | 5 |
| pear | 1 | 1 | 1 | 3 | 0 | 0 | 6 |
| plum | 2 | 1 | 1 | 2 | 0 | 0 | 6 |
| ladder | 0 | 0 | 0 | 3 | 1 | 1 | 5 |
| Column total | 4 | 3 | 3 | 10 | 1 | 1 | 22 |
Cosine on these rows already beats one-hot. Apple’s nearest words are pear at 0.982 and plum at 0.956. But the ladder scores 0.684, which is far too high for a thing you cannot eat.
The culprit is “tree”. It shares a note with every word, 10 times out of 22. It dominates every vector, and it says nothing about what kind of thing the word is.
Ask a better question: does this pair show up together more often than chance would predict? If apple took 5 of the 22 pairings, and juice took 3, then chance alone puts them together 5 × 3 / 22 times. Divide the real count by that, then take the log. That is pointwise mutual information. Clip negatives to 0 and you get PPMI.
real count times the grand total, over row total times column total. Above 1 means “more than chance”, and the log turns that into a positive score.
| Cosine with apple | Raw counts | PPMI |
|---|---|---|
| pear | 0.982 | 0.934 |
| plum | 0.956 | 0.575 |
| ladder | 0.684 | 0.000 |
The fruit still lead. The ladder falls to 0.000, because once “tree” stops counting, apple and ladder share no informative neighbour. Plum drops more than pear does, because plum’s strongest signal is that it is the sweetest of the three, and twelve notes are not much evidence.
Interactive · Raw counts or PPMI
Which word looks most like an apple? Switch the weighting and watch the ladder.
These vectors have one axis per neighbour, so they are as long as the vocabulary. Real count-based methods keep the same idea and then compress the big PPMI table to a few hundred dense columns. GloVe is a well-known method in that family.
word2vec gets to the same place by a different road. Give every word a short random vector. Then slide through the text. For each center word, the model is asked a yes-or-no question about another word: was this really a neighbour?
A real neighbour from the text is the positive. A few words drawn at random from the vocabulary are the negatives. The score is a dot product squashed by a sigmoid. The loss is low when the positive scores high and the negatives score low. That is skip-gram with negative sampling.
say “yes” to the real neighbour, say “no” to each random word. Each word has a center vector v and a context vector u.
One step by hand, with 2-D toy vectors. Center apple is (1, 1). Its real neighbour juice is (1, 0). The random negative is rung, at (0, −1).
The orchard log is far too small to train this way, which is why the counts above do the real work in this chapter. Typical word2vec models use 100 to 300 dimensions and train on billions of words of text. The sibling model, CBOW, flips the question and predicts the center word from its neighbours.
Skip-gram with negative sampling was later shown to behave like a factorization of a shifted PMI table: the same kind of table you built by hand in section 4. Counting and predicting are two routes to vectors that encode “more often together than chance”.
"""Word vectors from a twelve-note orchard log.
Count which words share a note, reweight the counts with PPMI,
then compare words by cosine. Last, one skip-gram step with
negative sampling on hand-made 2-D vectors.
"""
import math
# Twelve short notes. Stop words are already gone.
NOTES = [
"apple tree blossom", "sweet apple tree", "apple juice",
"pear tree blossom", "sweet pear tree", "pear juice tree",
"sweet plum tree", "plum blossom tree", "sweet plum juice",
"ladder tree rung", "climb ladder tree", "ladder tree",
]
# Rows: the words we want vectors for. Columns: the company they keep.
WORDS = ["apple", "pear", "plum", "ladder"]
CONTEXTS = ["sweet", "juice", "blossom", "tree", "rung", "climb"]
def one_hot(word):
"""A 1 in the word's own slot, 0 everywhere else. No two words overlap."""
vocab = WORDS + CONTEXTS
return [1 if w == word else 0 for w in vocab]
def cooccurrence(notes=None):
"""counts[word][j]: how many notes hold both the word and CONTEXTS[j]."""
notes = NOTES if notes is None else notes
counts = {w: [0] * len(CONTEXTS) for w in WORDS}
for note in notes:
tokens = note.split()
for w in WORDS:
if w in tokens:
for j, c in enumerate(CONTEXTS):
counts[w][j] += tokens.count(c)
return counts
def ppmi(counts):
"""max(0, log2( P(w, c) / (P(w) P(c)) )), all from the count table.
A context that shows up with every word ("tree") lands near 0.
A context that only one kind of word has ("rung") scores high.
"""
total = sum(sum(row) for row in counts.values())
row_sum = {w: sum(counts[w]) for w in counts}
col_sum = [sum(counts[w][j] for w in counts) for j in range(len(CONTEXTS))]
out = {}
for w in counts:
out[w] = []
for j, n in enumerate(counts[w]):
if n == 0:
out[w].append(0.0)
continue
pmi = math.log2(n * total / (row_sum[w] * col_sum[j]))
out[w].append(max(0.0, pmi))
return out
def cosine(left, right):
dot = sum(x * y for x, y in zip(left, right))
size = math.sqrt(sum(x * x for x in left)) * math.sqrt(sum(y * y for y in right))
return dot / size
def neighbours(vectors, word):
"""Every other word, most similar first."""
rows = [(w, cosine(vectors[word], vectors[w])) for w in vectors if w != word]
return sorted(rows, key=lambda row: row[1], reverse=True)
# --- Skip-gram with negative sampling, one step by hand ---------------
def sigmoid(x):
return 1 / (1 + math.exp(-x))
def sgns_loss(center, positive, negative):
"""-log s(center . positive) - log s(-center . negative).
Low when the true neighbour scores high and the random word scores low.
"""
pos = sum(a * b for a, b in zip(center, positive))
neg = sum(a * b for a, b in zip(center, negative))
return -math.log(sigmoid(pos)) - math.log(sigmoid(-neg))
def sgns_step(center, positive, negative, lr=0.5):
"""One gradient step on the center vector. The context vectors stay put."""
pos = sum(a * b for a, b in zip(center, positive))
neg = sum(a * b for a, b in zip(center, negative))
grad = [(sigmoid(pos) - 1) * p + sigmoid(neg) * n for p, n in zip(positive, negative)]
return [c - lr * g for c, g in zip(center, grad)]
# Toy 2-D vectors. "apple" is the center, "juice" a real neighbour,
# "rung" the randomly drawn negative.
APPLE = [1.0, 1.0]
JUICE = [1.0, 0.0]
RUNG = [0.0, -1.0]
Trusting raw co-occurrence counts. A neighbour that goes with everything, like “tree” here, inflates every similarity. The ladder looked 0.684 like an apple until PPMI removed it.
Reading similar as synonym. “Sweet” and “sour” would share almost every neighbour in a bigger orchard log, so they land close together. Embeddings measure shared contexts. Opposites often share contexts.
Expecting one vector to hold every sense. A static embedding gives a word one point. “Press” for cider and “press” the button get blended into one vector. Contextual models, used in the next chapter, fix this.
Over-reading analogy demos. The famous “a is to b as c is to ?” vector arithmetic usually removes the three input words from the answer list. Without that rule, the nearest vector is often one of the inputs. Analogies are a fun probe, not proof that the space understands relations.
Each vector has a single 1 in a different slot. The dot product multiplies slot by slot and every product is 0.
log2(1 × 22 / (5 × 1)) = log2(4.4) = 2.138, the same as ladder and rung. Both are neighbours only the ladder has.
Chance alone predicts 5 × 10 / 22 = 2.27 shared pairings. The real count, 2, is below that, so the log is negative and gets clipped.
A word drawn at random from the vocabulary and paired with the center word. The model learns to give it a low score.