---
title: "Language for AI Agents: Grammar, Translation, and Speech"
module: Frontiers
moduleNumber: 6
lessonNumber: 6
order: 606
summary: >
  N-gram models see only a local window; they cannot say why "black dog" is
  well-formed English and "dog black" is not, because that is a fact about
  structure. This lesson takes up structure: phrase-structure and probabilistic
  context-free grammars, syntactic analysis by chart parsing and CYK, augmented
  grammars and compositional semantics, then the two major statistical successes —
  machine translation and speech recognition — cast as noisy-channel problems. It
  closes with the bridge from n-grams to transformers and where the classical
  account sits relative to modern NLP.
topics: [Frontiers]
sources:
  - book: AIMA
    ref: "Ch. 23 — Natural Language for Communication; §23.1 Phrase Structure Grammars, §23.2 Syntactic Analysis, §23.3 Augmented Grammars & Semantic Interpretation"
  - book: AIMA
    ref: "§23.4 Machine Translation, §23.5 Speech Recognition"
---

This builds on
[Natural Language for AI Agents](/artificial-intelligence/frontiers/natural-language-in-ai),
which treated language as a source of information — n-gram language models and the
information-seeking tasks built on them: classification, retrieval, and extraction.
Those models read text as a sequence of symbols and asked what it was about. Here we
turn to how words are _arranged_: the grammatical structure of language, and the
parsing, translation, and transcription tasks that depend on it.

## Phrase-structure grammars

The n-gram models above see only a local window; they cannot capture that "black
dog" is well-formed while "dog black" is odd in English, because that fact is
about **structure**, not adjacency. A grammar generalizes over structure by
grouping words into **lexical categories** (part of speech — noun, verb) and
categories into **syntactic categories** like _noun phrase_ (NP) and _verb phrase_
(VP), then into trees.[^aima-grammar]

A **context-free grammar** (CFG) is a set of rewrite rules, each with a single
non-terminal on the left. A **probabilistic context-free grammar** (PCFG) attaches
a probability to each rule, so the grammar assigns a probability to every string.
A rule looks like

$$
VP \rightarrow Verb\ [0.70] \mid VP\ NP\ [0.30],
$$

reading: a verb phrase is a bare verb with probability 0.70, or a $VP$ followed by
an $NP$ with probability 0.30. AIMA builds a tiny grammar $\mathcal{E}_0$ for a
fragment of English, with a **lexicon** grouping words into categories and rules
combining them.

The output of parsing a sentence is a **parse tree**: nested phrases, each labeled
with its category, whose probability is the product of the rule probabilities
used.

$$
% caption: A parse tree for "Every wumpus smells" under a small PCFG. Interior nodes
% are syntactic categories with rule probabilities; the sentence probability is the
% product 0.90 x 0.25 x 0.05 x 0.15 x 0.40 x 0.10 = 0.0000675.
\begin{tikzpicture}[>=stealth, font=\small,
  nt/.style={draw=acc, text=acc, minimum width=10mm, minimum height=6mm, font=\footnotesize},
  lf/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[nt] (s) at (3,3) {S};
  \node[nt] (np) at (1.3,1.7) {NP};
  \node[nt] (vp) at (4.7,1.7) {VP};
  \node[nt] (art) at (0,0.3) {Article};
  \node[nt] (n) at (2.4,0.3) {Noun};
  \node[nt] (v) at (4.7,0.3) {Verb};
  \node[lf] (w1) at (0,-0.8) {Every};
  \node[lf] (w2) at (2.4,-0.8) {wumpus};
  \node[lf] (w3) at (4.7,-0.8) {smells};
  \draw (s) -- (np); \draw (s) -- (vp);
  \draw (np) -- (art); \draw (np) -- (n); \draw (vp) -- (v);
  \draw[black] (art) -- (w1); \draw[black] (n) -- (w2); \draw[black] (v) -- (w3);
\end{tikzpicture}
$$

Any grammar over a small hand-written rule set will both **overgenerate**
(accept nonsense like "Me go Boston") and **undergenerate** (reject valid
sentences). The generative power of a grammar formalism is classified by the
**Chomsky hierarchy**, which sorts grammars by the _form_ of their rewrite rules
into four nested classes, each strictly containing the one below:

- **Regular** grammars allow rules with a single nonterminal on the left and a
  terminal optionally followed by one nonterminal on the right ($X \to a\,Y$). They
  are exactly as powerful as finite-state machines. They can express $a^\ast{}b^\ast$ but
  not the balanced-parenthesis language $a^n b^n$ — counting requires memory a
  finite automaton does not have.
- **Context-free** grammars (CFGs) allow any single nonterminal on the left,
  rewritten in _any_ context ($X \to \gamma$). They add exactly the counting
  regular grammars lack: $a^n b^n$ is context-free, but $a^n b^n c^n$ — matching
  _three_ counts at once — is not.
- **Context-sensitive** grammars require only that the right side be at least as
  long as the left ($\alpha X \beta \to \alpha\gamma\beta$, so $X$ becomes $\gamma$
  only in the context of $\alpha$ and $\beta$). They can express $a^n b^n c^n$.
- **Recursively enumerable** (unrestricted) grammars place no constraint on the
  rules and are Turing-equivalent.

The containments are proper: each class recognizes strictly more languages than the
one below it, but at a cost — the higher up the hierarchy, the less efficient the
parsing algorithms. CFGs are the usual choice for natural and programming
languages, sitting at the sweet spot where cubic-time parsing (the next section)
is still possible, though some natural-language constructions (cross-serial
dependencies in Swiss German, for instance) are known to exceed context-free power.

$$
% caption: The Chomsky hierarchy as strictly nested classes, most restricted at the
% center. Each ring adds languages the inner ones cannot express: regular does
% $a^*b^*$, context-free adds $a^n b^n$, context-sensitive adds $a^n b^n c^n$, and
% unrestricted grammars are Turing-equivalent. The right-hand legend keys concrete
% instances to the smallest class that accepts them.
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc] (0,0) ellipse (4.4 and 3.2);
  \draw[acc] (0,-0.3) ellipse (3.3 and 2.4);
  \draw[acc] (0,-0.6) ellipse (2.2 and 1.6);
  \draw[acc] (0,-0.9) ellipse (1.2 and 0.85);
  \node[font=\scriptsize] at (0,-0.9) {regular};
  \node[font=\scriptsize] at (0,0.5)  {context-free};
  \node[font=\scriptsize] at (0,1.4)  {context-sensitive};
  \node[font=\scriptsize] at (0,2.5)  {recursively enumerable};
  \node[font=\scriptsize, text=black, anchor=west] at (5.2,1.0)  {aabb accepted: context-free};
  \node[font=\scriptsize, text=black, anchor=west] at (5.2,0.0)  {aabbcc accepted: context-sensitive};
  \node[font=\scriptsize, text=black, anchor=west] at (5.2,-1.0) {a*b* accepted: regular};
\end{tikzpicture}
$$

## Syntactic analysis (parsing)

**Parsing** recovers the phrase structure of a string according to a grammar.[^aima-parse]
One could search top-down (start from $S$, expand toward the words) or bottom-up
(start from the words, build up to $S$), but both repeat work: a substring
analyzed inside one branch of the search is re-analyzed in another. The fix is
**dynamic programming** — analyze each substring once, store the result in a table
called a **chart**, and reuse it. Parsers that do this are **chart parsers**.

The **CYK algorithm** is a bottom-up chart parser. It requires the grammar in
**Chomsky Normal Form** — every rule is either $X \rightarrow \text{word}$ or
$X \rightarrow Y\,Z$ — into which any CFG can be converted. CYK fills a table
$P[X, \text{start}, \text{length}]$ holding the probability of the most probable
constituent of category $X$, of that length, starting at that position; it works
from short spans to long ones, combining two adjacent subspans by every binary
rule.

```algorithm
caption: $\textsc{CYK-Parse}(\text{words}, \text{grammar})$ — most probable parse of every span
$N \gets \textsc{Length}(\text{words})$
$M \gets$ number of nonterminals in grammar
$P \gets$ array $[M, N, N]$, all $0$
for $i = 1$ to $N$ do // lexical rules: single words
  for each rule $(X \to \text{words}_i\ [p])$ do
    $P[X, i, 1] \gets p$
for $\text{length} = 2$ to $N$ do // combine, short spans first
  for $\text{start} = 1$ to $N - \text{length} + 1$ do
    for $\text{len1} = 1$ to $\text{length} - 1$ do
      $\text{len2} \gets \text{length} - \text{len1}$
      for each rule $(X \to Y\,Z\ [p])$ do
        $P[X, \text{start}, \text{length}] \gets \max(P[X, \text{start}, \text{length}],\ P[Y, \text{start}, \text{len1}] \times P[Z, \text{start} + \text{len1}, \text{len2}] \times p)$
return $P$
```

CYK uses $O(n^2 m)$ space and $O(n^3 m)$ time for $n$ words and $m$ nonterminals,
commonly written $O(n^3)$ since $m$ is fixed. Its virtue on ambiguous sentences is
that it never enumerates the parse trees — a sentence like "Fall leaves fall and
spring leaves spring" can have exponentially many parses, yet CYK computes the
probability of the _most probable_ tree in cubic time by storing shared subtrees
once in the chart.

$$
% caption: The CYK chart for a 4-word sentence. Cell (start, length) holds the best
% constituent spanning those words; the algorithm fills upward from single words
% (length 1) to the whole sentence, and the top cell is the sentence parse.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % grid: rows = length 1..4, cols = start 1..4
  \foreach \x in {0,1,2,3} {
    \foreach \y in {0,1,2,3} {
      \pgfmathtruncatemacro{\keep}{ifthenelse(\x+\y<4,1,0)}
      \ifnum\keep=1 \draw[black] (\x*1.5,\y*0.9) rectangle ++(1.5,0.9); \fi
    }
  }
  % labels bottom row (words)
  \node[font=\scriptsize] at (0.75,-0.45) {the};
  \node[font=\scriptsize] at (2.25,-0.45) {wumpus};
  \node[font=\scriptsize] at (3.75,-0.45) {is};
  \node[font=\scriptsize] at (5.25,-0.45) {dead};
  % fill some cells
  \node[acc] at (0.75,0.45) {Art};
  \node[acc] at (2.25,0.45) {Noun};
  \node[acc] at (3.75,0.45) {Verb};
  \node[acc] at (5.25,0.45) {Adj};
  \node[acc, fill=white, inner sep=1.5pt] at (1.5,1.35) {NP};
  \node[acc, fill=white, inner sep=1.5pt] at (4.5,1.35) {VP};
  \node[acc, fill=white, inner sep=1.5pt] at (3.0,3.15) {S};
  % axis labels outside the grid
  \node[anchor=east, font=\scriptsize] at (-0.15,0.45) {len 1};
  \node[anchor=east, font=\scriptsize] at (-0.15,3.15) {len 4};
\end{tikzpicture}
$$

### Filling the chart cell by cell

Run the numbers on "the wumpus is dead" with a tiny CNF grammar. The lexical rules
(each $X \to \text{word}\ [p]$) and the binary rules (each $X \to Y\,Z\ [p]$):

$$
\begin{aligned}
&\textit{Art} \to \text{the}\,[1.0], \quad
\textit{Noun} \to \text{wumpus}\,[1.0], \quad
\textit{Verb} \to \text{is}\,[1.0], \quad
\textit{Adj} \to \text{dead}\,[1.0]; \\
&NP \to \textit{Art}\ \textit{Noun}\,[0.6], \quad
VP \to \textit{Verb}\ \textit{Adj}\,[0.5], \quad
S \to NP\ VP\,[0.9].
\end{aligned}
$$

CYK indexes each cell by (start, length). Length-1 cells come straight from the
lexicon. Then it builds length-2 spans, and finally the length-4 span, each time
splitting the span every possible way and applying every binary rule. The filled
chart, with the one nonzero entry in each occupied cell:

| length \ start | 1 (the) | 2 (wumpus) | 3 (is) | 4 (dead) |
| --- | --- | --- | --- | --- |
| 1 | Art $= 1.0$ | Noun $= 1.0$ | Verb $= 1.0$ | Adj $= 1.0$ |
| 2 | NP $= 0.6$ | — | VP $= 0.5$ | |
| 3 | — | — | | |
| 4 | **S $= 0.27$** | | | |

The length-2 cell at start $1$ combines $\textit{Art}$ (start $1$, len $1$) with
$\textit{Noun}$ (start $2$, len $1$) under $NP \to \textit{Art}\ \textit{Noun}$:
$P = 1.0 \times 1.0 \times 0.6 = 0.6$. The length-2 cell at start $3$ combines
$\textit{Verb}$ and $\textit{Adj}$ under $VP$: $P = 1.0 \times 1.0 \times 0.5 =
0.5$. The middle spans (start $2$ len $2$; any len $3$) stay empty because no rule
combines $\textit{Noun}\ \textit{Verb}$ or the length-3 pieces. The top cell (start
$1$, len $4$) has only one productive split, len1 $= 2$ (the $NP$) plus len2 $= 2$
(the $VP$), under $S \to NP\ VP$:

$$
P[S, 1, 4] = \underbrace{P[NP, 1, 2]}_{0.6} \times \underbrace{P[VP, 3, 2]}_{0.5}
  \times \underbrace{0.9}_{S \to NP\ VP} = 0.27.
$$

Reading the back-pointers down from that top cell recovers the parse
$[S\ [NP\ [\textit{Art}\ \text{the}]\ [\textit{Noun}\ \text{wumpus}]]\ [VP\
[\textit{Verb}\ \text{is}]\ [\textit{Adj}\ \text{dead}]]]$ with probability
$0.27$. The other split of the length-4 span (len1 $= 1$: just $\textit{Art}$, plus
len2 $= 3$: empty) contributes nothing, which is why the $\max$ in the algorithm
leaves $0.27$ standing.

A PCFG's rule probabilities are learned by counting over a **treebank** — a corpus
of hand-parsed sentences, the Penn Treebank being the best known — or, harder,
from unparsed text with the **inside-outside algorithm**, the parsing analogue of
the forward-backward EM procedure for HMMs. The modern, neural version of this task
is the NLP subject's
[constituency parsing](/natural-language-processing/linguistic-structure/constituency-parsing)
lesson.

## Augmented grammars and semantic interpretation

Plain CFGs are too blunt: they cannot express that "I smell" is grammatical but "I
smells" is not (subject-verb agreement), nor that "eat a banana" is more probable
than "eat a bandanna" (a lexical dependency). An **augmented grammar** attaches
_variables_ to categories.[^aima-aug] Writing $NP(c, pn, head)$ threads a case
$c$, a person-number $pn$, and a **head** word through the rule, so a single rule
enforces agreement that would otherwise need an exponential blowup of subscripted
categories:

$$
S(head) \rightarrow NP(Sbj, pn, h)\ VP(pn, head).
$$

Read right-to-left: an $NP$ and a $VP$ form an $S$ only when the $NP$ is in the
subjective case and its person-number $pn$ matches the verb's. When these rules
are translated into logic they become a **definite clause grammar** (DCG), which
lets parsing be done by logical inference.

The same augmentation carries **semantics**. Under **compositional semantics**,
the meaning of a phrase is a function of the meanings of its parts. Attach a
semantic variable to each category, and each rule says how to combine the parts'
meanings. For arithmetic, $Exp(x) \rightarrow Exp(x_1)\ Operator(op)\ Exp(x_2)\ \{x = Apply(op, x_1, x_2)\}$
builds the value of an expression from its subexpressions. For English, "John loves
Mary" is built by giving the $VP$ "loves Mary" the $\lambda$-expression
$\lambda x\ Loves(x, \text{Mary})$ and applying it to the subject's meaning.

$$
% caption: Compositional semantics on "John loves Mary". Each node carries a meaning;
% the VP is a lambda-predicate, and applying it to the subject John yields the logical
% sentence Loves(John, Mary) at the root.
\begin{tikzpicture}[>=stealth, font=\small,
  nt/.style={draw=acc, text=acc, minimum height=6mm, font=\scriptsize, inner sep=3pt},
  lf/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[nt] (s) at (3,3) {S : Loves(John, Mary)};
  \node[nt] (np) at (0.4,1.6) {NP : John};
  \node[nt] (vp) at (4.6,1.6) {VP : lambda x. Loves(x, Mary)};
  \node[lf] (w1) at (0.4,0.5) {John};
  \node[nt] (v) at (3.7,0.5) {Verb};
  \node[nt] (np2) at (5.8,0.5) {NP : Mary};
  \node[lf] (w2) at (3.7,-0.5) {loves};
  \node[lf] (w3) at (5.8,-0.5) {Mary};
  \draw (s) -- (np); \draw (s) -- (vp);
  \draw (vp) -- (v); \draw (vp) -- (np2);
  \draw[black] (np) -- (w1); \draw[black] (v) -- (w2); \draw[black] (np2) -- (w3);
\end{tikzpicture}
$$

Full English adds **pragmatics** (resolving **indexicals** like "I" and "today"
against the situation, and reading the **speech act** — is the utterance a
statement, a question, a command?), **quantification** scope, **long-distance
dependencies**, and figures of speech like **metonymy** ("Chrysler announced ...")
and **metaphor**. **Disambiguation** — choosing the intended reading — needs four
models working together: a world model (what is likely true), a mental model (what
the speaker intends), a language model (what strings are likely), and, for speech,
an acoustic model. The last two are precisely the pieces the next two sections need.

## Machine translation

**Machine translation** (MT) converts text from a source language into a target
language.[^aima-mt] It is hard because languages carve up the world differently
(French "doux" spans English "soft," "sweet," and "gentle"), and a faithful
rendering may require understanding the situation, not just the words. Classical
systems span a range shown by the **Vauquois triangle** (Vauquois, 1968): a shallow
**transfer model** maps source structures directly to target structures, while a deep
**interlingua** system parses all the way to a language-independent meaning and
generates from there.

The triangle organizes every classical MT design by _how deep it analyzes before it
crosses to the target_. Its left side is **analysis**: starting from the source
words at the bottom-left corner, a system climbs through source syntax to source
semantics, and at the apex to an **interlingua** — a representation stripped of any
particular language, meaning alone. Its right side is **generation**, the mirror
descent from a target-side representation back down through target syntax to target
words. A translation is a path _up_ the left side, _across_ at some level, and _down_
the right. The crossing level names the approach:

- **Direct translation** crosses at the very bottom: substitute words (and reorder
  a little) with no structural analysis at all. Cheap, and adequate only for close
  languages.
- **Transfer** climbs partway — to syntax or shallow semantics — applies a set of
  bilingual **transfer rules** that rewrite a source structure into the corresponding
  target structure, then generates. It needs a separate rule set for each language
  _pair_ and each direction.
- **Interlingua** climbs to the apex, parsing the source into language-independent
  meaning, then generates the target from that meaning alone. It needs only an
  analyzer and a generator per language — $2n$ components for $n$ languages, against
  the $n(n-1)$ transfer systems every pair would otherwise require — but reaching a
  clean, fully language-neutral interlingua is hard.

$$
% caption: The Vauquois triangle (Vauquois, 1968). The left edge is analysis
% (source words up through source syntax and semantics to a language-independent
% interlingua at the apex); the right edge is generation (down through target
% semantics and syntax to target words). A translation goes up the left, across at
% some depth, and down the right. Direct translation crosses at the base, transfer
% at the syntactic or semantic level, interlingua at the apex; a deeper crossing
% means a shorter transfer but a harder analysis.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % triangle outline
  \draw[acc, thick] (0,0) -- (8,0) -- (4,4.4) -- cycle;
  % apex: interlingua
  \fill[acc] (4,4.4) circle (2pt);
  \node[acc, anchor=south, font=\footnotesize] at (4,4.5) {interlingua (meaning)};
  % left side analysis levels
  \fill[black] (1.45,1.6) circle (1.6pt);
  \node[black, anchor=east, font=\scriptsize] at (1.3,1.6) {source semantics};
  \fill[black] (0.73,0.8) circle (1.6pt);
  \node[black, anchor=east, font=\scriptsize] at (0.6,0.8) {source syntax};
  \fill[black] (0,0) circle (2pt);
  \node[black, anchor=north, font=\scriptsize] at (0,-0.1) {source words};
  % right side generation levels
  \fill[black] (6.55,1.6) circle (1.6pt);
  \node[black, anchor=west, font=\scriptsize] at (6.7,1.6) {target semantics};
  \fill[black] (7.27,0.8) circle (1.6pt);
  \node[black, anchor=west, font=\scriptsize] at (7.4,0.8) {target syntax};
  \fill[black] (8,0) circle (2pt);
  \node[black, anchor=north, font=\scriptsize] at (8,-0.1) {target words};
  % analysis / generation edge labels
  \node[acc, anchor=east, font=\scriptsize, rotate=48] at (1.7,3.1) {analysis};
  \node[acc, anchor=west, font=\scriptsize, rotate=-48] at (6.3,3.1) {generation};
  % crossing arrows at three depths
  \draw[red, ->, thick] (0.25,0.25) -- (7.75,0.25);
  \node[red, anchor=south, font=\scriptsize] at (4,0.3) {direct};
  \draw[red, ->, thick] (0.95,1.05) -- (7.05,1.05);
  \node[red, anchor=south, font=\scriptsize] at (4,1.1) {transfer};
  \draw[red, ->, thick] (1.75,1.95) -- (6.25,1.95);
  \node[red, anchor=south, font=\scriptsize] at (4,2.0) {deeper transfer};
\end{tikzpicture}
$$

The most successful classical approach is **statistical MT**, which learns from a
**bilingual corpus** of parallel texts and needs no hand-built grammar or
ontology. Cast as a noisy-channel problem, translating English $e$ into French
$f$ finds

$$
f^\ast = \argmax_{f} P(f \mid e) = \argmax_{f} P(e \mid f)\, P(f).
$$

The second equality is worth deriving, since the same step reappears in spam,
speech, and spelling correction. Bayes' rule expands the quantity we actually want,
$P(f \mid e)$, into

$$
P(f \mid e) = \frac{P(e \mid f)\,P(f)}{P(e)}.
$$

The denominator $P(e)$ is the probability of the English sentence we were _handed_.
It does not depend on the candidate French $f$, so as $f$ ranges over all
translations it is a fixed positive constant, and dividing every candidate's score
by the same constant cannot change which candidate is largest. Dropping it,

$$
\argmax_{f} P(f \mid e)
  = \argmax_{f} \frac{P(e \mid f)\,P(f)}{P(e)}
  = \argmax_{f} P(e \mid f)\,P(f).
$$

Here $P(f)$ is the target **language model** (how good is this French sentence?)
and $P(e \mid f)$ the **translation model** (how well does it correspond to the
English?). The benefit is a decomposition: instead of learning the one hard
distribution $P(f \mid e)$ directly, we learn a fluency model $P(f)$ from
monolingual French — of which there is far more — and a faithfulness model
$P(e \mid f)$ from the scarcer parallel corpus, and let Bayes' rule recombine them.
This is the **noisy-channel** shape: a source $f$ is imagined to pass through a
channel that garbles it into the observed $e$, and decoding inverts the channel.

$$
% caption: The noisy-channel decomposition shared by translation, speech, and spam.
% A hidden source (French sentence, spoken words, message intent) passes through a
% channel producing the observation (English, sound, email); decoding maximizes the
% product of a source prior P(source) and a channel likelihood P(observation | source).
\begin{tikzpicture}[>=stealth, font=\small,
  bx/.style={draw, minimum width=24mm, minimum height=9mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[bx, draw=acc, text=acc] (src) at (0,0)   {source f\\prior P(f)};
  \node[bx] (ch) at (4.2,0)  {channel\\P(e given f)};
  \node[bx] (obs) at (8.4,0) {observed e};
  \draw[->, acc] (src) -- (ch);
  \draw[->, acc] (ch) -- (obs);
  \draw[->, black] (obs.south) to[out=235,in=305] (src.south);
  \node[font=\scriptsize, anchor=north] at (4.2,-2.6) {decode: argmax over f of P(e given f) P(f)};
\end{tikzpicture}
$$

The language model $P(f)$ is a French n-gram model; the translation
model is learned from the parallel corpus by aligning **phrases** and modeling
their reordering with a **distortion** $d_i$, the shift each French phrase makes
relative to its predecessor. The full model factors as

$$
P(f, d \mid e) = \prod_i P(f_i \mid e_i)\, P(d_i).
$$

$$
% caption: Phrase-based statistical MT. The English sentence is split into phrases,
% each mapped to a French phrase with probability P(f_i given e_i), then reordered;
% the distortion d_i records how far each phrase moved. Crossing links are reorderings.
\begin{tikzpicture}[>=stealth, font=\small,
  en/.style={draw=acc, text=acc, minimum width=17mm, minimum height=7mm, font=\scriptsize},
  fr/.style={draw, minimum width=17mm, minimum height=7mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[en] (e1) at (0,1.4)   {There is a};
  \node[en] (e2) at (2.1,1.4) {smelly};
  \node[en] (e3) at (4.2,1.4) {wumpus};
  \node[en] (e4) at (6.3,1.4) {sleeping};
  \node[fr] (f1) at (0,0)     {Il y a un};
  \node[fr] (f2) at (2.1,0)   {wumpus};
  \node[fr] (f3) at (4.2,0)   {malodorant};
  \node[fr] (f4) at (6.3,0)   {qui dort};
  \draw[black] (e1) -- (f1);
  \draw[black] (e2) -- (f3); % smelly -> malodorant (crosses)
  \draw[black] (e3) -- (f2); % wumpus -> wumpus (crosses)
  \draw[black] (e4) -- (f4);
  \node[font=\scriptsize, anchor=north] at (2.1,-0.6) {d = +1};
  \node[font=\scriptsize, anchor=north] at (4.2,-0.6) {d = -2};
\end{tikzpicture}
$$

**Reading off the distortions.** The distortion is not the crossing-arrow picture's
"how far did this phrase move" in the loose sense; it is defined precisely by where
each French phrase's words sit. Number the French words left to right and set

$$
d_i = \START(f_i) - \END(f_{i-1}) - 1,
$$

where $\START(f_i)$ is the position of the first word of the $i$-th
English phrase's translation in the French output, and $\END(f_{i-1})$
the position of the last word of the previous phrase's translation. A phrase that
lands immediately after its predecessor gets $d = 0$. Take the ordering in the
figure, where the English phrases $e_1 e_2 e_3 e_4$ are realized in French as
$f_1$ (positions 1–4, "Il y a un"), then $f_3$ ("wumpus", position 5), then $f_2$
("malodorant", position 6), then $f_4$ ("qui dort", positions 7–8):

$$
\begin{aligned}
d_1 &= \START(f_1) - \END(f_0) - 1 = 1 - 0 - 1 = 0, \\
d_3 &= \START(f_3) - \END(f_1) - 1 = 5 - 4 - 1 = 0, \\
d_2 &= \START(f_2) - \END(f_3) - 1 = 6 - 5 - 1 = 0.
\end{aligned}
$$

The point of this definition is arithmetic, not linguistics. A sentence of
$n$ phrases has $n!$ possible orderings, an impossible number of parameters to
learn, but $d_i$ ranges only over $\{-n, \dots, +n\}$, so the whole distortion
distribution $P(d_i)$ has just $2n + 1$ entries. The model does not try to _explain_
why French puts the adjective after the noun — that fact lives in the French
language model $P(f)$; the distortion term only summarizes how volatile the
reordering tends to be, learned by counting how often each shift $d = 0, \pm 1, \pm
2, \dots$ occurs across the aligned corpus.

Because there are astronomically many candidate translations, the best $f$ is
found by beam search with a probability heuristic, not exhaustive enumeration. The
parameters are learned by aligning sentences and phrases in the corpus and refining
with EM. Neural MT — the encoder-decoder and attention models that supplanted this
pipeline — is the subject of the NLP
[machine translation](/natural-language-processing/applications/machine-translation)
lesson.

## Speech recognition

**Speech recognition** identifies the words a speaker uttered from the acoustic
signal.[^aima-asr] It is hard because sound is ambiguous: "recognize speech" and
"wreck a nice beach" sound nearly identical (**segmentation** — fast speech has no
pauses between words), the sounds of adjacent words blur (**coarticulation**), and
**homophones** like "to," "too," "two" sound the same. Like translation, it is a
noisy-channel problem. Seeking the most probable word sequence given the sounds,

$$
\argmax_{\text{word}_{1:t}} P(\text{word}_{1:t} \mid \text{sound}_{1:t})
  = \argmax_{\text{word}_{1:t}} P(\text{sound}_{1:t} \mid \text{word}_{1:t})\, P(\text{word}_{1:t}),
$$

where $P(\text{sound} \mid \text{word})$ is the **acoustic model** (how words
sound) and $P(\text{word})$ is the **language model** (which word sequences are
likely — "ceiling fan" beats "sealing fan"). Claude Shannon named this the **noisy
channel model**: the words are a message sent over a noisy channel and received as
sounds.

The acoustic signal is sampled (typically 8 kHz), sliced into ~10 ms **frames**,
and each frame summarized by a feature vector (mel-frequency cepstral
coefficients). Words are modeled as sequences of **phones** — the ~100 basic
speech sounds, written in the ARPAbet — and each phone is a small HMM (onset,
middle, end) whose self-loops absorb variation in duration. A **pronunciation
model** strings phone HMMs into a word, allowing dialect and coarticulation
variants.

$$
% caption: The speech pipeline as nested HMMs. The language model proposes word
% sequences; a pronunciation model expands each word into phones; each phone is a
% three-state HMM emitting acoustic frames. Viterbi finds the best word sequence.
\begin{tikzpicture}[>=stealth, font=\small,
  lv/.style={draw, minimum width=24mm, minimum height=8mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lv, draw=acc, text=acc] (lm) at (0,3) {language model\\P(word sequence)};
  \node[lv] (pr) at (0,1.5) {pronunciation\\word to phones};
  \node[lv] (ph) at (0,0)   {phone HMMs\\phones to frames};
  \node[lv] (ac) at (0,-1.5) {acoustic frames\\(MFCC features)};
  \draw[->, acc] (lm) -- (pr);
  \draw[->, acc] (pr) -- (ph);
  \draw[->, acc] (ph) -- (ac);
  \node[font=\scriptsize, anchor=west] at (2.0,0.75) {Viterbi decodes bottom-up};
  \draw[->, black] (2.0,-0.9) -- (2.0,2.4);
\end{tikzpicture}
$$

With acoustic and language models in hand, the most probable word sequence is
decoded with the **Viterbi algorithm** over the combined HMM.

**A two-step Viterbi trace.** Viterbi is dynamic programming over the trellis of
states and time steps: it keeps, for each state, the probability of the single best
path that ends there, and extends it one frame at a time. Take a stripped-down word
HMM with two hidden phone states, $A$ and $B$, start probabilities $\pi_A = 0.6$,
$\pi_B = 0.4$, transition probabilities $P(A \mid A) = 0.7$, $P(B \mid A) = 0.3$,
$P(A \mid B) = 0.4$, $P(B \mid B) = 0.6$, and observation likelihoods for the two
frames $o_1, o_2$ actually heard: $P(o_1 \mid A) = 0.5$, $P(o_1 \mid B) = 0.1$,
$P(o_2 \mid A) = 0.2$, $P(o_2 \mid B) = 0.6$. Write $\delta_t(s)$ for the best-path
probability into state $s$ at time $t$.

Step 1 (initialize on $o_1$): $\delta_1(A) = \pi_A\,P(o_1 \mid A) = 0.6 \cdot 0.5 =
0.30$ and $\delta_1(B) = \pi_B\,P(o_1 \mid B) = 0.4 \cdot 0.1 = 0.04$.

Step 2 (recurse on $o_2$): for each state, take the better of the two incoming
paths, then multiply by that state's emission of $o_2$.

$$
\begin{aligned}
\delta_2(A) &= \max\big(\underbrace{0.30 \cdot 0.7}_{A\to A},\ \underbrace{0.04 \cdot 0.4}_{B\to A}\big)\,P(o_2 \mid A)
   = \max(0.210, 0.016)\cdot 0.2 = 0.210 \cdot 0.2 = 0.042, \\
\delta_2(B) &= \max\big(\underbrace{0.30 \cdot 0.3}_{A\to B},\ \underbrace{0.04 \cdot 0.6}_{B\to B}\big)\,P(o_2 \mid B)
   = \max(0.090, 0.024)\cdot 0.6 = 0.090 \cdot 0.6 = 0.054.
\end{aligned}
$$

The best final state is $B$ ($0.054 > 0.042$), and its back-pointer names $A$ as
the winning predecessor, so the decoded state path is $A \to B$. Both winning
transitions came from $A$ at time 1, which is why Viterbi stores one back-pointer
per state rather than enumerating all $2^2$ paths — and over a real utterance of
hundreds of frames, that is the difference between linear and exponential work.

Parameters are
learned by EM from a corpus of speech paired with transcripts, replacing the
laborious hand-labeling of spectrograms used in early systems. Accuracy depends on
vocabulary size — word error rate is below 0.5% for the 11 digit words but rises to
~20% on a 64,000-word corpus — and on microphone quality and task constraint. The
modern end-to-end neural approach is the NLP subject's
[automatic speech recognition](/natural-language-processing/speech/automatic-speech-recognition)
lesson.

## From n-grams to transformers

Everything above predates the deep-learning turn, and AIMA's 3rd edition (2009)
catches the classical account just before it was overtaken. What replaced the
n-gram table and the HMM kept the problems — the argmax over word sequences, the
encoder/decoder split, the noisy channel — and changed the _representation_ of the
distributions inside them. Tracing the replacement clarifies which parts
of this lesson are permanent and which were artifacts of counting.

**The bottleneck the classical models shared.** An n-gram model represents a word
as an atomic symbol, so "cat" and "kitten" are as unrelated as "cat" and
"Tuesday": the model has no notion that some words are close in meaning. And a
trigram sees only two words of context; the count table for a five-word window over
a $10^5$-word vocabulary would need $10^{25}$ entries, so the Markov horizon is
short by necessity, not choice. Both limits are about representation. The neural
line of work attacked exactly these two.

**Distributed word embeddings (2013).** Mikolov et al. ("Efficient Estimation of
Word Representations in Vector Space," 2013) trained shallow networks —
skip-gram and CBOW, together called **word2vec** — to predict a word from its
neighbors, and read off the hidden layer as a dense vector for each word. Words
used in similar contexts landed near each other in the vector space, so "cat" and
"kitten" became close, and the vectors even supported analogies by arithmetic
(the widely reported $\textit{king} - \textit{man} + \textit{woman} \approx
\textit{queen}$ regularity). This dissolved the atomic-symbol problem: a word was
now a point in a continuous space where similarity is a distance.

**Sequence-to-sequence and attention (2014–2015).** Sutskever, Vinyals & Le
("Sequence to Sequence Learning with Neural Networks," NeurIPS 2014) built a
translator from two recurrent networks — an **encoder** that reads the source
sentence into a fixed-length vector, and a **decoder** that unrolls that vector
into the target sentence. This is the same encoder/decoder division AIMA describes
for statistical MT, now with learned recurrent states instead of phrase tables and
distortion counts. The fixed-length vector was the weak point: a long sentence had
to be crushed into one vector. Bahdanau, Cho & Bengio ("Neural Machine Translation
by Jointly Learning to Align and Translate," ICLR 2015) added **attention** — at
each output step the decoder computes a weighted average over _all_ encoder states,
learning where to look. Attention is a learned, soft version of the alignment that
phrase-based MT computed by counting, and it lifted the fixed-window limit.

**The transformer (2017).** Vaswani et al. ("Attention Is All You Need," NeurIPS
2017) removed the recurrence entirely and kept only the attention. In
**self-attention**, every position attends to every other position in the sequence
in one parallel operation, so the effective context is the whole sentence rather
than a fixed $n-1$ window, and there is no left-to-right recurrence to serialize —
the whole sequence is processed at once. This is the sharpest break with the n-gram
picture: where a trigram conditions on the two preceding symbols, a transformer
layer conditions on every symbol, with learned weights deciding which ones matter.

$$
% caption: The context each model conditions on when predicting the word "sat". A
% trigram (top) sees only the two preceding words, a fixed window of n-1 = 2.
% Self-attention (bottom) weights every word in the sequence, so the context is the
% whole span; the arrow thickness would encode the learned attention weights.
\begin{tikzpicture}[>=stealth, font=\small,
  tok/.style={draw, minimum width=11mm, minimum height=7mm, font=\footnotesize},
  hot/.style={draw=acc, text=acc, minimum width=11mm, minimum height=7mm, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % top: trigram
  \node[font=\scriptsize, anchor=east, text=black] at (-0.9,2.2) {n-gram};
  \node[tok] (a1) at (0,2.2)   {the};
  \node[tok] (a2) at (1.5,2.2) {cat};
  \node[hot] (a3) at (3.0,2.2) {sat};
  \node[tok] (a4) at (4.5,2.2) {on};
  \node[tok] (a5) at (6.0,2.2) {the};
  \draw[->, acc] (a1.north) to[bend left=25] (a3.north);
  \draw[->, acc] (a2.north) to[bend left=20] (a3.north);
  % bottom: self-attention
  \node[font=\scriptsize, anchor=east, text=black] at (-0.9,0) {self-attention};
  \node[tok] (b1) at (0,0)   {the};
  \node[tok] (b2) at (1.5,0) {cat};
  \node[hot] (b3) at (3.0,0) {sat};
  \node[tok] (b4) at (4.5,0) {on};
  \node[tok] (b5) at (6.0,0) {the};
  \draw[->, acc] (b1.south) to[bend right=30] (b3.south);
  \draw[->, acc] (b2.south) to[bend right=22] (b3.south);
  \draw[->, acc] (b4.south) to[bend left=22]  (b3.south);
  \draw[->, acc] (b5.south) to[bend left=30]  (b3.south);
\end{tikzpicture}
$$

**Pretraining at scale (2019–2020).** With the architecture fixed, the last shift
was in how it was trained. Devlin et al. ("BERT: Pre-training of Deep Bidirectional
Transformers for Language Understanding," NAACL 2019) pretrained a transformer on a
masked-language-modeling objective — hide some words and predict them from _both_
sides — producing representations that, fine-tuned, set new results across many
language tasks. Where the n-gram language model is strictly left-to-right, BERT is
bidirectional, conditioning each prediction on the full surrounding context. Brown
et al. ("Language Models are Few-Shot Learners," NeurIPS 2020) scaled a
left-to-right transformer to 175 billion parameters as **GPT-3** and showed that at
that scale the model performs new tasks from a few examples given in the prompt,
with no gradient updates — **in-context few-shot learning**. These are results
about what a large pretrained language model can do; they do not change the
underlying object, which is still a distribution over word sequences.

**What survived.** The through-line is that the _shape_ of every task in this
lesson carried over intact. A GPT-style model still scores text as an argmax over
$P(\text{word}_{1:n})$ — the same quantity the trigram estimated, now factored
left-to-right as $\prod_i P(w_i \mid w_{1:i-1})$ with the full history instead of a
two-word window. Neural translation still splits an encoder that reads the source
from a decoder that generates the target, exactly the division of statistical MT.
Classification is still $\argmax_c P(c \mid \text{text})$. What
changed is what fills the probabilities: learned continuous representations in place
of count tables, and attention over the whole sequence in place of a fixed Markov
horizon. The classical models named the problems cleanly, which is why they remain
worth knowing; the neural models solved them better by fixing the representation.
The full modern treatment — embeddings, transformers, pretraining, and the tasks
rebuilt on them — is the sibling
[natural language processing](/natural-language-processing/foundations/what-is-nlp)
subject.

## Where this sits

Two patterns run through the whole chapter. The first is the **noisy-channel
model**: classification, translation, and speech recognition all reduce to
$\argmax\ P(\text{observation} \mid \text{source})\,P(\text{source})$,
a likelihood times a prior recovered by Bayes' rule — the same shape as
[diagnosis with probability](/artificial-intelligence/uncertainty/probability-and-bayes).
The second is the split between **statistics and structure**: n-gram and HMM
models win on translation and speech precisely because large corpora exist for
those tasks, while structured parsing lags because parsed corpora are scarce and
parsing is rarely an end in itself.

Both patterns survived the deep-learning transition even as the models
underneath were replaced: a transformer language model is still an
$\argmax$ over $P(\text{word sequence})$, and neural translation
still separates an encoder that reads the source from a decoder that models the
target. That is the throughline to the
[natural language processing](/natural-language-processing/foundations/what-is-nlp)
subject — same problems, sharper tools. Language is the interface between an agent
and the knowledge and people it must work with, which is why it closes the loop
from perception through reasoning to
[decision-making](/artificial-intelligence/uncertainty/making-decisions).

[^aima-grammar]: **AIMA**, §23.1 — Phrase Structure Grammars: lexical and syntactic categories, context-free and probabilistic context-free grammars, parse trees, over- and undergeneration, and the Chomsky hierarchy of generative capacity.
[^aima-parse]: **AIMA**, §23.2 — Syntactic Analysis (Parsing): top-down versus bottom-up search, chart parsing by dynamic programming, the CYK algorithm and Chomsky Normal Form, its $O(n^3 m)$ complexity, and learning PCFG probabilities from a treebank or by the inside-outside algorithm.
[^aima-aug]: **AIMA**, §23.3 — Augmented Grammars and Semantic Interpretation: augmenting categories with case, agreement, and head variables; definite clause grammars; compositional ($\lambda$-based) semantics; and the pragmatics of indexicals, speech acts, quantification, metonymy, and disambiguation.
[^aima-mt]: **AIMA**, §23.4 — Machine Translation: the Vauquois triangle (transfer versus interlingua), the noisy-channel decomposition into language and translation models, phrase-based statistical MT with distortion, and learning from bilingual corpora.
[^aima-asr]: **AIMA**, §23.5 — Speech Recognition: the noisy-channel decomposition into acoustic and language models, segmentation/coarticulation/homophone difficulties, frames and MFCC features, phone HMMs and pronunciation models, and Viterbi decoding.