Older statistical translation systems learned from parallel text in two steps. First they linked individual words across the two languages. Then they used hand-written rules to cut out every "phrase pair" consistent with those links. Joint models instead learn which multi-word phrases correspond to each other directly. They yield phrase tables several times smaller at equal or better translation quality. They never displaced the pipeline because they are expensive to train. Summing over all ways to pair up the phrases of a sentence is #P-hard, a counting problem believed to have no efficient exact algorithm. In practice every joint model has survived by capping sentences at 20 to 30 words, by pruning its search with the heuristic word links it was meant to replace, or by running slow random-walk samplers for days.
This note proposes a different way to handle that hardness, borrowed from wireless engineering. When the region a probability is integrated over is hard to handle, enclose it in a slightly larger region that is easy to handle. Draw samples from the larger region and throw away the ones that fall outside the true region. For phrase alignment, the larger region is obtained by enforcing the "each target word is used exactly once" constraint only inside a sliding window of nearby positions. A dynamic program can track that window exactly, at cost linear in sentence length. Any sample that breaks the constraint at long range is rejected afterwards. The samples that survive are exact, independent draws from the true phrase-alignment posterior, the probability over alignments given the current model. The rejection rate tells you exactly how far the relaxation is from the true problem.
Core Claim
The claim is that sentence-level phrase-alignment posteriors can be sampled exactly, without length caps and without pruning by word alignments, for language pairs whose reordering is mostly local. The cost has two parts. The dynamic program is linear in sentence length $n$ and exponential only in a window width $d$. The number of draws needed grows with the inverse of a measurable acceptance rate.
Let $S$ be the set of bijective phrase alignments of a sentence pair: every word on both sides belongs to exactly one aligned phrase. Let $S_d \supseteq S$ be the relaxed set in which target coverage is checked only within distance $d$ of the current position. Write $w(a)$ for the model weight of alignment $a$, $Z=\sum_{a\in S} w(a)$ for the true sum, and $Z_d=\sum_{a\in S_d} w(a)$ for the relaxed sum. A forward-backward pass computes $Z_d$ exactly and samples from $q(a)=w(a)/Z_d$. Accepted samples are distributed exactly as $w(a)/Z$, with acceptance probability $p_d = Z/Z_d$. From $N$ proposals, $\hat Z = Z_d \cdot (\#\text{accepted}/N)$ is unbiased, with relative error
$$\mathrm{RE}(\hat Z)=\sqrt{\frac{1-p_d}{N\,p_d}},$$
which follows from the variance of a binomial proportion. This is the bounded-relative-error property in the sense of An Accurate Sample Rejection Estimator of the Outage Probability With Equal Gain Combining. That paper computes how likely a sum of signal strengths falls below a threshold. It notes that this hard region sits inside an easy-to-sample ball, samples the ball, and rejects. It holds whenever $p_d$ stays bounded away from zero.
Our working hypothesis is that $p_d$ decays roughly like $e^{-\lambda_d n}$. Here $\lambda_d$ is the per-word rate at which the relaxed sampler makes unchecked long-range violations, and it falls quickly as $d$ grows. The exponential form assumes violations occur roughly independently along the sentence. It implies that a small, sentence-adaptive $d$ keeps $p_d$ usable for European pairs. For Japanese–English we expect a larger $d$ to be needed, and that is the honest stress test.
Relation to Prior Work
The proposal takes its motivating hardness result, and its strongest competitor for the argmax problem, from The Complexity of Phrase Alignment Problems. That paper proves that finding the best bijective phrase alignment is NP-hard and that computing its expectations is #P-hard. It then solves the argmax with integer linear programming, an exact combinatorial optimizer, reaching the global optimum 93.4% of the time on English–Spanish sentences up to 25 words. It leaves the summation problem open. We address the summation problem and do not need candidate phrases from a heuristic pipeline.
Three lines of work approximate the sum by Markov chain Monte Carlo, a random walk over alignments that converges to the posterior only after many local moves:
- Sampling Alignment Structure under a Bayesian Translation Model uses five local edit operators under Dirichlet-process priors. It needed up to two days on 8 processors for 177K Spanish–English pairs capped at 20 words.
- A Gibbs Sampler for Phrasal Synchronous Grammar Induction uses split/join and insert/delete tree edits.
- An Infinite Hierarchical Bayesian Model of Phrasal Translation uses Metropolis-Hastings over trees of an inversion transduction grammar (ITG), a grammar that builds an alignment by recursively keeping or swapping adjacent blocks. It prunes with word alignments and caps sentences at 30 words.
All three give correlated samples with no error certificate. We replace their local moves with whole-sentence exact draws whose quality is certified by the acceptance rate.
The ITG models of An Unsupervised Model for Joint Phrase Alignment and Extraction and Joint Phrase Alignment and Extraction for Statistical Machine Translation motivate the target. They match the heuristic pipeline in BLEU with tables five times smaller, so they show the payoff. They also constrain the design. Their ITG restriction costs $O(n^6)$, and their flat, non-hierarchical joint model performed poorly. We therefore keep a hierarchical Pitman-Yor phrase prior, a prior that favours reusing frequent phrases while still building rare ones from smaller parts. We change only how the alignment space is searched. Our relaxation is a superset of the bijective space, whereas ITG is a subset of it. The difference matters because importance sampling requires the proposal to cover every alignment the target can produce.
The heuristic-extraction literature explains why posterior expectations, rather than a single frozen alignment, are worth having. Deng, 2005 shows that one stray word link vetoes a whole phrase block. Consistency-Aware Search for Word Alignment shows that better word-alignment scores need not translate into better phrase extraction. Phrase counts averaged over posterior samples should be robust to any single bad link.
Research Program
The relaxed dynamic program. We first build the relaxed sampler. Source phrases are generated left to right, and each picks a target span. The state records the leftmost uncovered target position plus a bitmask of the next $d$ target positions, as in phrase-based decoding with a distortion limit. Spans landing inside the window are checked for overlap exactly. Spans landing beyond the window are placed but not tracked. Cost is $O(n\,2^d L^2)$ for maximum phrase length $L$. A final check accepts the sample only if the target side is covered exactly once.
Correctness. We verify by brute-force enumeration, on sentences of up to 10 words, that the accepted samples match the exact posterior. We also check that $\hat Z$ is unbiased with the predicted relative error.
Training. We embed the sampler in a sentence-blocked sampler for the Bayesian joint model. The Chinese-restaurant-process count dependence means the proposal weights use counts from all other sentences. A Metropolis-Hastings correction accounts for within-sentence count changes, the standard device for blocked sampling under such priors. The acceptance rate of that correction is reported separately from the rejection rate.
Adaptive window. Per sentence, $d$ is grown until a pilot estimate of $p_d$ exceeds a target such as 0.1. This yields a cost profile over the corpus that we report in full.
Fallback. When $d$ would exceed a budget (we expect this mostly for long Japanese–English sentences), the sentence falls back to the local-move Gibbs sampler. The fraction of fallbacks is itself a result.
Baselines
Naive heuristic pipeline. This is GIZA++ word alignment followed by grow-diag-final-and extraction and relative-frequency scoring in Moses, trained on full-length sentences. It is the do-nothing reference and what practitioners actually run. On Spanish–English Europarl up to 20 words, Sampling Alignment Structure under a Bayesian Translation Model reports this baseline at 30.5 BLEU. Beating it means equal or better BLEU with a substantially smaller table, on the same full-length data.
Strongest existing joint model. This is the hierarchical Pitman-Yor ITG model (HIER) of Joint Phrase Alignment and Extraction for Statistical Machine Translation. It reports 21.50 BLEU against 21.35 for the pipeline on French–English and 23.23 against 23.20 on Japanese–English, with tables of 1.0M versus 4.9M entries on German–English. It is the strongest competitor because it already achieves the compactness we target. We run it with its own beam pruning on identical data, give it the same CPU-hour budget as our system, and tune both with the same number of tuning runs. Beating it means equal or better BLEU and table size at matched compute, or the same quality on sentences beyond its length cap. For Spanish–English HIER, no reported result was found on Lacuna.
Local-move Gibbs sampler. This is the sampler of Sampling Alignment Structure under a Bayesian Translation Model, run under the same prior with the same wall-clock budget. Its best reported configuration is 30.7 BLEU at a 92% smaller table. Beating it means matching that BLEU in less time. We also compare cross-chain agreement of phrase counts, a measure of how well the sampler has explored the posterior.
Hard EM on the ILP Viterbi alignment. This trains on the single best alignment found by the integer program of The Complexity of Phrase Alignment Problems. It isolates whether posterior uncertainty matters at all.
Ablations. Two ablations isolate the key ingredient. The first replaces our superset proposal with the ITG-restricted model, an exact but subset-only space. This tests whether non-ITG mass matters. The second sets $d=0$, a monotone proposal. This shows how acceptance collapses without the window.
Why not just…?
Why not just use the heuristic pipeline, which already gets the same BLEU? This is a real threat. The joint-model gains in the file are often fractions of a BLEU point: 21.50 versus 21.35 and 23.23 versus 23.20 in Neubig et al., and 30.7 versus 30.5 in DeNero et al. If our system only ties on BLEU, the contribution is compactness plus calibrated phrase counts at full sentence length. Prior joint models could not deliver that combination without truncation. We will say plainly if that is all we deliver.
Why not just do Viterbi with the ILP and hard EM? The ILP solves the argmax but, as The Complexity of Phrase Alignment Problems states, not the sum. An Infinite Hierarchical Bayesian Model of Phrasal Translation reports that averaging over sampled posteriors gave 16.97 BLEU on Urdu–English against 15.65 for pialign. The hard-EM baseline above measures this gap directly in our setting.
Why not just run Gibbs sampling longer? More compute does not certify that the chain has explored the posterior. The documented runtimes are already days at 20 words. Our sampler produces independent exact draws whose cost is predicted by $p_d$, and we compare the two at equal wall-clock time. If Gibbs matches our counts and BLEU at equal time, the method's value reduces to its diagnostic, and we will report that.
Why not just use exact ITG inside-outside, which is polynomial? It is exact only over ITG alignments, a subset that cannot serve as an importance proposal for the full space. Its $O(n^6)$ cost is what forced length caps in the first place. The ITG-proposal ablation shows whether the excluded non-ITG mass matters for each language pair. If it does not matter for European pairs, our advantage there reduces to speed.
Proposed Experiments
Correctness on short sentences. On Europarl sentences of up to 10 words we enumerate the bijective space exactly. We then check that accepted samples match the true posterior in total-variation distance, and that the empirical relative error of $\hat Z$ follows $\sqrt{(1-p_d)/(Np_d)}$.
Acceptance against length and window. We measure $p_d$ against $n$ and $d$ on Spanish–English, French–English and German–English Europarl, and on Japanese–English. This is the decisive check. If $p_d$ falls exponentially with no affordable $d$ that restores it on full-length European sentences, the central claim fails.
End-to-end translation. We train on full-length Spanish–English Europarl and on the subset of up to 20 words. The short subset gives a direct comparison to the reported 30.7 and 30.5 BLEU. We also train on French–English and German–English against HIER. We report BLEU, phrase-table size and wall-clock time for every system under the matched budgets described above.
Hard reordering. Japanese–English, and if feasible the Urdu and Farsi pairs, test where the window assumption breaks. There we report the fallback rate alongside BLEU.
The method succeeds if it removes the length cap and the word-alignment pruning while keeping the five-fold table reduction at equal BLEU. It fails if acceptance collapses at realistic lengths.
References
- An Accurate Sample Rejection Estimator of the Outage Probability With Equal Gain Combining
- The Complexity of Phrase Alignment Problems
- Sampling Alignment Structure under a Bayesian Translation Model
- A Gibbs Sampler for Phrasal Synchronous Grammar Induction
- An Infinite Hierarchical Bayesian Model of Phrasal Translation
- An Unsupervised Model for Joint Phrase Alignment and Extraction
- Joint Phrase Alignment and Extraction for Statistical Machine Translation
- Phrase Table Training for Precision and Recall: What Makes a Good Phrase and a Good Phrase Pair?
- Consistency-Aware Search for Word Alignment