Natural Language Processing

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).

Natural Language Processing is the subfield of artificial intelligence and computational linguistics concerned with algorithmic processing of natural (human) language, encompassing both understanding (parsing, semantics, inference) and generation. Its central mathematical object is a probability distribution over sequences of discrete symbols (tokens), from which nearly all tasks can be cast as conditional inference or estimation problems. NLP matters because language is humanity's primary information medium, and automating its processing unlocks search, translation, knowledge extraction, and human–computer interaction at scale. A surprising fact is that purely self-supervised objectives — predicting the next or a masked token from massive unlabeled corpora — yield representations that transfer to virtually every downstream linguistic task, suggesting that much of "meaning" is recoverable from distributional statistics alone (the distributional hypothesis). The field has progressively shed handcrafted rules in favor of learned, high-dimensional vector representations.

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.

Formal Statement

Language 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:

P (w_{1 : n}) = i = 1 \prod n P (w_{i} ∣ w_{1 : i - 1})

⟳Repeatedly apply the definition of conditional probability

P (A, B) = P (A) P (B ∣ A)

along the sequence.

Here $w_{1 : i - 1}$ is the context (history), $P (w_{i} ∣ 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).

n-gram Approximation

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

P (w_{i} ∣ w_{1 : i - 1}) \approx P (w_{i} ∣ w_{i - n + 1 : i - 1})

⟳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

\hat{P} (w_{i} ∣ w_{i - 1}) = \frac{C ( w _{i - 1} , w _{i} )}{C ( w _{i - 1} )}

⟳Maximize the multinomial log-likelihood subject to

\sum_{w_{i}} P (w_{i} ∣ w_{i - 1}) = 1

; the Lagrangian yields normalized counts.

where $C (\cdot)$ denotes corpus counts.

Word Embeddings

A word embedding is a map $E : V \to 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$ :

L = \frac{1}{T} i = 1 \sum T - m \leq j \leq m, j \neq = 0 \sum lo g P (w_{i + j} ∣ w_{i}), P (w_{O} ∣ w_{I}) = \frac{exp ( u _{w_{O}}^{⊤} v _{w_{I}} )}{\sum _{w \in V} exp ( u _{w}^{⊤} v _{w_{I}} )}

⟳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.

Self-Attention as Weighted Information Retrieval

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

Attention (Q, K, V) = softmax (\frac{Q K ^{⊤}}{d _{k}}) V

⟳The softmax row-normalizes pairwise compatibility scores into a convex combination over value vectors; the

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.

Why It Holds / Derivation

From 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

θ

θ^{*} = ar g θ max i = 1 \sum N lo g P_{θ} (w_{i} ∣ w_{1 : i - 1})

⟳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

H = - \frac{1}{N} i = 1 \sum N lo g_{2} P_{θ} (w_{i} ∣ w_{1 : i - 1})

⟳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:

PP = 2^{H} = P_{θ} (w_{1 : N})^{- 1/ N}

⟳Substitute Equation [7] into

2^{H}

and use

2^{l o g_{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

PP = 1

; a uniform model over

∣ V ∣

tokens has

PP = ∣ V ∣

. Lower perplexity means better predictive compression of the language.

■

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.

Building 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.

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

Worked Examples

Bigram Probability and Perplexity

Given a tiny corpus (with sentence boundaries <s> and </s>): <s> I am Sam </s> <s> Sam I am </s> <s> I do not like green eggs </s> Task: Estimate

P (am ∣ I)

and the perplexity of the test sentence <s> I am Sam </s>. Step 1 — Counts.

C (I) = 3

(positions: "I am", "I am", "I do").

C (I, am) = 2

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

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

Step 3 — Other needed bigrams (approximate from corpus):

P (I ∣ ⟨ s ⟩) = 2/3

P (Sam ∣ am) = 1/2

P (⟨ / s ⟩ ∣ Sam) = 1/2

. Step 4 — Test sentence probability:

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

Step 5 — Perplexity over

N = 4

transitions (Equation [8]):

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

\hat{P} (am ∣ I) = 0.667, PP \approx 1.73 (branching factor, dimensionless)

Add-One (Laplace) Smoothing

Given: Same corpus, vocabulary size

∣ V ∣ = 8

(I, am, Sam, do, not, like, green, eggs). We need

P (Sam ∣ am)

but want to avoid zero probabilities for unseen bigrams. Step 1 — Raw counts.

C (am) = 2

C (am, Sam) = 1

. Step 2 — Laplace-smoothed estimate:

P_{Laplace} (w_{i} ∣ w_{i - 1}) = \frac{C ( w _{i - 1} , w _{i} ) + 1}{C ( w _{i - 1} ) + ∣ V ∣}

⟳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_{Laplace} (Sam ∣ 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.

P_{Laplace} (Sam ∣ am) = 0.20 (dimensionless probability)

Common Misconceptions

"A language model understands meaning." A language model estimates

P (w_{i} ∣ 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). "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. 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.

Connections

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.

Real-World Applications

Google Translate / DeepL — neural machine translation using encoder–decoder Transformers translates between 100+ languages, casting translation as conditional generation $P (target ∣ source)$ .
GPT-4 / ChatGPT, Claude, Gemini — large language models trained on next-token prediction power conversational assistants, code generation, and reasoning tasks.
Spam filtering (Gmail) — Naive Bayes and neural classifiers estimate $P (spam ∣ email tokens)$ at billions-of-messages scale.
Voice assistants (Siri, Alexa) — pipeline of automatic speech recognition, intent classification, and natural-language generation.
Search engines (Google BERT integration, 2019) — contextual embeddings improve query–document matching beyond keyword overlap.
Clinical NLP (cTAKES, BioBERT) — extracting diagnoses, medications, and outcomes from unstructured electronic health records.
Code completion (GitHub Copilot) — language models trained on source code predict and synthesize program text.

Historical Development

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.

Subtleties & Limits

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.