Natural Language Processing

⚡ Key Takeaways

Natural Language Processing (NLP) is the computational study of human language, blending linguistics, statistics, and machine learning to enable machines to understand, generate, and manipulate text and speech. Key result in words: language can be modeled probabilistically as sequences of tokens, and modern neural architectures (especially the Transformer) learn distributed representations that capture syntax and semantics from raw data. Where it applies: machine translation, search, dialogue systems, information extraction, summarization, sentiment analysis. Who/when: roots in 1950s machine translation and Shannon's information theory; revolutionized by statistical methods (1990s) and deep learning / Transformers (2013–present).

💡 The Core Insight

Language is modeled as a probability distribution $P(w_1, w_2, \dots, w_n)$ over token sequences. By the chain rule of probability, this factorizes into a product of conditional next-token distributions. The entire enterprise of modern NLP reduces to estimating these conditionals well — from $n$ -gram counts to recurrent networks to self-attention — and then using the learned distribution either to score, generate, or extract structured information. The distributional hypothesis ("you shall know a word by the company it keeps," Firth 1957) provides the semantic justification: words appearing in similar contexts have similar meanings, so context-prediction objectives implicitly learn semantics.

DefinitionLanguage Model

A language model is a probability distribution over sequences of tokens drawn from a finite vocabulary $V$ . Given a sequence $w_{1:n} = (w_1, \dots, w_n)$ with each $w_i \in V$ , the joint probability factorizes by the chain rule:

1

\quad P(w_{1:n}) = \prod_{i=1}^{n} P(w_i \mid w_{1:i-1})

Derivation hint: Repeatedly apply the definition of conditional probability $P(A,B)=P(A)P(B\mid A)$ along the sequence. Here $w_{1:i-1}$ is the context (history), $P(w_i \mid w_{1:i-1})$ is the next-token conditional, and the product runs left to right. The vocabulary $V$ may consist of words, characters, or subword units (e.g., Byte-Pair Encoding tokens).

Definitionn-gram Approximation

Under the Markov assumption of order $n-1$ , the full history is truncated to the previous $n-1$ tokens:

2

\quad P(w_i \mid w_{1:i-1}) \approx P(w_i \mid w_{i-n+1:i-1})

Derivation hint: Assume conditional independence of $w_i$ from all but the most recent $n-1$ tokens; the maximum-likelihood estimate is the ratio of co-occurrence counts. The maximum-likelihood estimate for a bigram ( $n=2$ ) is

3

\quad \hat{P}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}

Derivation hint: Maximize the multinomial log-likelihood subject to $\sum_{w_i} P(w_i\mid w_{i-1})=1$ ; the Lagrangian yields normalized counts. where $C(\cdot)$ denotes corpus counts.

DefinitionWord Embeddings

A word embedding is a map $E: V \to \mathbb{R}^d$ assigning each token a dense vector. The skip-gram objective (word2vec) maximizes the log-probability of context words $w_{i+j}$ given a center word $w_i$ over a window of size $m$ :

4

\quad \mathcal{L} = \frac{1}{T}\sum_{i=1}^{T}\sum_{-m \le j \le m,\, j\neq 0} \log P(w_{i+j}\mid w_i),\quad P(w_O\mid w_I)=\frac{\exp(u_{w_O}^\top v_{w_I})}{\sum_{w\in V}\exp(u_{w}^\top v_{w_I})}

Derivation hint: Model context prediction as a softmax over the vocabulary using separate input ( $v$ ) and output ( $u$ ) embeddings; the softmax is intractable, motivating negative sampling or hierarchical softmax.

TheoremSelf-Attention as Weighted Information Retrieval

The Transformer's scaled dot-product attention computes, for query matrix $Q\in\mathbb{R}^{n\times d_k}$ , key matrix $K\in\mathbb{R}^{n\times d_k}$ , and value matrix $V\in\mathbb{R}^{n\times d_v}$ :

5

\quad \mathrm{Attention}(Q,K,V) = \mathrm{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}}\right)V

Derivation hint: The softmax row-normalizes pairwise compatibility scores into a convex combination over value vectors; the $\sqrt{d_k}$ divisor keeps the dot-product variance $\approx 1$ to avoid saturated softmax gradients. This allows every position to aggregate information from all other positions in $O(n^2 d)$ time with $O(1)$ sequential dependency, enabling full parallelization across the sequence — the key advantage over recurrent models.

ProofFrom Cross-Entropy to Perplexity

We show that minimizing the standard training loss (cross-entropy) is equivalent to maximizing data likelihood, and that perplexity is its natural exponential form.

Step 1. Training maximizes the log-likelihood of the corpus under the model parameters $\theta$ :

6

\quad \theta^* = \arg\max_\theta \sum_{i=1}^{N} \log P_\theta(w_i \mid w_{1:i-1})

Derivation hint: Take the log of the chain-rule factorization in Equation [1] and apply it across the corpus.

Step 2. Equivalently, minimize the average negative log-likelihood, the cross-entropy $H$ :

7

\quad H = -\frac{1}{N}\sum_{i=1}^{N} \log_2 P_\theta(w_i \mid w_{1:i-1})

Derivation hint: Negate and normalize Equation [6]; this approximates the cross-entropy between the true data distribution and the model.

Step 3. Define perplexity as the exponentiated cross-entropy:

8

\quad \mathrm{PP} = 2^{H} = P_\theta(w_{1:N})^{-1/N}

Derivation hint: Substitute Equation [7] into $2^H$ and use $2^{\log_2 x}=x$ ; the geometric mean of inverse probabilities emerges.

Step 4. Interpretation: perplexity is the effective branching factor — the average number of equally likely next tokens. A perfect model on a deterministic sequence has $\mathrm{PP}=1$ ; a uniform model over $|V|$ tokens has $\mathrm{PP}=|V|$ . Lower perplexity means better predictive compression of the language. $\blacksquare$

∎

CS

Claude Shannon

1916–2001

Though an electrical engineer and mathematician rather than a linguist, Shannon laid NLP's quantitative foundation. In A Mathematical Theory of Communication (1948) and his 1951 paper Prediction and Entropy of Printed English, he treated English as a stochastic source, estimated its entropy via human prediction experiments (~1.1 bits/character), and introduced the very notions of entropy, redundancy, and $n$ -gram models of text. His framing of language as an information source emitting symbols with measurable uncertainty is the conceptual seed from which perplexity, cross-entropy training, and the entire probabilistic-language-modeling program grew.

🧠 Intuition

Imagine reading a sentence and covering the last word: "I drove my car to the ___." You don't assign equal probability to every English word; "garage," "store," or "office" feel far more likely than "elephant." A language model formalizes precisely this intuition as a probability distribution. Early models ( $n$ -grams) only peeked at the last few words — like predicting from a tiny window — and were brittle: unseen combinations got zero probability. Word embeddings then realized that "car" and "automobile" should share statistical strength because they appear in similar contexts, packing meaning into geometry where direction and distance encode semantic relationships. The Transformer's attention is best imagined as each word querying every other word and asking "how relevant are you to my meaning here?" — then blending in their information weighted by that relevance. "Bank" attends to "river" or "money" depending on context, resolving ambiguity dynamically. The deep stacking of these attention layers builds, layer by layer, from surface tokens to abstract meaning.

Figure

Transformer self-attention: each query attends over all keys/values to form a context-weighted output

ExampleBigram Probability and Perplexity

Given a tiny corpus (with sentence boundaries `~~` and `~~`): ` ~~I am Sam~~ ~~Sam I am~~ ~~I do not like green eggs~~ `

Task: Estimate $P(\text{am}\mid\text{I})$ and the perplexity of the test sentence ` ~~I am Sam~~ `.

Step 1 — Counts. $C(\text{I}) = 3$ (positions: "I am", "I am", "I do"). $C(\text{I, am}) = 2$ .

Step 2 — Bigram MLE (Equation [3]):

\hat P(\text{am}\mid\text{I}) = \frac{C(\text{I, am})}{C(\text{I})} = \frac{2}{3} \approx 0.667

Step 3 — Other needed bigrams (approximate from corpus): $P(\text{I}\mid\langle s\rangle)=2/3$ , $P(\text{Sam}\mid\text{am})=1/2$ , $P(\langle/s\rangle\mid\text{Sam})=1/2$ .

Step 4 — Test sentence probability:

P = \tfrac{2}{3}\cdot\tfrac{2}{3}\cdot\tfrac{1}{2}\cdot\tfrac{1}{2} = \tfrac{4}{36}=0.1111

Step 5 — Perplexity over $N=4$ transitions (Equation [8]):

\mathrm{PP} = P^{-1/N} = 0.1111^{-1/4} = (9)^{1/4} \approx 1.732

\boxed{\hat P(\text{am}\mid\text{I}) = 0.667,\qquad \mathrm{PP}\approx 1.73\ \text{(branching factor, dimensionless)}}

ExampleAdd-One (Laplace) Smoothing

Given: Same corpus, vocabulary size $|V| = 8$ (I, am, Sam, do, not, like, green, eggs). We need $P(\text{Sam}\mid\text{am})$ but want to avoid zero probabilities for unseen bigrams.

Step 1 — Raw counts. $C(\text{am})=2$ , $C(\text{am, Sam})=1$ .

Step 2 — Laplace-smoothed estimate:

9

\quad P_{\text{Laplace}}(w_i\mid w_{i-1}) = \frac{C(w_{i-1},w_i)+1}{C(w_{i-1})+|V|}

Derivation hint: Add a pseudocount of 1 to every possible bigram; equivalent to a uniform Dirichlet prior with concentration 1 on the multinomial.

Step 3 — Plug in:

P_{\text{Laplace}}(\text{Sam}\mid\text{am}) = \frac{1+1}{2+8} = \frac{2}{10} = 0.20

Step 4 — Compare to unsmoothed $1/2 = 0.50$ . Smoothing redistributes probability mass to unseen events, lowering the spike on observed bigrams.

\boxed{P_{\text{Laplace}}(\text{Sam}\mid\text{am}) = 0.20\ \text{(dimensionless probability)}}

⚠️ Common mistake

"A language model understands meaning." A language model estimates $P(w_i\mid \text{context})$ — it is a statistical sequence predictor, not a grounded reasoner. High fluency does not imply truthfulness, comprehension, or symbolic reasoning. Large models exhibit emergent abilities, but they can also "hallucinate" plausible-sounding falsehoods because the training objective rewards likely continuations, not factual correctness. Distinguish fluency (well-formed output) from faithfulness (correctness relative to a source or the world).

⚠️ Common mistake

"More $n$ in $n$ -grams is always better." As $n$ grows, the number of possible contexts grows as $|V|^{n-1}$ , so most are never observed — the data sparsity problem. Without smoothing or backoff, large- $n$ models assign zero probability to most test sequences (infinite perplexity). The bias–variance trade-off applies: higher $n$ reduces bias but explodes variance. Neural models circumvent this by sharing parameters across contexts via continuous representations.

Counterexample

The softmax does not preserve relative attention under length. One might assume attention weights for a fixed query stay stable as context grows. Consider a query with uniform compatibility scores over $n$ keys: each weight is $1/n$ . Adding more keys dilutes every existing weight, so a salient token's relative contribution can vanish in very long sequences — a known weakness ("attention dilution") that motivates sparse, local, or retrieval-augmented attention variants. Thus the convex-combination structure of Equation [5] does not guarantee scale-invariant focus.

connection

NLP sits at the intersection of several mathematical fields. The probabilistic backbone connects to Information Theory (entropy, cross-entropy, perplexity) and Bayesian Inference (smoothing as priors, latent-variable topic models). Sequence labeling relies on Hidden Markov Models and Conditional Random Fields. Word embeddings and attention are grounded in Linear Algebra (dot products, matrix factorization — word2vec implicitly factorizes a shifted PMI matrix). Training rests on Stochastic Gradient Descent and Backpropagation. Parsing and grammar formalisms link to Formal Language Theory and Context-Free Grammars. The Transformer's representational power connects to Universal Approximation and the broader theory of Deep Learning.

🔬 Where this appears

⏳ History

- 1948–1951 — Claude Shannon models English as a stochastic source, introduces

n

-gram entropy estimation, founding probabilistic language modeling.

- 1954 — Georgetown–IBM experiment demonstrates Russian–English machine translation (60 sentences), igniting MT optimism (and later disappointment via the 1966 ALPAC report).

- 1957 — Chomsky's Syntactic Structures establishes generative grammar and formal language hierarchies, dominating symbolic NLP for decades; Firth articulates the distributional hypothesis.

- 1970s–1980s — Rule-based and symbolic systems (SHRDLU, expert systems); Hidden Markov Models adopted for speech recognition.

- 1990s — Statistical revolution: IBM alignment models for MT, statistical parsing, the rise of corpus-driven, probabilistic methods over hand-written rules.

- 2003 — Bengio et al. introduce the neural probabilistic language model, learning distributed word representations.

- 2013 — Mikolov et al. release word2vec; efficient embeddings make distributed semantics mainstream. GloVe follows in 2014.

- 2014–2015 — Sequence-to-sequence learning (Sutskever et al.) and the attention mechanism (Bahdanau et al.) transform neural MT.

- 2017–2019 — "Attention Is All You Need" (Vaswani et al., 2017) introduces the Transformer; BERT (2018) and GPT (2018) usher in the pretraining/fine-tuning paradigm and the era of large language models.

open-problem

Grounding, reasoning, and scaling limits remain open. Despite remarkable fluency, current models struggle with (1) factual grounding — distinguishing learned associations from truth, leading to hallucination; (2) compositional generalization — systematically combining known parts in novel ways (the systematicity critique from Fodor & Pylyshyn); (3) long-range and quadratic cost — self-attention's $O(n^2)$ scaling limits context length, spurring linear-attention and state-space alternatives; (4) interpretability — we lack a theory mapping the geometry of learned representations to formal semantic structure; and (5) data and energy efficiency — humans acquire language from orders of magnitude less data than LLMs. Whether scaling alone yields robust reasoning, or whether explicit symbolic structure, world models, or grounding in perception/action are necessary, is a central and contested open question.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also