How do you turn a document into numbers?

To compare documents mathematically, we need a numerical representation of their text. We'll build a bag-of-words vector from a sentence, then use it to measure similarity between documents. Along the way, we'll see why word counts alone can give common words too much influence and how tf-idf changes their weights.

Tokenization

Before we can count words, we need to decide how to split the text. A tokenizer divides it into units called tokens. Let's start with this sentence:

we sat on the bank of the river

Splitting on spaces gives us eight tokens, with "the" appearing twice.

wesatonthebankoftheriver

In other text, the boundaries can be less clear. We might treat "don't" as one token or split it into two, and punctuation in "U.S." needs different handling from a sentence-ending period. A tokenizer that assigns a separate token to each whole word also needs a way to handle words outside its vocabulary.

Subword tokenization and BPE

Subword tokenizers let us represent an unfamiliar word using smaller pieces. Common words can stay whole, while less common words are split into parts. Byte pair encoding, or BPE, learns these pieces by repeatedly merging the most frequent pair of adjacent symbols [1].

Starting from individual characters, suppose our training text contains "hug" 10 times, "pug" 5 times, "pun" 12 times, "bun" 4 times, and "hugs" 5 times. The pair "u g" appears 20 times across "hug", "pug", and "hugs", so we merge it first. Recounting the pairs after each merge gives:

1. "u" + "g" becomes "ug" (20 occurrences).
2. "u" + "n" becomes "un" (16 occurrences, in "pun" and "bun").
3. "h" + "ug" becomes "hug" (15 occurrences, in "hug" and "hugs").

After these merges, we can represent "hug" with one token and "hugs" with "hug" + "s". We can also represent "bugs", which did not appear in the training text, as "b" + "ug" + "s".

The same process, applied to a much larger collection of text, produces a vocabulary of common pieces. GPT-2's BPE tokenizer keeps "bank" whole and splits "riverbank" and "tokenization" into smaller parts:

bank→

bank

riverbank→

riverbank

tokenization→

tokenization

For the document vectors we'll build below, we'll use whole words as tokens. This lets us work directly with the counts in our sentence.

Term frequency

We now count how often each token appears in the document. This is its term frequency, written $\text{tf}(w, d)$ for word $w$ in document $d$. In our sentence, $\text{tf}(\text{the}, d) = 2$; every other word appears once.

the2

we1

sat1

on1

bank1

of1

river1

$$\mathrm{tf}(\mathrm{the})=2$$$$\mathrm{tf}(w)=1\text{ for every other word }w$$

Keeping these counts gives us a bag of words. We retain how often each word occurs and discard its position in the sentence. To use the counts in a calculation, we need a consistent place for each word in a vector.

Building a document vector

We fix a vocabulary and assign each token a position. Every document uses the same positions, so the entry for "river" always refers to "river".

A single token can be represented as a one-hot vector, with 1 in its position and 0 everywhere else. We build a document vector by adding the one-hot vectors of all its tokens. For our sentence, this gives 2 in the position for "the", 1 for each of the other six words, and 0 for every word that does not appear.

a0

$\color{#72746c}{\vdots}$

bank1

$\color{#72746c}{\vdots}$

of1

on1

$\color{#72746c}{\vdots}$

river1

sat1

$\color{#72746c}{\vdots}$

the2

$\color{#72746c}{\vdots}$

we1

$\color{#72746c}{\vdots}$

zebra0

7 non-zero slots out of tens of thousands. Vectors that are mostly zeros are called sparse.

A vocabulary may contain tens of thousands of words, while a short document uses only a few of them. Its vector is therefore sparse, meaning most entries are zero. We can store just the non-zero entries, such as "the: 2, bank: 1, river: 1", instead of storing every position.

Cosine similarity

With documents represented in the same vector space, we can compare their word usage [2]. Consider three documents:

• A: "we sat on the bank of the river"
• B: "the river was high"
• C: "she opened an account at the bank"

Placing their vectors side by side gives us a term-document matrix, with a row for each vocabulary word and a column for each document. The figure shows five rows; the similarity calculations use every word in the documents.

	A	B	C
bank	1	0	1
river	1	1	0
account	0	0	1
the	2	1	1
sat	1	0	0

$$\cos(\mathbf{A},\mathbf{B})=\color{#c9342d}{0.47}$$$$\cos(\mathbf{A},\mathbf{C})=0.36$$

Cosine similarity compares the directions of two vectors. For document vectors $\mathbf{A}$ and $\mathbf{B}$, we calculate:

$$\cos(\mathbf{A}, \mathbf{B}) = \frac{\mathbf{A} \cdot \mathbf{B}}{\lVert \mathbf{A} \rVert \, \lVert \mathbf{B} \rVert}$$

The dot product in the numerator multiplies the counts for each matching word and adds the results. Dividing by the vector lengths normalizes the score, so simply repeating a document does not make it more similar to another one. For non-negative count vectors, the score ranges from 0 when no words overlap to 1 when the words occur in the same proportions.

Let's calculate the score for A and B. They share "the", with counts 2 and 1, and "river", with counts 1 and 1. Their dot product is therefore $2 \cdot 1 + 1 \cdot 1 = 3$. A has one count of 2 and six counts of 1; B has four counts of 1. Their lengths are:

Substituting these values gives:

$$\cos(\mathbf{A}, \mathbf{B}) = \frac{3}{\sqrt{10} \cdot 2} \approx 0.47$$

The same calculation gives $\cos(\mathbf{A}, \mathbf{C}) \approx 0.36$. A is closer to B, but both scores are strongly influenced by "the", which appears in all three documents. We need a way to reduce the weight of words that provide little information about a document's topic.

Document frequency and tf-idf

We can use the whole collection of documents to decide which words deserve more weight. A word that appears in only a few documents can help distinguish them, while a word that appears everywhere is less informative [3].

The document frequency, $\text{df}(w)$, counts how many documents contain word $w$. For a collection of $N$ documents, we calculate its inverse document frequency, or idf, as:

$$\text{idf}(w) = \ln \frac{N}{\text{df}(w)}$$

Multiplying the term frequency by this value gives the tf-idf weight:

$$\text{tf-idf}(w, d) = \text{tf}(w, d) \times \ln \frac{N}{\text{df}(w)}$$

A word found in every document has an idf of 0. Words found in fewer documents receive larger weights. For our three documents, $N = 3$:

• "the" appears in all three, so its idf is $\ln(3/3) = 0$. Its weight in A changes from 2 to 0.
• "bank" appears in A and C, and "river" in A and B. Each receives an idf of $\ln(3/2) \approx 0.41$.
• "sat" appears only in A, so its idf is $\ln 3 \approx 1.10$.

tf (count)tf-idf (weight)

the

2

0.00

sat

1

1.10

bank

1

0.41

river

1

0.41

$$\mathrm{tf\text{-}idf}(w)=\mathrm{tf}(w)\times\ln\frac{3}{\mathrm{df}(w)}$$

We can now replace the raw counts with tf-idf weights and calculate cosine similarity again. The scores become $\cos(\mathbf{A}, \mathbf{B}) \approx 0.05$ and $\cos(\mathbf{A}, \mathbf{C}) \approx 0.03$. With "the" contributing nothing, A's overlap with B comes from "river", and its overlap with C comes from "bank". A remains closer to B, although both scores are lower because much of the original overlap came from the common word.

What a bag of words throws away

Weighting makes the word counts more useful for comparison, but the vector still leaves out word order. "dog bites man" and "man bites dog" contain the same words with the same counts, so they have identical vectors.

dogbitesman

↓

bites1

dog1

man1

$\color{#c9342d}{=}$

manbitesdog

↓

bites1

dog1

man1

We can retain some local order by adding vocabulary entries for adjacent word pairs, called bigrams, or longer sequences, called n-grams. "dog bites" and "bites dog" then occupy different positions. This also makes the vocabulary larger and the vectors sparser.

Word choice creates another limitation. "river" and "stream" occupy separate positions even when they refer to the same thing, so documents with similar meanings may have little word overlap.

In our example, "bank" has the opposite problem: A uses it for the side of a river, while C uses it for a financial institution. Both meanings occupy the same position. Tf-idf can adjust the importance of that word, but it cannot distinguish what it means in each sentence.

References

1. Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL. doi:10.18653/v1/P16-1162 ↩
2. Salton, G., Wong, A., & Yang, C. S. (1975). A Vector Space Model for Automatic Indexing. Communications of the ACM 18(11). doi:10.1145/361219.361220 ↩
3. Spärck Jones, K. (1972). A Statistical Interpretation of Term Specificity and Its Application in Retrieval. Journal of Documentation 28(1). doi:10.1108/eb026526 ↩