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

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 1011–1019, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions Michael Heilman Noah A. Smith Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA {mheilman,nasmith}@cs.cmu.edu Abstract We describe tree edit models for representing sequences of tree transformations involving complex reordering phenomena and demon- strate that they offer a simple, intuitive, and effective method for modeling pairs of seman- tically related sentences. To efficiently extract sequences of edits, we employ a tree kernel as a heuristic in a greedy search routine. We describe a logistic regression model that uses 33 syntactic features of edit sequences to clas- sify the sentence pairs. The approach leads to competitive performance in recognizing tex- tual entailment, paraphrase identification, and answer selection for question answering. 1 Introduction Many NLP tasks involve modeling relations be- tween pairs of sentences or short texts in the same language. Examples include recognizing textual en- tailment, paraphrase identification, and question an- swering. Generic approaches are, of course, desir- able; we believe such approaches are also feasible because these tasks exhibit some similar semantic relationships between sentences. A popular method for such tasks is Tree Edit Dis- tance (TED), which models sentence pairs by find- ing a low or minimal cost sequence of editing oper- ations to transform a tree representation of one sen- tence (e.g., a dependency or phrase structure parse tree) into a tree for the other. Unlike grammar- based models and shallow-feature discriminative ap- proaches, TED provides an intuitive story for tree pairs where one tree is derived from the other by a sequence of simple transformations. The available operations in standard TED are the following: insertion of a node, relabeling (i.e., re- naming) of a node, and deletion (i.e., removal) of a node. While the restriction to these three operations permits efficient dynamic programming solutions for finding a minimum-cost edit sequence (Klein, 1989; Zhang and Shasha, 1989), certain interesting and prevalent phenomena involving reordering and movement cannot be elegantly captured. For exam- ple, consider the following sentence pair, which is a simplified version of a true entailment (i.e., the premise entails the hypothesis) in the development data for the RTE-3 task. Premise: Pierce built the home for his daughter off Rossville Blvd, as he lives nearby. Hypothesis: Pierce lives near Rossville Blvd. In a plausible dependency tree representation of the premise, live and Rossville Blvd would be in sep- arate subtrees under built. In the hypothesis tree, however, the corresponding nodes would be in a grandparent-child relationship as part of the same phrase, lives near Rossville Blvd. In general, one would expect that short transformation sequences to provide good evidence of true entailments. How- ever, to account for the grandparent-child relation- ship in the hypothesis, TED would produce a fairly long sequence, relabeling nearby to be near, delet- ing the two nodes for Rossville Blvd, and then re- …

Content truncated to 500 words