Vector Semantics and Embeddings

The n-gram model and naive Bayes share a limitation: both treat a word as an atom with no internal structure. Ongchoi, water spinach, and kangkong are three distinct symbols with nothing in common, even though they name the same vegetable. Under that view the only thing a model knows about a word is whether it is identical to another word. Every notion of similar meaning — that delicious and tasty are close, that cat and dog are closer than cat and theorem — is invisible.

Vector semantics repairs this. It represents each word as a point in a high-dimensional space, a vector, positioned so that words with similar meanings sit near each other.¹ A classifier trained on delicious reviews can then generalize to a review that says tasty, because the two words land in the same neighborhood. Meaning is no longer a discrete label but a position in a geometric space.

The distributional hypothesis

Where does the geometry come from? The answer, from 1950s linguistics, is that meaning can be read off from use. Suppose you have never met the word ongchoi but you see it in these sentences:

Ongchoi is delicious sauteed with garlic. Ongchoi is superb over rice. ...ongchoi leaves with salty sauces...

and you have separately seen spinach sauteed with garlic over rice, chard stems and leaves are delicious, and collard greens and other salty leafy greens. The company ongchoi keeps — garlic, rice, delicious, salty, leaves — is the company those leafy greens keep. You can conclude that ongchoi is a leafy green vegetable, having never seen it on a plate.¹ This is the distributional hypothesis: words that occur in similar contexts tend to have similar meanings, so a word's distribution over contexts is a usable proxy for its meaning.

The plan follows directly. Count, for each word, the contexts it appears in; store those counts as a vector; and let vector geometry stand in for meaning. Everything in this lesson builds on this idea.

Words and vectors: co-occurrence matrices

The raw material is a co-occurrence matrix, a table of how often words appear together. Two versions matter, differing only in what a context is.

The term-document matrix

In a term-document matrix each row is a word in the vocabulary and each column is a document; cell $(t,d)$ holds the number of times word $t$ occurs in document $d$. Four words across four Shakespeare plays give a $4\times 4$ slice:²

Read the matrix two ways. Each column is a document vector: As You Like It is $[1,114,36,20]$, a point in a space whose dimensions are the four words. This is the vector space model of information retrieval — documents with similar word counts are similar documents, and a query is just another vector to compare against.² Each row is a word vector: battle is $[1,0,7,13]$, a point in a space whose dimensions are the four plays. Similar words occur in similar documents, so the row for fool $[36,58,1,4]$ and the row for wit$[20,15,2,3]$ — both high in the comedies, low in the histories — come out close.

The word-word matrix

For word meaning specifically, a finer context works better than a whole document. The word-word matrix (also term-term or term-context matrix) has both rows and columns labeled by words; cell $(w,c)$ counts how often context word $c$ occurred near target word $w$ — typically within a window of $\pm 4$ words across a training corpus.³ The matrix is $|V|\times |V|$. A hand-picked slice from Wikipedia counts:

The rows already carry meaning. cherry and strawberry both live near pie and sugar, so their vectors point the same way; digital and information both live near computer and data, so they cluster elsewhere. In a real corpus $|V|$ runs from 10,000 to 50,000, and almost every cell is zero — these are sparse, long vectors.³

Cosine: measuring similarity

Two words are similar when their vectors point the same direction. The standard measure is the cosine of the angle between them, built from the dot product (inner product),

The dot product is large when the two vectors have big values in the same dimensions, and zero for orthogonal vectors with no shared dimensions. But used raw it is a poor similarity metric: it favors long vectors. Frequent words co-occur with many things, so their vectors have large entries and large dot products with everything, similarity or not.⁴ The fix is to divide out the lengths, where the length of a vector is $\Vert \mathbf{v}\Vert =\sqrt{{\sum }_i{v}_i^2}$. Dividing the dot product by both lengths gives exactly the cosine of the angle, since $\mathbf{a}\cdot \mathbf{b}=\Vert \mathbf{a}\Vert \Vert \mathbf{b}\Vert \cos \theta$:

For the non-negative count vectors here the cosine runs from $0$ (orthogonal, share nothing) to $1$ (identical direction). Two vectors are more similar when the angle between them is smaller and the cosine is larger.

On the actual Wikipedia counts, $\cos ({\mathbf{v}}_{\text{digital}},{\mathbf{v}}_{\text{information}})=0.996$ while $\cos ({\mathbf{v}}_{\text{cherry}},{\mathbf{v}}_{\text{information}})=0.017$: the measure puts information far closer to digital than to cherry, as it should.⁴

Weighting: why raw counts mislead

Raw frequency is skewed and undiscriminating. The most frequent context words — the, it, they — sit near everything and so tell you almost nothing about which words are alike. Yet it is the words that appear in only a few, specific contexts — pie, say — that are informative about cherry. Raw counts get this backwards: they reward ubiquity. Two weighting schemes fix it, one per matrix type.⁵

TF-IDF, for term-document matrices

TF-IDF balances two opposing intuitions, and is the product of two terms.

The term frequency rewards a word for appearing often in a document, but with diminishing returns — a word seen 100 times is not 100 times more relevant than a word seen once — so we squash the count with a log:

The inverse document frequency penalizes a word for appearing in many documents. A word confined to a few documents discriminates them from the rest; a word in every document (like good across all 37 Shakespeare plays) discriminates nothing. With $N$ documents in the collection and ${\mathrm{df}}_t$ the number containing term $t$,

A word in all $N$ documents gets $\mathrm{idf}={\log }_{10}(1)=0$; a word in one gets the maximum. The tf-idf weight is their product,

Under tf-idf the dimension for good collapses to $0$ everywhere — it appears in every play, so its idf is zero — and the near-ubiquitous fool is sharply downweighted, leaving the discriminative words to carry the meaning.⁵

Worked example: tf-idf on the Shakespeare matrix

Take the collection of $N=37$ Shakespeare plays and weight the four-word slice above. First the idf column, from each word's document frequency. good appears in all $37$ plays, so ${\mathrm{df}}_{\text{good}}=37$ and ${\mathrm{idf}}_{\text{good}}={\log }_{10}(37/37)=0$. fool appears in $36$, giving ${\mathrm{idf}}_{\text{fool}}={\log }_{10}(37/36)=0.012$. wit appears in $34$, giving ${\log }_{10}(37/34)=0.037$, and battle in $21$, giving ${\log }_{10}(37/21)=0.246$ — the rarest of the four, so the most discriminative.

Now the tf-idf cell for wit in As You Like It. The raw count is $20$, so the squashed term frequency is $\mathrm{tf}={\log }_{10}(20+1)={\log }_{10}(21)=1.322$, and the weight is $w=\mathrm{tf}\times \mathrm{idf}=1.322\times 0.037=0.049$. The same procedure over the whole slice replaces every count with a weight:

Two things happened. The good row is now zero everywhere — a word in every document carries no information about which document you are in, and its idf of $0$ enforces exactly that. And battle, once a near-invisible count of $1$ in As You Like It, is now the row with the largest weights, because its rarity across the collection makes each occurrence informative. The weighting inverted the raw ranking: frequency alone had good dominating, and tf-idf shifts the discriminative power to battle.⁵

PPMI, for word-word matrices

When the dimensions are context words rather than documents, the natural question is different: does word $w$ co-occur with context $c$ more than we would expect by chance? Pointwise mutual information measures exactly that — the log ratio of the joint probability to the product of the marginals:⁶

The numerator is how often $w$ and $c$ actually occur together; the denominator is how often they would if they were independent. A ratio above $1$ (positive PMI) means association; below $1$ (negative PMI) means the pair co-occurs less than chance. But negative PMI is unreliable — asserting that two words co-occur less than chance demands an enormous corpus to establish — so in practice we clip it to zero, giving positive PMI:

Given a co-occurrence matrix with counts $f_{ij}$, the probabilities are the maximum-likelihood estimates: $p_{ij}=f_{ij}/{\sum }_{ij}{f}_{ij}$, with $p_{i\ast }$ and $p_{\ast j}$ the row and column marginals. PPMI has one known flaw — it is biased toward rare events, giving very infrequent words inflated scores. The common fix raises the context probability to a power $\alpha =0.75$, which inflates $P(c)$ for rare contexts and so damps their PMI.⁶ The same $\alpha =0.75$ correction reappears inside word2vec.

Worked example: PPMI from co-occurrence counts

Carry the whole computation through on a five-context slice of Wikipedia counts, with the row and column marginals attached. Pretend, for arithmetic's sake, that these are the only words and contexts in the corpus, so the grand total is ${\sum }_{ij}{f}_{ij}=11716$.⁶

Compute $\mathrm{PPMI}(\text{information},\text{data})$. The joint probability is the cell over the grand total, $p_{ij}=3982/11716=0.3399$. The two marginals are $p_{i\ast }=P(\text{information})=7703/11716=0.6575$ and $p_{\ast j}=P(\text{data})=5673/11716=0.4842$. Then

A small positive value: information and data co-occur slightly more than chance. Now a pair that co-occurs less than chance, cherry and computer: the joint is $2/11716=0.00017$, the marginals are $486/11716=0.0415$ and $4997/11716=0.4265$, so ${\log }_2(0.00017/(0.0415\times 0.4265))={\log }_2(0.0096)=-6.7$. Negative, so PPMI clips it to $0$ rather than assert a co-occurrence deficit that cannot be reliably measured. Applying this to every cell turns the raw counts into the PPMI matrix:

The block structure the raw counts only hinted at is now explicit: cherry and strawberry carry all their weight on pie and sugar, digital and information on computer and data, and the cross terms are zeroed out. The two fruit rows are close, the two tech rows are close, and the two groups are orthogonal — similarity is now encoded in the geometry, through association rather than raw frequency.⁶

From counts to embeddings

The vectors built so far already work: cosine over a PPMI-weighted word-word matrix recovers real similarity, and every dimension is an interpretable context word. But they have two practical defects. They are long — one dimension per vocabulary word, so tens of thousands wide — and sparse, almost all zeros. The next lesson keeps the distributional idea but compresses it, learning a short, dense vector per word whose dimensions mean nothing individually yet capture similarity better than any count matrix. That is the move from counting contexts to predicting them.

This continues in Static Word Embeddings: word2vec and After.