30 · The Noisy Channel Model — Brown et al. (1990)

30 · The Noisy Channel Model — Brown et al. (1990)#

Dependencies: stdlib + numpy Runtime: < 1 min CPU

“We are led, therefore, to a model in which the English string e is passed through a noisy channel… and emerges as the French string f.” — Brown et al., 1990

The IBM MT group’s landmark paper “A Statistical Approach to Machine Translation” (1990) did not invent a new algorithm — it reframed the entire problem. Instead of hand-crafting translation rules, they asked: what if translation were a communication problem?

This chapter develops the noisy channel intuition, shows why it is mathematically beautiful, and lays the statistical foundation for IBM Models 1–5 (chapters 31–32) and phrase-based SMT (chapter 33).

# Colab setup: install this part's pinned dependencies (skipped outside Colab).
import sys
if "google.colab" in sys.modules:
    import subprocess
    subprocess.run(["wget", "-q", "-O", "requirements_part3.txt",
        "https://raw.githubusercontent.com/eduardosanchezg/mthistory/main/requirements_part3.txt"])
    subprocess.run(["pip", "install", "-q", "-r", "requirements_part3.txt"])

import math
import json
import os
import re
from collections import Counter, defaultdict
import numpy as np

1 · The Noisy Channel Decomposition#

Given a foreign sentence f, we want the English sentence e that is most likely given f:

\[ \hat{e} = \arg\max_e P(e \mid f) \]

Bayes’ theorem gives us the noisy channel decomposition:

\[ P(e \mid f) = \frac{P(f \mid e) \cdot P(e)}{P(f)} \propto P(f \mid e) \cdot P(e) \]

This separates into two independent, improvable components:

Term	Name	What it models
$P(f \mid e)$	Translation model	How likely is this French given this English?
$P(e)$	Language model	How likely is this English sentence in general?

Why is this useful? Before 1990, MT systems had a single monolithic component that had to handle both fluency (is this good English?) and faithfulness (does this match the French?). The noisy channel separates concerns: you can train a better language model on any English text — you don’t need parallel data for it. And you can improve the translation model independently.

2 · A Worked Example with Toy Distributions#

Let’s build the smallest possible noisy channel system and watch it decode.

# ---------------------------------------------------------------------------
# Toy translation model  P(f_word | e_word)
# English vocabulary: {dog, cat, fish}
# German vocabulary: {Hund, Katze, Fisch, der, die, das}
# ---------------------------------------------------------------------------

# P(f | e) — emission probabilities
trans_model = {
    # German word  English word   P(f|e)
    ("Hund",   "dog"):  0.80,
    ("Hund",   "cat"):  0.10,
    ("Hund",   "fish"): 0.10,
    ("Katze",  "cat"):  0.90,
    ("Katze",  "dog"):  0.05,
    ("Katze",  "fish"): 0.05,
    ("Fisch",  "fish"): 0.85,
    ("Fisch",  "dog"):  0.10,
    ("Fisch",  "cat"):  0.05,
    ("der",    "dog"):  0.50,   # articles are ambiguous
    ("der",    "cat"):  0.30,
    ("der",    "fish"): 0.20,
    ("die",    "cat"):  0.60,
    ("die",    "dog"):  0.20,
    ("die",    "fish"): 0.20,
    ("das",    "fish"): 0.50,
    ("das",    "dog"):  0.30,
    ("das",    "cat"):  0.20,
}

# ---------------------------------------------------------------------------
# Toy language model  P(e)  for short English sentences
# ---------------------------------------------------------------------------

lm = {
    "the dog runs":   0.30,
    "a dog runs":     0.15,
    "the cat sleeps": 0.25,
    "a cat sleeps":   0.15,
    "the fish swims": 0.10,
    "a fish swims":   0.05,
}

print("Translation model entries:", len(trans_model))
print("Language model entries:   ", len(lm))
print()
print("Sample P(f|e) values:")
for (f, e), p in list(trans_model.items())[:6]:
    print(f"  P({f:6s} | {e:4s}) = {p:.2f}")

Decoding: given German input, find best English#

We assume a simple bag-of-words translation model for now: the probability of the German sentence is the product of per-word translation probabilities (averaged over English words). IBM Model 1 will make this principled — for now we just want to see the noisy channel in action.

def sentence_trans_prob(f_sent, e_sent, tm):
    """
    Bag-of-words approximation to P(f | e).
    For each German word, take the max P(f_word | e_word) over English words.
    (Simplified — IBM Model 1 uses the proper sum over alignments.)
    """
    f_words = f_sent.lower().split()
    e_words = e_sent.lower().split()
    log_prob = 0.0
    for f_w in f_words:
        best = max((tm.get((f_w, e_w), 1e-9) for e_w in e_words), default=1e-9)
        log_prob += math.log(best)
    return math.exp(log_prob)


def noisy_channel_decode(f_input, trans_model, lm):
    """
    Enumerate all candidate English sentences, score with noisy channel,
    return ranked list of (score, sentence) tuples.
    """
    results = []
    for e_sent, p_e in lm.items():
        p_f_given_e = sentence_trans_prob(f_input, e_sent, trans_model)
        score = p_f_given_e * p_e
        results.append((score, e_sent))

    # Normalise so scores sum to 1 (posterior P(e|f))
    total = sum(s for s, _ in results)
    results = [(s / total, e) for s, e in results]
    results.sort(reverse=True)
    return results


# --- Run the decoder ---
test_inputs = [
    "der Hund",
    "die Katze",
    "das Fisch",
    "Hund Katze",
]

for german in test_inputs:
    print(f"\nInput (German): '{german}'")
    print(f"{'Rank':>4}  {'P(e|f)':>10}  English")
    print("-" * 40)
    for rank, (score, e) in enumerate(noisy_channel_decode(german, trans_model, lm), 1):
        print(f"  {rank:2d}  {score:10.4f}  {e}")

3 · Channel Capacity and Shannon’s Entropy#

In Chapter 00 we computed Shannon entropy on language. The noisy channel interpretation gives us a way to think about translation difficulty using the same information-theoretic tools.

Mutual Information $I(E; F)$ measures how much knowing the German sentence $f$ reduces our uncertainty about the English $e$:

\[ I(E; F) = H(E) - H(E \mid F) \]

$H(E)$ = entropy of the English language model (how uncertain are we about English?)
$H(E \mid F)$ = conditional entropy (how uncertain are we after seeing German?)
$I(E; F)$ = the “channel capacity” — how much information translation preserves

Perfect translation would have $I(E; F) = H(E)$: knowing the German resolves all uncertainty about English.

def entropy_bits(dist):
    """Entropy of a distribution (dict of prob values) in bits."""
    return -sum(p * math.log2(p) for p in dist.values() if p > 0)


# H(E) — entropy of the language model (prior over English sentences)
H_E = entropy_bits(lm)
print(f"H(E) = {H_E:.3f} bits  (uncertainty about English sentence)")

# H(E | F) — expected conditional entropy after observing each German input
# We use our four test inputs with equal probability
test_inputs_for_mi = ["der Hund", "die Katze", "das Fisch", "Hund Katze"]

H_E_given_F = 0.0
p_f_uniform = 1.0 / len(test_inputs_for_mi)
for f in test_inputs_for_mi:
    posterior = dict(noisy_channel_decode(f, trans_model, lm))
    h_e_given_this_f = entropy_bits(posterior)
    H_E_given_F += p_f_uniform * h_e_given_this_f
    print(f"  H(E|F='{f}') = {h_e_given_this_f:.3f} bits")

MI = H_E - H_E_given_F
print(f"\nH(E|F) = {H_E_given_F:.3f} bits  (residual uncertainty after seeing German)")
print(f"I(E;F) = {MI:.3f} bits  (mutual information = information preserved by translation)")
print(f"\nChannel efficiency = {MI/H_E*100:.1f}%  (how much uncertainty the German resolves)")

4 · Decoding = Search#

The theoretical decoder is:

\[ \hat{e} = \arg\max_e P(f \mid e) \cdot P(e) \]

In the toy example we enumerated all 6 candidate English sentences. In reality, there are roughly $V^n$ possible English sentences of length $n$. For $V = 50{,}000$ and $n = 20$, this is $10^{93}$ candidates — larger than the number of atoms in the observable universe.

Beam search is the practical solution: instead of keeping all hypotheses, keep only the $k$ best at each step (the “beam”). Chapter 33 implements beam search properly for phrase-based SMT.

The table below shows how the search space explodes:

import numpy as np

print(f"{'Length':>8}  {'Exact (V=50k)':>20}  {'Beam k=10':>12}  {'Beam k=100':>12}")
print("-" * 60)
V = 50_000
for n in [5, 10, 15, 20, 30]:
    exact = V ** n
    beam10 = 10 * n * V      # operations (not states)
    beam100 = 100 * n * V
    exact_str = f"10^{math.log10(exact):.0f}" if exact > 1e10 else str(exact)
    print(f"{n:>8}  {exact_str:>20}  {beam10:>12,}  {beam100:>12,}")

print()
print("Beam search makes decoding tractable by pruning to the k most promising")
print("partial hypotheses at each position. The quality loss vs. exact search")
print("is small when k >= 10 for typical sentence lengths.")

5 · Historical Context: The Hansard Corpus#

The IBM group’s key resource was the Canadian Hansard — the bilingual (French-English) proceedings of the Canadian parliament, containing roughly 3 million sentence pairs.

Resource	Scale	Notes
Georgetown-IBM demo (1954)	63 sentences	Hand-crafted
Brown et al. (1990) Hansard	~3 million pairs	Auto-aligned
Multi30k (2016)	29,000 pairs	Images + captions
WMT18 En-De	~5.9 million pairs	News text

The Hansard was revolutionary because:

It was large — large enough for EM to find reliable patterns
It was naturally parallel — both language versions recorded the same debates
It was public — the Canadian government published it freely

The IBM team’s Candide system, trained on the Hansard, achieved BLEU ~12 — the first quantitatively measured baseline for statistical MT. Every subsequent chapter in Part 3 is measured against this lineage.

Why separating P(f|e) and P(e) was a breakthrough#

Before the noisy channel, a translation system had to learn from parallel data alone. With the decomposition:

P(e) can be trained on any English text — news articles, books, Wikipedia. More data = more fluent output.
P(f|e) only needs parallel data, but focused on what words translate to what, not fluency.
Improvements in monolingual English corpora automatically improved translation quality.

This data-efficiency argument was the key insight that made SMT practical.

6 · Corpus Statistics on Multi30k (foreshadowing IBM Model 1)#

Before building the full EM algorithm (Chapter 31), let’s look at raw co-occurrence counts from aligned sentence pairs. The EM intuition: words that frequently co-occur across aligned sentences are likely translations of each other.

# ---------------------------------------------------------------------------
# Fallback corpus — 20 aligned EN/DE sentence pairs
# Used when data/multi30k/ is not present
# ---------------------------------------------------------------------------

FALLBACK_EN = """A man in an orange hat starring at something .
A Boston Terrier is running on lush green grass in front of a white fence .
A girl in karate uniform striking a rock .
Two women pushing a cart full of cans across a field .
A man is skateboarding down a flight of concrete stairs .
A man in a black shirt and black shorts is doing a trick on a skateboard .
Two girls are posing together for a photo .
A man and a woman are dancing in a street .
A young boy jumps off a diving board into a pool .
A group of people are gathered around a fire .
A woman is sitting on a bench reading a book .
A dog is running through the snow .
Several children are playing on a playground .
A man is riding a bicycle on a dirt road .
A woman in a red dress is walking down the street .
A boy and a girl are playing in the sand .
A group of hikers are climbing a steep mountain trail .
A man is playing guitar on a stage .
Two dogs are playing fetch in a park .
A child is blowing out candles on a birthday cake .""".strip().split("\n")

FALLBACK_DE = """Ein Mann mit einem orangefarbenen Hut starrt auf etwas .
Ein Boston Terrier läuft auf üppigem grünem Gras vor einem weißen Zaun .
Ein Mädchen in einer Karate-Uniform schlägt auf einen Stein ein .
Zwei Frauen schieben einen mit Dosen gefüllten Wagen über ein Feld .
Ein Mann fährt mit einem Skateboard eine Betontreppe hinunter .
Ein Mann in einem schwarzen Hemd und schwarzen Shorts macht einen Trick auf einem Skateboard .
Zwei Mädchen posieren zusammen für ein Foto .
Ein Mann und eine Frau tanzen auf einer Straße .
Ein kleiner Junge springt von einem Sprungbrett in einen Pool .
Eine Gruppe von Menschen versammelt sich um ein Feuer .
Eine Frau sitzt auf einer Bank und liest ein Buch .
Ein Hund läuft durch den Schnee .
Mehrere Kinder spielen auf einem Spielplatz .
Ein Mann fährt mit dem Fahrrad auf einer unbefestigten Straße .
Eine Frau in einem roten Kleid läuft die Straße entlang .
Ein Junge und ein Mädchen spielen im Sand .
Eine Gruppe von Wanderern besteigt einen steilen Bergpfad .
Ein Mann spielt Gitarre auf einer Bühne .
Zwei Hunde spielen Apportieren in einem Park .
Ein Kind bläst Kerzen auf einer Geburtstagstorte aus .""".strip().split("\n")


def load_bitext(en_path=None, de_path=None):
    """Load aligned EN/DE sentence pairs. Falls back to FALLBACK corpus."""
    base = os.path.join(os.path.dirname(os.path.abspath("__file__")),
                        "..", "..", "data", "multi30k")
    if en_path is None:
        en_path = os.path.join(base, "train.en")
    if de_path is None:
        de_path = os.path.join(base, "train.de")

    if os.path.exists(en_path) and os.path.exists(de_path):
        with open(en_path) as f:
            en_sents = [l.strip() for l in f if l.strip()]
        with open(de_path) as f:
            de_sents = [l.strip() for l in f if l.strip()]
        n = min(len(en_sents), len(de_sents))
        print(f"Loaded Multi30k: {n:,} aligned pairs.")
        return en_sents[:n], de_sents[:n]
    else:
        print(f"Multi30k not found at {en_path!r}.")
        print(f"Using built-in fallback corpus ({len(FALLBACK_EN)} pairs).")
        return FALLBACK_EN, FALLBACK_DE


en_sents, de_sents = load_bitext()
print(f"\nFirst pair:")
print(f"  EN: {en_sents[0]}")
print(f"  DE: {de_sents[0]}")

def simple_tokenize(text):
    return re.sub(r"[^\w\s]", " ", text.lower()).split()


def cooccurrence_counts(en_sents, de_sents):
    """
    Count how many times each (EN word, DE word) pair appear in the same
    aligned sentence pair.  This is the raw signal IBM Model 1 will refine.
    """
    counts = Counter()
    en_vocab = Counter()
    de_vocab = Counter()
    for en, de in zip(en_sents, de_sents):
        en_words = set(simple_tokenize(en))
        de_words = set(simple_tokenize(de))
        en_vocab.update(simple_tokenize(en))
        de_vocab.update(simple_tokenize(de))
        for e in en_words:
            for f in de_words:
                counts[(e, f)] += 1
    return counts, en_vocab, de_vocab


cooc, en_vocab, de_vocab = cooccurrence_counts(en_sents, de_sents)

print(f"EN vocab size: {len(en_vocab):,}")
print(f"DE vocab size: {len(de_vocab):,}")
print(f"Co-occurring (EN, DE) pairs: {len(cooc):,}")
print()

# --- Show top co-occurrences for a few English words ---
focus_words = ["man", "dog", "woman", "running", "playing"]
print(f"{'EN word':>10}  Top German co-occurrences (count)")
print("-" * 55)
for en_w in focus_words:
    relevant = {f: c for (e, f), c in cooc.items() if e == en_w}
    top = sorted(relevant.items(), key=lambda x: -x[1])[:5]
    top_str = ", ".join(f"{f}({c})" for f, c in top)
    print(f"{en_w:>10}  {top_str}")

# Normalise co-occurrence counts to get a crude P(f|e) estimate
# This is essentially IBM Model 0 — uniform alignment, word counts only

def crude_translation_probs(cooc, en_vocab):
    """
    P(f|e) ≈ count(e,f) / sum_f' count(e,f')
    This is Model 0 — ignores alignment entirely.
    """
    en_totals = Counter()
    for (e, f), c in cooc.items():
        en_totals[e] += c

    tm = {}
    for (e, f), c in cooc.items():
        tm[(e, f)] = c / en_totals[e]
    return tm


crude_tm = crude_translation_probs(cooc, en_vocab)

# Show crude translation table for a few words
print("Crude P(DE word | EN word)  — Model 0 estimate (before EM):")
print()
for en_w in ["man", "woman", "dog", "running"]:
    relevant = {f: p for (e, f), p in crude_tm.items() if e == en_w}
    top = sorted(relevant.items(), key=lambda x: -x[1])[:5]
    print(f"  P(? | '{en_w}'):")
    for f, p in top:
        bar = "█" * int(p * 30)
        print(f"    {f:20s} {p:.3f} {bar}")
    print()

print("Note: EM (IBM Model 1, Chapter 31) will sharpen these distributions significantly.")

Time Machine · Noisy Channel Posterior#

Every chapter runs the same 20 held-out test sentences so the quality arc across chapters is directly comparable.

This chapter doesn’t produce translations yet — we don’t have a trained translation model. Instead, we show the noisy channel posterior $P(e \mid f)$ using our toy model, and project what quality we’ll achieve once IBM Model 1 is trained.

TIME_MACHINE_EN = [
    "A man is walking his dog in the park .",
    "Two children are playing near a fountain .",
    "A woman is reading a book on a bench .",
    "The dog is running through the snow .",
    "A group of people are watching a soccer game .",
    "A young girl is jumping rope in the street .",
    "Several men are fishing at the lake .",
    "A woman in a red dress is dancing .",
    "Two boys are riding bicycles on a path .",
    "A cat is sleeping on a windowsill .",
    "A man is playing guitar at a concert .",
    "Children are swimming in the ocean .",
    "A woman is cooking dinner in the kitchen .",
    "A dog is catching a frisbee in a field .",
    "Two men are playing chess in the park .",
    "A girl is painting a picture outdoors .",
    "A man is climbing a rock face .",
    "Several people are hiking through the forest .",
    "A woman is pushing a stroller in the park .",
    "Two friends are sharing a meal at a table .",
]

# Run crude noisy channel on the toy vocabulary
print("=" * 65)
print("TIME MACHINE — Chapter 30: Noisy Channel Model (toy system)")
print("=" * 65)
print()
print("Translation quality: not applicable (toy 3-word vocabulary)")
print("Posterior P(e|f) on toy inputs:")
print()

toy_inputs = [
    ("der Hund", "the dog"),
    ("die Katze", "the cat"),
    ("das Fisch",  "the fish"),
]

for german, expected in toy_inputs:
    results = noisy_channel_decode(german, trans_model, lm)
    best_score, best_e = results[0]
    correct = "✓" if expected in best_e else " "
    print(f"  German: '{german}'")
    print(f"  Best:   '{best_e}'  (P={best_score:.3f}) {correct}")
    print()

print("Chapter progression (projected BLEU scores after training):")
print(f"  Ch 30 (Noisy Channel concept)  : —   (no decoder yet)")
print(f"  Ch 31 (IBM Model 1 EM)         : ~5  BLEU")
print(f"  Ch 33 (Phrase-based SMT)       : ~18 BLEU")
print(f"  Ch 41 (RNN seq2seq)            : ~25 BLEU")
print(f"  Ch 50 (Transformer)            : ~35 BLEU")

Summary#

Concept	Equation	What it does
Noisy channel	$\hat{e} = \arg\max_e P(f	e) P(e)$
Translation model	$P(f	e)$
Language model	$P(e)$	How fluent/probable is this English?
Mutual information	$I(E;F) = H(E) - H(E	F)$
Beam search	keep top-$k$	Makes $\arg\max$ tractable

Next chapter: IBM Model 1 — Full EM on Multi30k. We replace the toy translation model with a principled EM-trained word alignment model, and see the noisy channel actually produce translations.

Term	Name	What it models
\(P(f \mid e)\)	Translation model	How likely is this French given this English?
\(P(e)\)	Language model	How likely is this English sentence in general?