Elamur Research⌕
☰
home / papers / 2009 / Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition

Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition

Summary

The paper addresses paraphrase identification: deciding whether two sentences mean essentially the same thing. Most strong systems of the time relied on surface overlap features and ignored how parts of the sentences correspond. Das and Smith instead build a generative model. One sentence is produced by a base grammar, and the other is generated from it by a class-specific quasi-synchronous dependency grammar (QG), one for paraphrases and one for non-paraphrases. Word alignments between the two dependency trees are treated as hidden variables and summed out with dynamic programming. A WordNet-based lexical semantics component models how words change between the sentences. Although the model is generative, its parameters are trained discriminatively by maximizing conditional likelihood. On the Microsoft Research Paraphrase Corpus (MSRPC), the syntactic model alone comes close to a strong SVM overlap baseline (Wan et al., 2006). Combining it with a logistic regression overlap model through a product of experts reaches 76.06% accuracy, the best in the paper's comparison. This suggests that loose syntactic alignment and string similarity capture complementary evidence.

Key points

  • Data and features. Experiments use the MSRPC. Parses come from the McDonald et al. (2005) dependency parser, trained on WSJ Penn Treebank sections 2–21 converted following Yamada and Matsumoto (2003). POS tags come from MXPOST and named entity tags from BBN's Identifinder. Lexical relations come from WordNet.
  • Alignment configurations. Child generation is conditioned on how aligned source words relate in the source tree. The configuration types are:
    • parent-child and child-parent;
    • grandparent-grandchild and siblings;
    • same-node and c-command;
    • root, child-null and parent-null;
    • a catch-all "other" type.
  • Efficiency. Summing over latent alignments takes O(m²n) time and O(mn) space.
  • Overlap model. The logistic regression model uses 18 features: n-gram precision, recall and F for n = 1–3, in plain and lemmatized forms.
  • Results.
    • The product of experts reaches 76.06% accuracy, which is significantly better than the QG alone (p < 0.04) but not significantly better than the SVM.
    • Its positive-class precision is 79.6%, compared with 76.1% for Wu's (2005) ITG approach.
    • Oracle pairings that include the QG reach about 83%, matching human agreement on MSRPC.

Interesting ideas

  • I1. A grammar for the negative class. The authors train a separate grammar for "not paraphrase" because the corpus negatives were chosen to share many words. Modeling a hard negative class explicitly, instead of treating it as "everything else," could help any pair-classification task built with adversarially similar negatives.
  • I2. Soft, summed-out alignment. The model sums over all alignments rather than committing to one best alignment, and it allows non-isomorphic tree correspondences. This makes it robust to parser errors and to structural divergence, which is useful for entailment, QA answer selection, or cross-lingual sentence matching.
  • I3. Order-agnostic pair scoring. Each pair is scored by averaging both generation directions (s1→s2 and s2→s1), so a directional generative model becomes a symmetric classifier.
  • I4. Product of experts for combining models. Multiplying and renormalizing posteriors lets each model veto a class. This is a simple, principled way to merge a structured model with a surface-feature model when putting the features into one model would make inference intractable.
  • I5. Oracle ensembles as a complementarity check. An oracle that is correct when either system is correct shows whether two models make different errors. Here, LR and SVM overlapped heavily, while QG-based pairs did not, so the oracle indicates which combinations are worth pursuing.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Machine translation · Natural language processing

Topics: Dependency parsing

Cited by

69 papers of our library cite it (of the 140673 whose bibliographies we read); 10 of them have a page here, 59 not yet.

Cite

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

@inproceedings{das2009paraphrase,
  title = {{Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition}},
  author = {Das, Dipanjan and Smith, Noah A.},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  doi = {10.3115/1687878.1687944},
  url = {https://doi.org/10.3115/1687878.1687944}
}

References

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

  1. Regina Barzilay and Lillian Lee. 2003. Learning to paraphrase: an unsupervised approach using multiple-sequence alignment. In Proc. of NAACL. ↗ our card
  2. Daniel M. Bikel, Richard L. Schwartz, and Ralph M. Weischedel. 1999. An algorithm that learns what’s in a name. Machine Learning, 34(1-3):211–231. ↗
  3. Chris Callison-Burch, Philipp Koehn, and Miles Osborne. 2006. Improved statistical machine translation using paraphrases. In Proc. of HLT-NAACL. find
  4. Courtney Corley and Rada Mihalcea. 2005. Measuring the semantic similarity of texts. In Proc. of ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment. find
  5. William B. Dolan and Chris Brockett. 2005. Automatically constructing a corpus of sentential paraphrases. In Proc. of IWP. find our card
  6. Bill Dolan, Chris Quirk, and Chris Brockett. 2004. Unsupervised construction of large paraphrase corpora: exploiting massively parallel news sources. In Proc. of COLING. find our card
  7. Andrew Finch, Young Sook Hwang, and Eiichiro Sumita. 2005. Using machine translation evaluation techniques to determine sentence-level semantic equivalence. In Proc. of IWP. find
  8. Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and Bill Dolan. 2007. The third PASCAL recognizing textual entailment challenge. In Proc. of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing. find
  9. David Graff. 2003. English Gigaword. Linguistic Data Consortium. find
  10. Geoffrey E. Hinton. 2002. Training products of experts by minimizing contrastive divergence. Neural Computation, 14:1771–1800. ↗
  11. Thorsten Joachims. 1999. Making large-scale SVM learning practical. In Advances in Kernel Methods - Support Vector Learning. MIT Press. ↗
  12. Dong C. Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Math. Programming (Ser. B), 45(3):503–528. ↗
  13. Erwin Marsi and Emiel Krahmer. 2005. Explorations in sentence fusion. In Proc. of EWNLG. find
  14. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proc. of ACL. find our card
  15. Kathleen R. McKeown. 1979. Paraphrasing using given and new information in a question-answer system. In Proc. of ACL. find
  16. I. Dan Melamed. 2004. Statistical machine translation by parsing. In Proc. of ACL. find
  17. George A. Miller. 1995. Wordnet: a lexical database for English. Commun. ACM, 38(11):39–41. ↗ our card
  18. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2001. BLEU: a method for automatic evaluation of machine translation. In Proc. of ACL. find our card
  19. Long Qiu, Min-Yen Kan, and Tat-Seng Chua. 2006. Paraphrase recognition via dissimilarity significance classification. In Proc. of EMNLP. find
  20. Chris Quirk, Chris Brockett, and William B. Dolan. 2004. Monolingual machine translation for paraphrase generation. In Proc. of EMNLP. find our card
  21. Adwait Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. of EMNLP. find
  22. David A. Smith and Jason Eisner. 2006. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Proc. of the HLT-NAACL Workshop on Statistical Machine Translation. find our card
  23. Joseph P. Turian, Luke Shen, and I. Dan Melamed. 2003. Evaluation of machine translation and its evaluation. In Proc. of Machine Translation Summit IX. find our card
  24. Stephen Wan, Mark Dras, Robert Dale, and Cécile Paris. 2006. Using dependency-based features to take the “para-farce” out of paraphrase. In Proc. of ALTW. find
  25. Mengqiu Wang, Noah A. Smith, and Teruko Mitamura. 2007. What is the Jeopardy model? a quasi-synchronous grammar for QA. In Proc. of EMNLP-CoNLL. find our card
  26. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Comput. Linguist., 23(3). find our card
  27. Dekai Wu. 2005. Recognizing paraphrases and textual entailment using inversion transduction grammars. In Proc. of the ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment. find
  28. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT. find our card
  29. Yitao Zhang and Jon Patrick. 2005. Paraphrase identification by text canonicalization. In Proc. of ALTW. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/das-2009-paraphrase-identification-as-probabilistic-quasi/