35 · Hierarchical Phrase-Based MT — Chiang (2005)#
Dependencies: numpy, scipy
Runtime: ~5 min CPU
Chapter stub — implementation coming in a future commit.
Time-machine sentences#
Every chapter runs the same 20 held-out test sentences so the quality arc across chapters is directly comparable.
# 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")
Hierarchical Phrase-Based MT (Chiang 2005)#
PBSMT can only translate contiguous phrases in a fixed order. Hiero (Chiang 2005) extends PBSMT to a Synchronous Context-Free Grammar (SCFG), allowing long-range reordering and discontinuous phrases.
This chapter:
SCFG rule representation
Hierarchical phrase extraction
CYK chart parsing for translation
Key advantages over PBSMT
Time-machine: rules and CYK chart
CORPUS = [
("the cat sat on the mat", "die Katze sass auf der Matte"),
("the dog runs fast", "der Hund laeuft schnell"),
("a man walks in the park", "ein Mann geht im Park"),
("the woman reads a book", "die Frau liest ein Buch"),
("children play in the garden", "Kinder spielen im Garten"),
("the cat and the dog", "die Katze und der Hund"),
("a fast dog runs", "ein schneller Hund laeuft"),
("the man reads the book", "der Mann liest das Buch"),
("a woman walks fast", "eine Frau geht schnell"),
("children run in the park", "Kinder laufen im Park"),
]
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 .",
]
print(f"Corpus: {len(CORPUS)} sentence pairs")
1. Synchronous Context-Free Grammar (SCFG)#
An SCFG rule has the form:
X -> <gamma, alpha>
where:
X is a non-terminal (Hiero uses only one: X)
gamma is the source-side string (mix of terminals and X)
alpha is the target-side string (mix of terminals and X)
Non-terminals on source and target side are co-indexed
Examples (EN->DE):
X -> <the cat, die Katze> (flat phrase rule)
X -> <the X1 in the park, X1 im Park> (one non-terminal)
X -> <X1 and X2, X1 und X2> (two non-terminals, same order)
X -> <X1 of X2, X2 von X1> (two non-terminals, inverted order)
# SCFG rule data structure
from collections import defaultdict
import math
class SCFGRule:
def __init__(self, src_rhs, tgt_rhs, alignment, log_prob=0.0):
# src_rhs and tgt_rhs: tuples of strings or non-terminal markers
# Non-terminals are represented as ("X", index)
# alignment: list of (src_pos, tgt_pos) for terminal tokens only
self.src_rhs = src_rhs
self.tgt_rhs = tgt_rhs
self.alignment = alignment
self.log_prob = log_prob
def __repr__(self):
def render(side):
parts = []
for tok in side:
if isinstance(tok, tuple):
parts.append("X" + str(tok[1]))
else:
parts.append(tok)
return " ".join(parts)
return f"X -> < {render(self.src_rhs)} , {render(self.tgt_rhs)} > lp={self.log_prob:.2f}"
# Example rules
r1 = SCFGRule(
src_rhs=("the", "cat"),
tgt_rhs=("die", "Katze"),
alignment=[(0,0),(1,1)],
log_prob=-0.1
)
r2 = SCFGRule(
src_rhs=("the", ("X", 1), "in", "the", "park"),
tgt_rhs=(("X", 1), "im", "Park"),
alignment=[(2,1),(4,2)],
log_prob=-0.5
)
r3 = SCFGRule(
src_rhs=(("X", 1), "and", ("X", 2)),
tgt_rhs=(("X", 1), "und", ("X", 2)),
alignment=[(1,1)],
log_prob=-0.3
)
print("Example SCFG rules:")
print(" ", r1)
print(" ", r2)
print(" ", r3)
2. Flat Phrase Extraction#
Hiero starts with the same flat phrase extraction as PBSMT, then generalises them by replacing sub-phrases with non-terminals X.
# IBM Model 1 and 2 for alignment
def ibm_model1(corpus, n_iters=15):
tgt_vocab = set(w for _, ts in corpus for w in ts.split())
t = defaultdict(lambda: 1.0 / (len(tgt_vocab) + 1))
for _ in range(n_iters):
count = defaultdict(float)
total = defaultdict(float)
for src, tgt in corpus:
sw = src.split()
tw = tgt.split()
for e in sw:
Z = sum(t[(e, f)] for f in tw)
if Z == 0:
continue
for f in tw:
d = t[(e, f)] / Z
count[(e, f)] += d
total[e] += d
for (e, f), c in count.items():
t[(e, f)] = c / total[e] if total[e] > 0 else 0.0
return t
def ibm_model2(corpus, n_iters=15, t_init=None):
t = defaultdict(lambda: 0.01)
if t_init:
t.update(t_init)
a = defaultdict(lambda: 0.1)
for _ in range(n_iters):
count_t = defaultdict(float)
total_t = defaultdict(float)
count_a = defaultdict(float)
total_a = defaultdict(float)
for src, tgt in corpus:
sw = src.split()
tw = tgt.split()
l, m = len(sw), len(tw)
for j, e in enumerate(sw):
Z = sum(t[(e, tw[i])] * a[(i, j, l, m)] for i in range(m))
if Z < 1e-300:
continue
for i, f in enumerate(tw):
delta = t[(e, f)] * a[(i, j, l, m)] / Z
count_t[(e, f)] += delta
total_t[e] += delta
count_a[(i, j, l, m)] += delta
total_a[(j, l, m)] += delta
for key, c in count_t.items():
t[key] = c / total_t[key[0]] if total_t[key[0]] > 0 else 0.0
for key, c in count_a.items():
j, l, m = key[1], key[2], key[3]
t_key = (j, l, m)
a[key] = c / total_a[t_key] if total_a[t_key] > 0 else 0.0
return t, a
def viterbi_align(src, tgt, t, a):
sw = src.split()
tw = tgt.split()
l, m = len(sw), len(tw)
al = set()
for j, e in enumerate(sw):
scores = [t[(e, tw[i])] * a[(i, j, l, m)] for i in range(m)]
bi = max(range(m), key=lambda i: scores[i])
al.add((j, bi))
return al
def extract_flat_phrases(sw, tw, alignment, max_len=4):
phrases = []
for t_s in range(len(tw)):
for t_e in range(t_s, min(len(tw), t_s + max_len)):
aligned_src = [sp for sp, tp in alignment if t_s <= tp <= t_e]
if not aligned_src:
continue
s_s = min(aligned_src)
s_e = max(aligned_src)
if s_e - s_s >= max_len:
continue
ok = True
for sp in range(s_s, s_e + 1):
for sp2, tp2 in alignment:
if sp2 == sp and not (t_s <= tp2 <= t_e):
ok = False
break
if not ok:
break
if not ok:
continue
for tp in range(t_s, t_e + 1):
for sp2, tp2 in alignment:
if tp2 == tp and not (s_s <= sp2 <= s_e):
ok = False
break
if not ok:
break
if not ok:
continue
phrases.append((tuple(sw[s_s:s_e+1]), tuple(tw[t_s:t_e+1]),
s_s, s_e, t_s, t_e))
return phrases
print("Training alignment models...")
t1 = ibm_model1(CORPUS)
t2, a2 = ibm_model2(CORPUS, t_init=dict(t1))
print("Done. Extracting flat phrases...")
corpus_with_align = []
for src, tgt in CORPUS:
sw = src.split()
tw = tgt.split()
al = viterbi_align(src, tgt, t2, a2)
flat = extract_flat_phrases(sw, tw, al)
corpus_with_align.append((sw, tw, al, flat))
total_flat = sum(len(f) for _, _, _, f in corpus_with_align)
print(f"Total flat phrase pairs: {total_flat}")
3. Hierarchical Rule Extraction#
For every pair of consistent flat phrases (outer, inner) where inner is strictly contained in outer, we create a hierarchical rule by replacing the inner phrase with a non-terminal X.
Constraints (Chiang 2005):
The inner span must be strictly contained in the outer span
At least one terminal must remain on each side of the rule
At most 2 non-terminals per rule
Source and target RHS each have at most 5 tokens
def extract_hiero_rules(sw, tw, alignment, flat_phrases, max_nt=2, max_len=5):
rules = []
# First, add all flat phrases as glue rules (no non-terminals)
for sp, tp, s_s, s_e, t_s, t_e in flat_phrases:
if len(sp) <= max_len and len(tp) <= max_len:
rule_al = [(j - s_s, i - t_s) for j, i in alignment
if s_s <= j <= s_e and t_s <= i <= t_e]
rules.append(SCFGRule(sp, tp, rule_al))
# Then create hierarchical rules by nesting phrases
for outer_sp, outer_tp, os_s, os_e, ot_s, ot_e in flat_phrases:
nt_count = 0
for inner_sp, inner_tp, is_s, is_e, it_s, it_e in flat_phrases:
# Inner must be strictly inside outer
if not (os_s <= is_s and is_e <= os_e and ot_s <= it_s and it_e <= ot_e):
continue
if (is_s == os_s and is_e == os_e) or (it_s == ot_s and it_e == ot_e):
continue
if nt_count >= max_nt:
break
# Build new source RHS: replace inner span with X
new_src = (tuple(sw[os_s:is_s]) +
(("X", nt_count + 1),) +
tuple(sw[is_e+1:os_e+1]))
# Build new target RHS: replace inner tgt span with X
new_tgt = (tuple(tw[ot_s:it_s]) +
(("X", nt_count + 1),) +
tuple(tw[it_e+1:ot_e+1]))
if len(new_src) > max_len or len(new_tgt) > max_len:
continue
# At least one terminal on each side
src_terminals = [x for x in new_src if isinstance(x, str)]
tgt_terminals = [x for x in new_tgt if isinstance(x, str)]
if not src_terminals or not tgt_terminals:
continue
rule_al = [(j - os_s, i - ot_s) for j, i in alignment
if os_s <= j <= os_e and ot_s <= i <= ot_e
and not (is_s <= j <= is_e)]
rules.append(SCFGRule(new_src, new_tgt, rule_al))
nt_count += 1
return rules
# Extract rules from first 3 sentence pairs
all_rules = []
for sw_c, tw_c, al, flat in corpus_with_align[:3]:
rules = extract_hiero_rules(sw_c, tw_c, al, flat)
all_rules.extend(rules)
sw_str = " ".join(sw_c)
tw_str = " ".join(tw_c)
print(f"Pair: {sw_str} | {tw_str}")
print(f" Flat phrases: {len(flat)}, Hiero rules: {len(rules)}")
for r in rules[:4]:
print(f" {r}")
print()
print(f"Total rules extracted: {len(all_rules)}")
4. CYK Chart Parsing for Translation#
The Hiero decoder uses CYK (Cocke-Younger-Kasami) parsing. The chart is a 2D table where chart[i][j] contains translation hypotheses for the source span from position i to j.
Algorithm:
for span_len in 1..n:
for start in 0..n-span_len:
end = start + span_len
# Apply all rules whose source RHS matches span[start:end]
# Either flat rules (no X) or hierarchical rules (with X sub-spans)
chart[start][end] = best hypothesis
Each chart cell stores the best partial translation and its score.
# Toy CYK decoder for Hiero SCFG
def build_rule_index(rules):
# Index rules by their source terminal pattern
# For flat rules: key = src_rhs (all terminals)
# For rules with 1 NT: key = (terminals_before, terminals_after)
flat_index = defaultdict(list) # src_tuple -> [rules]
nt1_index = defaultdict(list) # (prefix, suffix) -> [rules]
for rule in rules:
nts = [tok for tok in rule.src_rhs if isinstance(tok, tuple)]
if len(nts) == 0:
flat_index[rule.src_rhs].append(rule)
elif len(nts) == 1:
nt_pos = next(k for k, tok in enumerate(rule.src_rhs)
if isinstance(tok, tuple))
prefix = rule.src_rhs[:nt_pos]
suffix = rule.src_rhs[nt_pos+1:]
nt1_index[(prefix, suffix)].append(rule)
return flat_index, nt1_index
def cyk_translate(src_words, flat_index, nt1_index):
n = len(src_words)
# chart[i][j] = (score, translation_words)
chart = [[None] * n for _ in range(n)]
# Fill span length 1..n
for span_len in range(1, n + 1):
for start in range(0, n - span_len + 1):
end = start + span_len - 1 # inclusive
span = tuple(src_words[start:end+1])
# Try flat rules
if span in flat_index:
for rule in flat_index[span]:
score = rule.log_prob
# Build translation (no NTs)
tgt_str = [t for t in rule.tgt_rhs if isinstance(t, str)]
if chart[start][end] is None or score > chart[start][end][0]:
chart[start][end] = (score, tgt_str)
# Try rules with 1 NT
for (prefix, suffix), rules_list in nt1_index.items():
p_len = len(prefix)
s_len = len(suffix)
if p_len + s_len >= span_len:
continue
# Check prefix and suffix match
if tuple(src_words[start:start+p_len]) != prefix:
continue
if tuple(src_words[end-s_len+1:end+1]) != suffix:
continue
# The NT covers [start+p_len, end-s_len]
nt_start = start + p_len
nt_end = end - s_len
if nt_start > nt_end:
continue
if chart[nt_start][nt_end] is None:
continue
nt_score, nt_tgt = chart[nt_start][nt_end]
for rule in rules_list:
score = rule.log_prob + nt_score
# Build translation by substituting NT
tgt_tokens = []
for tok in rule.tgt_rhs:
if isinstance(tok, tuple): # NT
tgt_tokens.extend(nt_tgt)
else:
tgt_tokens.append(tok)
if chart[start][end] is None or score > chart[start][end][0]:
chart[start][end] = (score, tgt_tokens)
return chart
def print_chart(src_words, chart):
n = len(src_words)
sw_joined = " ".join(src_words)
print(f"\nCYK chart for: {sw_joined}")
hdr = ("Span" + " " * 16) + " " + ("Translation" + " " * 19) + " Score"
print(hdr)
print("-" * 65)
for span_len in range(1, n + 1):
for start in range(0, n - span_len + 1):
end = start + span_len - 1
cell = chart[start][end]
if cell is not None:
score, tgt = cell
span_str = " ".join(src_words[start:end+1])
tgt_str = " ".join(tgt)
print(f"{span_str:>20s} {tgt_str:30s} {score:.2f}")
# Build rule index from extracted rules
flat_idx, nt1_idx = build_rule_index(all_rules)
print(f"Rule index: {len(flat_idx)} flat rules, {len(nt1_idx)} NT-1 rule patterns")
# Test on corpus sentences
for src, tgt in CORPUS[:3]:
sw_test = src.split()
chart = cyk_translate(sw_test, flat_idx, nt1_idx)
print_chart(sw_test, chart)
n = len(sw_test)
result = chart[0][n-1]
if result:
print(f" REF: {tgt}")
hyp_j = " ".join(result[1])
print(f" HYP: {hyp_j}")
print()
5. Key Advantages of Hiero Over PBSMT#
Long-range reordering: Hiero rules can move entire sub-phrases. Example (German verb-final in subordinate clauses):
EN: I know that he the book reads
DE: Ich weiss, dass er das Buch liest
Rule: X -> <he X1 reads, er X1 liest> (verb wraps around object)
Discontinuous phrases: PBSMT can only translate contiguous spans. Hiero can model German separable verbs:
EN: he turns the light on
DE: er macht das Licht an
Rule: X -> <turns X1 on, macht X1 an>
No explicit reordering model: Reordering emerges from grammar rules, not a separate distortion penalty.
Expressive power: SCFG is equivalent to a Linear Context-Free Rewriting System. It can model most linguistic reordering patterns seen in real language pairs.
# Concrete example where PBSMT fails but Hiero handles it
# Simulated PBSMT: only flat phrase lookup
def pbsmt_translate(src_words, flat_index_pb):
result = []
i = 0
while i < len(src_words):
best_match = None
best_len = 0
for plen in range(min(4, len(src_words) - i), 0, -1):
phrase = tuple(src_words[i:i+plen])
if phrase in flat_index_pb and flat_index_pb[phrase]:
best_match = list(flat_index_pb[phrase][0].tgt_rhs)
best_len = plen
break
if best_match:
result.extend(best_match)
i += best_len
else:
result.append(src_words[i]) # OOV: copy
i += 1
return result
print("Translation comparison: PBSMT vs Hiero")
print("=" * 60)
for src, ref in CORPUS[:4]:
sw_cmp = src.split()
pbsmt_out = pbsmt_translate(sw_cmp, flat_idx)
chart_h = cyk_translate(sw_cmp, flat_idx, nt1_idx)
n = len(sw_cmp)
hiero_out = chart_h[0][n-1][1] if chart_h[0][n-1] else ["<no translation>"]
pb_str = " ".join(pbsmt_out)
hi_str = " ".join(hiero_out)
print(f"SRC: {src}")
print(f"REF: {ref}")
print(f"PBSMT: {pb_str}")
print(f"HIERO: {hi_str}")
print()
Time Machine#
Show the SCFG rules extracted from a few sentence pairs and the CYK chart for one of the TIME_MACHINE_EN sentences.
# Show rules for first 2 sentence pairs in detail
print("SCFG rules from training data")
print("=" * 60)
for idx in [0, 2]:
sw_tm, tw_tm, al_tm, flat_tm = corpus_with_align[idx]
rules_tm = extract_hiero_rules(sw_tm, tw_tm, al_tm, flat_tm)
src_str = " ".join(sw_tm)
tgt_str = " ".join(tw_tm)
print(f"\nPair: {src_str}")
print(f" {tgt_str}")
print(f" Alignment: {sorted(al_tm)}")
print(f" Rules extracted ({len(rules_tm)}):")
for r in rules_tm[:8]:
print(f" {r}")
# CYK chart for a short TIME_MACHINE sentence
# Use words that overlap with our training vocabulary
tm_test = "a man walks in the park"
tw_test = tm_test.split()
print(f"\nCYK chart for: '{tm_test}'")
chart_tm = cyk_translate(tw_test, flat_idx, nt1_idx)
print_chart(tw_test, chart_tm)
n_test = len(tw_test)
result_tm = chart_tm[0][n_test-1]
if result_tm:
rtm_str = " ".join(result_tm[1])
print(f"\nFull translation: {rtm_str} (score={result_tm[0]:.2f})")
else:
print("No full-span translation found (expected for tiny corpus)")
# Show TIME_MACHINE sentences and what words are in our phrase table
print("\nTime Machine: Phrase-table coverage for TIME_MACHINE_EN")
print("=" * 60)
all_src_phrases = set(flat_idx.keys())
for sent in TIME_MACHINE_EN[:4]:
words = sent.lower().split()
covered = [w for w in words if (w,) in all_src_phrases]
pct = 100.0 * len(covered) / len(words) if words else 0
print(f" {sent[:50]:50s} coverage={pct:.0f}%")