Elamur Research
☰
home / papers / 2003 / Learning to Paraphrase: An Unsupervised Approach Using Multiple-Sequence Alignment

Learning to Paraphrase: An Unsupervised Approach Using Multiple-Sequence Alignment

What it is about

The paper addresses sentence-level paraphrase, which is harder than word or phrase paraphrase, using comparable news corpora: different sources reporting the same events. Sentences are first clustered by topic and similarity within each source. Each cluster is aligned by multiple-sequence alignment into a word lattice, whose shared backbone nodes are the fixed words and whose gaps are slots. Pairs of lattices from different sources form paraphrase patterns, and a new sentence that matches one lattice is rewritten with the other. On held-out articles about violence in the Middle East, the system paraphrases 59 of 484 sentences (12.2%), against 7 sentences that appeared in the training set, so the lattices generalise far better than exact matching. Human judges rated the generated pairs, and the output was compared with a WordNet synonym baseline. Coverage is high on short articles and low on long ones, which the authors trace to the lattice matching.

Ideas

For Mova

The paper addresses the author delta (open problem 6) and the encoder's chunks (open problem 3). The data are news, not verses, so the lattice matching must be tried on the verse pairs before any gain is claimed. Summary only, as the licence is non-commercial.

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-1003.pdf

Summary

Barzilay and Lee address sentence-level paraphrase generation. This is harder than swapping words or phrases, because whole clauses can be equivalent without any word-to-word correspondence, and valid substitutions often depend on the domain. Their unsupervised, knowledge-lean method uses only comparable corpora: news articles from two different agencies covering the same events. It needs no parallel data, parsers or lexical databases.

The method has three stages:

  1. Within each corpus, structurally similar sentences are clustered, and multiple-sequence alignment (MSA) turns each cluster into a word lattice. Highly variable regions of the lattice become argument slots.
  2. A lattice from one corpus is paired with a lattice from the other as a paraphrase pattern when the two typically share the same argument fillers.
  3. A new sentence is matched to a lattice and rewritten using the paired lattice, with its arguments substituted in.

On held-out AFP news about Middle East violence, human judges rated about 80% of the system's paraphrases as meaning-preserving. A synonym-substitution baseline scored under 70%. The work shows that full-sentence rewriting can be learned from easily collected non-parallel data.

Key points

  • Clustering: sentences are grouped by hierarchical complete-link clustering on word n-gram overlap. Dates, numbers and proper names are first replaced with generic tokens, and clusters of fewer than ten sentences are dropped.
  • Alignment scoring: a match scores 1, an insertion scores −0.01, and a mismatch scores −0.5. Multi-sentence alignment uses iterative pairwise alignment, a standard technique from computational biology.
  • Test set and coverage: the test set was 20 AFP articles with 484 sentences. The system paraphrased 59 of them (12.2%), although only seven test sentences appeared verbatim in training.
  • Coverage by article length: short articles (ten sentences or fewer) averaged 60.8% of sentences paraphrased, versus 9.3% for longer ones. Long articles contain much article-specific material, such as personal stories.
  • Human judgments: two judges rated MSA output valid at 81.4% and 78%, versus 69.5% and 66.1% for the baseline, with Kappa 0.6. The two systems made largely different kinds of errors.

Interesting ideas

  • Variability marks the slots. Inside a cluster of sentences about the same kind of event, the positions where the aligned sentences differ most are treated as arguments. This turns raw text into templates without any annotation, and could work for any domain with repetitive reporting, such as trade bulletins or weather reports.
  • Pair patterns by shared fillers. Two patterns are considered equivalent if they take the same arguments across two comparable sources, even when their wording looks nothing alike. Cross-source news coverage of the same events thus serves as cheap, implicit supervision.
  • Normalize before clustering. Masking names, numbers and dates before measuring similarity keeps sentences about the same event type together. This avoids overly fragmented clusters and also guarantees the variability the slot-finding step depends on.
  • Isolate the evaluated component. The authors deliberately skipped language-model reranking so the paraphrasing module's own contribution could be judged. They also had judges assess complete sentences rather than templates, which makes judgments easier and more reliable.
  • Treat coverage as data-dependent. Reporting coverage separately for short and long documents shows where a pattern-based system actually applies. This kind of breakdown is a useful diagnostic for any template- or rule-based generator.

Topics: Machine translation

Cite

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

@inproceedings{barzilay2003learning,
  title = {{Learning to Paraphrase: An Unsupervised Approach Using Multiple-Sequence Alignment}},
  author = {Barzilay, Regina and Lee, Lillian},
  booktitle = {Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1073445.1073448},
  url = {https://doi.org/10.3115/1073445.1073448}
}

References

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

  1. Srinivas Bangalore, Vanessa Murdock, and Giuseppe Riccardi. 2002. Bootstrapping bilingual data using consensus translation for a multilingual instant messaging system. In Proc. of COLING. find
  2. Regina Barzilay and Lillian Lee. 2002. Bootstrapping lexical choice via multiple-sequence alignment. In Proc. of EMNLP, pages 164–171. find
  3. Regina Barzilay and Kathleen McKeown. 2001. Extracting paraphrases from a parallel corpus. In Proc. of the ACL/EACL, pages 50–57. find our card
  4. Raman Chandrasekar and Srinivas Bangalore. 1997. Automatic induction of rules for text simplification. Knowledge-Based Systems, 10(3):183–190. find
  5. Mark Dras. 1999. Tree Adjoining Grammar and the Reluctant Paraphrasing of Text. Ph.D. thesis, Macquarie University. find
  6. Richard Durbin, Sean Eddy, Anders Krogh, and Graeme Mitchison. 1998. Biological Sequence Analysis. Cambridge University Press, Cambridge, UK. find
  7. Gregory Grefenstette. 1994. Explorations in Automatic Thesaurus Discovery, volume 278. Kluwer. find
  8. L. Iordanskaja, R. Kittredge, and A. Polguere. 1991. Lexical selection and paraphrase in a meaning-text generation model. In C. Paris, W. Swartout, and W. Mann, editors, Natural Language Generation in Artificial Intelligence and Computational Linguistics, chapter 11. Kluwer. find
  9. Christian Jacquemin. 1999. Syntagmatic and paradigmatic representations of term variations. In Proc. of the ACL, pages 341–349. find
  10. Kevin Knight and Daniel Marcu. 2000. Statistics-based summarization — Step one: Sentence compression. In Proc. of AAAI. find
  11. J. Richard Landis and Gary G. Koch. 1977. The measurement of observer agreement for categorical data. Biometrics, 33:159–174. find
  12. Dekang Lin and Patrick Pantel. 2001. Discovery of inference rules for question-answering. Natural Language Engineering, 7(4):343–360. find
  13. Dekang Lin. 1998. Automatic retrieval and clustering of similar words. In Proc. of ACL/COLING, pages 768–774. find
  14. Lidia Mangu, Eric Brill, and Andreas Stolcke. 2000. Finding consensus in speech recognition: Word error minimization and other applications of confusion networks. Computer, Speech and Language, 14(4):373–400. find
  15. Kathleen R. McKeown, Karen Kukich, and James Shaw. 1994. Practical issues in automatic documentation generation. In Proc. of ANLP, pages 7–14. find
  16. Kathleen R. McKeown. 1979. Paraphrasing using given and new information in a question-answer system. In Proc. of the ACL, pages 67–72. find
  17. Marie Meteer and Varda Shaked. 1988. Strategies for effective paraphrasing. In Proc. of COLING, pages 431–436. find
  18. Franz Josef Och, Christoph Tillman, and Hermann Ney. 1999. Improved alignment models for statistical machine translation. In Proc. of EMNLP, pages 20–28. find
  19. Bo Pang, Kevin Knight, and Daniel Marcu. 2003. Syntax-based alignment of multiple translations: Extracting paraphrases and generating new sentences. In Proceedings of HLT/NAACL. find our card
  20. Kishore A. Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: A method for automatic evaluation of machine translation. In Proc. of the ACL, pages 311–318. find our card
  21. Fernando Pereira, Naftali Tishby, and Lillian Lee. 1993. Distributional clustering of English words. In Proc. of the ACL, pages 183–190. find
  22. Jacques Robin. 1994. Revision-Based Generation of Natural Language Summaries Providing Historical Background: Corpus-Based Analysis, Design, Implementation, and Evaluation. Ph.D. thesis, Columbia University. find
  23. Yusuke Shinyama, Satoshi Sekine, Kiyoshi Sudo, and Ralph Grishman. 2002. Automatic paraphrase acquisition from news articles. In Proc. of HLT, pages 40–46. find
  24. Frank Smadja and Kathleen McKeown. 1991. Using collocations for language generation. Computational Intelligence, 7(4). Special issue on natural language generation. find
  25. Stephan Vogel and Hermann Ney. 2000. Construction of a hierarchical translation memory. In Proc. of COLING, pages 1131–1135. find
  26. Ye-Yi Wang. 1998. Grammar Inference and Statistical Machine Translation. Ph.D. thesis, CMU. find