Phrase Extraction from the Price of Consistency

Phrase-based translation systems learn their vocabulary of multi-word translations ("phrase pairs") by first aligning words between parallel sentences with an unsupervised statistical model, then cutting out every block of words whose alignment links stay inside the block. That cutting step is a hard yes/no geometric rule, and it is brittle. One stray link from a function word or punctuation mark into or out of a block forbids the block outright, so good large phrases are lost and nothing downstream can bring them back. This proposal replaces the rule with a learned decision. For every candidate block, we ask the generative word aligner how much likelihood it would lose if it were forced to keep that block self-contained. We then feed a discriminative classifier both this cost and its gradient with respect to the aligner's word-translation parameters. The gradient is a sparse, readable vector that names which word pairs pay the cost.

The bet is that the classifier can learn which violations are tolerable and which are fatal. A block whose only outside link is a "de" or a comma attaching to a neighbor should be kept. A block whose content word wants to translate to something outside should be dropped. Today this distinction is either ignored, as in heuristic extraction, or hand-engineered as surface features, as in discriminative rescoring. If the bet holds, extraction recovers phrases the hard rule blocks, keeps tables compact, and does it in a single stage rather than by filtering a table that has already lost those phrases.

Core Claim

Let a sentence pair be $(\mathbf{f}, \mathbf{e})$. Let $b$ be a candidate bispan, meaning a source span paired with a target span. Let $\theta$ be the word-translation parameters of a generative aligner (IBM Model 1 or an HMM aligner). Let $\mathcal{A}_b$ be the set of alignments in which no link crosses the boundary of $b$. The price of consistency for $b$ is

$$\Delta(b) = \log P_\theta(\mathbf{f} \mid \mathbf{e}, \mathcal{A}_b) - \log P_\theta(\mathbf{f} \mid \mathbf{e}),$$

the log-likelihood the aligner gives up when restricted to alignments that respect $b$. Its gradient,

$$g(b) = \nabla_\theta \Delta(b) = \frac{\mathbb{E}_{\mathcal{A}_b}[c] - \mathbb{E}[c]}{\theta},$$

is a Fisher score difference. Here $c$ is the vector of word-pair link counts, the two expectations are over constrained and unconstrained alignment posteriors, and the division is elementwise. It is nonzero only on the word pairs whose posterior link mass the constraint moves, so it says exactly which lexical translations the phrase would suppress or boost. For Model 1 both terms are closed-form products of per-word sums. For the HMM aligner they come from one forward-backward pass with crossing transitions masked out.

The claim is specific. A linear classifier over $g(b)$, together with $\Delta(b)$ and a few shape features, predicts gold-standard phrase pairs better than the scalar $\Delta(b)$ alone, better than unweighted indicators of the crossing word pairs, and better than hand-crafted phrasal feature sets. The resulting phrase tables translate at least as well as discriminative extraction-set models at a fraction of their inference cost.

Relation to Prior Work

The motivating evidence comes from phrase extraction itself. Phrase Table Training for Precision and Recall shows that a single spurious link blocks valid large phrases and damages rule recall. Consistency-Aware Search for Word Alignment shows that aligners are blind to extraction consistency and that lower alignment error does not reliably bring better translation. Shen et al. respond by adding a scalar coverage bonus to alignment search. We instead keep the alignment soft and move the consistency judgment into a learned extraction decision.

The closest work is Discriminative Modeling of Extraction Sets for Machine Translation. It trains a margin-based model to predict whole nested sets of phrase pairs under an inversion transduction grammar, a restricted class of word reorderings that permits efficient parsing. It uses handcrafted phrasal and lexical-template features and a recall-weighted phrase F-measure ($F_5$). Our model differs in two ways. It scores bispans independently from generative-gradient features, with no grammar-constrained parsing, so it does not inherit their limit to that reordering class or their coarse-to-fine pruning cost. And its features come from the aligner's own information geometry rather than templates. The post-hoc approaches, Feature-Rich Discriminative Phrase Rescoring for SMT and Selective Phrase Pair Extraction for Improved Statistical Machine Translation, score phrases that heuristic extraction already produced. Huang and Xiang's coverage-ratio feature is a hand-built cousin of $\Delta$. Neither approach can recover blocked phrases, because their candidate set is the heuristic table. Our candidate set is all bispans up to a length limit.

The method is supplied by the generative-discriminative literature. Exploiting Generative Models in Discriminative Classifiers introduced Fisher scores, the gradient of a generative model's log-likelihood, as fixed-length features for variable-length inputs. We apply the gradient to a difference of constrained and unconstrained likelihoods, not to a marginal likelihood. That turns a generic embedding into a targeted measure of one structural decision. Because $\theta$ is a word-translation table, we use the diagonal approximation to the Fisher information. This sidesteps the matrix-inversion cost that paper flags. Baselines and Bigrams shows that scaling sparse indicators by generative ratios before discriminative training is a strong, cheap regularizer. Our $g(b)$ is the same kind of object: crossing-pair indicators scaled by posterior shifts.

Two papers constrain the design. Discriminative Substring Decoding for Transliteration found that dense generative scores beat rich sparse indicators in a controlled comparison. That warns us the scalar $\Delta$ may already carry most of the signal, and it makes the scalar-only model a required baseline. A Discriminative Matching Approach to Word Alignment and Designing an Improved Discriminative Word Aligner show that generative probabilities work well as features for discriminative aligners. But both stop at word links and still extract heuristically. We test whether their strength survives once extraction is no longer heuristic.

Research Program

We first build the generative side. We train Model 1 and HMM aligners in both directions on the parallel training data. We implement constrained inference that returns $\Delta(b)$ and the sparse $g(b)$ for every bispan up to seven words per side.

Scoring all such bispans with the HMM is the expensive part. We use the closed-form Model 1 $\Delta$ as a cheap prefilter and share forward-backward computations across bispans with a common source span. We will measure what fraction of gold bispans the prefilter discards, so the speed-up is not silently buying lost recall.

Supervision comes from hand-aligned sentences, from which gold bispans follow by the standard consistency rule. This matches the supervision regime of DeNero and Klein and of Huang and Xiang. The classifier is $\ell_1$-regularized logistic regression over $[\Delta(b), g(b)$ hashed to a fixed width, the two span lengths$]$. We weight the loss toward recall so that training targets $F_5$. We also train an NBSVM-style variant that interpolates with a generative-only weight vector, following Wang and Manning.

At extraction time, each bispan's classifier probability becomes a fractional count. Phrase translation probabilities are estimated from these counts, and a threshold controls table size. The tables then go into an unchanged phrase-based decoder.

The analysis question is interpretive. We will inspect the learned weights on $g(b)$ coordinates to see whether the classifier has in fact learned to tolerate violations from function words and punctuation. If it has, that confirms the mechanism rather than only the score.

Baselines

The do-nothing reference is GIZA++ alignments symmetrized with grow-diag-final followed by standard heuristic extraction. It is trained on the same parallel corpus with the same maximum phrase length. On NIST Chinese–English, DeNero and Klein report bispan $F_5$ of 46.0 for this pipeline. On Hansards French–English, Zettlemoyer and Moore report 26.78 BLEU.

The strongest existing method on our question is the extraction-set model of DeNero and Klein. It reports bispan $F_5$ of 74.0 on the hand-aligned NIST MT02 portion, AER of 15.6, and BLEU gains of 1.2 with Moses and 1.4 with Joshua over the GIZA++ pipeline on MT04/MT05. It is the strongest competitor because it already does single-stage, extraction-oriented discriminative training against the same $F_5$ target. We will reimplement it on identical training and hand-aligned data. We will give both models the same hyperparameter search budget on a held-out slice of the hand alignments, and report wall-clock training and extraction time alongside accuracy. Beating it means higher $F_5$ on the same test bispans. Failing that, it means matching $F_5$ within a percentage point at substantially lower cost while matching its Moses BLEU gain. If our reimplementation falls short of 74.0, we will report the gap and compare against both numbers.

We include both post-hoc competitors. The first is Huang and Xiang's rescoring, which reports 39.87 vs. 38.67 BLEU on NIST MT08 English–Chinese with a 16% table reduction. The second is Zettlemoyer and Moore's competitive linking, at 28.30 vs. 26.78 BLEU on Hansards. Each runs on top of the same GIZA++ table, with its pruning threshold tuned on the same development set as ours. Beating them requires higher BLEU at equal or smaller table size. Shen et al.'s coverage-aware alignment search followed by heuristic extraction is the alignment-side competitor. It reports about +1.0 BLEU on Chinese–English, and we run it with its coverage weight tuned on the same development data. Neubig et al.'s unsupervised joint model, HIER, is the no-supervision competitor. It reports 23.23 BLEU vs. 23.20 for GIZA++ on Japanese–English, with tables shrinking from 4.22M to 723K entries.

Two ablations isolate the key ingredient. The scalar-only model drops $g(b)$ and keeps $\Delta(b)$ and span lengths. The unweighted-indicator model replaces $g(b)$ with binary indicators of which word pairs carry crossing posterior mass. The Fisher-difference vector earns its place only if it beats both ablations on $F_5$ with overlapping-free confidence intervals across resampled test sentences.

Why not just…?

Why not just run grow-diag-final on top of a strong discriminative aligner? Better links do not remove the hard rule; they only make violations rarer. Shen et al. show that alignment accuracy and extraction quality come apart, and Deng shows that a single residual spurious link still blocks a large phrase. Tomeh et al.'s aligner, with an AER of 11.2 against 19.8, gained about 1 BLEU, which is comparable to what extraction-side methods report. We will settle this directly. We run heuristic extraction over the best discriminative aligner we can train on the same hand alignments, and over the oracle gold alignments, and compare $F_5$. If extraction from that aligner matches our classifier, the proposal's premise is wrong.

Why not just prune or rescore the heuristic table? Post-hoc methods only remove or reweight phrases that heuristic extraction already produced. They cannot add a phrase that a stray link blocked. We will measure this as the share of gold bispans absent from the GIZA++ table that our model recovers. That share bounds what Huang and Xiang or Zettlemoyer and Moore could ever achieve. Pruning remains a real competitor on table size, which is why both are tuned to match our table size in the BLEU comparison.

Why not just add the scalar generative score to sparse indicators? This is the most serious threat. Cherry and Suzuki found dense generative scores alone beat rich indicators, and $\Delta(b)$ is exactly such a score. If the scalar-only ablation matches the full model, the honest conclusion is that a soft, likelihood-based consistency test is the contribution and the Fisher vector is unnecessary. We would report it that way. The unweighted-indicator ablation separately checks whether the posterior weighting in $g(b)$, rather than just knowing which words cross, does the work.

Why not just use unsupervised Bayesian joint phrase induction? Neubig et al.'s HIER produces compact tables without labels, but it matched rather than beat GIZA++ BLEU. It also optimizes likelihood rather than extraction quality, which Xiao and Xiong identify as the limitation their max-margin induction overcomes. Our method needs a few thousand hand-aligned sentences. If HIER's tables match ours at similar size on Japanese–English, the supervision is not paying for itself, and the comparison is designed to show that.

Proposed Experiments

The primary benchmark is NIST Chinese–English. Following DeNero and Klein, we train on the same scale of parallel text (about 22M words), measure bispan $F_5$, precision, and recall on the hand-aligned MT02 portion, and measure Moses BLEU on MT04 and MT05. Canadian Hansards French–English, with Zettlemoyer and Moore's 500K training pairs and 2,000 test sentences, tests the table-size trade-off. Japanese–English tests against HIER.

The first decisive check is the ablation ladder on $F_5$: scalar $\Delta$, unweighted crossing indicators, full $g(b)$, and NBSVM-interpolated $g(b)$. This tells us whether the generative gradient matters. The second is recovered recall: among gold bispans blocked under GIZA++ grow-diag-final, what fraction we extract, broken down by the part of speech of the blocking word. The third is the BLEU-versus-table-size curve traced by our extraction threshold, plotted against the operating points of competitive linking, rescoring, and HIER. The fourth is cost, as extraction time per sentence against the reimplemented extraction-set model.

We will count the proposal as successful under two conditions. The full model must beat both ablations on $F_5$ and match or exceed the extraction-set model's BLEU gain over GIZA++. It must also do so with the weight analysis showing that tolerated violations concentrate on function words and punctuation. If only the scalar $\Delta$ is needed, we will report a simpler result: a likelihood-priced soft consistency test that replaces the hard extraction rule.