Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions

What it is about

The paper models a pair of sentences as a sequence of tree edits between their dependency trees. Edits are insert, delete and relabel operations plus three that handle reordering: move a subtree, make a new root, and move a sibling. The sequence is found by greedy best-first search, using a normalised partial tree kernel as the heuristic, and capped at 200 iterations (400 for RTE). A logistic regression over 33 integer features, mostly counts of edit types and of the nodes they touch, classifies the pair. The model reaches 62.8% accuracy on RTE-3, against 64.3% for the best cited hybrid system, 73.2% on the paraphrase corpus, and a MAP of 0.6091 on TREC answer selection, the best reported for that task at the time. Each pair takes about five seconds.

Ideas

• I1. A move-subtree operation in the tree-diff code of tools/roundtrip: the paper's example "lives near Rossville Blvd" needs three edits without a move and one with it. Count the edits per pair before and after, on the school lessons.
• I2. Use the 33 count features as an explainable classifier: each weight belongs to an edit type a teacher can read, such as "a subject was removed". Fit the weights on a training split, then print the top contributions for every decision.
• I3. Check that the search is deterministic by fixing the enumeration order in a BTreeMap. The paper reports that the order had no effect on the transformations; Mova should confirm this by running twice on the same pairs.
• I4. Negative control: shuffle the words of the hypothesis. Edit counts should rise and the classifier should drop, otherwise the features are not measuring the pair.

For Mova

The relevant chapters are 21. The simple clause and 36. Discourse relations and coherence. The code is tools/roundtrip (tree-to-tree comparison) and prag/src/infer.rs. The measures are the edit count per pair, the classifier accuracy on a held-out split, and the negative control.

Cite

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

@inproceedings{heilman2010tree,
  title = {{Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions}},
  author = {Heilman, Michael and Smith, Noah A.},
  booktitle = {Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/N10-1145/}
}

References

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

1. M. Bernard, L. Boyer, A. Habrard, and M. Sebban. 2008. Learning probabilistic models of tree edit distance. Pattern Recognition. find
2. D. M. Bikel, R. Schwartz, and R. M. Weischedel. 1999. An algorithm that learns what’s in a name. Machine Learning, 34. find
3. P. Bille. 2005. A survey on tree edit distance and related problems. Theoretical Computer Science, 337. find
4. S. Chawathe and H. Garcia-Molina. 1997. Meaningful change detection in structured data. In Proc. of ACM SIGMOD. find
5. M. Collins and N. Duffy. 2001. Convolution kernels for natural language. In Proc. of NIPS. find
6. H. Cui, R. Sun, K. Li, M. Kan, , and T. Chua. 2005. Question answering passage retrieval using dependency relations. In Proc. of ACM-SIGIR. find
7. A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. of ACL. find
8. D. Das and N. A. Smith. 2009. Paraphrase identification as probabilistic quasi-synchronous recognition. In Proc. of ACL-IJCNLP. find
9. M. de Marneffe, B. MacCartney, T. Grenager, D. Cer, A. Rafferty, and C. D. Manning. 2006. Learning to distinguish valid textual entailments. In Proc. of the Second PASCAL Challenges Workshop. find
10. B. Dolan, C. Quirk, and C. Brockett. 2004. Unsupervised construction of large paraphrase corpora: Exploiting massively parallel news sources. In Proc. of COLING. find
11. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of COL-ING. find our card
12. D. Giampiccolo, B. Magnini, I. Dagan, and B. Dolan, editors. 2007. The third pascal recognizing textual entailment challenge. find
13. D. Gildea. 2003. Loosely tree-based alignment for machine translation. In Proc. of ACL. find
14. S. Harmeling. 2007. An extensible probabilistic transformation-based approach to the third Recognizing Textual Entailment challenge. In Proc. of ACL-PASCAL Workshop on Textual Entailment and Paraphrasing. find
15. T. Hastie, R. Tibshirani, and J. Friedman. 2001. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer. find
16. D. Haussler. 1999. Convolution kernels on discrete structures. Technical Report ucs-crl-99-10, University of California Santa Cruz. find
17. G. E. Hinton. 1999. Product of experts. In Proc. of ICANN. find
18. P. N. Klein. 1989. Computing the edit-distance between unrooted ordered trees. In Proc. of European Symposium on Algorithms. find
19. M. Kouylekov and B. Magnini. 2005. Recognizing textual entailment with tree edit distance algorithms. In Proc. of the PASCAL RTE Challenge. find
20. S. le Cessie and J. C. van Houwelingen. 1997. Ridge estimators in logistic regression. Applied Statistics, 41. find
21. B. MacCartney and C. D. Manning. 2008. Modeling semantic containment and exclusion in natural language inference. In Proc. of COLING. find
22. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP. find our card
23. G. A. Miller, R. Beckwith, C. Fellbaum, D. Gross, and K. J. Miller. 1990. WordNet: An on-line lexical database. International Journal of Lexicography, 3(4). find
24. A. Moschitti. 2006. Efficient convolution kernels for dependency and constituent syntactic trees. In Proc. of ECML. find
25. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proc. of ACL. find our card
26. J. Pearl. 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. find
27. V. Punyakanok, D. Roth, and W. Yih. 2004. Mapping dependencies trees: An application to question answering. In Proc. of the 8th International Symposium on Artificial Intelligence and Mathematics. find
28. A. Ratnaparkhi. 1996. A maximum entropy part-of-speech tagger. In Proc. of EMNLP. find
29. F. Schilder and B. T. McInnes. 2006. TLR at DUC 2006: approximate tree similarity and a new evaluation regime. In Proc. of DUC. find
30. B. Schölkopf and A. J. Smola. 2001. Learning with Kernels. MIT Press. find
31. D. A. Smith and J. Eisner. 2006. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Proc. of HLT-NAACL Workshop on Statistical Machine Translation. find our card
32. V. N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer. find
33. E. M. Voorhees. 2004. Overview of TREC 2004. In Proc. of TREC. find
34. S. Wan, M. Dras, R. Dale, and C. Paris. 2006. Using dependency-based features to take the “para-farce” out of paraphrase. In Proc. of the Australasian Language Technology Workshop. find
35. M. Wang, N. A. Smith, and T. Mitamura. 2007. What is the Jeopardy model? A quasi-synchronous grammar for QA. In Proc. of EMNLP-CoNLL. find
36. F. M. Zanzotto and A. Moschitti. 2006. Automatic learning of textual entailments with cross-pair similarities. In Proc. of COLING/ACL. find
37. D. Zelenko, C. Aone, and A. Richardella. 2003. Kernel methods for relation extraction. J. of Machine Learning Research, 3. find
38. K. Zhang and D. Shasha. 1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing, 18. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/heilman-2010-tree-edit-models-recognizing-textual/