TF-IDF Weighting

Term Frequency (TF) measures how often a term `t` occurs in a document `d`, capturing the intuition that a word mentioned five times is more central to that document's topic than a word mentioned once. Raw counts are usually transformed — most commonly with a logarithm — because the difference between 1 and 2 occurrences matters more than the difference between 50 and 51.

Inverse Document Frequency (IDF) measures how rare a term is across the entire document collection `D`. If a term appears in nearly every document, it carries little information about what distinguishes any particular document, so IDF pushes its weight down. If a term appears in only a few documents, it is highly discriminative, so IDF pushes its weight up. Formally, `df(t)` is the number of documents containing `t` at least once, and IDF is a decreasing function of `df(t)`.

TF-IDF is the product of these two signals: ``` w(t, d) = tf(t, d) × idf(t) ``` The multiplication is the crucial design choice: a term only receives high weight when it is both locally frequent (informative about this document) and globally rare (informative about the corpus). A term that is locally frequent but globally common (like "said" in news text) gets cancelled out by a near-zero IDF. A term that is globally rare but never appears in this document contributes zero because `tf(t,d) = 0`. Each document is then represented as a vector in a `|V|`-dimensional space (`V` = vocabulary), turning text similarity into geometric similarity — the basis of the classic vector space model for information retrieval, building directly on the Bag-of-Words Model representation.

Step 1 — Build vocabulary and counts. Tokenize every document and build a term-document count matrix, or more efficiently an inverted index mapping each term to the list of documents it appears in and its count there.

Step 2 — Compute term frequency. For each term-document pair, compute a TF score. The raw count `count(t,d)` is one option; a common alternative is log-scaled TF: ``` tf(t, d) = 1 + log10(count(t, d)) if count(t, d) > 0 tf(t, d) = 0 otherwise ``` Log-scaling compresses the effect of very high counts, reflecting diminishing marginal informativeness.

Step 3 — Compute document frequency and inverse document frequency. For each term, count `df(t)`, the number of documents it appears in at least once. Then: ``` idf(t) = log10(N / df(t)) ``` where `N = |D|` is the total number of documents. A smoothed variant adds 1 to the denominator and/or numerator to avoid division by zero and to prevent terms appearing in every document from getting exactly `idf = 0` in edge cases: ``` idf(t) = log( (1 + N) / (1 + df(t)) ) + 1 (scikit-learn style smoothing) ```

Step 4 — Multiply. Combine the two into a single weight per term-document pair, forming the TF-IDF vector for each document.

Step 5 — Normalize (optional but standard). L2-normalize each document vector so that document length does not artificially inflate similarity scores: ``` v(d) = w(d) / ||w(d)||_2 ```

Step 6 — Use the vectors. Compute cosine similarity between a query vector and each document vector for search, or feed the TF-IDF vectors directly into a downstream classifier or clustering algorithm. ```pseudocode function BUILD_TFIDF(documents):

# documents: list of D token lists N = length(documents) df = empty map from term -> integer # document frequency tf_raw = empty map from (term, doc_id) -> integer

# Pass 1: raw counts and document frequency for doc_id, tokens in enumerate(documents): seen_in_this_doc = empty set for term in tokens: tf_raw[(term, doc_id)] += 1 if term not in seen_in_this_doc: df[term] += 1 seen_in_this_doc.add(term)

# Pass 2: compute IDF once per term idf = empty map from term -> float for term in df.keys(): idf[term] = log10(N / df[term])

# Pass 3: compute weighted, normalized vectors vectors = empty map from doc_id -> sparse vector for doc_id in range(N): vec = empty sparse vector for term in distinct_terms(documents[doc_id]): count = tf_raw[(term, doc_id)] tf = 1 + log10(count) # log-scaled TF, count > 0 guaranteed vec[term] = tf idf[term] norm = sqrt(sum(vv for v in vec.values())) if norm > 0: for term in vec.keys(): vec[term] = vec[term] / norm vectors[doc_id] = vec return vectors, idf

function COSINE_SIMILARITY(vec_a, vec_b): dot = 0 for term in vec_a.keys(): if term in vec_b: dot += vec_a[term] * vec_b[term] return dot # vectors already L2-normalized, so dot = cosine ``` The pseudocode handles two edge cases explicitly: `count(t,d) = 0` never reaches the `log10` call (the loop only iterates over terms actually present in the document, so `count > 0` is guaranteed), and the zero-vector case (an empty document) is guarded before dividing by `norm`.

Time complexity. Let `N = |D|` be the number of documents and `L` the average document length in tokens. Building the raw counts and document-frequency table requires a single pass over every token in every document: `O(N · L) = O(total tokens in corpus)`. Computing IDF requires one pass over the vocabulary `|V|`: `O(|V|)`. Computing the final weighted vectors requires, for each document, one pass over its distinct terms, which is at most `O(L)` per document, so `O(N · L)` overall. Total: ``` O(total tokens) + O(|V|) = O(N · L) ``` since `|V| ≤ total tokens` always. This is linear in corpus size, not quadratic — the naive mistake would be to compute `df(t)` by rescanning the whole corpus for every term, which costs `O(|V| · N · L)`; using a single pass with a hash map avoids this entirely.

Space complexity. The count table and vocabulary require `O(|V| + total tokens)` in the worst case, but because most terms appear in few documents, the count matrix is stored sparsely, typically as an inverted index: for each term, a posting list of `(doc_id, count)` pairs. Sparse storage costs `O(number of nonzero (term, doc) pairs)`, which is far smaller than the dense `N × |V|` matrix for any real corpus, since a document only ever uses a tiny fraction of the vocabulary.

Query time. Computing cosine similarity between a query and all `N` documents naively costs `O(N · |V|)`, but using the inverted index — only visiting documents that share at least one term with the query — costs `O(sum over query terms of |posting list|)`, which is typically far smaller than `N`.

Correctness argument. The core claim to justify is that TF-IDF weighting produces a more discriminative representation than raw counts. Consider two documents sharing a stopword `t` with `df(t) = N` (appears in every document). Then: ``` idf(t) = log(N / N) = log(1) = 0 ``` so `w(t, d) = tf(t,d) × 0 = 0` for every document — the term contributes nothing to any similarity computation, which is exactly the desired behavior since a term present everywhere carries zero information about which documents are related. Conversely, a term appearing in exactly one document has maximal `idf(t) = log(N)`, the largest possible value, and it can only ever contribute weight to that one document, correctly marking it as highly document-specific. More formally, IDF is a monotonically decreasing function of `df(t)`: as `df(t)` increases from `1` to `N`, `idf(t) = log(N/df(t))` decreases monotonically from `log(N)` to `0`. This monotonicity is the entire correctness property required: rarer terms (small `df`) always receive weight greater than or equal to more common terms, for any fixed TF. This matches the information-theoretic intuition that a term seen in `df(t)` out of `N` documents carries roughly `log(N / df(t))` bits of information about document identity — IDF is literally an empirical estimate of self-information under a uniform prior over documents.

Tradeoffs. TF-IDF is a bag-of-words method: it discards word order, syntax, and polysemy — "bank" (river) and "bank" (finance) get one shared weight regardless of context. It also has no notion of semantic similarity between different words ("car" and "automobile" are orthogonal dimensions). These limitations motivate the move toward dense, learned embeddings, but TF-IDF remains attractive because it is deterministic, requires no training, is fully interpretable (every weight traces to a count), and is extremely cheap to compute and update incrementally as new documents arrive.

Consider a tiny corpus of three documents: ``` d1: "the cat sat on the mat" d2: "the cat sat on the sofa" d3: "the dog barked loudly" ``` `N = 3`. After removing pure counting (no stopword removal, to show IDF handles "the" automatically), the document frequencies are:

Now compute TF-IDF for document `d1` ("the cat sat on the mat"), using log-scaled TF `tf(t,d) = 1 + log10(count(t,d))`:

Notice that "the" appears twice in `d1` — the single most frequent term by raw count — yet its final weight is exactly zero, because it appears in every document and contributes nothing to distinguishing `d1` from anything else. Meanwhile "mat," appearing only once, receives the highest weight of any term in the document, because it is unique to `d1` in this corpus. This is the entire point of TF-IDF made concrete: raw frequency and final importance can be inversely related. L2-normalizing the raw weight vector `[0.176, 0.176, 0.176, 0.477]` (norm ≈ `sqrt(0.176²·3 + 0.477²) ≈ 0.559`) gives the final unit vector `≈ [0.315, 0.315, 0.315, 0.853]` for the terms {cat, sat, on, mat}. Repeating this for `d2` yields a vector sharing high weight on {cat, sat, on} but with "sofa" instead of "mat," so cosine similarity between `d1` and `d2` will be moderately high (they share three discriminative-ish terms) while similarity with `d3` (which shares only the zero-weighted "the") will be essentially zero — correctly reflecting that `d1` and `d2` are about similar things and `d3` is not.

TF-IDF grew out of early information retrieval research at Cornell, where scientists were building the first computerized document search and indexing systems, formalizing intuitions that had been circulating informally about term specificity.

Search engines use TF-IDF or its close descendant BM25 to rank documents against a query, forming the retrieval stage of virtually every classical information retrieval system and many modern hybrid search pipelines that combine sparse lexical scores with dense neural retrieval. Document clustering and topic modeling pipelines often use TF-IDF vectors as input features before applying k-means or matrix factorization. Plagiarism and near-duplicate detection systems compare TF-IDF vectors via cosine similarity to flag suspiciously similar documents. Recommender systems for text-heavy content (news, articles, product descriptions) use TF-IDF to build content-based similarity scores. Even in the era of transformer-based embeddings, TF-IDF remains a standard baseline in benchmarking, a common feature in hybrid retrieval-augmented generation pipelines (sparse + dense retrieval), and a fast fallback when labeled training data or GPU compute is unavailable — a natural bridge into the statistical foundations of Text Classification Fundamentals, where TF-IDF vectors often serve as the input features to a classifier before neural methods are introduced.

Ask the tutor: How would you modify the TF-IDF formula to handle a streaming corpus where documents arrive continuously and the vocabulary keeps growing?