Syntax-based Alignment of Multiple Translations: Extracting Paraphrases and Generating New Sentences

What it is about

The authors take groups of 11 English translations of the same Chinese sentence (899 groups) and parse each one. The parse trees are merged top-down: two nodes join when they expand by the same rule, and a keyword check stops a join when the content words under the two nodes overlap elsewhere. The merged forest becomes a word lattice whose paths are paraphrases; a squeezing step then joins the far ends of equal-word edges that share a node. Four judges rated 600 paraphrase pairs: 77–85% of the syntax-based pairs were correct, against 63–68% for a co-training baseline. Multiple-sequence alignment produced lattices with many bad paths, where a word repeats though no source sentence repeats it (repetition ratio 0.030 against 0.0035 for this method).

Ideas

I1. Join only where the parents agree. When tools/translate merges two meta tokens from two translations of a verse into one concept (meta.rs), allow the join only if the heads they hang from already joined, and go top-down, stopping at the first disagreement. This is the paper's rule against open problems 1 and 2. Measure the number of joins and the reader plus encoder bits, run twice.
I2. A keyword veto. Before a join, check whether the content words under each side occur elsewhere in the same verse; if they do, do not join. Count how many of today's merges (for example be with have) it removes.
I3. A squeeze step on the meta-world. When two edges with the same concept leave one node, join their far ends. Measure how often a concept appears twice in one reading of a verse where the source has it once, before and after.
I4. A held-out gain. Hold one translation of a verse out, and compare its edit distance to the meta-world paths with its edit distance to the other translations as a plain set (the paper's ed gain, mean 0.91 over 899 groups). It is a measure of the lexicon that uses no test set.

For Mova

The paper is the nearest published method to the meta-world: several translations of one text merged into one structure, with rules and no learned model. Its target is paraphrase, not translation, so only the reader and the lexicon carry over. Measure the join counts under I1 and I2 on dev before any claim about the residual.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/N03-1024.pdf

Summary

The paper tackles two linked problems: how to represent paraphrases so that their combinations can be generated, and how to induce such representations automatically. Simple lists of equivalent phrase pairs cannot be recombined into new sentences. The authors instead take groups of 11 independent English translations of the same Chinese sentence from the LDC Multiple-Translation Chinese (MTC) Corpus. They parse each translation with Charniak's parser and merge the trees top-down into a forest-like structure. A keyword filter blocks merges that are likely wrong. The forest is then turned into a word lattice (FSA), which a bottom-up "squeezing" step compacts further. Every path through the lattice is a candidate rendering of the same meaning. This yields lexical and structural paraphrase pairs plus many new, unseen sentences. Unlike plain multi-sequence alignment, the method copes with translations that order their constituents differently. In leave-one-out tests, the FSA predicts a held-out translation better than the raw set of references does. This suggests a way to refine MT evaluation metrics such as BLEU.

Key points

Data: MTC Corpus (LDC2002T01), with 105 news stories and 993 sentences, each translated by 11 agencies. The experiments use 899 sentence groups, after dropping groups with sentences over 45 words.
Pipeline: parse every sentence, merge the trees recursively wherever two nodes share the same expansion rule, linearize the result into an FSA, then squeeze it.
In the running example, 11 translations yield an FSA that encodes 49 distinct renderings. On the same input, an MSA baseline produces many ungrammatical paths.
Edit-distance gain of the FSA over the closest single reference has a mean of 0.91 (std. dev. 0.78) across 899 groups, and most gains fall below 2.
Adding references keeps helping, even the tenth one. The advantage of the FSA over a plain reference set grows from 0 with one reference to 0.93 with ten.

Interesting ideas

Syntax-guided alignment instead of pure sequence alignment. Matching nodes only when they share the same expansion rule lets translations with different word orders be aligned safely. The same trick could help build paraphrase or variant lattices for any language that has a decent parser.
Lexical veto on structural merges. Each node keeps a list of the content words it spans (nouns, verbs, adjectives). A merge is cancelled if a child's words show up under a different sibling in the other tree. This is a cheap sanity check that could prevent false alignments in many tree-matching tasks.
Strict top-down merging followed by a bottom-up repair pass. A conservative first pass keeps precision high, and the later "squeezing" recovers merges missed because of parse errors or small structural differences. This high-precision-then-recall pattern is reusable in many induction pipelines.
Evaluating against a lattice rather than a set of references. Scoring a sentence by its minimum edit distance to any path in an FSA rewards valid recombinations of reference fragments. This could make reference-based MT or generation metrics less brittle when only a few references exist.
Leave-one-out predictive power as an intrinsic evaluation. Checking how well a structure built from n−1 translations predicts the held-out one measures generalization without human judges. Varying n also shows how much each extra reference contributes.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{pang2003syntax,
  title = {{Syntax-based Alignment of Multiple Translations: Extracting Paraphrases and Generating New Sentences}},
  author = {Pang, Bo and Knight, Kevin and Marcu, Daniel},
  booktitle = {Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
  url = {https://aclanthology.org/N03-1024/}
}

References

16 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

Srinivas Bangalore, German Bordel, and Giuseppe Riccardi. 2001. Computing consensus translation from multiple machine translation systems. In Workshop on Automatic Speech Recognition and Understanding. find
Regina Barzilay and Lillian Lee. 2002. Bootstrapping lexical choice via multiple-sequence alignment. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 164–171. find
Regina Barzilay and Lillian Lee. 2003. Learning to paraphrase: An unsupervised approach using multiple-sequence alignment. In Proceedings of HLT/NAACL. find our card
Regina Barzilay and Kathleen McKeown. 2001. Extracting paraphrases from a parallel corpus. In Proceedings of the ACL/EACL, pages 50–57. find our card
Regina Barzilay, Kathleen McKeown, and Michael Elhadad. 1999. Information fusion in the context of multi-document summarization. In Proceedings of the ACL, pages 550–557. find
Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of the NAACL. find
DARPA. 2002. In DARPA IAO Machine Translation Workshop, Santa Monica, CA, July 22-23. find
Ulf Hermjakob, Abdessamad Echihabi, and Daniel Marcu. 2002. Natural language based reformulation resource and web exploitation for question answering. In Proceedings of the Text Retrieval Conference (TREC–2002). November. find
Lidija Iordanskaja, Richard Kittredge, and Alain Polgére. 1991. Lexical selection and paraphrase in a meaning-text generation model. In Cécile L. Paris, William R. Swartout, and William C. Mann, editors, Natural Language Generation in Artificial Intelligence and Computational Linguistics, pages 293–312. Kluwer Academic Publisher. find
Irene Langkilde and Kevin Knight. 1998. Generation that exploits corpus-based statistical knowledge. In Proceedings of of ACL/COLING. find
Nils Lenke. 1994. Anticipating the reader’s problems and the automatic generation of paraphrases. In Proceedings of the 15th International Conference on Computational Linguistics, volume 1, pages 319–323, Kyoto, Japan, August 5–9. find
Dekang Lin and Patrick Pantel. 2001. Discovery of inference rules for question answering. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining 2001, pages 323–328. find
Kishore Papineni, Salim Roukos, Todd Ward, John Henderson, and Florence Reeder. 2002. Corpus-based comprehensive and diagnostic MT evaluation: Initial Arabic, Chinese, French, and Spanish results. In Proceedings of the Human Language Technology Conference, pages 124–127, San Diego, CA, March 24-27. find
Yusuke Shinyama, Satoshi Sekine, Kiyoshi Sudo, and Ralph Grishman. 2002. Automatic paraphrase acquisition from news articles. In Proceedings of the Human Language Technology Conference (HLT–02), San Diego, CA, March 24-27. Poster presentation. find
Karen Sparck Jones and John I. Tait. 1984. Automatic search term variant generation. Journal of Documentation, 40(1):50–66. find
Manfred Stede. 1999. Lexical Semantics and Knowledge Representation in Multilingual Text Generation. Kluwer Academic Publishers, Boston/Dordrecht/London. find