Fertility and Agreement as Expectation Constraints on Exact Alignment Posteriors

Word alignment means deciding which words in a sentence correspond to which words in its translation. The most accurate models score candidate alignments with many overlapping clues: dictionary entries, spelling similarity, part-of-speech tags, and how far the alignment jumps between neighbouring words. These models face a trade-off. When an alignment is a simple chain (each source word points to one target word), dynamic programming can sum over every possible alignment exactly. That sum gives calibrated probabilities for each link and smooth training signals. The constraints that make alignments linguistically sensible, however, are not local. Fertility, meaning how many words a single word may align to, and agreement between the two translation directions both break the chain. So the field has given up exact summation for greedy search, local perturbation, or beam search over the top few alignments.

This note proposes a way to keep exact summation and still impose those constraints. The constraints are applied to the expected link counts of the model, not written into its scoring function. Expected link counts are sums of marginals that forward-backward already computes. Projecting the model's distribution onto the set of distributions that satisfy such constraints leaves a distribution with the same chain structure, so exact summation survives. The same setup lets us test, inside one model, a claim the literature leaves unresolved: that alignment posteriors are so peaked that summing over the tail of unlikely alignments is pointless.

Core Claim

Take two discriminatively trained directional aligners. Each is a linear-chain conditional random field (CRF): a model that scores label sequences with arbitrary overlapping features and normalizes over all sequences by dynamic programming, as in Discriminative Word Alignment with Conditional Random Fields. Fertility caps and bidirectional agreement can be imposed on these aligners as linear constraints on their expected links. The constrained distribution is computed by an exact projection, and decoding reads links off its marginals.

We predict two things. First, this beats heuristic symmetrization and posterior averaging on alignment error rate. Second, its advantage over a top-$n$ truncated version of the same model grows with how spread out the posterior is. The truncation should be harmless on French-English and harmful on Romanian-English and Japanese-English.

The mechanism is posterior regularization. Let $p_\theta(a \mid E,F)$ be a directional CRF over alignments $a$, and let $\phi(a)$ be a vector of link counts. For example, $\phi_j(a)$ is the number of source words aligned to target word $j$. The projection is

$$q^\* = \arg\min_q \mathrm{KL}(q \,\|\, p_\theta) \quad \text{s.t.} \quad \mathbb{E}_q[\phi(a)] \le b,$$

where $b$ holds the per-word fertility bounds. Its solution has the form $q^\* \propto p_\theta \exp(-\lambda^\top \phi(a))$, with dual variables $\lambda \ge 0$. Each $\phi_j$ is a sum of per-position link indicators, so $\lambda^\top\phi$ adds only per-position potentials. The projected $q^\*$ is therefore still a linear chain, and forward-backward computes it exactly.

Agreement works the same way. We add the equality constraint that the expected link $(i,j)$ under the source-to-target model matches the one under the target-to-source model, with a small slack. The dual is optimized by projected gradient, and each step costs one forward-backward per direction.

The honest limitation is that constraining an expectation is weaker than a hard cap. A distribution can satisfy "expected fertility ≤ 2" while putting mass on alignments of fertility 4. Whether this weaker form is enough is an empirical question, and the experiments are built around it.

Relation to Prior Work

Three papers motivate the gap. Discriminative Word Alignment with Conditional Random Fields keeps exact forward-backward by restricting alignment to a many-to-one chain. It then symmetrizes with grow-diag-final-and and cannot express fertility. We reuse its feature-rich chain model and replace the heuristic with a principled projection.

Log-Linear Models for Word Alignment and Discriminative Word Alignment with a Function Word Reordering Model model the full alignment matrix with non-local features. Because the matrix cannot be normalized, they fall back on greedy or stochastic local search. We keep their goal of non-local structure but give up their matrix-level scoring.

Word Alignment via Submodular Maximization over Matroids enforces fertility through partition matroids and greedy search. It produces a single hard alignment and no posterior.

Two papers constrain the design. Contrastive Unsupervised Word Alignment with Non-Local Features reports that the top five alignments hold over 99% of posterior mass. On that basis it truncates summation to the top $n$. If this holds generally, exact summation buys nothing, and our proposal must show where it fails rather than assume it does.

Learning Bilingual Word Representations by Marginalizing Alignments shows that summing over alignments with a generative IBM Model 2 back end left alignment error near the fast_align level, roughly 16% on Europarl French-English. Soft summation alone does not improve alignments; the features and constraints have to do the work.

Two papers supply methods. Unsupervised Word Alignment by Agreement Under ITG Constraint projects directional posteriors onto structural constraints, but only for generative IBM and HMM aligners during training. We apply the projection to discriminative CRFs, add fertility constraints, and project at decoding time too. Differentiable Dynamic Programming for Structured Prediction and Attention shows that the gradient of the log-partition function is the expected path. This is why constrained marginals can be used directly in the training gradient.

Discriminative Weighted Alignment Matrices For Statistical Machine Translation predicts each link independently with a MaxEnt classifier and uses the resulting soft matrices for phrase extraction. Our projected marginals are a drop-in soft matrix in which links compete with one another.

Research Program

We will build bidirectional linear-chain CRF aligners with the feature set of Blunsom and Cohn: jump width, part-of-speech pairs, Dice coefficients, IBM Model 1 scores, and orthographic similarity. They are trained on the small gold sets those benchmarks provide.

On top of them we implement the projection with two constraint families. The first is agreement between the directional expected links. The second is fertility, with bounds $b_j$ that are either fixed or predicted per word type from features.

Constraints enter in two places. At training time, the gradient uses the projected expectations; this is constraint-driven learning. At test time, links are read off the projected marginals with a threshold tuned on development data. We also extend to a semi-supervised setting: the projection serves as the E-step on unlabeled bitext, which addresses the supervision bottleneck these aligners share.

The analysis component is a controlled test of the concentration property. We replace exact marginals with expectations over the top-$n$ alignments from beam search, keeping the same model, features, and constraints. For each sentence we then record two quantities: how much posterior mass the top five alignments hold, and how far the truncated marginals are from the exact ones. This turns Liu and Sun's observation into a measurable quantity per language pair.

Baselines

The naive reference point is GIZA++ IBM Model 4 with grow-diag-final-and symmetrization, trained on each benchmark's full bitext. On Hansards, Discriminative Word Alignment with Conditional Random Fields reports Model 4 alignment error rate (AER) of 9.81, and 28.63 on Romanian-English.

The strongest supervised competitor is the Blunsom and Cohn CRF with heuristic symmetrization. It reports AER 5.29 on English-French Hansards and 25.8 on Romanian-English. We will reproduce it with identical features, gold splits, and hyperparameter search budget. Beating it means lower AER on both pairs, beyond the variance across three random seeds and data orderings.

The strongest number in the file on French-English comes from Contrastive Unsupervised Word Alignment with Non-Local Features: AER 5.01, against GIZA++ at 6.36 and the Berkeley aligner at 5.34. On Chinese-English it reports 20.24. That system is unsupervised, so it is not a like-for-like comparison. We will run its top-$n$ estimation inside our model and report its published figures only for context.

The key ablation separates our ingredient from cheap heuristics. One variant averages the two directional CRF posteriors and thresholds them, with no projection. A second applies agreement but no fertility constraint. A third projects only at test time. A fourth uses top-$n$ truncation in place of exact summation. All variants share features, training data, and the tuning budget for the threshold and slack.

For decoding, we compare thresholding against greedy submodular selection with fertility matroids, run on our own marginals. Word Alignment via Submodular Maximization over Matroids reports AER 18.6 on Hansards with IBM Model 2 link scores.

For Japanese-English we include the posterior-regularized ITG aligners of Unsupervised Word Alignment by Agreement Under ITG Constraint. The file quotes no exact KFTT AER for them, so we will rerun them.

Why not just…?

Why not just average the two directional posteriors and threshold? This is the cheapest form of symmetric soft alignment, and it may capture most of the agreement gain. It cannot express fertility, though, and averaging does not make links compete. Our ablation runs exactly this variant. If projection adds nothing over averaging on Romanian-English and Japanese-English, the constraint component is not justified, and we will report that.

Why not just use top-$n$ alignments, given the concentration property? This is the most serious threat. Liu and Sun found that the top five alignments hold over 99% of mass on their data, and they reached AER 5.01 on French-English. We expect them to be right for close, high-resource pairs, and we predict no gap there. The decisive experiment uses the same model under both estimators and plots the AER gap against per-sentence posterior entropy across languages. If the gap stays near zero on divergent pairs as well, the summation half of the proposal fails. What would remain is the cheaper claim that expectation constraints beat heuristics.

Why not just run submodular greedy decoding with fertility matroids? For 1-best AER, hard fertility caps may well outperform our softer expectation constraints. We therefore test the combination of our marginals with greedy matroid decoding as well as plain thresholding. What greedy decoding cannot provide is calibrated link probabilities for downstream soft use. We evaluate that separately, so a decoding win for greedy search would not undermine the soft-alignment result.

Why not just use fast_align with pre-reordering? Improving fast_align by Reordering matches GIZA++ on Japanese-English BLEU at 28.8 while running 2–4 times faster. It reports translation quality, not AER, and it cannot use the rich features that drive the CRF's lead in the supervised regime. We include it as a speed and quality reference point on Japanese-English.

Proposed Experiments and Decisive Checks

Alignment quality is measured by AER and F-measure on English-French Hansards, Romanian-English (ACL 2005 shared task), Chinese-English with the gold sets used by Liu et al., and Japanese-English KFTT and BTEC. Calibration of link marginals is measured by expected calibration error against gold links. Downstream, we follow Tomeh et al.: the projected marginals serve as weighted alignment matrices for phrase extraction on NIST Arabic-English, and we report BLEU. That paper reports AER 14–15% against MGIZA++ at 25%, and gains of up to +1.2 BLEU in a 30K-sentence setting. Our marginals replace their independent MaxEnt links under the same extraction pipeline.

Three checks decide the outcome. First, the projected model must beat both the Blunsom and Cohn CRF and the posterior-averaging ablation on Romanian-English and Japanese-English AER. Second, the gap between exact and top-$n$ estimation must be near zero on Hansards and grow with posterior entropy on divergent pairs. Third, the projected marginals must be better calibrated than averaged ones, and that calibration must translate into weighted-matrix phrase extraction at least as good as Tomeh et al.'s independent-link matrices. The third check is the one setting where soft posteriors, rather than 1-best links, are what is being consumed.