Four sentence pairs, and a translation table that arrives without anyone labelling a single word.
The notebook carries the source, the install step and every run below, so nothing has to be on your machine. Open it, then choose Runtime › Run all.
Colab opens it read only. Click Copy to Drive to keep
your changes. You can also download
ibm_model1.ipynb, or run it
locally: python3 ibm_model1.py.
python3 ibm_model1.py
The corpus, the steps and what was learned.
python3 ibm_model1.py --step
One EM iteration in full, from uniform probabilities to updated counts.
python3 ibm_model1.py --learned
The table after convergence, and the alignments it implies.
Download ibm_model1.py
· served verbatim at https://nlp.jcrlabz.com/code/ibm_model1.py
"""IBM Model 1, worked as Chapter 24 works it.
The translation model that learns word alignment from nothing but sentence
pairs. No dictionary, no alignment annotation, four sentences.
the corpus four English and Swahili pairs, from the lectures
one EM iteration every posterior and every count, by hand
convergence the table at iterations 1, 5 and 10
what it learned the alignments nobody supplied, and the one tie it
refuses to break
one more sentence what that tie needed, and what it also fixed
python3 ibm_model1.py # all five
python3 ibm_model1.py --step # one iteration in full detail
python3 ibm_model1.py --learned # the table, and the honest tie
python3 ibm_model1.py --extra # add a fifth pair, watch it resolve
python3 ibm_model1.py --iters 50 # the tie is still there at 50
python3 ibm_model1.py --pair "my dog" "mbwa wangu"
Install: nothing, the Python standard library is enough
"""
import argparse
from collections import defaultdict
# The lecture corpus. English on the left, Swahili on the right. Nobody has
# said which word translates which; that is exactly what has to be learned.
PAIRS = [
(["my", "dog"], ["mbwa", "wangu"]),
(["my", "house"], ["nyumba", "yangu"]),
(["my", "cycle"], ["mzunguko", "wangu"]),
(["his", "dog"], ["mbwa", "wake"]),
]
# One more pair, held back on purpose. Section 4 shows what it fixes.
EXTRA = (["his", "house"], ["nyumba", "wake"])
EN = ["my", "house", "cycle", "his", "dog"]
SW = ["mbwa", "wangu", "nyumba", "yangu", "mzunguko", "wake"]
def init_table():
"""Uniform. Every Swahili word is equally likely for every English word."""
return {e: {f: 1.0 / len(SW) for f in SW} for e in EN}
def em_step(t):
"""One expectation-maximisation pass over the whole corpus.
E-step: for each Swahili word in a pair, split one unit of count across
the English words in that pair, in proportion to the current t(f|e).
That split is the posterior over alignments, and Model 1 makes it this
simple because it assumes all alignments are a priori equally likely.
M-step: renormalise the collected counts into probabilities.
"""
count = defaultdict(float) # count[(e, f)]
total = defaultdict(float) # total[e]
detail = []
for en, sw in PAIRS:
for f in sw:
z = sum(t[e][f] for e in en) # the normaliser
for e in en:
delta = t[e][f] / z
count[(e, f)] += delta
total[e] += delta
detail.append((en, sw, f, e, t[e][f], z, delta))
new = {e: {f: 0.0 for f in SW} for e in EN}
for (e, f), c in count.items():
new[e][f] = c / total[e]
return new, detail, count, total
def table(t, title, top=None):
print(f"\n {title}\n")
print(" " + " " * 9 + "".join(f"{f[:8]:>10}" for f in SW))
print(" " + "-" * (9 + 10 * len(SW)))
for e in EN:
row = "".join(f"{t[e][f]:>10.4f}" for f in SW)
best = max(SW, key=lambda f: t[e][f])
mark = f" -> {best}" if top else ""
print(f" {e:<9}{row}{mark}")
# ------------------------------------------------------------------ the corpus
def show_corpus():
print("\nSTEP 1 four sentence pairs, and nothing else\n")
for i, (en, sw) in enumerate(PAIRS, start=1):
print(f" {i}. {' '.join(en):<12} {' '.join(sw)}")
print(f"\n English vocabulary: {EN}")
print(f" Swahili vocabulary: {SW}")
print("\n Nobody has said which word translates which. There is no")
print(" dictionary and no alignment annotation. The only signal is that")
print(" these sentences mean the same thing.")
print("\n Two things make it solvable. 'my' appears in three pairs and")
print(" 'dog' in two, so the words that travel with them are visible.")
print(" And 'wangu' appears with 'my' twice, which is the wedge.")
print("\n One wrinkle worth noticing. Swahili marks possession by noun")
print(" class, so 'my' is 'wangu' with dog and cycle but 'yangu' with")
print(" house. A model that assumed one translation per word would be")
print(" wrong, and Model 1 does not assume that.")
# --------------------------------------------------------------- one iteration
def show_step():
t = init_table()
print("\n\nSTEP 2 one iteration, every number\n")
print(f" Start uniform: every t(f|e) = 1/{len(SW)} ="
f" {1/len(SW):.4f}\n")
print(" E-STEP. For each Swahili word, split one unit of count over the")
print(" English words in its pair, in proportion to t(f|e).\n")
new, detail, count, total = em_step(t)
seen = set()
print(f" {'pair':<24}{'f':<11}{'e':<8}{'t(f|e)':>9}{'sum':>9}"
f"{'delta':>9}")
print(" " + "-" * 72)
for en, sw, f, e, tv, z, d in detail:
key = " ".join(en)
label = f"{' '.join(en)} / {' '.join(sw)}" if key not in seen else ""
seen.add(key)
print(f" {label:<24}{f:<11}{e:<8}{tv:>9.4f}{z:>9.4f}{d:>9.4f}")
print("\n Every delta is 0.5000, because the table is still uniform and")
print(" each pair has two English words. The first iteration cannot")
print(" prefer anything. What it can do is count.\n")
print(" M-STEP. Collect the counts and renormalise.\n")
print(f" {'e':<9}{'f':<11}{'count(e,f)':>12}{'total(e)':>11}"
f"{'t(f|e)':>10}")
print(" " + "-" * 55)
for (e, f), c in sorted(count.items()):
print(f" {e:<9}{f:<11}{c:>12.4f}{total[e]:>11.4f}"
f"{c/total[e]:>10.4f}")
print("\n Read the rows for 'my'. It occurred in three pairs, so it")
print(" collected 3.0 units of count spread over six Swahili words.")
print(" 'wangu' got 1.0 of that and every other word got 0.5.")
print("\n That asymmetry is the entire seed. 'wangu' appeared alongside")
print(" 'my' twice and everything else once, and one pass of counting")
print(" is enough to notice.")
# ---------------------------------------------------------------- convergence
def show_convergence(iters=10, checkpoints=(1, 5, 10)):
print(f"\n\nSTEP 3 what repetition does\n")
t = init_table()
for i in range(1, iters + 1):
t, _, _, _ = em_step(t)
if i in checkpoints:
table(t, f"after iteration {i}")
print("\n Follow one cell across the three tables. t(mbwa | dog) goes")
for i, tt in enumerate([init_table()], start=0):
pass
t2 = init_table()
row = []
for i in range(1, iters + 1):
t2, _, _, _ = em_step(t2)
if i in (1, 5, 10):
row.append((i, t2["dog"]["mbwa"], t2["my"]["wangu"],
t2["house"]["yangu"]))
print(f"\n {'iteration':>10}{'t(mbwa|dog)':>14}{'t(wangu|my)':>14}"
f"{'t(yangu|house)':>16}")
print(" " + "-" * 56)
print(f" {'0 uniform':>10}{1/len(SW):>14.4f}{1/len(SW):>14.4f}"
f"{1/len(SW):>16.4f}")
for i, a, b, c in row:
print(f" {i:>10}{a:>14.4f}{b:>14.4f}{c:>16.4f}")
print("\n Nothing pushed those numbers except counting and")
print(" renormalising, repeated. That is all EM is here.")
# ------------------------------------------------------------- what it learned
def show_learned(iters=10):
t = init_table()
for _ in range(iters):
t, _, _, _ = em_step(t)
print(f"\n\nSTEP 4 the alignment nobody supplied (after {iters}"
f" iterations)\n")
print(f" {'English':<10}{'best Swahili':<12}{'p':>9}"
f"{'runner up':>12}{'p':>9}")
print(" " + "-" * 54)
for e in EN:
ranked = sorted(SW, key=lambda f: -t[e][f])
print(f" {e:<10}{ranked[0]:<12}{t[e][ranked[0]]:>9.4f}"
f"{ranked[1]:>12}{t[e][ranked[1]]:>9.4f}")
print("\n Four of the five are settled. 'dog' went to 'mbwa' at"
f" {t['dog']['mbwa']:.4f},")
print(f" 'cycle' to 'mzunguko' at {t['cycle']['mzunguko']:.4f}, 'his' to"
f" 'wake' at {t['his']['wake']:.4f},")
print(f" and 'my' to 'wangu' at {t['my']['wangu']:.4f}. Nobody supplied"
" any of that.")
print("\n\n NOW LOOK AT 'house'.\n")
print(f" t(nyumba | house) = {t['house']['nyumba']:.4f}")
print(f" t(yangu | house) = {t['house']['yangu']:.4f}")
t50 = init_table()
for _ in range(50):
t50, _, _, _ = em_step(t50)
print(f"\n Exactly tied, and it stays tied. After 50 iterations it is"
f" still")
print(f" {t50['house']['nyumba']:.4f} and {t50['house']['yangu']:.4f}.")
print("\n This is not a failure of EM. It is EM being honest.")
print("\n 'house' occurs in exactly one sentence pair, beside 'nyumba'")
print(" and 'yangu'. Nothing anywhere else in the corpus distinguishes")
print(" those two words. 'my' correctly pushes both of them down, and")
print(f" pushes them down equally: {t50['my']['nyumba']:.4f} each.")
print("\n So 'house' inherits both, in equal measure. The data contains")
print(" a tie, and the model reports a tie rather than inventing a")
print(" preference. A model that broke it would be making something up.")
def show_extra(iters=10):
"""Add one sentence pair and watch the tie resolve."""
global PAIRS
base = list(PAIRS)
t = init_table()
for _ in range(iters):
t, _, _, _ = em_step(t)
before = dict(t["house"])
PAIRS = base + [EXTRA]
t2 = init_table()
for _ in range(iters):
t2, _, _, _ = em_step(t2)
PAIRS = base
print("\n\nSTEP 5 one more sentence, and the tie breaks\n")
print(f" Add a fifth pair: {' '.join(EXTRA[0]):<12}"
f"{' '.join(EXTRA[1])}")
print("\n 'house' now meets 'nyumba' twice and 'yangu' once. That is")
print(" the only new information, and it is enough.\n")
print(f" {'':<10}{'4 pairs':>12}{'5 pairs':>12}")
print(" " + "-" * 36)
for f in ("nyumba", "yangu"):
print(f" t({f[:6]}|house){before[f]:>10.4f}{t2['house'][f]:>12.4f}")
print(f"\n 'house' resolves to 'nyumba' at {t2['house']['nyumba']:.4f}.")
print("\n Something else moved too. Watch 'my':\n")
print(f" {'':<12}{'4 pairs':>12}{'5 pairs':>12}")
print(" " + "-" * 36)
for f in ("wangu", "yangu"):
print(f" t({f}|my){t['my'][f]:>12.4f}{t2['my'][f]:>12.4f}")
print(f"\n t(yangu|my) rose from {t['my']['yangu']:.4f} to"
f" {t2['my']['yangu']:.4f}, which is more correct.")
print(" 'yangu' really is Swahili for 'my', in the noun class that")
print(" 'house' belongs to. Freeing 'house' from the tie let the")
print(" evidence for that reach 'my'.")
print("\n One sentence pair. That is the argument for parallel corpus")
print(" size, and it is why statistical MT waited for the Canadian")
print(" Hansard and the European Parliament proceedings.")
def trace_pair(en_s, sw_s, iters=10):
t = init_table()
for _ in range(iters):
t, _, _, _ = em_step(t)
en, sw = en_s.split(), sw_s.split()
print(f"\n\nALIGNMENT for '{en_s}' / '{sw_s}' (after {iters} iterations)\n")
print(f" {'Swahili':<12}" + "".join(f"{e:>10}" for e in en)
+ f"{' most likely':>16}")
print(" " + "-" * (12 + 10 * len(en) + 16))
for f in sw:
if f not in SW:
print(f" {f:<12}not in the vocabulary")
continue
z = sum(t[e][f] for e in en if e in EN)
post = {e: (t[e][f] / z if z else 0.0) for e in en if e in EN}
cells = "".join(f"{post.get(e, 0.0):>10.4f}" for e in en)
best = max(post, key=post.get) if post else "?"
print(f" {f:<12}{cells}{best:>16}")
print("\n Each row is a posterior over alignments for one target word.")
print(" Model 1 has no notion of position, so this is decided entirely")
print(" by the translation table.")
def main():
ap = argparse.ArgumentParser(description=__doc__)
ap.add_argument("--corpus", action="store_true")
ap.add_argument("--step", action="store_true")
ap.add_argument("--converge", action="store_true")
ap.add_argument("--learned", action="store_true")
ap.add_argument("--extra", action="store_true",
help="add a fifth pair and watch the tie break")
ap.add_argument("--iters", type=int, default=10)
ap.add_argument("--pair", nargs=2, metavar=("ENGLISH", "SWAHILI"))
a = ap.parse_args()
if a.pair:
trace_pair(a.pair[0], a.pair[1], a.iters)
print()
return
picked = a.corpus or a.step or a.converge or a.learned or a.extra
if a.corpus or not picked:
show_corpus()
if a.step or not picked:
show_step()
if a.converge or not picked:
show_convergence(a.iters)
if a.learned or not picked:
show_learned(a.iters)
if a.extra or not picked:
show_extra(a.iters)
print()
if __name__ == "__main__":
main()