Term matrices and cosine similarity

Take four Shakespeare plays and four words, and count. As You Like It uses battle once, good 114 times, fool 36 times and wit 20 times. Twelfth Night has no battle at all but 58 fools. Julius Caesar and Henry V, the two histories, have almost no fools and plenty of battles. Put the counts in a grid with one row per word and one column per play, and you already have a usable representation of each play.

This grid is a Term-document matrix. In general it has |V| rows, one per word in the vocabulary, and |D| columns, one per document, and the cell in row w and column d counts how often w occurs in d. Each column is then a list of |V| numbers: a vector. As You Like It becomes [1, 114, 36, 20], a point in a 4-dimensional space whose axes are the words. This is the basic move of Vector semantics, applied first to documents rather than words.

Notice what was thrown away. The counts do not record where in the play a word appeared, or what came before it. A document reduced to word frequencies with order discarded is a bag of words, and it is the oldest representation in information retrieval. It sounds crude, but for the question "what is this document about?" it is surprisingly strong, because topic is carried mostly by which words occur and how often.

Seeing the vectors

Four dimensions cannot be drawn, so pick two: fool on the horizontal axis and battle on the vertical one. The comedies become long arrows lying almost flat along fool (As You Like It at [36, 1], Twelfth Night at [58, 0]), while the histories become short arrows pointing up along battle (Julius Caesar at [1, 7], Henry V at [4, 13]). Comedies point one way, histories another. That is the whole promise of the vector view: similar documents have similar columns, so they point in similar directions.

Gerard Salton turned this picture into the vector space model of information retrieval: represent every document and every query as a vector of term weights, measure how close the query vector is to each document vector, and return the closest documents first (Salton, Wong and Yang 1975). A web search for "battle" is, in this model, a vector with a single non-zero entry, and Henry V wins because its column leans hardest in that direction. The measure of closeness is the cosine you will meet in concept 4. Here is a preview of what it says about the plays, computed once on the two plotted dimensions and once on all four.

On the plane, the pattern is crisp: comedies with comedies near 1, comedy with history near 0.15. On all four dimensions every pair lands between about 0.81 and 0.999, and As You Like It looks 0.945 similar to Julius Caesar. The culprit is good: it is frequent in every play, so it dominates every vector and makes all of them point roughly the same way. A word that occurs everywhere carries no information about which document you are in, and the next part's tf-idf exists precisely to turn its weight down.

Turn the same Shakespeare table sideways and read it by rows. battle becomes [1, 0, 7, 13]: a word that shows up a little in the comedies and a lot in Julius Caesar and Henry V. fool becomes [36, 58, 1, 4], the opposite profile. Without any dictionary, the rows already say that battle is a history word and fool is a comedy word, and two words with similar rows occur in similar documents.

Counting neighbors instead of documents

Documents are a coarse unit of context. A play contains thousands of words, so two words sharing a play says little more than that they share a topic. The finer alternative is to count, for each target word, which words appear right next to it. Slide the target through a large corpus, and every time it occurs, look at the words within a fixed window on each side (SLP uses ±4) and add 1 to the cell for each of them.

The result is a Term-context matrix, also called a word-word or word-context matrix. It is square, |V| x |V|: rows are target words, columns are context words, and the cell (w, c) counts how often c appeared inside the window around w. Here are four rows from Wikipedia counts, restricted to five of the context columns.

The rows sort themselves into two families. cherry and strawberry have their mass in pie and sugar; digital and information have theirs in computer and data. Plot digital at [1683, 1670] and information at [3982, 3325] on the data and computer axes and the two arrows point almost the same way, about 5° apart, even though information is more than twice as long. That is the Distributional hypothesis made concrete: two words are similar when their context vectors are similar. Each row is an Embedding of its word, a sparse one built by counting, which later parts will reweight and then replace with short dense vectors.

Ahead of concept 4, here is what the cosine, a 0 to 1 score of how closely two rows point the same way, says about these rows.

Two practical facts follow from the shape. First, almost every cell is zero: most of the |V| words never appear within four words of cherry. These are sparse vectors, and real systems store only the non-zero entries (a compressed sparse row format in SciPy, for example). Second, |V| is not the full vocabulary of the corpus. SLP notes that it is usually the 10,000 to 50,000 most frequent words, and that keeping more than about 50,000 rarely helps (SLP 5.3).

Which word is closer to fool: good or wit? Multiply the Shakespeare rows entry by entry and add. For good and fool that gives 9162; for fool and wit only 1604. By this measure good is almost six times closer to fool than wit is, which is clearly wrong: wit and fool are both comedy words, while good is just everywhere.

The measure is the Dot product, the most natural way to compare two vectors:

It is large when both vectors have large values in the same dimensions, so it does behave like a similarity measure. Vectors whose non-zero entries sit in different dimensions get 0: they are orthogonal, which for count vectors means the two words never share a context. The trouble is that a product of two numbers grows with either number. The dot product therefore depends on how big the vectors are, and the size of a vector is its Vector length:

The general lesson is SLP's: the dot product favors long vectors, and more frequent words have longer vectors, because they co-occur with many words and do so many times. Words such as of, the and you would therefore come out as the nearest neighbor of almost everything. Information retrieval met the same problem with documents: a long document has larger counts everywhere, and a raw dot product with a query rewards it for being long rather than for being on topic (Manning, Raghavan and Schütze, "Dot products").

Run an experiment on digital. Suppose the corpus were twice as large, so every count in its row doubles, from [5, 1683, 1670] to [10, 3366, 3340] over (pie, data, computer). Its dot product with information doubles too, from 12,254,481 to 24,508,962. Nothing about the meaning of digital changed, yet the similarity score did. The cure is to measure the angle between the vectors rather than their overlap, and the angle does not move at all.

Geometry supplies the formula. For any two vectors, the dot product equals the product of their lengths times the cosine of the angle θ between them. Solve for the cosine and you get Cosine similarity:

The middle form is the useful one to remember. Dividing a vector by its own length gives a unit vector, a vector of length 1 pointing the same way: [3, 4] has length 5, so its unit vector is [0.6, 0.8], and 0.6² + 0.8² = 1. The cosine is simply the dot product of the two unit vectors. Length has been removed before the comparison, so only direction is left.

Three properties follow. The range is -1 to 1: 1 for vectors pointing the same way, 0 for orthogonal vectors, -1 for opposite directions. Scaling is invisible: for any c > 0, cos(cv, w) = cos(v, w), because the c appears once in the numerator and once in |cv| = c|v| and cancels (SLP exercise 5.2). And for raw counts the range shrinks to 0 to 1, because no count is negative.

This is also why real systems often skip the division at query time. If every stored vector is normalized to length 1 once, in advance, then a plain dot product is the cosine. scikit-learn documents exactly this: cosine_similarity is the normalized dot product, and on L2-normalized data it is equivalent to linear_kernel. Vector databases that offer an "inner product" metric rely on the same identity, and it is why the embedding vectors of many retrieval models come out already normalized.

Now do the whole computation once by hand, on three words and three context dimensions (pie, data, computer): cherry [442, 8, 2], digital [5, 1683, 1670] and information [5, 3982, 3325]. The question is which of cherry and digital is closer to information under the cosine.

The picture makes the numbers obvious. Plot the words on two of the dimensions, pie upward and computer to the right. cherry stands nearly upright, because nearly all of its mass is in pie. digital and information both lie almost flat along computer. The angle between cherry and information is close to a right angle, so its cosine is close to 0; the angle between digital and information is a sliver, so its cosine is close to 1.