TF-IDF and Bag of Words: Text Representation & Search › Technical Deep Dive

Let's start with the simplest approach. Given a vocabulary $V$ with $|V|$ unique words, we can represent any document $d$ as a vector $\mathbf{v}_d$ of length $|V|$, where each element $v_{d,i}$ counts how many times word $i$ appears in document $d$.

The process involves three steps:

1. Tokenization: Split documents into individual words (tokens)
2. Vocabulary building: Collect all unique words across all documents
3. Vectorization: For each document, count occurrences of each vocabulary word

For example, if our vocabulary is $\{ \text{cat}, \text{dog}, \text{runs} \}$ and a document contains "cat runs", the vector would be $[1, 0, 1]$: one occurrence of "cat", zero of "dog", and one of "runs".

This representation has several properties:

• Fixed dimensionality: All documents map to vectors of the same length
• Sparsity: Most documents use only a small fraction of the vocabulary, so most vector elements are zero
• Order independence: "cat runs" and "runs cat" produce identical vectors

The sparsity is important. In practice, vocabularies can contain tens of thousands of words, but individual documents might use only hundreds. This makes sparse matrix representations efficient for storage and computation.

Term frequency measures how often a word appears in a document. The simplest version is the raw count:

$$\text{TF}(t, d) = \text{count of term } t \text{ in document } d$$

However, longer documents naturally contain more words. To make frequencies comparable across documents of different lengths, we often normalize by document length:

$$\text{TF}(t, d) = \frac{\text{count of term } t \text{ in document } d}{\text{total words in document } d}$$

This gives us a proportion: what fraction of the document consists of this word? Normalized TF values range from 0 to 1, with 1 meaning the entire document consists of that single word.

Another common normalization uses logarithmic scaling to dampen the effect of very frequent words:

$$\text{TF}(t, d) = 1 + \log(\text{count of term } t \text{ in document } d)$$

This formula ensures that doubling the word count doesn't double the TF score, which helps prevent extremely common words from dominating the representation.

While term frequency tells us how important a word is within a document, inverse document frequency measures how distinctive it is across the entire collection. The key insight: words that appear in many documents are less informative than words that appear in few.

The inverse document frequency is calculated as:

$$\text{IDF}(t, D) = \log \frac{|D|}{|\{d \in D : t \in d\}|}$$

where $|D|$ is the total number of documents, and $|\{d \in D : t \in d\}|$ is the number of documents containing term $t$.

Let's break this down:

• If a word appears in all documents, the denominator equals $|D|$, so $\text{IDF} = \log(1) = 0$
• If a word appears in only one document, the denominator is 1, so $\text{IDF} = \log(|D|)$
• Words appearing in fewer documents get higher IDF scores

The logarithm serves two purposes: it compresses the scale (so IDF doesn't grow linearly with collection size), and it makes the metric more interpretable. Without the log, a word appearing in 1 out of 1000 documents would have IDF = 1000, while one appearing in 500 documents would have IDF = 2, a 500x difference. The logarithm smooths this out.

Some implementations add 1 to avoid division by zero and to ensure all terms get at least some weight:

$$\text{IDF}(t, D) = \log \frac{|D| + 1}{|\{d \in D : t \in d\}| + 1}$$

TF-IDF multiplies term frequency by inverse document frequency:

$$\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D)$$

This creates a scoring system where:

• High TF-IDF: Words that are frequent in a specific document but rare across the collection
• Low TF-IDF: Words that are either rare in the document or common across many documents

The multiplication is crucial. A word with high TF but low IDF (common everywhere) gets downweighted. A word with low TF but high IDF (rare but distinctive) gets some weight. Only words with both high TF and high IDF get the highest scores.

This weighting scheme automatically identifies the most distinctive words in each document, exactly what we want for tasks like search, classification, and topic modeling.