Skip to content

NLP Foundations

What you’ll learn. What problems “NLP” actually covers; how text was processed before neural networks and why those ideas (counting, smoothing, sparse vectors, distributional semantics) still matter; how n-gram language models, TF-IDF and word2vec work, with the math and runnable code; and the sequence of limitations that pushed the field from bag-of-words to transformers. This lecture is deliberately concise: it is the historical and conceptual on-ramp for the rest of the section.

Natural language processing turns unstructured text into something a program can act on, or produces text a human can use. Most tasks fall into a handful of shapes:

Shape Examples
Text to label sentiment, spam, topic, intent, toxicity
Text to span/sequence labels named entity recognition (NER), part-of-speech (POS) tagging, extractive QA
Text pair to relation entailment, paraphrase, retrieval relevance
Text to text translation, summarization, rewriting, generative QA
Text to structure parsing, information extraction, text-to-SQL
Anything to text chat, code generation, tool calls

The modern shift is that the last two rows swallowed the rest: a single autoregressive model prompted appropriately can do nearly every row above. But the older framing is still useful because it tells you what evaluation looks like for each task (Evaluating LLMs) and when a small specialized model is the cheaper right answer.

Until roughly 2015, a typical system was a chain of hand-designed stages:

raw text -> sentence split -> tokenize -> normalize (lowercase, stem/lemmatize)
-> POS tag -> parse / NER -> feature extraction -> linear classifier / CRF

Key ideas worth knowing:

  • Tokenization: splitting into units. Whitespace splitting fails on punctuation, contractions, and languages without spaces. This problem never went away; modern subword tokenizers are its descendant (Tokenization).
  • Normalization: lowercasing, Unicode normalization (NFC/NFKC), stemming (crude suffix stripping: “running” to “run”) or lemmatization (dictionary-based: “better” to “good”). Neural models mostly dropped these because they destroy information the model can use.
  • Stopwords: removing “the”, “of”. Helpful for sparse retrieval, harmful for most neural tasks (negation words like “not” are often on stopword lists, which is a classic bug).
  • Sequence labeling: HMMs and conditional random fields (CRFs) tagged each token using neighbouring context. Viterbi decoding finds the best tag sequence in O(nK2)O(nK^2) for KK tags.

A language model assigns a probability to a token sequence. By the chain rule,

P(w1,…,wn)=∏t=1nP(wt∣w1,…,wt−1).P(w_1,\dots,w_n) = \prod_{t=1}^{n} P(w_t \mid w_1,\dots,w_{t-1}).

Conditioning on the whole history is infeasible (almost every long history is unique), so an n-gram model truncates it with a Markov assumption:

P(wt∣w1:t−1)≈P(wt∣wt−n+1:t−1).P(w_t \mid w_{1:t-1}) \approx P(w_t \mid w_{t-n+1:t-1}).

The maximum-likelihood estimate is just counting. For a bigram model:

P^(wt∣wt−1)=C(wt−1,wt)C(wt−1).\hat P(w_t \mid w_{t-1}) = \frac{C(w_{t-1}, w_t)}{C(w_{t-1})}.

Any n-gram not seen in training gets probability zero, which makes the whole sentence probability zero. Smoothing reallocates mass to unseen events:

  • Add-one (Laplace): P^=C(wt−1,wt)+1C(wt−1)+V\hat P = \frac{C(w_{t-1},w_t)+1}{C(w_{t-1})+V}. Simple, but steals too much mass for large VV.
  • Interpolation / backoff: mix higher- and lower-order estimates.
  • Kneser-Ney: the best classical method. Its key insight: a lower-order word should be scored by how many distinct contexts it follows, not raw frequency. “Francisco” is frequent but almost always follows “San”, so as a fallback unigram it deserves low weight.

The standard intrinsic metric is perplexity, the exponentiated average negative log-likelihood per token:

PPL=exp⁡(−1N∑t=1Nlog⁡P(wt∣w<t)).\mathrm{PPL} = \exp\Big(-\frac1N \sum_{t=1}^N \log P(w_t\mid w_{<t})\Big).

Intuitively it is the effective branching factor: a perplexity of 50 means the model is as uncertain as a uniform choice among 50 tokens. Perplexities are only comparable between models that use the same tokenizer and test set; a model with a bigger vocabulary has fewer, more informative tokens per sentence. Bits-per-byte normalizes this.

from collections import Counter, defaultdict
import math
corpus = [
"the cat sat on the mat",
"the dog sat on the log",
"the cat saw the dog",
]
tokens = [["<s>"] + s.split() + ["</s>"] for s in corpus]
unigram, bigram = Counter(), Counter()
for sent in tokens:
unigram.update(sent)
bigram.update(zip(sent, sent[1:]))
V = len(unigram)
def p(w, prev, k=1.0): # add-k smoothing
return (bigram[(prev, w)] + k) / (unigram[prev] + k * V)
def perplexity(sent):
s = ["<s>"] + sent.split() + ["</s>"]
lp = sum(math.log(p(w, prev)) for prev, w in zip(s, s[1:]))
return math.exp(-lp / (len(s) - 1))
print(perplexity("the cat sat on the log")) # low: familiar
print(perplexity("log the on cat sat the")) # high: scrambled

n-gram models are fast and surprisingly strong for their size, and they remain useful as cheap baselines, in speech decoding, and as the reference for some data-deduplication and contamination checks. Their fatal weakness: they cannot generalize across similar words. Having seen “the cat sat on the mat” tells a trigram model nothing about “a kitten lay on a rug.”

Representing documents: bag of words and TF-IDF

Section titled “Representing documents: bag of words and TF-IDF”

For classification and search, the classic representation ignores order: a document becomes a vector of word counts over a vocabulary of size VV (a bag of words), typically with hundreds of thousands of dimensions, almost all zero.

Raw counts overweight common words. TF-IDF reweights each term by how rare it is across the corpus:

tfidf(t,d)=tf(t,d)⋅log⁡Ndf(t)\mathrm{tfidf}(t,d) = \mathrm{tf}(t,d)\cdot \log\frac{N}{\mathrm{df}(t)}

where NN is the number of documents and df(t)\mathrm{df}(t) the number containing tt. Variants use sublinear tf (1+log⁡tf1+\log \mathrm{tf}) and smoothed idf. Similarity between two documents is typically the cosine of their vectors.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
docs = [
"the cat sat on the mat",
"dogs and cats are pets",
"stock markets fell sharply today",
]
vec = TfidfVectorizer(sublinear_tf=True, ngram_range=(1, 2))
X = vec.fit_transform(docs) # sparse (3, V)
q = vec.transform(["my cat is a pet"])
print(cosine_similarity(q, X)) # ranks doc 0/1 above doc 2

TF-IDF’s retrieval cousin is BM25, which adds term-frequency saturation and length normalization. BM25 is not obsolete: it is still a strong baseline and a standard half of hybrid search (RAG). Its limitation is the vocabulary mismatch problem: “car” and “automobile” share no dimensions.

The linguistic hypothesis (“you shall know a word by the company it keeps”, Firth, 1957) suggests representing a word by its contexts. Early versions factorized co-occurrence matrices (LSA, PPMI + SVD). word2vec (Mikolov et al., 2013) learns dense vectors, typically 100 to 300 dimensions, by prediction.

Each word ww has an input vector vw\mathbf v_w and, as a context, an output vector uc\mathbf u_c. For a center word ww and an observed context word cc within a window, skip-gram maximizes the probability that this pair is real versus KK random “negative” pairs drawn from a noise distribution (unigram frequency to the power 0.75):

L=−log⁡σ(uc⊤vw)−∑k=1KEck∼Pn[log⁡σ(−uck⊤vw)].\mathcal L = -\log \sigma(\mathbf u_c^\top \mathbf v_w) - \sum_{k=1}^{K} \mathbb E_{c_k\sim P_n}\big[\log \sigma(-\mathbf u_{c_k}^\top \mathbf v_w)\big].

This avoids a softmax over the entire vocabulary, making training on billions of tokens feasible. It is, in effect, an implicit factorization of a shifted PMI matrix (Levy and Goldberg, 2014). GloVe reaches similar vectors by fitting log co-occurrence counts directly; fastText adds character n-grams so rare and misspelled words get sensible vectors.

import torch, torch.nn as nn, torch.nn.functional as F
class SkipGram(nn.Module):
def __init__(self, V, d):
super().__init__()
self.inp = nn.Embedding(V, d)
self.out = nn.Embedding(V, d)
nn.init.uniform_(self.inp.weight, -0.5 / d, 0.5 / d)
nn.init.zeros_(self.out.weight)
def forward(self, center, pos, neg):
# center: (B,), pos: (B,), neg: (B, K)
v = self.inp(center) # (B, d)
pos_score = (v * self.out(pos)).sum(-1) # (B,)
neg_score = torch.einsum("bd,bkd->bk", v, self.out(neg))
return -(F.logsigmoid(pos_score).mean() + F.logsigmoid(-neg_score).sum(-1).mean())

The famous demonstration is vector arithmetic: vking−vman+vwoman≈vqueen\mathbf v_{\text{king}} - \mathbf v_{\text{man}} + \mathbf v_{\text{woman}} \approx \mathbf v_{\text{queen}}. It works for some relations and is cherry-picked for others, but the broader point holds: geometry in the embedding space captures semantic relationships. The same embeddings also absorb social biases present in the corpus, which was an early and important finding.

  1. One vector per word type: “bank” (river) and “bank” (money) share a vector. Context is ignored.
  2. Out-of-vocabulary words: unknown tokens get nothing (fastText partly fixes this).
  3. No composition: sentence meaning needed ad hoc pooling (averaging vectors loses order and negation).

The progression is a story of removing each bottleneck:

  1. RNNs / LSTMs (c. 2013-2016). A recurrent network reads a sequence left to right, updating a hidden state, so representations become contextual and sentence length is unbounded. Seq2seq models (Sutskever et al., 2014) compressed the entire source into one fixed vector, an information bottleneck. Training also couldn’t be parallelized across time, and gradients over long spans vanished.
  2. Attention (Bahdanau et al., 2014). Let the decoder look back at all encoder states, weighting them by relevance. This fixed the bottleneck and gave alignment for free.
  3. Contextual embeddings (ELMo, 2018). Use the internal states of a bidirectional LSTM language model as features. “Bank” now gets different vectors in different sentences.
  4. Transformers (Vaswani et al., 2017). Drop recurrence entirely; use self-attention so every token attends to every other in parallel. Training becomes massively parallel on GPUs, which is what allowed scale. See Attention and Transformers.
  5. Pretrain, then adapt (2018+). BERT (encoder, masked-token objective) and GPT (decoder, next-token objective) showed that a large model pretrained on raw text transfers to nearly every task with little labeled data. The “feature engineering” stage of the classical pipeline was replaced by self-supervised pretraining.
  6. Scale and instruction following (2020+). Scaling laws (Pretraining) plus alignment (Post-Training) turned next-token predictors into general assistants.

Notice what stayed constant: it is still language modeling (predict the next token given context), still dense learned embeddings of tokens, still tokenization. The n-gram model is the same objective with a different function approximator.

  • Always build a trivial baseline (TF-IDF + logistic regression, or BM25) before an LLM. It often gets within a few points on classification and costs nothing to run; it also reveals label noise.
  • Use perplexity only to compare models with identical tokenization; use task metrics for everything else.
  • Don’t strip stopwords or stem when feeding text to a neural model.
  • Sparse methods are more debuggable (you can read the weights); keep that in mind when interpretability matters.
  • Language modeling, predicting the next token given context, is the common thread from n-grams to LLMs; only the function approximator changed.
  • n-gram models count and smooth; their failure is sparsity and inability to generalize across similar contexts.
  • TF-IDF/BM25 weight terms by rarity and remain strong retrieval baselines, but suffer vocabulary mismatch.
  • word2vec learns dense vectors from co-occurrence by prediction; vectors are static, so polysemy is lost.
  • RNNs, attention, then transformers removed the bottlenecks of fixed-size summaries and sequential computation, and enabled pretraining at scale.
  1. Conceptual. Why does Kneser-Ney use continuation counts for the lower-order distribution instead of raw unigram frequency?
  2. Conceptual. Two language models report perplexities of 20 and 35 on the same text, but use different tokenizers. Can you conclude the first is better? What would you compute instead?
  3. Hands-on. Extend the bigram code to trigrams with linear interpolation λ1P3+λ2P2+λ3P1\lambda_1 P_3+\lambda_2P_2+\lambda_3P_1 and tune the λ\lambda on a held-out split. Report perplexity versus add-one smoothing.
  4. Hands-on. Train the skip-gram module above on a small text corpus (for example the text8 dataset), then print the nearest neighbors (by cosine) of five words. Which are polysemous failures?
  5. Conceptual. Why can an LSTM encoder-decoder without attention degrade on long inputs, and what exactly does attention change?
Solutions (sketch)
  1. “Francisco” has high raw frequency but follows very few distinct words, so as a backoff for an unseen context it should get low mass. Continuation counts measure versatility, which better predicts appearing in a novel context.
  2. No. Different tokenizations yield different token counts, so per-token perplexity is not comparable. Compute bits-per-byte (total negative log-likelihood divided by number of bytes) for both.
  3. The whole source must pass through one fixed-size vector, so information about early tokens is overwritten. Attention lets each decoder step compute a weighted sum over all encoder states, so the effective memory grows with the input.
  • Jurafsky and Martin, Speech and Language Processing (3rd ed. draft, free online): chapters on n-grams, vector semantics, and neural language models.
  • Mikolov et al., “Efficient Estimation of Word Representations in Vector Space” (2013) and “Distributed Representations of Words and Phrases” (2013).
  • Levy and Goldberg, “Neural Word Embedding as Implicit Matrix Factorization” (2014).
  • Pennington, Socher, Manning, “GloVe: Global Vectors for Word Representation” (2014).
  • Bahdanau, Cho, Bengio, “Neural Machine Translation by Jointly Learning to Align and Translate” (2014).
  • Vaswani et al., “Attention Is All You Need” (2017).
  • Manning, Raghavan, Schutze, Introduction to Information Retrieval (2008), for TF-IDF and BM25.