Statistical Phrase-Based Translation

Phrase translation clearly improved statistical MT, but what is the best way to extract phrase translation pairs? They built one uniform framework (model and decoder) that works with any phrase table, to compare extraction methods and explain why phrase-based models beat word-based ones.

Top performance comes from simple means: heuristic phrase extraction from word alignments plus lexical weighting. Phrases longer than three words and high-accuracy word alignment models matter little, and restricting phrases to syntactic constituents hurts.

A noisy-channel model with a length bonus: \(\mathbf{e}_{\text{best}} = \arg\max_{\mathbf{e}} p(\mathbf{f} \mid \mathbf{e})\, p_{\text{LM}}(\mathbf{e})\, \omega^{\text{length}(\mathbf{e})}\), with a trigram language model \(p_{\text{LM}}\). The factor \(\omega\), usually above 1, biases towards longer output to calibrate length.

The foreign sentence is segmented into \(I\) phrases (all segmentations equally likely); each is translated independently and the English phrases may be reordered: \(p(\bar f_1^I \mid \bar e_1^I) = \prod_{i=1}^{I} \phi(\bar f_i \mid \bar e_i)\, d(a_i - b_{i-1})\), with phrase translation probabilities \(\phi\) and a distortion model \(d\).

\(a_i\) is the start position of the foreign phrase translated into the \(i\)th English phrase, \(b_{i-1}\) the end position of the foreign phrase translated into the \((i-1)\)th one. A simple choice is \(d(a_i - b_{i-1}) = \alpha^{|a_i - b_{i-1} - 1|}\), which penalizes jumps; monotone translation (\(a_i = b_{i-1} + 1\)) costs nothing.

Because of Bayes’ rule in the noisy-channel formulation: to translate \(\mathbf{f}\) into English we maximize \(p(\mathbf{f} \mid \mathbf{e})\, p(\mathbf{e})\), so the translation direction is inverted from the modelling standpoint.

Left to right as partial hypotheses: starting from the empty hypothesis, pick a sequence of untranslated foreign words and an English translation for them, append it to the output, mark the foreign words as covered and update the cost. The best complete hypothesis covering all foreign words is the output.

Stack \(m\) holds hypotheses with \(m\) foreign words translated; equivalent hypotheses are recombined. Stack size is still exponential, so each stack keeps only a beam of the best \(n\) hypotheses, ranked by cost so far plus a future cost estimate. Imperfect estimates cause search errors.

Without it, hypotheses that have translated the easy words first look cheaper than ones that have tackled hard words. For each translation option, multiply its phrase probability by an LM estimate of the English phrase (unigram for the first word, bigram, then trigram); dynamic programming gives the cheapest cost for each of the \(n(n+1)/2\) spans of consecutive foreign words. Distortion is ignored. Gaps multiply their spans’ costs.

Translation options are linear in sentence length, so the search is quadratic in sentence length and linear in beam size. A beam of 100 was enough; larger beams changed few translations.

(1) All phrase pairs consistent with word alignments from GIZA++ (IBM models); (2) only syntactic phrases, pairs that are also subtrees in parse trees of both sides; (3) the joint phrase model of Marcu and Wong (2002), which learns phrase-level alignments directly with EM.

Its words are aligned only to each other, never to words outside the pair (at least one alignment point inside). All consistent pairs are collected, with no restriction to linguistic units.

By relative frequency over all extracted pairs, with no smoothing: \(\phi(\bar f \mid \bar e) = \frac{\text{count}(\bar f, \bar e)}{\sum_{\bar f'} \text{count}(\bar f', \bar e)}\).

Consistent pairs include non-intuitive phrases like “house the”, and syntax-based MT models (Yamada and Knight 2001; Wu 1997) can only use phrases spanning whole subtrees. Both sides were parsed, and only consistent pairs where both phrases are subtrees were kept: a subset of all consistent pairs.

EM in that model learns a joint distribution \(\phi(\bar e, \bar f)\) over phrase pairs and a joint distortion distribution; these were marginalized to conditional probabilities for the decoder, as Marcu and Wong themselves did when decoding.

On German–English Europarl, from 10k to 320k sentence pairs: all consistent phrases (AP) slightly beat the joint model, syntactic phrases only were worse, and all phrase methods beat a word-based IBM Model 4 system. All systems improved with more data.

Almost linearly with corpus size, because of the many singleton pairs (about 3.2M distinct pairs at 320k sentence pairs, maximum length 4). Restricting to syntactic phrases eliminated over 80% of pairs. Even the largest tables fit in a few hundred megabytes of RAM.

Not because they are more reliable but too few: giving syntactic pairs extra weight (counting them twice or a decoder bonus) didn’t help, and penalizing them didn’t hurt much. Useful pairs like German “es gibt” ↔ “there is” aren’t constituents, and “with regard to” or “note that” often have simple one-word translations.

A maximum of three words already gave top performance; longer phrases gave little improvement and sometimes worse results, while a limit of two was clearly worse. Table size grows almost linearly with the length limit.

A check of how well a pair’s words translate each other: \(p_w(\bar f \mid \bar e, a) = \prod_{i=1}^{n} \frac{1}{|\{j \mid (i,j) \in a\}|} \sum_{(i,j) \in a} w(f_i \mid e_j)\), with word probabilities \(w(f \mid e)\) by relative frequency from the same alignments. Unaligned foreign words align to NULL; with several alignments, take the highest weight.

\(p_w = w(f_1 \mid e_1) \cdot \tfrac{1}{2}\big(w(f_2 \mid e_2) + w(f_2 \mid e_3)\big) \cdot w(f_3 \mid \text{NULL})\): average over a word’s alignment points, multiply over foreign words.

As an extra factor: \(\phi(\bar f_i \mid \bar e_i)\, p_w(\bar f_i \mid \bar e_i, a)^{\lambda}\), with \(\lambda\) around 0.25. It improved BLEU by up to 0.01, and can be precomputed into the phrase table.

IBM models align each foreign word to at most one English word, so one direction can’t express many-to-many links. Aligning both directions gives two alignments: their intersection is high-precision, their union high-recall.

Start from the intersection; add only points from the union that connect at least one still unaligned word. First iteratively add points directly adjacent to existing ones until nothing changes, then in a final step add non-adjacent points under the same conditions. Variants: diag also allows diagonal neighbours; diag-and requires both words unaligned in the final step.

A lot: about 0.02 BLEU between the best and worst, and rankings change with corpus size. diag-and was best for almost all sizes; f2e alone started near the bottom but became competitive at 320k sentence pairs.

Not much: alignments from IBM Model 1 were clearly worse, but Models 2 and 3 came close to the expensive Model 4. The symmetrization heuristic mattered more than the word alignment model.

Yes: for English–German, French–English, English–French, Finnish–English, Swedish–English and Chinese–English, the phrase model beat IBM Model 4 (e.g. French–English BLEU 0.2787 → 0.3294), and lexical weighting always helped further (0.3389).

Straightforward syntactic models mapping constituents to constituents miss important phrase alignments, so they don’t beat unmotivated phrase mappings: a challenge for syntactic translation models.