31 · IBM Model 1 — Full EM Implementation#
Dependencies: numpy (pre-installed, no pip needed for Parts 0–3 core) Runtime: ~20 sec CPU (Multi30k) · fallback corpus runs in < 1 sec
Brown, P., Della Pietra, S., Della Pietra, V., & Mercer, R. (1993). The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2), 263–311.
IBM Model 1 is the simplest word-based translation model. It defines the translation probability P(f | e) by assuming each target word f is independently generated from some source word e, with uniform attention over positions (hence “Model 1”—position is ignored entirely).
Despite the harsh independence assumption, Model 1 converges to linguistically meaningful word correspondences after only ~10 EM iterations and takes ~20 seconds on 29 k sentence pairs.
What we implement#
Step |
Description |
|---|---|
1 |
Load Multi30k EN→DE (with fallback to a 20-sentence built-in corpus) |
2 |
Vocabulary building; add NULL token to every source sentence |
3 |
Full EM training of t(f | e) |
4 |
Viterbi (1-best) word alignment |
5 |
Top-translation lexicon inspection |
6 |
Bidirectional training + grow-diagonal symmetrization |
7 |
Time-machine: greedy word-by-word translation of 20 shared test sentences |
# Colab setup: install this part's pinned dependencies (skipped outside Colab).
import sys
if "google.colab" in sys.modules:
get_ipython().system("wget -q -O requirements_part3.txt https://raw.githubusercontent.com/eduardosanchezg/mthistory/main/requirements_part3.txt")
get_ipython().system("pip install -q -r requirements_part3.txt")
import os
# ── Smoke mode (used by CI) ──────────────────────────────────────────────────
# Set SMOKE=1 env var or flip the flag here to run a fast subset.
SMOKE = bool(os.environ.get("SMOKE", ""))
SMOKE_PAIRS = 500 # sentence pairs used in smoke mode
SMOKE_ITERS = 2 # EM iterations in smoke mode
FULL_ITERS = 10 # EM iterations in normal mode
N_ITER = SMOKE_ITERS if SMOKE else FULL_ITERS
print(f"Smoke mode: {SMOKE} | EM iterations: {N_ITER}")
import math
import os
import re
from collections import defaultdict, Counter
from pathlib import Path
import numpy as np
print("numpy", np.__version__)
1 · Corpus Loading#
We use Multi30k (English→German), which contains ~29 k sentence pairs with an average length of ~11 tokens. If the dataset is not present locally the notebook falls back to the 20-sentence built-in corpus so that it runs with zero network access (e.g. in CI).
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 breaking a stick with a front kick .
Five people wearing winter jackets and helmets stand in the snow .
People are near a car and one is carrying a red bag .
A man in a gray shirt is lifting weights .
Two young boys with a kite in a grassy field .
A woman in a brown dress and white shirt is talking on a cell phone .
A man is riding a bicycle on a trail through the woods .
A group of people is sitting on a set of bleachers .
Two dogs are running through the grass .
A woman in a red shirt is holding a dog on a leash .
A young boy in a blue shirt is playing in the sand .
A man in a white shirt is painting a fence .
A girl with a yellow umbrella is walking in the rain .
A dog is jumping to catch a frisbee .
Two children are playing on a swing set .
A man wearing a blue jacket is taking a photograph .
A woman is reading a book in a park .
A black and white dog is running through a field ."""
FALLBACK_DE = """Ein Mann mit einem orangefarbenen Hut starrt auf etwas .
Ein Boston Terrier läuft auf sattgrünem Gras vor einem weißen Zaun .
Ein Mädchen in Karateuniform bricht einen Stock mit einem Frontlift .
Fünf Personen in Winterjacken und Helmen stehen im Schnee .
Menschen stehen bei einem Auto und einer trägt eine rote Tasche .
Ein Mann in einem grauen Hemd hebt Gewichte .
Zwei junge Jungs mit einem Drachen auf einem Grasfeld .
Eine Frau in einem braunen Kleid und weißem Hemd telefoniert .
Ein Mann fährt auf einem Fahrrad auf einem Waldweg .
Eine Gruppe von Personen sitzt auf einem Tribünenblock .
Zwei Hunde rennen durch das Gras .
Eine Frau in einem roten Hemd hält einen Hund an der Leine .
Ein kleiner Junge in einem blauen Hemd spielt im Sand .
Ein Mann in einem weißem Hemd streicht einen Zaun .
Ein Mädchen mit einem gelben Regenschirm geht im Regen .
Ein Hund springt um eine Frisbee zu fangen .
Zwei Kinder spielen auf einem Schaukelgestell .
Ein Mann in einer blauen Jacke fotografiert .
Eine Frau liest ein Buch in einem Park .
Ein schwarz-weißer Hund rennt durch ein Feld ."""
def load_bitext(src_path, tgt_path, max_pairs=29_000):
"""Load a parallel corpus; fall back to built-in 20-sentence corpus."""
if Path(src_path).exists() and Path(tgt_path).exists():
with open(src_path, encoding="utf-8") as f:
src = [l.strip().lower() for l in f if l.strip()]
with open(tgt_path, encoding="utf-8") as f:
tgt = [l.strip().lower() for l in f if l.strip()]
pairs = list(zip(src, tgt))[:max_pairs]
print(f"Loaded {len(pairs):,} sentence pairs from {src_path}")
return pairs
# Fallback corpus
src = [l.strip().lower() for l in FALLBACK_EN.strip().splitlines()]
tgt = [l.strip().lower() for l in FALLBACK_DE.strip().splitlines()]
print(f"[fallback] Using {len(src)}-pair built-in corpus (Multi30k not found)")
return list(zip(src, tgt))
# ── Paths (Multi30k layout as downloaded by scripts/download_multi30k.py) ─────
DATA_DIR = Path("../../data/multi30k")
EN_TRAIN = DATA_DIR / "train.en"
DE_TRAIN = DATA_DIR / "train.de"
pairs = load_bitext(EN_TRAIN, DE_TRAIN)
if SMOKE:
pairs = pairs[:SMOKE_PAIRS]
print(f"[smoke] Trimmed to {len(pairs)} pairs")
print(f"Example pair:\n EN: {pairs[0][0]}\n DE: {pairs[0][1]}")
2 · Vocabulary Building#
We tokenize on whitespace (Multi30k is already pre-tokenized). A NULL token is prepended to every source sentence — it accounts for target function words that have no overt source correspondent.
def build_vocab(pairs):
"""Count tokens in both sides of the parallel corpus."""
src_vocab = Counter()
tgt_vocab = Counter()
for src_str, tgt_str in pairs:
src_vocab.update(src_str.split())
tgt_vocab.update(tgt_str.split())
return src_vocab, tgt_vocab
src_vocab, tgt_vocab = build_vocab(pairs)
print(f"Source (EN) vocabulary: {len(src_vocab):,} types")
print(f"Target (DE) vocabulary: {len(tgt_vocab):,} types")
print(f" Most common EN: {src_vocab.most_common(10)}")
print(f" Most common DE: {tgt_vocab.most_common(10)}")
3 · IBM Model 1 — EM Training#
Generative story#
For a source sentence e = (e₁ … eₗ) and target sentence f = (f₁ … fₘ):
where t(f | e) is the word translation probability table we learn via EM.
EM equations#
E-step — compute soft alignment posteriors: $\(\delta(e_i, f_j) = \frac{t(f_j \mid e_i)}{\sum_{i'=0}^{l} t(f_j \mid e_{i'})}\)$
M-step — re-estimate parameters from fractional counts: $\(t(f \mid e) \leftarrow \frac{\sum_{(\mathbf{e},\mathbf{f})} \sum_{j} \delta(e, f_j) \cdot \mathbf{1}[f_j = f]}{\sum_{f'} \sum_{(\mathbf{e},\mathbf{f})} \sum_{j} \delta(e, f_j') \cdot \mathbf{1}[f_j' = f']}\)$
Initialization: uniform — t(f | e) = 1 / |V_f| for all (e, f).
def train_ibm1(pairs, n_iter=10, verbose=True):
"""
EM training of IBM Model 1.
Parameters
----------
pairs : list of (src_str, tgt_str) — source is English, target is German
n_iter : number of EM iterations
verbose : print log-likelihood each iteration
Returns
-------
t : dict[src_word -> dict[tgt_word -> float]]
t[e][f] = P(f | e)
"""
# ── Collect vocabulary ────────────────────────────────────────────────────
all_src = set(["NULL"])
all_tgt = set()
for src_str, tgt_str in pairs:
all_src.update(src_str.split())
all_tgt.update(tgt_str.split())
V_f = len(all_tgt)
if verbose:
print(f" |V_e| = {len(all_src):,} |V_f| = {V_f:,}")
# ── Initialize t(f|e) uniformly ──────────────────────────────────────────
# Use a defaultdict so unseen pairs get a small default probability.
uniform = 1.0 / V_f
t = defaultdict(lambda: defaultdict(lambda: uniform))
# Pre-tokenise once to avoid repeated splitting inside the loop
tokenised = []
for src_str, tgt_str in pairs:
tokenised.append((["NULL"] + src_str.split(), tgt_str.split()))
# ── EM iterations ─────────────────────────────────────────────────────────
for iteration in range(n_iter):
count = defaultdict(lambda: defaultdict(float)) # count(f, e)
total = defaultdict(float) # total(e)
# E-step + accumulate counts in a single pass
for e_words, f_words in tokenised:
for f in f_words:
# Normalisation constant for this target word in this sentence
s_total = sum(t[e][f] for e in e_words)
if s_total == 0:
continue
for e in e_words:
delta = t[e][f] / s_total
count[e][f] += delta
total[e] += delta
# M-step: re-normalise
for e in count:
denom = total[e]
if denom == 0:
continue
for f in count[e]:
t[e][f] = count[e][f] / denom
# ── Log-likelihood on a sample (first 200 pairs) ──────────────────────
if verbose:
ll = 0.0
n_sample = min(200, len(tokenised))
for e_words, f_words in tokenised[:n_sample]:
le = len(e_words)
for f in f_words:
s = sum(t[e][f] for e in e_words)
if s > 0:
ll += math.log(s / le)
print(f" Iter {iteration + 1:2d}: log-likelihood (sample) = {ll:10.2f}")
return t
print("Training IBM Model 1 EN→DE ...")
t_en_de = train_ibm1(pairs, n_iter=N_ITER)
4 · Viterbi Word Alignment#
Given a trained t(f|e) we compute the 1-best alignment for each target word: for every f_j, pick the source word e_i that maximises t(f_j | e_i).
Alignments are expressed as 0-based source indices (NULL = −1).
def viterbi_align(src_tokens, tgt_tokens, t):
"""
Return list of (tgt_idx, src_idx, tgt_word, src_word) tuples.
src_idx == -1 means the target word is aligned to NULL (no source word).
"""
e_words = ["NULL"] + list(src_tokens)
alignments = []
for j, f in enumerate(tgt_tokens):
best_e = max(e_words, key=lambda e: t[e][f])
best_i = e_words.index(best_e) - 1 # shift so NULL → -1
alignments.append((j, best_i, f, best_e))
return alignments
# ── Demo alignment ────────────────────────────────────────────────────────────
demo_en = "a man is running in the park".split()
demo_de = "ein mann läuft im park".split()
aligns = viterbi_align(demo_en, demo_de, t_en_de)
print("Viterbi alignment (DE → EN source word):")
print(f" EN: {' '.join(demo_en)}")
print(f" DE: {' '.join(demo_de)}")
print()
for j, i, f, e in aligns:
src_disp = f"e[{i}]={e}" if i >= 0 else "NULL"
print(f" f[{j}]={f:12s} ← {src_disp}")
5 · Inspecting the Learned Lexicon#
A sanity-check: look at the top German translations for a handful of English words. Model 1 should recover morphological variants of the correct German word even without any morphological analysis.
def top_translations(word, t, n=10):
"""Top n target words for a given source word, sorted by P(f|e)."""
if word not in t:
return []
return sorted(t[word].items(), key=lambda x: -x[1])[:n]
PROBE_WORDS = ["man", "woman", "dog", "running", "red", "park", "playing",
"children", "white", "black"]
print(f"{'EN word':12s} Top German translations (P(f|e))")
print("-" * 60)
for word in PROBE_WORDS:
tops = top_translations(word, t_en_de, n=5)
if tops:
entries = " ".join(f"{f}({p:.3f})" for f, p in tops)
print(f"{word:12s} {entries}")
else:
print(f"{word:12s} [not in vocabulary]")
6 · Bidirectional Training & Grow-Diagonal Symmetrization#
Training in both directions (EN→DE and DE→EN) and then combining the two alignment matrices dramatically reduces alignment errors.
Grow-Diagonal-Final-And (GDFA)#
This is the standard heuristic used in Moses and most phrase-based pipelines:
Start with the intersection of forward and backward alignments.
Grow by adding neighbouring points present in either direction that are adjacent (diagonal, horizontal, or vertical) to an already-accepted point.
Final-and: add any remaining points from either alignment set that can expand coverage of unaligned words.
def train_reverse(pairs, n_iter=10, verbose=False):
"""Train IBM Model 1 in the DE→EN direction."""
reversed_pairs = [(tgt, src) for src, tgt in pairs]
return train_ibm1(reversed_pairs, n_iter=n_iter, verbose=verbose)
def get_alignment_set(src_tokens, tgt_tokens, t):
"""
Return the Viterbi alignment as a set of (src_idx, tgt_idx) pairs.
NULL-aligned words (src_idx == -1) are excluded.
"""
aligns = viterbi_align(src_tokens, tgt_tokens, t)
return {(i, j) for j, i, _f, _e in aligns if i >= 0}
def symmetrize_gdfa(align_fwd, align_bwd, src_len, tgt_len):
"""
Grow-Diagonal-Final-And symmetrization.
Parameters
----------
align_fwd : set of (src_idx, tgt_idx) from EN→DE model
align_bwd : set of (src_idx, tgt_idx) from DE→EN model (already flipped)
src_len : number of source tokens
tgt_len : number of target tokens
Returns
-------
set of (src_idx, tgt_idx)
"""
result = align_fwd & align_bwd # intersection
union = align_fwd | align_bwd
# Track which source / target positions are already covered
src_aligned = {i for i, _j in result}
tgt_aligned = {j for _i, j in result}
neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1),
(-1, -1), (-1, 1), (1, -1), (1, 1)]
# Grow phase
added = True
while added:
added = False
for (i, j) in list(union):
if (i, j) in result:
continue
# Add if adjacent to an existing point AND grows coverage
for di, dj in neighbors:
ni, nj = i + di, j + dj
if (ni, nj) in result and (i not in src_aligned or j not in tgt_aligned):
result.add((i, j))
src_aligned.add(i)
tgt_aligned.add(j)
added = True
break
# Final-and: add points that cover still-unaligned words
for (i, j) in union:
if i not in src_aligned or j not in tgt_aligned:
result.add((i, j))
src_aligned.add(i)
tgt_aligned.add(j)
return result
def format_alignment_matrix(src_tokens, tgt_tokens, aligned_pairs):
"""Pretty-print an alignment matrix to stdout."""
src = list(src_tokens)
tgt = list(tgt_tokens)
col_w = max(len(w) for w in src) + 1
header = " " * 14 + " ".join(f"{w:{col_w}}" for w in src)
print(header)
for j, f in enumerate(tgt):
row = f"{f:13s} "
for i in range(len(src)):
row += ("● " + " " * col_w if (i, j) in aligned_pairs
else " " + " " * col_w)
print(row)
# ── Train reverse model ───────────────────────────────────────────────────────
print("Training IBM Model 1 DE→EN ...")
t_de_en = train_reverse(pairs, n_iter=N_ITER, verbose=False)
print("Done.")
# ── Demo symmetrization ───────────────────────────────────────────────────────
demo_en_toks = "a man is running in the park".split()
demo_de_toks = "ein mann läuft im park".split()
a_fwd = get_alignment_set(demo_en_toks, demo_de_toks, t_en_de)
# Reverse model trained DE→EN; viterbi gives (src=DE, tgt=EN) so flip indices
a_bwd_raw = get_alignment_set(demo_de_toks, demo_en_toks, t_de_en)
a_bwd = {(j, i) for i, j in a_bwd_raw} # flip to (en_idx, de_idx)
a_sym = symmetrize_gdfa(a_fwd, a_bwd, len(demo_en_toks), len(demo_de_toks))
print("\nAlignment matrices for: 'a man is running in the park' → 'ein mann läuft im park'")
print("\nForward (EN→DE):")
format_alignment_matrix(demo_en_toks, demo_de_toks, a_fwd)
print("\nBackward (DE→EN, flipped):")
format_alignment_matrix(demo_en_toks, demo_de_toks, a_bwd)
print("\nSymmetrized (GDFA):")
format_alignment_matrix(demo_en_toks, demo_de_toks, a_sym)
Alignment Statistics#
Let us look at aggregate alignment properties across the training data.
def alignment_stats(pairs, t_fwd, t_bwd, sample=500):
"""Compute basic alignment statistics on a random sample."""
rng = np.random.default_rng(42)
sample_pairs = [pairs[i] for i in rng.choice(len(pairs),
min(sample, len(pairs)),
replace=False)]
null_counts, total_tgt = 0, 0
sym_densities = []
for src_str, tgt_str in sample_pairs:
e_toks = src_str.split()
f_toks = tgt_str.split()
if not e_toks or not f_toks:
continue
a_fwd = get_alignment_set(e_toks, f_toks, t_fwd)
a_bwd_raw = get_alignment_set(f_toks, e_toks, t_bwd)
a_bwd = {(j, i) for i, j in a_bwd_raw}
a_sym = symmetrize_gdfa(a_fwd, a_bwd, len(e_toks), len(f_toks))
# Count NULL-aligned target words (in forward model)
fwd_aligns = viterbi_align(e_toks, f_toks, t_fwd)
null_counts += sum(1 for _, i, _, _ in fwd_aligns if i < 0)
total_tgt += len(f_toks)
# Symmetrized alignment density
sym_densities.append(len(a_sym) / (len(e_toks) * len(f_toks)))
print(f"Sample size : {len(sample_pairs)} pairs")
print(f"NULL-aligned DE words : {null_counts}/{total_tgt} "
f"({100*null_counts/max(total_tgt,1):.1f}%)")
print(f"Sym. alignment density: {np.mean(sym_densities):.4f} "
f"(links / (|e|×|f|))")
alignment_stats(pairs, t_en_de, t_de_en)
7 · Time-Machine Cell#
Every chapter in this course translates the same 20 held-out test sentences so we can observe the quality arc across eras.
IBM Model 1 translates word-by-word: for each source token, emit the German word with the highest t(f|e). The result is lexically reasonable but has
wrong word order (German is verb-final, English is SVO),
wrong morphological agreement, and
missing or incorrect function words.
This is exactly what you would expect from a position-blind model — and the lesson is visceral when you compare it to the Phrase-Based SMT output in Chapter 33.
TIME_MACHINE_EN = [
"A man is walking his dog in the park .",
"Two children are playing near a fountain .",
"A woman in a red coat is reading a book .",
"Several people are waiting at a bus stop .",
"A cyclist is riding through a crowded street .",
"A dog is chasing a ball on the beach .",
"A group of tourists is taking photographs .",
"A young girl is feeding ducks by a pond .",
"Two men are playing chess in a cafe .",
"A street musician is playing the violin .",
"Children are running through a field of flowers .",
"An old man is sitting on a bench reading a newspaper .",
"A woman is carrying groceries up a flight of stairs .",
"A boy is kicking a football against a wall .",
"A couple is dancing on an empty street .",
"A chef is preparing food in an outdoor kitchen .",
"A cat is sleeping on a warm windowsill .",
"Workers are repairing a road in the rain .",
"A small boat is sailing on a calm lake .",
"Firefighters are climbing a tall ladder .",
]
def ibm1_translate(src_sentence, t, min_prob=0.01):
"""
Greedy word-by-word translation via IBM Model 1.
Each source token is replaced by its most probable German translation.
Tokens with max P(f|e) < min_prob are left in brackets to signal OOV.
"""
tokens = src_sentence.lower().rstrip(" .").split()
result = []
for word in tokens:
tops = top_translations(word, t, n=1)
if tops and tops[0][1] >= min_prob:
result.append(tops[0][0])
else:
result.append(f"[{word}]")
return " ".join(result)
print("=" * 70)
print("IBM MODEL 1 — GREEDY WORD-BY-WORD TRANSLATION (EN → DE)")
print("=" * 70)
print()
for i, sent in enumerate(TIME_MACHINE_EN, 1):
translation = ibm1_translate(sent, t_en_de)
print(f"{i:2d}. EN: {sent}")
print(f" DE: {translation}")
print()
Observations#
Property |
Model 1 behaviour |
|---|---|
Lexical accuracy |
Reasonable — core nouns/verbs mostly correct |
Word order |
Wrong — no reordering model at all |
Morphology |
Wrong — inflection not handled |
Function words |
Patchy — NULL token absorbs some |
Unknown words |
Bracketed |
What’s Missing (fixed in later models)#
IBM Models 2–5 (Chapter 32): add explicit position/fertility models.
Phrase-Based SMT (Chapter 33): phrases preserve local word order and handle multi-word morphological patterns.
Neural MT (Part 4): jointly learns reordering, morphology, and contextual disambiguation.
Alignment quality note#
Without gold alignments (e.g. NAACL 2003 shared task) we cannot compute AER here, but visual inspection of the matrices above shows that Model 1 already finds the dominant content-word correspondences after only 10 iterations.
Optional: Save the Translation Table#
The t table can be pickled and reused in Chapter 32 (IBM Models 2–5) as a
warm-start initialisation, which is the standard practice.
import pickle, pathlib
SAVE_PATH = pathlib.Path("../../checkpoints/ibm1_en_de.pkl")
# Only save when running interactively (not in CI smoke mode)
if not SMOKE:
SAVE_PATH.parent.mkdir(parents=True, exist_ok=True)
with open(SAVE_PATH, "wb") as fh:
# Convert defaultdicts to plain dicts for portability
serialisable = {e: dict(fd) for e, fd in t_en_de.items()}
pickle.dump(serialisable, fh, protocol=4)
size_kb = SAVE_PATH.stat().st_size / 1024
print(f"Saved translation table to {SAVE_PATH} ({size_kb:.0f} KB)")
else:
print("[smoke] Skipping model save.")