Chapter 3: Text Representation

The TF-IDF score is the product of two terms: TF measures local importance (how frequent is $t$ in document $d$?), and IDF measures global rarity (how many documents contain $t$?). The logarithm dampens the IDF factor so that a term appearing in 1 out of 1000 documents does not receive a score 1000x higher than one appearing in all documents. Common IDF variants include smooth IDF: $\log\frac{|D| + 1}{\text{df}(t) + 1} + 1$ to avoid division by zero.

The document frequency $\text{df}(t)$ counts how many documents contain term $t$ at least once. IDF is the log of the inverse of this proportion. Terms appearing in every document get IDF = 0 (no discriminative power). Terms appearing in only one document get the maximum IDF = $\log|D|$. The logarithm ensures the scale is manageable -- without it, a term in 1 of 1,000,000 documents would get a weight of 1,000,000.

Several variants exist for both TF and IDF components. Sublinear TF: Uses $1 + \log(\text{TF})$ instead of raw TF, dampening the effect of very high frequencies. Smooth IDF: Adds 1 to numerator and denominator to prevent division by zero for unseen terms. L2 normalization: After computing TF-IDF, each document vector is normalized to unit length, making cosine similarity equivalent to a dot product. Scikit-learn's TfidfVectorizer uses smooth IDF and L2 normalization by default.

In information retrieval, queries are also converted to TF-IDF vectors. Documents are ranked by cosine similarity between the query vector and each document vector. This is the foundation of vector space models used in search engines. The process: (1) Build IDF from the document corpus, (2) Convert the query to a TF-IDF vector using the same vocabulary, (3) Compute cosine similarity with all document vectors, (4) Return top-$k$ most similar documents.

Single-word counts lose phrases such as "not good" and "New York". An n-gram slides a window of $n$ tokens across the text and records each window: unigrams for $n = 1$, bigrams for $n = 2$, trigrams for $n = 3$. A sequence of $L$ tokens yields $L - n + 1$ n-grams, with repeats counted separately. In feature extraction, n-grams are usually added alongside unigrams, as with ngram_range=(1, 2) in scikit-learn, so the model keeps word evidence and gains phrase evidence. The cost is size: the number of possible n-grams grows as $|V|^n$, so higher orders produce enormous, sparse feature spaces that need minimum-frequency cutoffs.

A language model assigns probabilities to word sequences, which spelling correction, speech recognition, and text generation all need. The chain rule writes $P(w_1, \ldots, w_n)$ as a product of next-word probabilities, but full histories are almost never repeated in a corpus. The Markov assumption truncates the history to the previous $N-1$ words, as in the formula, and the maximum-likelihood estimate divides counts: for a bigram, the count of the pair over the count of the previous word. Model quality is measured by perplexity, the inverse probability of held-out text normalized by its length. Any unseen n-gram gets probability zero, so real models need smoothing.

Contiguous n-grams miss relations interrupted by other words: in "I really love NLP", the pair (I, love) is split by an adverb. Skip-grams allow up to $K$ words to be skipped between elements, so a $K$-skip-bigram pairs each word with any of the next $K+1$ words, and $K = 0$ gives ordinary bigrams. They extract more relations from the same text, which helps on small corpora and on text with inserted words, but they also create more features and more noise. The same idea of pairing a word with neighbors inside a window drives the Word2Vec Skip-gram model in the next chapter.

Higher-order n-grams are more specific, which makes them rarer. With a 50,000-word vocabulary there are $2.5 \times 10^9$ possible bigrams and $1.25 \times 10^{14}$ trigrams, far more than any corpus contains, so most valid sequences have count zero and any sentence containing one gets maximum-likelihood probability zero. Smoothing moves probability mass from seen to unseen events. Laplace adds 1 to every count and $|V|$ to the denominator, as in the formula, but takes too much mass from frequent n-grams. Backoff and interpolation fall back to shorter histories, and Kneser-Ney, the strongest classical method, discounts seen counts and favors words that follow many different histories.

Assign every vocabulary word a unique index $i$, and represent it by $\mathbf{e}_i$, a length-$|V|$ vector that is zero everywhere except at position $i$. These vectors form the standard basis of $\mathbb{R}^{|V|}$, so a Bag of Words vector is simply the sum of the one-hot vectors of a document's tokens. The encoding is lossless for identity, since each word maps to a distinct vector, but it carries no other information. Any two distinct one-hot vectors have dot product 0 and Euclidean distance $\sqrt{2}$. A model therefore cannot transfer anything it learns about "cat" to "dog" through the input representation alone.

One-hot vectors have one dimension per vocabulary word, so a 50,000-word vocabulary gives 50,000-dimensional vectors with a single non-zero entry each. Materializing all of them as a dense matrix needs $|V|^2$ entries, as the formula shows, which is 10 GB in float32 for 50,000 words. Even one 512-token sequence of dense one-hot rows takes about 100 MB. No real system stores them this way: sparse formats keep only the index, and neural models pass integer ids directly to an embedding layer. The deeper cost is statistical, since a first layer on one-hot input has $|V| \times d$ weights, and rare words receive too few updates to learn them well.

An embedding layer is a weight matrix $E \in \mathbb{R}^{|V| \times d}$ with one row per vocabulary word. Feeding it a one-hot vector $\mathbf{e}_i$ computes $E^T \mathbf{e}_i$, and because only position $i$ is non-zero, the product just copies row $i$. Libraries therefore implement the layer as an index lookup, as in PyTorch's nn.Embedding, which costs $O(d)$ instead of $O(|V| d)$ multiplications. During training, gradients reach only the rows of words that appeared in the batch, so each row learns from its own contexts. This links one-hot encoding to the embedding methods of the next chapter: the input stays an index, but the representation becomes dense and learned.

Given a corpus and a context window of size $k$, the co-occurrence matrix $M$ records how many times word $w_i$ appears within $k$ positions of word $w_j$. The matrix is symmetric ($M_{ij} = M_{ji}$) when using a symmetric window. Each row of $M$ is a word's distributional representation -- words with similar rows have similar meanings. Window size matters: small windows (2-5) capture syntactic relationships; large windows (5-10+) capture topical/semantic relationships.

Raw co-occurrence counts are dominated by frequent words: "the" appears near everything, so it looks related to everything. Pointwise mutual information compares the observed joint probability $P(w_i, w_j)$ with the product $P(w_i) P(w_j)$ expected if the two words were independent. The log of that ratio is positive for words that attract each other, zero for independent words, and negative for words that avoid each other; in base 2 it is measured in bits. All three probabilities are estimated from the co-occurrence counts. PMI's weakness is rare events: a single co-occurrence of two rare words gets a huge score, so practical systems add count thresholds or smoothing.

Positive PMI clamps negative values to zero. This is important because: (1) Negative PMI values are unreliable -- the absence of a co-occurrence could mean the words are unrelated OR that we simply have not seen enough data. (2) Sparse PPMI matrices are more memory-efficient (many zeros can be stored in sparse format). (3) Empirically, PPMI matrices produce better word representations than raw PMI. PPMI word vectors have been shown to be competitive with Word2Vec on many benchmarks.

PPMI rows are long and sparse, one dimension per context word, and synonyms such as "car" and "automobile" may share few non-zero contexts. Truncated SVD factors the matrix as $U \Sigma V^T$ and keeps the top $k$ singular values, which by the Eckart-Young theorem gives the best rank-$k$ approximation in squared error. Rows of $U_k \Sigma_k$, or of $U_k \sqrt{\Sigma_k}$ in a common symmetric variant, become dense $k$-dimensional word vectors, and words with similar context profiles land close together even when their raw rows barely overlap. Levy and Goldberg showed that Word2Vec with negative sampling implicitly factorizes a shifted PMI matrix, so SVD of PPMI is a close relative of learned embeddings.

PCA finds orthogonal directions, the principal components, along which the data varies most. Center the data by subtracting the mean $\mu$, compute the covariance matrix, take its top $k$ eigenvectors $W_k$, and project, as in the formula. Each eigenvalue is the variance captured by its component, and the explained variance ratio reports that component's share. For dense data with strongly correlated features, a few components often capture most of the variance, but sparse text behaves differently: on a 20 Newsgroups TF-IDF matrix of about 39,000 terms, 100 SVD components explain only about 11 percent. Centering also destroys sparsity, which is why text pipelines use truncated SVD instead.

SVD factors any $m \times n$ matrix as $M = U \Sigma V^T$. The columns of $U$ are orthonormal directions in document space, the columns of $V$ are orthonormal directions in word space, and the diagonal $\Sigma$ holds non-negative singular values in decreasing order, each measuring the importance of one direction. Keeping the top $k$ gives $\hat{M}_k$, the best rank-$k$ approximation, and the share of squared singular values kept is the share of the matrix's energy retained. Unlike eigendecomposition, SVD works for rectangular matrices and needs no centering. PCA is the SVD of the centered data matrix, and LSA is the SVD of a term-document matrix.

LSA applies truncated SVD to a TF-IDF (or term-frequency) matrix. The resulting low-dimensional space captures latent semantic topics: dimensions no longer correspond to individual words but to abstract concepts. For example, one dimension might capture a "technology" topic (high loading for words like computer, software, algorithm) while another captures "biology" (gene, cell, protein). LSA was one of the first methods to handle synonymy ("car" and "automobile" map to the same latent dimension) and polysemy (multiple senses mapped to different dimensions).

Full SVD of an $m \times n$ matrix costs $O(\min(mn^2, m^2 n))$ time and needs the dense matrix in memory, which is impossible for 50,000 documents by 100,000 terms. Truncated SVD computes only the top $k$ singular triplets, using Lanczos iteration or randomized range finding (Halko, Martinsson, and Tropp), which touch the matrix only through products with a few vectors. On a sparse matrix each product costs time proportional to the number of non-zeros, so the total work scales roughly with nnz times $k$. scikit-learn's TruncatedSVD accepts sparse input and does not center it, unlike PCA, because centering would fill every zero and destroy sparsity.