Elamur Research
☰
home / papers / 2004 / Monolingual Machine Translation for Paraphrase Generation

Monolingual Machine Translation for Paraphrase Generation

What it is about

The paper treats paraphrase generation as translation within one language. Training pairs are sentences from news stories that different web sources wrote about the same event, clustered and aligned at sentence level. Word alignment uses the GIZA++ IBM models and an HMM, with alignment error rate 11.58% on 250 hand-aligned sentences (interrater agreement 93.1%). A monotone phrasal decoder then generates contextual replacements, and the paper argues that statistical MT tools are a route to better coverage and scale than hand-built paraphrase rules. Human judges rated the paraphrases as plausible more often than outputs of a WordNet synonym baseline, an unsupervised clustering baseline and the Barzilay and Lee system on the same 59-sentence set. A trigram language model did not help the WordNet baseline, which the authors take to mean that lexical choice, not fluency, is the bottleneck.

Ideas

For Mova

The paper's data and its alignment step are close to the translator's verse pairs and its IBM alignment. The standard encoder in profile.rs and the lexicon in meta.rs are the places for the replacement table. Only counts are proposed here, not the neural decoders the paper also discusses. Summary only.

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/W04-3219.pdf

Summary

The paper treats paraphrase generation as translation within a single language. It applies the standard noisy-channel SMT setup, so English sentences are "translated" into other English sentences. The authors needed a large parallel monolingual corpus, so they built one automatically. They took news clusters from aggregators such as Google News and Yahoo News, in which many outlets report the same event. Within each cluster they paired sentences that were close by word-level Levenshtein distance. They aligned these pairs with Giza++ and checked alignment quality against a hand-aligned gold set using AER. From the alignments they extracted a database of phrasal replacements, scored the replacements with IBM Model 1, and decoded with a monotone phrasal decoder.

Human judges preferred this output to baseline methods, including the MSA template approach of Barzilay & Lee. The rewrites are modest: there is no reordering. However, the method is much more general and loses far less information. It matters because it shows that cheap, scalable web data can support broad-domain paraphrasing.

Key points

  • Data collection: About 8 months of crawling yielded 11,162 clusters with 177,095 articles, an average of 15.8 per cluster.

    • An HMM separated story text from ads and captions, reaching 95% F-measure. It was trained on 1,150 hand-tagged articles.

  • Filtering: Pairs were kept only if they passed these rules:

    • not identical, and not differing only in punctuation;
    • not duplicates;
    • length ratio of at least 2/3;
    • Levenshtein distance of at most 12.

    This left 139K pairs, with a mean edit distance of 5.17 and a mean sentence length of 18.6 words.

  • Alignment quality: Bidirectional Giza++ alignment was evaluated on 250 held-out, hand-aligned pairs with SURE/POSSIBLE links. Interannotator agreement on this set was 93.1%.

    • Overall AER was 11.58%.
    • AER was 10.57% on identical words and 20.88% on non-identical words.

  • Phrase extraction and scoring: Phrase pairs were limited to at most five cepts and had to be contiguous on both sides. Their probabilities came from five iterations of IBM Model 1, and an identity lexicon was added to the training data.

  • Qualitative comparison with MSA: MSA rewrites more aggressively but drops information much more often.

DimensionMSA (59 paraphrases)Top-ranked PR (100 paraphrases)
Reordering47%0%
Information lost73%31%

In addition, 25.4% of MSA outputs relied on one domain-specific template.

Interesting ideas

  • News clusters as free parallel data. Clusters of stories about the same event can serve as a ready-made source of same-language parallel text. This could be reused for any language with active online news, such as Ukrainian, to bootstrap paraphrase or simplification corpora without paid translation.
  • Cheap filtering with known blind spots. Simple filters (edit distance, length ratio, deduplication) can turn noisy comparable text into alignable pairs. The authors note that this misses pairs that mean the same but are worded very differently. They suggest using the first two sentences of articles as a richer, if noisier, alternative.
  • Model 1 scoring for phrase pairs. Scoring phrase replacements with word-level Model 1, rather than counting each phrase pair, avoids the sparsity problem of direct estimation. It also gives multiword collocations a fair chance, which is useful whenever a phrase table is built from limited data.
  • Measuring alignment quality before building anything. Checking corpus quality with AER against a small double-annotated SURE/POSSIBLE gold set is a reusable recipe. It lets you see whether an automatically mined corpus is trustworthy before training on it.
  • Evaluating along separate dimensions. Scoring paraphrases separately for reordering, phrasal alternation, information added and information lost reveals trade-offs that a single quality score hides. So does checking how many outputs depend on a single template. Both checks could help when evaluating any generation system.

Topics: Machine translation

Cite

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

@inproceedings{quirk2004monolingual,
  title = {{Monolingual Machine Translation for Paraphrase Generation}},
  author = {Quirk, Chris and Brockett, Chris and Dolan, William},
  booktitle = {Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing},
  year = {2004},
  url = {https://aclanthology.org/W04-3219/}
}

References

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

  1. R. Barzilay and K. R. McKeown. 2001. Extracting Paraphrases from a parallel corpus. In Proceedings of the ACL/EACL. find our card
  2. R. Barzilay and L. Lee. 2003. Learning to Paraphrase; an unsupervised approach using multiple-sequence alignment. In Proceedings of HLT/NAACL. find our card
  3. P. Brown, S. A. Della Pietra, V. J. Della Pietra and R. L. Mercer. 1993. The Mathematics of Statistical Machine Translation. Computational Linguistics 19(2): 263-311. find
  4. W. Dolan, C. Quirk and C. Brockett. 2004. Unsupervised Construction of Large Paraphrase Corpora: Exploiting Massively Parallel News Sources. To appear in Proceedings of COLING-2004. find our card
  5. C. Fellbaum, ed. 1998. WordNet: An Electronic Lexical Database. MIT Press, Cambridge, MA. find
  6. J. Goodman. 2002. JCLUSTER. Software available at http://research.microsoft.com/~joshuago/ ↗
  7. A. Ibrahim. 2002. Extracting Paraphrases from Aligned Corpora. Master of Engineering Thesis, MIT. find
  8. A. Ibrahim, B. Katz, and J. Lin. 2003. Extracting Structural Paraphrases from Aligned Monolingual Corpora. In Proceedings of the Second International Workshop on Paraphrasing (IWP 2003). Sapporo, Japan. find
  9. R. Kneser and H. Ney. 1995. Improved backing-off for N-gram language modeling. In Proc. Int. Conf. on Acoustics, Speech and Signal Processing: 181-184. Detroit, MI. find
  10. P. Koehn, F. Och, and D. Marcu. 2003. Statistical Phrase-Based Translation. In Proceedings of HLT/NAACL. find
  11. V. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physice-Doklady 10: 707-710. find
  12. D. Lin and P. Pantel. 2001. DIRT - Discovery of Inference Rules from Text. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining: 323-328. find
  13. I. D. Melamed. 2001. Empirical Methods for Exploiting Parallel Texts. The MIT Press. find
  14. R. Mihalcea and T. Pedersen. 2003. An Evaluation Exercise for Word Alignment. In HLT/NAACL Workshop: Building and Using Parallel Texts: 1-10. find
  15. F. Och and H. Ney. 2000. Improved Statistical Alignment Models. In Proceedings of the ACL: 440-447. Hong Kong, China. find
  16. F. Och and H. Ney. 2003. A Systematic Comparison of Various Statistical Alignment Models. Computational Linguistics 29(1): 19-52. find
  17. B. Pang, K. Knight, and D. Marcu. 2003. Syntax-based Alignment of Multiple Translations: Extracting Paraphrases and Generating New Sentences. Proceedings of HLT/NAACL. find our card
  18. Y. Shinyama, S. Sekine and K. Sudo. 2002. Automatic Paraphrase Acquisition from News Articles. In Proceedings of NAACL-HLT. find
  19. F. K. Soong and E. F. Huang. 1991. A tree-trellis based fast search for finding the n-best sentence hypotheses in continuous speech recognition. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing 1: 705-708. Toronto, Canada. find
  20. E. Sumita. 2001. Example-based machine translation using DP-matching between work sequences. In Proceedings of the ACL 2001 Workshop on Data-Driven Methods in Machine Translation: 1–8. find
  21. C. Tillmann, S. Vogel, H. Ney, and A. Zubaiga. 1997. A DP Based Search Using Monotone Alignments in Statistical Translation. In Proceedings of the ACL. find
  22. L. Vita, A. Ittycheriah, S. Roukos, and N. Kambhatla. 2003. tRuEcasing. In Proceedings of the ACL: 152-159. Sapporo, Japan. find
  23. S. Vogel, H. Ney and C. Tillmann. 1996. HMM-Based Word Alignment in Statistical Translation. In Proceedings of the ACL: 836-841. Copenhagen Denmark. find
  24. S. Vogel, Y. Zhang, F. Huang, A. Venugopal, B. Zhao, A. Tribble, M. Eck, and A. Waibel. 2003. The CMU Statistical Machine Translation System. In Proceedings of MT Summit IX, New Orleans, Louisiana, USA. find