Notes / Natural Language Processing / Note 3 of 8

The vector space model

How a search engine finds the chapter a query is about, by turning words into weights, chapters into vectors and relevance into an angle, and how BM25 refines the weights.

Readers remember the chapters of Don Quixote by their adventures: the windmills, the galley slaves, the lions, the puppet show. A search engine has only the words. Given a few of them, it must find the chapters they are about, out of the book's 126, 52 in part I and 74 in part II. The vector space model turns every chapter, and the query too, into a vector with one number per word of the vocabulary, and ranks the chapters by how closely they point the same way as the query:

Which chapter has the windmills?
Each chapter, a column of counts
Chapters ranked by their angle to the query

Section 1 prepares the words, section 2 builds the vectors, section 3 weighs them, section 4 ranks the chapters by angle, and section 5 replaces the weights with BM25's, which search engines still use as a standard.

1Stopwords and the pipeline

The book's most frequent words, the head of Zipf's curve from the first note, are the invariable ones from the second: the, and, of, to, along with pronouns and auxiliary verbs. They appear in every chapter, so they say nothing about which chapter is which. A search engine drops them as stopwords. Snowball's English list has 174 of them, and 161 appear in the book: about 1% of its different words, yet 55% of its tokens. Without them, the text keeps less than half its length and loses almost none of the words that tell chapters apart.

Dropping stopwords is one step of a pipeline that turns raw text into a vocabulary: split it into sentences, then into tokens, lowercase them, drop the stopwords and reduce each word to its lemma. Each step after the tokens is optional, and the figure lets you switch them on and off, both on the first line of chapter I and on the whole book.

Switch the steps on and off with the buttons. A dropped word stays faint, struck through.

Stopwords are not always noise. In the line above, without them, I have no desire to call to mind becomes desire call mind: the no is gone, and with it the line's meaning. A search for an exact phrase, or a task where negation matters, keeps them.

2The term-document matrix

After the pipeline, each chapter is a bag of words with their counts. Write the counts in a table with a row for each word of the vocabulary and a column for each chapter: this is the term-document matrix. Each column lists one chapter's counts, a vector

d_j = (w_1,j, …, w_V,j),

where w_i,j is the weight of word i in chapter j, for now its count. In the vector space model each word of the vocabulary is a dimension and each chapter a point in that space, here of 14,711 dimensions. Two of them at a time can be drawn: pick a pair of words, and every chapter becomes a point whose coordinates are its counts of the two.

Click a point, or move from chapter to chapter with the arrow keys.

A chapter's arrow has a direction and a length. The direction says which words dominate: the chapters of Sancho's government lean toward sancho. The length depends mostly on how long the chapter is, since a long chapter repeats everything more. Section 4 ranks by the first and ignores the second.

3Weights

The count is a poor weight, for two reasons. A word in every chapter tells none of them apart, however often it appears; and a word used ten times is not ten times as telling as a word used once. The usual weights fix both. The first scales by the chapter's most frequent word, or damps the count with a logarithm:

tf_i,j = f_i,jmax_l f_l,j, tf^log_i,j = 1 + log₁₀ f_i,j (for f_i,j > 0),

where f_i,j counts word i in chapter j: 28 uses weigh 2.45, not 28. The second looks at the whole collection, N chapters, of which n_i contain the word, and rewards the rare:

idf_i = log₁₀ Nn_i, w_i,j = tf_i,j · idf_i.

A word in every chapter gets idf_i = log₁₀ 1 = 0 and drops out on its own; the product, tf-idf, is high for a word frequent in this chapter and rare in the rest. The figure shows five chapters' ten heaviest words under each weighting; tf-idf here uses the logarithmic tf.

Pick a chapter and a weighting, then a word to see its calculation.

Under the count the chapters look alike, led by don, quixote and said. Under tf-idf each one shows its own story, its people, objects and places, and the words found in all 126 chapters, chapter, said and will, weigh 0.

4Ranking by angle

A query is a short text, so it becomes a vector like any chapter, with a weight for each of its words and 0 for the rest. Which chapters are closest to it? Distance is a poor answer: a long chapter has a long vector, far from a short query even when it points the same way. The angle ignores length. Its cosine is the dot product divided by both lengths:

cos(q, d) = q · d‖q‖ ‖d‖ = ∑_i q_i d_i√∑_i q_i² √∑_i d_i².

It is 1 when the two vectors point the same way and 0 when they share no word; with weights that are never negative, it is never below 0. The figure goes back to the plane of section 2, where the query is a point like any chapter, placed by how many times it uses each of the two words: the red point starts at (6, 2), as if the query said sancho six times and quixote twice. Drag it, and compare the chapters closest in angle with the closest in distance.

Drag the query’s red point, or move it with the arrow keys. The close-up shows the corner near the origin, where most chapters lie.

By angle, the closest chapters are those that use the two words in the query's proportion, whatever their length. By distance, they are the chapters as long as the query is short, whatever they are about. A search engine ranks by the cosine over all the dimensions at once, with tf-idf weights for both the query and the chapters.

5BM25

BM25 is a weighting that search engines still use as a standard. A chapter's score for a query is the sum of its weights for the query's words:

w_i,j = f_i,j (k₁ + 1)k₁ [(1 − b) + b l(d_j) / l_avg] + f_i,j · log₁₀ Nn_i,

where l(d_j) is the chapter's length in words and l_avg the average, 1,441 here. The first factor saturates: in a chapter of average length, with k₁ = 1.2, one use weighs 1, two weigh 1.38 and twenty only 2.08, under a ceiling of k₁ + 1 = 2.2. The bracket corrects for length: a long chapter needs more uses to weigh as much, and b sets how much, from 0, no correction, to 1, full correction. The values b ≈ 0.75 and k₁ ≈ 1.2 come from experiments, not from theory: they rank well on collections where people judged which documents answer which queries. Many implementations replace log(N/n_i) with a smoothed form, log((N − n_i + 0.5)/(n_i + 0.5)), with the same idea.

The figure searches the book's 126 chapters. Build a query with the words, and compare the cosine of section 4, over tf-idf, with BM25.

k₁

Pick one or more words for the query, then a ranking.

Ask for lions. The cosine ranks first chapter XXX of part II, short, where lions appears 7 times, all in Don Quixote's new title, the Knight of the Lions. BM25 ranks first chapter XVII, the adventure of the lions itself, with 19 uses in a chapter twice as long. The cosine divides by the length of the whole chapter vector, which favors short chapters; BM25's saturation and its milder length correction let the 19 uses count.

6Summary

The note's ideas in NumPy. f is the term-document matrix of counts, a row per word and a column per chapter, l the chapters' lengths, w_q the query's vector and q the rows of its words.

Normalized tf

tf_i,j = f_i,j / max_l f_l,j

tf = f / f.max(axis=0)

Logarithmic tf

1 + log₁₀ f_i,j

g = np.maximum(f, 1)
tf_log = 1 + np.log10(g)
tf_log *= f > 0

idf

log₁₀(N/n_i)

N = f.shape[1]
n = (f > 0).sum(axis=1)
idf = np.log10(N / n)

tf-idf

w_i,j = tf_i,j · idf_i

w = tf_log * idf[:, None]

Cosine

cos(q, d) = q · d / (‖q‖ ‖d‖)

norm = np.linalg.norm
cos = w.T @ w_q / (
    norm(w, axis=0)
    * norm(w_q))

BM25

f (k₁ + 1)k₁ [1 − b + b l/l_avg] + f · idf

r = l / l.mean()
k = k1 * (1 - b + b * r)
bm = f * (k1+1) / (k+f)
s = bm[q] * idf[q, None]
score = s.sum(axis=0)

The note's data: the stopwords are Snowball's lists, and the lemmas come from Michal Měchura's lemmatization lists (ODbL).