Classical NLP and n-gram language models

Text as a bag of words

The simplest representation of a document ignores order entirely: count how often each vocabulary term appears. The bag-of-words vector of a document $d$ has one entry per term. Raw counts over-reward long documents and common words, so we re-weight with TF-IDF:

where $\text{tf}(t,d)$ is the count of term $t$ in $d$ (often log-scaled), $N$ the number of documents and $\text{df}(t)$ the number of documents containing $t$. A term that appears everywhere ("the") has $\text{idf}\approx0$; a term that appears in one document gets the maximum weight. (scikit-learn uses the smoothed form $\log\frac{1+N}{1+\text{df}}+1$ and then L2-normalizes each vector.) Documents and queries are then compared with cosine similarity (1.1 Vectors, dot products and norms).

Worked example. Corpus: $d_1$ = "the cat sat", $d_2$ = "the cat ran", $d_3$ = "dogs ran fast"; $N=3$. Document frequencies: the 2, cat 2, ran 2, sat 1, dogs 1, fast 1. So $\text{idf}(\text{the})=\text{idf}(\text{cat})=\text{idf}(\text{ran})=\log(3/2)=0.405$ and $\text{idf}(\text{sat})=\text{idf}(\text{dogs})=\text{idf}(\text{fast})=\log 3=1.099$ (natural logs). Query $q$ = "cat sat" has weights (cat 0.405, sat 1.099), norm $\sqrt{0.164+1.208}=1.171$. Document $d_1$ has weights (the 0.405, cat 0.405, sat 1.099), norm $1.239$; $d_2$ has (0.405, 0.405, 0.405), norm $0.702$. Then

The rare, specific word sat dominates the ranking — exactly the behaviour you want from a search engine. BM25, the standard in search engines, refines TF-IDF with saturating term frequency and document-length normalization; you will meet its formula in 9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics. These vectors are sparse (one dimension per word) and exact: they match the literal string, which is a strength for names, IDs and code and a weakness for synonyms ("car" vs "automobile") — the gap that dense embeddings close (6.3 Word embeddings, 9.2 Embeddings deep dive).

Language models: assigning probability to text

A language model assigns a probability to a sequence of tokens $w_1,\dots,w_T$. The chain rule of probability (1.7 Probability II: Bayes, independence, MLE and MAP) factorizes it exactly:

Conditioning on the entire history is impossible to estimate from counts, so an n-gram model makes the Markov assumption $P(w_t\mid w_{<t})\approx P(w_t\mid w_{t-n+1},\dots,w_{t-1})$. The maximum-likelihood estimate (1.7 Probability II: Bayes, independence, MLE and MAP) is a ratio of counts; for a bigram,

Worked example (Jurafsky & Martin's corpus): ⟨s⟩ I am Sam ⟨/s⟩ · ⟨s⟩ Sam I am ⟨/s⟩ · ⟨s⟩ I do not like green eggs and ham ⟨/s⟩. Then $P(\text{I}\mid⟨s⟩)=2/3$, $P(\text{am}\mid\text{I})=2/3$, $P(\text{Sam}\mid\text{am})=1/2$, $P(⟨/s⟩\mid\text{Sam})=1/2$, so

Any sentence containing an unseen bigram gets probability zero, which is fatal for evaluation and for applications. Smoothing fixes this by moving probability mass to unseen events: add-$k$ (Laplace) smoothing $P=\frac{C(w_{t-1}w_t)+k}{C(w_{t-1})+kV}$; backoff (use a shorter context when the longer one is unseen); interpolation $\hat P=\lambda_3P_3+\lambda_2P_2+\lambda_1P_1$ with weights tuned on held-out data; and Kneser–Ney, the best classical method, which estimates a word's unigram weight by how many distinct contexts it follows ("Francisco" is frequent but follows only "San"). The parameter count $V^n$ explodes with $n$: a trigram model over a 50k vocabulary has $1.25\times10^{14}$ possible parameters, almost all unseen — the data-sparsity problem neural LMs solve by sharing statistics through embeddings (6.3 Word embeddings).

Perplexity

How good is a language model? Measure the average surprise it assigns to held-out text. The per-token cross-entropy (1.9 Information theory: entropy, cross-entropy and KL divergence) is $H=-\frac1N\sum_{t=1}^{N}\log_2 P(w_t\mid w_{<t})$, and perplexity is its exponential:

Math check. For a model that spreads probability uniformly over $k$ equally likely next tokens at every step, $P(w_t|w_{<t})=1/k$, so $H=\log_2 k$ and $\text{PP}=k$. Perplexity is the effective branching factor: a perplexity of 20 means the model is, on average, as uncertain as if it were choosing uniformly among 20 tokens. Lower is better; it is minimized when the model's distribution equals the true distribution (Gibbs' inequality).

Perplexity only compares models that share a tokenizer and test set: changing the tokenization changes $N$ and the numbers. Classical trigram models reached perplexities around 100–150 on standard English benchmarks; GPT-2 pushed word-level WikiText perplexity into the teens, and pretraining curves for today's LLMs are still plotted as cross-entropy per token (7.9 Scaling laws and compute-optimal training).

Naive Bayes for text

The multinomial Naive Bayes classifier from 3.7 Naive Bayes and generative vs discriminative models is a bag-of-words model with class-conditional word probabilities: $P(c\mid d)\propto P(c)\prod_{t\in d}P(t\mid c)^{\text{count}(t,d)}$, estimated with Laplace smoothing and computed in log space. It is a linear classifier in log-count space, trains in one pass, and remains a surprisingly strong baseline for topic and spam classification — always run it before anything neural.

Why sparse methods still matter

Lexical retrieval is cheap, interpretable and exact. On the BEIR zero-shot benchmark BM25 remained a strong baseline that many early dense retrievers failed to beat out of domain, and production RAG systems almost always combine BM25 with dense retrieval (9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics). The n-gram lineage matters for a different reason: the next-token objective, the chain-rule factorization and perplexity are exactly what GPT-style models optimize (7.6 Decoder-only: GPT and autoregressive generation). Bengio's 2003 neural language model simply replaced the count table with a learned function of embedded previous words — the step you take next in 6.3 Word embeddings and reproduce in 6.8 Project: character-level language model.

Where this shows up later

• Dense embeddings replace exact word matching — 6.3 Word embeddings, 9.2 Embeddings deep dive; BM25 and hybrid search — 9.5 Retrieval quality: hybrid search, reranking, query transforms and metrics; chunking a corpus for retrieval — 9.4 Chunking and ingestion.
• The next-token objective and perplexity carry straight into RNN LMs — 6.4 Recurrent neural networks and BPTT, GPT — 7.6 Decoder-only: GPT and autoregressive generation, and scaling-law plots — 7.9 Scaling laws and compute-optimal training; perplexity vs task metrics — 8.7 Evaluating LLMs.