Words as Vectors

A computer sees words the same way. To a computer, "chai" is just a label. Our job in this unit is to turn every word into numbers that carry its meaning.

First, what counts as a word? Before a computer can count anything, it cuts the text into pieces called tokens. Often everything is lower-cased first, so that "Chai" and "chai" count as one word. Punctuation becomes a token of its own. And we add two markers to every sentence: $\langle s\rangle$ at the start and $\langle/s\rangle$ at the end. They mean "a sentence starts here" and "a sentence stops here", and §2 will need them. So I drink chai. becomes

<s> I drink chai . </s>

(We keep "I" as a capital so the examples read naturally.) Modern language models go one step further and cut rare words into smaller pieces; §16 shows how.

Now the simplest way to turn a word into numbers: give each word its own slot. Take a tiny vocabulary of three words — chai, coffee, cricket. Each word becomes a list of three numbers with a single 1 in its own slot:

$$\begin{aligned}\text{chai}&=(1,0,0),\\ \text{coffee}&=(0,1,0),\\ \text{cricket}&=(0,0,1).\end{aligned}$$

A list of zeros with a single 1 is called a one-hot vector. With a real vocabulary of 50 000 words, each list is 50 000 numbers long: one 1 and 49 999 zeros.

Now measure how alike two words are, the way Unit 3 taught us: with the dot product. Multiply slot by slot and add:

$$\text{chai}\cdot\text{coffee}=1\cdot0+0\cdot1+0\cdot0=0.$$

Chai with cricket? Also 0. Every pair of different one-hot words has dot product 0: they all stand at right angles to each other. And every pair is the same distance apart: $\sqrt{1^2+1^2}=\sqrt2\approx1.414$. In one-hot land, chai is exactly as far from coffee as it is from cricket.

The road ahead. The unit has five acts.

1. A word is just a label (§1) — the directory we start from.
2. Guessing the next word by counting (§2–§4): a sentence as a chain of guesses, what to do about words never seen, and how to score a guesser by its surprise — its perplexity.
3. Meaning from the company a word keeps (§5–§7): count the company, weigh it (TF-IDF and PMI), and squeeze it with the SVD from Unit 5.
4. Stop counting, start predicting (§8–§14): word2vec's two games, CBOW and skip-gram; how to make them cheap; why counting and predicting arrive at the same answer; and a small neural language model.
5. The geometry of meaning, and its limits (§15–§17): king − man + woman, words with two meanings, words cut into pieces, and the road to Units 17 and 18.

That game is exactly how a language model scores a sentence. The chance of the whole sentence is the chance of the first word, times the chance of the second word given the first, times the chance of the third given the first two, and so on. This is the chain rule of probability:

$$\begin{aligned}&P(w_1w_2w_3\cdots w_n)\\ &=P(w_1)\,P(w_2\mid w_1)\,P(w_3\mid w_1w_2)\cdots\end{aligned}$$

Read it aloud: a sentence is a string of guesses, and each guess is allowed to use everything that came before it. Nothing is approximated yet. The rule is exact.

The trouble is the history. To know the chance of chai after every morning my grandfather drinks a hot cup of, we would need to have seen that exact history many times. Long histories almost never repeat, so we cannot count them.

So we make a bold simplification, called the Markov assumption: the guesser keeps only the last few words and forgets the rest. It is a guesser with a short memory. If it remembers one word, it is a bigram model ("bi" = two words at a time); if it remembers two, a trigram model; in general, remembering $N-1$ words makes an N-gram model:

$$P(\text{chai}\mid\text{I drink})\approx P(\text{chai}\mid\text{drink}).$$

Now count. Here is a tiny collection of text — people call such a collection a corpus — with the sentence markers added:

<s> I drink chai </s> · <s> I drink coffee </s> · <s> I drink chai </s> · <s> I play cricket </s>

"drink" is followed by chai twice and by coffee once. So the best guess for what follows "drink" is to split the chances the same way:

$$\begin{aligned}P(\text{chai}\mid\text{drink})&=\frac{\text{count}(\text{drink chai})}{\text{count}(\text{drink})}\\ &=\frac23,\\ P(\text{coffee}\mid\text{drink})&=\frac13.\end{aligned}$$

This "count ÷ total" is not a guess about guessing. It is the maximum-likelihood answer of Unit 14: a coin that showed 7 heads in 10 tosses is best described by $p=7/10$, and a word followed by chai 2 times out of 3 is best described by $2/3$.

Now score a whole sentence by multiplying the guesses along the chain. The start marker gives the first word a history too: its guess is $P(\text{I}\mid\langle s\rangle)$, "how often does a sentence start with I?"

$$\begin{aligned}&P(\langle s\rangle\ \text{I drink chai}\ \langle/s\rangle)\\ &=P(\text{I}\mid\langle s\rangle)\,P(\text{drink}\mid\text{I})\\ &\quad\cdot P(\text{chai}\mid\text{drink})\,P(\langle/s\rangle\mid\text{chai})\\ &=1\cdot\tfrac34\cdot\tfrac23\cdot1=\tfrac12.\end{aligned}$$

Why the end marker matters. $\langle/s\rangle$ is a word the model must guess, so the model learns when to stop. Without it, the half-sentence "I drink" would score $\tfrac34$ — more than any complete sentence — and the chances of all sentences would add up to more than 1. With it, every sentence must pay for its ending, and the chances of all possible sentences add up to exactly 1.

And the model can write. Start at $\langle s\rangle$, roll a loaded die whose faces are the next words and whose weights are their chances, write down the face, and repeat until $\langle/s\rangle$ comes up. Claude Shannon wrote sentences this way, by hand, in 1948.

The zero problem. What does our bigram model say about "I drink cricket"? The pair "drink cricket" was never counted, so its chance is 0 — and one zero in the chain makes the whole sentence 0. With real text most possible pairs are never seen, so this happens all the time. Worse, in §4 a single zero will make the model's score infinitely bad.

Fix 1 · one free ticket for every pair. Pretend every possible next word was seen one extra time. This is add-one (or Laplace) smoothing. After "drink" the possible next words are the 7 words that can come next — I, drink, chai, coffee, play, cricket and $\langle/s\rangle$ — so the row gains 7 extra counts:

$$\begin{aligned}P(\text{chai}\mid\text{drink})&=\frac{2+1}{3+7}=0.3,\\ P(\text{cricket}\mid\text{drink})&=\frac{0+1}{3+7}=0.1.\end{aligned}$$

No zeros any more. The price: the words we really saw lost some of their share. Chai fell from 0.667 to 0.3.

Fix 2 · smaller tickets. Give each unseen pair a fraction $k$ of a ticket instead of a whole one: $P=\dfrac{c+k}{n+kV}$, called add-$k$. It helps, but somebody has to choose $k$.

Fix 3 · ask several advisers. Planning a trip, you might ask a friend who went there last month (specific, but little experience) and a travel agent (general, but lots of experience), and blend their advice. Interpolation does the same with a trigram, a bigram and a unigram model (which ignores the history and just knows how common each word is), mixing their guesses with weights that add up to 1.

Worked example: blend the bigram with weight 0.8 and the unigram with weight 0.2. The unigram adviser counts every token that can come next — everything except the $\langle s\rangle$ markers, 16 tokens in all: I 4, drink 3, chai 2, coffee 1, play 1, cricket 1, $\langle/s\rangle$ 4. So

$$\begin{aligned}&P(\text{chai}\mid\text{drink})\\ &\quad=0.8\cdot\tfrac23+0.2\cdot\tfrac{2}{16}=0.5583,\\ &P(\text{cricket}\mid\text{drink})\\ &\quad=0.8\cdot0+0.2\cdot\tfrac{1}{16}=0.0125.\end{aligned}$$

Cricket is no longer impossible, and chai still leads by far.

Fix 4 · backoff. Ask the specialist first. If the specialist has never seen this history, back off and ask the generalist: use the trigram if it has counts, else the bigram, else the unigram. (The borrowed chances are scaled down a little so that each row still adds up to 1.)

In Unit 14 we measured surprise. If the model gave the word that really came next a probability $p$, its surprise is $\log_2(1/p)$ bits. Probability $\tfrac12$ → 1 bit. Probability $\tfrac14$ → 2 bits. Probability 1 → 0 bits: no surprise at all.

Let a model read four words of real text. It gave the words that really came next these probabilities: $0.5,\ 0.25,\ 0.5,\ 0.125$. The surprises are 1, 2, 1 and 3 bits, and the average surprise is

$$\frac{1+2+1+3}{4}=1.75\text{ bits}.$$

This average is the cross-entropy of Unit 14. It is hard to feel what "1.75 bits" means, so we turn it back into a number of choices:

$$2^{1.75}\approx3.364.$$

This number is the perplexity. Here is the picture to keep: how many sides does the model's die have? On average, this model was as unsure as someone rolling a fair die with about 3.4 faces. Lower is better. A perfect model has perplexity 1 — a die with one face.

Our bigram model scoring $\langle s\rangle$ I drink chai $\langle/s\rangle$ made four guesses (I, drink, chai and $\langle/s\rangle$) whose product was $\tfrac12$. So its perplexity on that sentence is

$$\Big(\tfrac12\Big)^{-1/4}=2^{0.25}\approx1.189.$$

That is a die with barely more than one face — no surprise, since the model is being tested on a sentence it was counted from.

A model that knows nothing spreads its guess evenly over a vocabulary of $V$ words and gives every word $1/V$. Its surprise is $\log_2V$ every time, so its perplexity is exactly $V$: a fair die with $V$ faces. That is the worst sensible score, and a useful yardstick. A model with perplexity 120 on a 50 000-word vocabulary has narrowed each guess from 50 000 choices to about 120.

The counting of Act II only asked "what comes next?". Now we ask a wider question: "what is around?". There are two classic ways to write the company down in a table.

1 · Word × document. Rows are words, columns are documents, and each box counts how often the word appears in that document. A row answers "which documents talk about this word?". This term–document table is how search engines began: to answer the query "chai", look along the row for chai.

2 · Word × word. Rows are the words we want to understand (the targets), columns are neighbour words, and each box counts how often the neighbour appears within a few words of the target. How many words either side count as "near" is the window size. With a window of 2, here is the table from a small made-up corpus (the widget shows its sentences):

This is a co-occurrence matrix: "how often do these two words occur together". Read each row as a vector. Chai is $(5,4,0,1)$, coffee is $(4,5,0,0)$, cricket is $(0,0,5,4)$. These are our first real word vectors, and they are no longer one-hot: chai and coffee share neighbours, so their rows look alike.

How alike? Use the angle between the rows, from Unit 3:

$$\cos\theta=\frac{\mathbf a\cdot\mathbf b}{\lVert\mathbf a\rVert\,\lVert\mathbf b\rVert}.$$

For chai and coffee the dot product is $5\cdot4+4\cdot5+0+0=40$, and the lengths are $\sqrt{42}$ and $\sqrt{41}$. So

$$\cos(\text{chai},\text{coffee})=\frac{40}{\sqrt{42}\,\sqrt{41}}\approx0.964.$$

For chai and cricket the dot product is only $1\cdot4=4$, so the cosine is $4/(\sqrt{42}\sqrt{41})\approx0.096$. Cricket and football give $40/(\sqrt{41}\sqrt{42})\approx0.964$ again. The tea words point almost the same way, the sport words point almost the same way, and the two groups are nearly at right angles.

Why the angle and not the length? A word used ten times as often has counts ten times as big — a longer arrow — but the same kind of company. The cosine ignores the length and keeps only the direction: which company a word keeps, not how often it talks.

Raw counts reward words that are everywhere. "The", "is" and "a" sit next to every word and appear in every document, so they swamp both of our tables. We need to weigh each count by how surprising it is. There is one standard fix for each table.

For the term–document table: TF-IDF. Give each count a weight

$$\text{weight}=\text{tf}\times\log_{10}\frac{N}{\text{df}}.$$

Read it aloud: tf, the term frequency, is how often the word appears in this document. df, the document frequency, is how many of the $N$ documents contain the word at all. The log part, the idf, is large for rare words and exactly 0 for a word that is in every document, because $\log 1=0$.

Take three documents. D1 has "the" 3 times, "chai" twice and "hot" once. D2 has "the" twice and "cricket" three times. D3 has "the", "chai" and "cricket" once each. Then

• "the" is in all 3 documents: idf $=\log_{10}(3/3)=\mathbf0$.
• "chai" and "cricket" are in 2 of 3: idf $=\log_{10}1.5\approx\mathbf{0.176}$.
• "hot" is in 1 of 3: idf $=\log_{10}3\approx\mathbf{0.477}$.

So in D1, chai weighs $2\times0.176=0.352$, hot weighs $0.477$, and "the" weighs $0$ despite being the most frequent word. In D2 cricket weighs $3\times0.176=0.528$; in D3 chai and cricket weigh 0.176 each. A word that is in every document says nothing about any one of them.

For the word × word table: PMI. Ask how many times more often two words meet than two strangers would by chance. If chai and "hot" had nothing to do with each other, they would meet with probability $P(\text{chai})\,P(\text{hot})$ (independence, Unit 14). So compare the real meetings with that:

$$\operatorname{PMI}(w,c)=\log_2\frac{P(w,c)}{P(w)\,P(c)}.$$

This is the pointwise mutual information. Worked example, with $N=40$ counted pairs: chai meets hot 8 times, "the" 10 times and "match" 2 times; cricket meets hot 2 times, "the" 10 times and "match" 8 times. Add up the rows and columns first. Chai and cricket each take part in 20 of the 40 pairs; hot in 10, "the" in 20 and match in 10. So $P(\text{chai})=20/40=0.5$, $P(\text{hot})=10/40=0.25$, $P(\text{the})=20/40=0.5$, $P(\text{match})=10/40=0.25$, and $P(\text{chai},\text{hot})=8/40=0.2$:

$$\begin{aligned}&\operatorname{PMI}(\text{chai},\text{hot})\\ &\quad=\log_2\frac{0.2}{0.5\cdot0.25}=\log_21.6\approx0.678,\\ &\operatorname{PMI}(\text{chai},\text{the})\\ &\quad=\log_2\frac{0.25}{0.5\cdot0.5}=0,\\ &\operatorname{PMI}(\text{chai},\text{match})\\ &\quad=\log_2\frac{0.05}{0.5\cdot0.25}\approx-1.322.\end{aligned}$$

Raw counts said "the" was chai's biggest neighbour (10 meetings). PMI says it tells us nothing: chai meets "the" exactly as often as chance predicts. Negative values mean "meet less often than chance", and they are noisy with small counts, so people usually keep only the positive part, $\operatorname{PPMI}=\max(\operatorname{PMI},0)$.

A real table has one row for every word and one column for every neighbour word: 50 000 × 50 000, mostly zeros. Rows that long are clumsy. We want short rows that keep the pattern and drop the noise.

The tool is the SVD from Unit 5. It writes any matrix as $C=U\Sigma V^{\mathsf T}$: a turn, a stretch by the singular values $\sigma_1\ge\sigma_2\ge\dots$, and another turn. Big singular values are the strong patterns; small ones are mostly noise. Keep only the top $k$ and you get the best rank-$k$ copy of the table (Unit 5's layer cake). Each word's new, short vector is its row of $U_k\Sigma_k$.

For our 4 × 4 table of §5 the singular values are $\sigma\approx(9.528,\ 8.528,\ 1.143,\ 1.087)$: two big, two small. Measure a table's "energy" as the sum of the squares of all its entries — here $42+41+41+42=166$, which also equals $\sigma_1^2+\dots+\sigma_4^2$. The top two keep

$$\frac{\sigma_1^2+\sigma_2^2}{\sigma_1^2+\dots+\sigma_4^2}\approx\frac{163.5}{166}\approx98.5\%$$

of the energy, and rebuilding the table from just those two leaves an error of $\sqrt{\sigma_3^2+\sigma_4^2}\approx1.578$ — small next to entries of 4 and 5. Each word now gets two numbers:

$$\begin{aligned}\text{chai}&\approx(5.009,\,-4.032)\\ \text{coffee}&\approx(4.530,\,-4.452)\\ \text{cricket}&\approx(4.450,\,4.540)\\ \text{football}&\approx(5.037,\,4.004)\end{aligned}$$

(The SVD may flip the sign of any direction, so another program may print some of these with the opposite sign; the angles do not change.) The first number is about 5 for every word: it says "this word is used a lot". The second is the interesting one: negative for tea, positive for sport. In two numbers, $\cos(\text{chai},\text{coffee})\approx0.995$ and $\cos(\text{chai},\text{cricket})\approx0.097$. The squeeze made the tea words even more alike — it threw away the noise that kept them apart.

Weigh first, then squeeze. On real text, run the SVD on the PPMI table of §6, not on raw counts. Otherwise the loud columns like "the" take over the first direction, and it only says "how common is this word".

Now the surprise: friends of friends. Here is a new table with seven neighbour words:

Chai and tea never share a single neighbour, so their raw cosine is exactly 0. But coffee shares neighbours with both of them. The singular values are $\sqrt{68}\approx8.246$, $\sqrt{48}\approx6.928$, $\sqrt{32}\approx5.657$, $4$ and $0$, so the energy kept is 41.5% at $k=1$, 70.7% at $k=2$ and 90.2% at $k=3$.

Squeeze to $k=2$. The words get the coordinates chai $(4,0)$, tea $(4,0)$, coffee $(6,0)$, cricket $(0,\ 4.899)$, football $(0,\ 4.899)$. Chai and tea now sit on the very same line: $\cos(\text{chai},\text{tea})=\mathbf1$. Coffee, a friend of both, made them friends. The rebuilt table even fills in the blanks: it gives chai a count of 2 next to cup and next to kettle, words it never met — because coffee meets them.

Keep one more direction, $k=3$, and the new direction gives chai $-4$ and tea $+4$: it records exactly what makes them different. The cosine drops back to 0. Squeeze enough and hidden friendships appear; keep everything and you keep the differences too. Using the SVD this way on a word–document table is called latent semantic analysis (LSA) — "latent" because it finds similarities that no single count shows.

Acts II and III kept the register. The company table of §5 has a row and a column for every word: with 50 000 words that is 2.5 billion boxes, almost all of them zero. New text means counting again, and squeezing such a table with the SVD (§7) is heavy work.

In 2013 Tomas Mikolov and his team at Google played the teacher's game instead. Their method is called word2vec, and its motto could be: don't write down the gossip — train a guesser, then read its mind.

Here is the game. Slide a window along the text, one word at a time. The word in the middle is the centre word. The words up to $C$ places on either side are its context. At every stop the machine plays one of two games:

• Fill in the blank. Hide the centre word and guess it from the context. This game is called CBOW (§9).
• Guess the neighbours. Show the centre word and guess each context word. This game is called skip-gram (§10).

Take we drink hot chai every morning with $C=2$, and stop at "hot". Its context is we, drink, chai, every. CBOW makes one example from this stop: (we, drink, chai, every) → hot. Skip-gram makes four pairs: hot → we, hot → drink, hot → chai, hot → every.

Now count over the whole sentence. CBOW makes one example at each of the 6 stops: 6 examples. Skip-gram makes one pair per neighbour, and the words near the ends have fewer neighbours: $2+3+4+4+3+2=\mathbf{18}$ pairs. Keep that ratio in mind. It is the whole difference in cost between the two games (§11).

One small network plays both games. It is made of just two tables of numbers, and it works in four moves.

1. Look up. Every word owns a row in the input table $W_{\text{in}}$, which has $V$ rows of $d$ numbers. The row of word $w$ is its input vector $\mathbf v_w$. Feeding a one-hot word into the table simply picks out its row (§14 shows why).
2. Form one opinion, $\mathbf h$. CBOW averages the rows of the context words. Skip-gram just takes the centre word's row. Either way $\mathbf h$ is a list of $d$ numbers.
3. Score every word. Every word also owns a column in the output table $W_{\text{out}}$, its output vector $\mathbf u_w$. Its score is the dot product $\mathbf u_w\cdot\mathbf h$ — how well it lines up with the opinion (Unit 3).
4. Turn scores into chances with a softmax over the whole vocabulary (Unit 14), and learn from the surprise at the true word.

Read the shapes along the way: $V\to d\to V$. With $V=50\,000$ words and $d=300$, every word has to squeeze through a doorway only 300 numbers wide.

That game — fill in the blank from the words around it — is the first way word2vec learns. It is called CBOW, the continuous bag of words.

Let us play one round by hand. We use a toy model with a vocabulary of five words and vectors of just $d=2$ numbers, so that every step fits on paper. We chose the starting numbers by hand to keep the arithmetic clean; a real model starts from small random numbers.

Take the tiny sentence we drink chai daily, use a window of one word on each side, and hide the middle word, chai. The committee is drink and daily. The machine plays in four moves.

1. Look up the neighbours. Their input vectors are drink = (1, 0) and daily = (0, 1).
2. Average them. $\mathbf h=\big((1,0)+(0,1)\big)/2=(0.5,\ 0.5)$. This single point is the committee's combined opinion.
3. Score every word. Dot each output vector with $\mathbf h$: we 0, drink 0.5, chai 1, daily 0.5, cricket −1.
4. Turn scores into a guess. The softmax gives 0.135, 0.223, 0.368, 0.223, 0.050. The true word is chai, so the surprise is $-\ln0.368\approx1.00$.

Written as formulas, the four moves are:

$$\begin{aligned}\mathbf h&=\tfrac12\big(\mathbf v_{\text{drink}}+\mathbf v_{\text{daily}}\big),\\ s_w&=\mathbf u_w\cdot\mathbf h,\\ \mathbf p&=\operatorname{softmax}(\mathbf s),\\ L&=-\ln p_{\text{chai}}.\end{aligned}$$

Read them aloud. The first line asks the committee for its average opinion. The second gives every word in the vocabulary a score: how well its answer-arrow lines up with that opinion. The third turns the scores into chances that add up to 1. The fourth measures how surprised the model was by the truth.

And now the name makes sense. Bag: averaging throws away the order of the neighbours — "drink … daily" and "daily … drink" give the same $\mathbf h$, like words tipped into a bag. Continuous: the vectors are dense lists of real numbers, not counts.

How it learns. Unit 15 showed that the blame arriving at the scores of a softmax is simply prediction − truth:

$$\begin{aligned}\mathbf e=\mathbf p-\mathbf y=(&0.135,\ 0.223,\ -0.632,\\ &0.223,\ 0.050).\end{aligned}$$

Only chai's entry is negative, and negative blame means "raise me". One step (with step size $\eta=1$) now does three things:

• The answers move. Every output vector moves by $-\eta\,e_w\,\mathbf h$. Chai's is pulled toward $\mathbf h$: $(1,1)+0.632\,(0.5,0.5)=(1.316,\ 1.316)$. Every other word's is pushed away from $\mathbf h$, each in proportion to the probability it wrongly took.
• The blame reaches the committee. The blame on $\mathbf h$ is $\sum_w e_w\,\mathbf u_w=(-0.458,\ -0.458)$. It says: move the opinion toward chai's answer-arrow.
• The blame is shared equally. $\mathbf h$ was an average of two neighbours, so each member moves by half: $-\eta\cdot\tfrac12(-0.458,\ -0.458)=(0.229,\ 0.229).$ Drink becomes $(1.229,\ 0.229)$ and daily becomes $(0.229,\ 1.229)$.