---
title: "Paraphrase Identification as Probabilistic — Das 2009"
description: "The paper addresses paraphrase identification: deciding whether two sentences mean essentially the same thing."
authors: ["Dipanjan Das", "Noah A. Smith"]
year: 2009
venue: "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"
source: "https://aclanthology.org/P09-1053/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/das-2009-paraphrase-identification-as-probabilistic-quasi/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/das-2009-paraphrase-identification-as-probabilistic-quasi/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2009](https://md.research.elamur.ai/free/papers/2009/) / Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition

# Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition

**Authors:** [Dipanjan Das](https://md.research.elamur.ai/free/authors/dipanjan-das/), [Noah A. Smith](https://md.research.elamur.ai/free/authors/noah-a-smith/) · **Year:** 2009 · **Venue:** 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 · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P09-1053/) · [PDF](https://aclanthology.org/P09-1053.pdf) · [OpenAlex](https://openalex.org/W2099884836)

**Citations:** 207 citations (openalex-snapshot · 2026-10-14) · [69](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## 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

- **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.
- **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.
- **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.
- **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.
- **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](https://md.research.elamur.ai/free/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/shelves/nlp/)

Topics: [Dependency parsing](https://md.research.elamur.ai/free/topics/dependency-parsing/)

## Cited by

Cited by

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

- [Feature-Rich Translation by Quasi-Synchronous Lattice Parsing](https://md.research.elamur.ai/free/papers/gimpel-2009-feature-rich-translation-quasi-synchronous/)
- [Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions](https://md.research.elamur.ai/free/papers/heilman-2010-tree-edit-models-recognizing-textual/)
- [An Analysis of Natural Language Inference Benchmarks through the Lens of Negation](https://md.research.elamur.ai/free/papers/hossain-2020-analysis-natural-language-inference-benchmarks/)
- [A Continuously Growing Dataset of Sentential Paraphrases](https://md.research.elamur.ai/free/papers/lan-2017-continuously-growing-dataset-sentential-paraphrases/)
- [Generating Phrasal and Sentential Paraphrases: A Survey of Data-Driven Methods](https://md.research.elamur.ai/free/papers/madnani-2010-generating-phrasal-sentential-paraphrases-survey/)
- [Re-examining Machine Translation Metrics for Paraphrase Identification](https://md.research.elamur.ai/free/papers/madnani-2012-re-examining-machine-translation-metrics/)
- [Learning to Simplify Sentences with Quasi-Synchronous Grammar and Integer Programming](https://md.research.elamur.ai/free/papers/woodsend-2011-learning-simplify-sentences-quasi-synchronous/)
- [Paraphrasing for Style](https://md.research.elamur.ai/free/papers/xu-2012-paraphrasing-style/)
- [SemEval-2015 Task 1: Paraphrase and Semantic Similarity in Twitter (PIT)](https://md.research.elamur.ai/free/papers/xu-2015-semeval-2015-task-1-paraphrase/)

## Cite

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

```bibtex
@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}
}
```

- [← previous Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints](https://md.research.elamur.ai/free/papers/klenner-2009-optimization-coreference-resolution-is-not/)
- [next → Personalizing PageRank for Word Sense Disambiguation](https://md.research.elamur.ai/free/papers/agirre-2009-personalizing-pagerank-word-sense-disambiguation/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/papers/2009/)

## 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. [↗](https://doi.org/10.48550/arxiv.cs/0304006) [our card](https://md.research.elamur.ai/free/papers/barzilay-2003-learning-paraphrase-unsupervised-approach-multiple/)
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. [↗](https://doi.org/10.1023/a:1007558221122)
3. Chris Callison-Burch, Philipp Koehn, and Miles Osborne. 2006. Improved statistical machine translation using paraphrases. In Proc. of HLT-NAACL. [find](https://scholar.google.com/scholar?q=Chris+Callison%2DBurch%2C+Philipp+Koehn%2C+and+Miles+Osborne%2E+2006%2E+Improved+statistical+machine+translation+using+paraphrases%2E+In+Proc%2E+of+HLT%2DNAACL%2E)
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](https://scholar.google.com/scholar?q=Courtney+Corley+and+Rada+Mihalcea%2E+2005%2E+Measuring+the+semantic+similarity+of+texts%2E+In+Proc%2E+of+ACL+Workshop+on+Empirical+Modeling+of+Semantic+Equivalence+and+Entailment%2E)
5. William B. Dolan and Chris Brockett. 2005. Automatically constructing a corpus of sentential paraphrases. In Proc. of IWP. [find](https://scholar.google.com/scholar?q=William+B%2E+Dolan+and+Chris+Brockett%2E+2005%2E+Automatically+constructing+a+corpus+of+sentential+paraphrases%2E+In+Proc%2E+of+IWP%2E) [our card](https://md.research.elamur.ai/free/papers/dolan-2005-automatically-constructing-corpus-sentential-paraphrases/)
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](https://scholar.google.com/scholar?q=Bill+Dolan%2C+Chris+Quirk%2C+and+Chris+Brockett%2E+2004%2E+Unsupervised+construction+of+large+paraphrase+corpora%3A+exploiting+massively+parallel+news+sources%2E+In+Proc%2E+of+COLING%2E) [our card](https://md.research.elamur.ai/free/papers/dolan-2004-unsupervised-construction-large-paraphrase-corpora/)
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](https://scholar.google.com/scholar?q=Andrew+Finch%2C+Young+Sook+Hwang%2C+and+Eiichiro+Sumita%2E+2005%2E+Using+machine+translation+evaluation+techniques+to+determine+sentence%2Dlevel+semantic+equivalence%2E+In+Proc%2E+of+IWP%2E)
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](https://scholar.google.com/scholar?q=Danilo+Giampiccolo%2C+Bernardo+Magnini%2C+Ido+Dagan%2C+and+Bill+Dolan%2E+2007%2E+The+third+PASCAL+recognizing+textual+entailment+challenge%2E+In+Proc%2E+of+the+ACL%2DPASCAL+Workshop+on+Textual+Entailment+and+Paraphra)
9. David Graff. 2003. English Gigaword. Linguistic Data Consortium. [find](https://scholar.google.com/scholar?q=David+Graff%2E+2003%2E+English+Gigaword%2E+Linguistic+Data+Consortium%2E)
10. Geoffrey E. Hinton. 2002. Training products of experts by minimizing contrastive divergence. Neural Computation, 14:1771–1800. [↗](https://doi.org/10.1162/089976602760128018)
11. Thorsten Joachims. 1999. Making large-scale SVM learning practical. In Advances in Kernel Methods - Support Vector Learning. MIT Press. [↗](https://doi.org/10.17877/de290r-14262)
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. [↗](https://doi.org/10.1007/bf01589116)
13. Erwin Marsi and Emiel Krahmer. 2005. Explorations in sentence fusion. In Proc. of EWNLG. [find](https://scholar.google.com/scholar?q=Erwin+Marsi+and+Emiel+Krahmer%2E+2005%2E+Explorations+in+sentence+fusion%2E+In+Proc%2E+of+EWNLG%2E)
14. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Koby+Crammer%2C+and+Fernando+Pereira%2E+2005%2E+Online+large%2Dmargin+training+of+dependency+parsers%2E+In+Proc%2E+of+ACL%2E) [our card](https://md.research.elamur.ai/free/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)
15. Kathleen R. McKeown. 1979. Paraphrasing using given and new information in a question-answer system. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=Kathleen+R%2E+McKeown%2E+1979%2E+Paraphrasing+using+given+and+new+information+in+a+question%2Danswer+system%2E+In+Proc%2E+of+ACL%2E)
16. I. Dan Melamed. 2004. Statistical machine translation by parsing. In Proc. of ACL. [find](https://scholar.google.com/scholar?q=I%2E+Dan+Melamed%2E+2004%2E+Statistical+machine+translation+by+parsing%2E+In+Proc%2E+of+ACL%2E)
17. George A. Miller. 1995. Wordnet: a lexical database for English. Commun. ACM, 38(11):39–41. [↗](https://doi.org/10.1145/219717.219748) [our card](https://md.research.elamur.ai/free/papers/lex-1994-miller-wordnet/)
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](https://scholar.google.com/scholar?q=Kishore+Papineni%2C+Salim+Roukos%2C+Todd+Ward%2C+and+Wei%2DJing+Zhu%2E+2001%2E+BLEU%3A+a+method+for+automatic+evaluation+of+machine+translation%2E+In+Proc%2E+of+ACL%2E) [our card](https://md.research.elamur.ai/free/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
19. Long Qiu, Min-Yen Kan, and Tat-Seng Chua. 2006. Paraphrase recognition via dissimilarity significance classification. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=Long+Qiu%2C+Min%2DYen+Kan%2C+and+Tat%2DSeng+Chua%2E+2006%2E+Paraphrase+recognition+via+dissimilarity+significance+classification%2E+In+Proc%2E+of+EMNLP%2E)
20. Chris Quirk, Chris Brockett, and William B. Dolan. 2004. Monolingual machine translation for paraphrase generation. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=Chris+Quirk%2C+Chris+Brockett%2C+and+William+B%2E+Dolan%2E+2004%2E+Monolingual+machine+translation+for+paraphrase+generation%2E+In+Proc%2E+of+EMNLP%2E) [our card](https://md.research.elamur.ai/free/papers/quirk-2004-monolingual-machine-translation-paraphrase-generation/)
21. Adwait Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. of EMNLP. [find](https://scholar.google.com/scholar?q=Adwait+Ratnaparkhi%2E+1996%2E+A+maximum+entropy+model+for+part%2Dof%2Dspeech+tagging%2E+In+Proc%2E+of+EMNLP%2E)
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](https://scholar.google.com/scholar?q=David+A%2E+Smith+and+Jason+Eisner%2E+2006%2E+Quasi%2Dsynchronous+grammars%3A+Alignment+by+soft+projection+of+syntactic+dependencies%2E+In+Proc%2E+of+the+HLT%2DNAACL+Workshop+on+Statistical+Machine+Translation%2E) [our card](https://md.research.elamur.ai/free/papers/smith-2006-quasi-synchronous-grammars-alignment-soft/)
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](https://scholar.google.com/scholar?q=Joseph+P%2E+Turian%2C+Luke+Shen%2C+and+I%2E+Dan+Melamed%2E+2003%2E+Evaluation+of+machine+translation+and+its+evaluation%2E+In+Proc%2E+of+Machine+Translation+Summit+IX%2E) [our card](https://md.research.elamur.ai/free/papers/turian-2003-evaluation-machine-translation-its-evaluation/)
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](https://scholar.google.com/scholar?q=Stephen+Wan%2C+Mark+Dras%2C+Robert+Dale%2C+and+Ce%CC%81cile+Paris%2E+2006%2E+Using+dependency%2Dbased+features+to+take+the+%E2%80%9Cpara%2Dfarce%E2%80%9D+out+of+paraphrase%2E+In+Proc%2E+of+ALTW%2E)
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](https://scholar.google.com/scholar?q=Mengqiu+Wang%2C+Noah+A%2E+Smith%2C+and+Teruko+Mitamura%2E+2007%2E+What+is+the+Jeopardy+model%3F+a+quasi%2Dsynchronous+grammar+for+QA%2E+In+Proc%2E+of+EMNLP%2DCoNLL%2E) [our card](https://md.research.elamur.ai/free/papers/wang-2007-what-is-jeopardy-model-quasi/)
26. Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Comput. Linguist., 23(3). [find](https://scholar.google.com/scholar?q=Dekai+Wu%2E+1997%2E+Stochastic+inversion+transduction+grammars+and+bilingual+parsing+of+parallel+corpora%2E+Comput%2E+Linguist%2E%2C+23%283%29%2E) [our card](https://md.research.elamur.ai/free/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/)
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](https://scholar.google.com/scholar?q=Dekai+Wu%2E+2005%2E+Recognizing+paraphrases+and+textual+entailment+using+inversion+transduction+grammars%2E+In+Proc%2E+of+the+ACL+Workshop+on+Empirical+Modeling+of+Semantic+Equivalence+and+Entailment%2E)
28. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT. [find](https://scholar.google.com/scholar?q=Hiroyasu+Yamada+and+Yuji+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proc%2E+of+IWPT%2E) [our card](https://md.research.elamur.ai/free/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)
29. Yitao Zhang and Jon Patrick. 2005. Paraphrase identification by text canonicalization. In Proc. of ALTW. [find](https://scholar.google.com/scholar?q=Yitao+Zhang+and+Jon+Patrick%2E+2005%2E+Paraphrase+identification+by+text+canonicalization%2E+In+Proc%2E+of+ALTW%2E)