Elamur Research
☰
home / papers / 2010 / Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions

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

For Mova

The relevant chapters are languages/en/21-clause-structure.md and languages/en/36-discourse-relations.md. 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.

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/N10-1145.pdf

Summary

The paper proposes one framework for three sentence-pair tasks: judging whether one sentence entails another, detecting whether two sentences are paraphrases, and picking the correct answer sentences for QA. Classic Tree Edit Distance (TED) allows only insertion, deletion and relabeling, so it handles reordering and movement poorly. A single displaced phrase can cost many edits. Heilman and Smith extend the edit inventory over dependency trees with operations such as MOVE-SUBTREE, NEW-ROOT and MOVE-SIBLING. These new operations rule out exact dynamic programming. Instead, the authors find edit sequences with greedy best-first search, guided by a normalized tree kernel derived from Moschitti's partial tree kernel. A logistic regression classifier then labels each pair using 33 syntactic features of its edit sequence. The approach is evaluated on RTE-3, the paraphrase corpus of Dolan et al. (2004), and the QA answer-selection setup of Wang et al. (2007). It is competitive on all three. On answer selection it gave the best result reported at the time, without any lexical semantic resources. This matters because a syntax-only, task-agnostic representation performs strongly across several semantic tasks.

Key points

  • Edit operations: INSERT-CHILD, INSERT-PARENT, DELETE-LEAF, DELETE-&-MERGE, RELABEL-NODE, RELABEL-EDGE, MOVE-SUBTREE, NEW-ROOT and MOVE-SIBLING.
  • Each tree node holds a lemma, a POS tag and the label of the dependency edge to its parent. Children are stored head-outward in separate left and right lists, following Eisner (1996).
  • The search heuristic is 1 minus the kernel K(Tc,Tt) normalized by the geometric mean of the self-kernels. It reaches 0 exactly when the current tree matches the target.
  • For QA, training data came from TREC-8 through TREC-12 and testing from TREC-13, evaluated with MAP and MRR. Candidates were ranked by posterior probability, and edits were extracted from answer to question only.
  • On QA, the tree edit model beat all baselines (sign test, p < 0.01) except Wang et al. (2007) with WordNet, where the difference was not significant. The comparison systems included Punyakanok et al. (2004) and Cui et al. (2005).

Interesting ideas

  • Kernel as a search heuristic, not a classifier. The normalized tree kernel steers a search toward the target tree rather than feeding an SVM. Any similarity kernel could likewise guide greedy transformation search over structured objects.
  • Normalizing to avoid size bias. Raw tree kernels grow with tree size, so dividing by self-similarity keeps the search from inflating the tree. This trick applies whenever a similarity score is used as a distance-to-goal.
  • Features of the path, not just its length. Instead of a single edit cost, the model counts edit types, such as deletions of proper nouns or changes to subjects, and learns their weights from labeled data. This is an easy way to turn alignment or diff output into an interpretable classifier.
  • Separating representation extraction from classification. The edit sequence is extracted first and classified afterwards. Either stage can then be swapped or enriched, for example by adding lexical semantics to the heuristic or running the search over semantic parses instead of dependency trees.
  • Movement operations for free-word-order data. Moving whole subtrees and reordering siblings yields short, intuitive edit scripts where TED would delete and reinsert. This could suit languages with flexible word order, such as Ukrainian UD treebanks.

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, 5 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 our card
  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