Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions ltiMichael Heilman and Noah A. Smith1Summary Simple transformational approach for modeling sentence pair relations. Experiments for multiple problems:• Recognizing textual entailment•Paraphrase identificationlti•Paraphrase identification• Answer selection for question answering Competitive but not standout performance.2IntuitionTree edits are syntactic transformations that can modify semantic properties in various ways.obliquesubj.pp-obj.oblique pp-obj.ltiMexicoCanada3We represent sentence pairs as sequences of edits that convert one tree into the other.L.A. belonged toBefore1848 before1848Outline Introduction Connections to Prior Work Finding & Classifying Edit Sequences Experimentslti4Prior Work on Sentence Pairs Numerous approaches for sentence pair relations, some task-specific. Considerable work involving tree and phrase alignments.lti Less work on transformational or tree edit approaches.5Harmeling, 07; Bar Haim et al., 07Das & Smith, 09; MacCartney et al., 08; Zanzotto, 09; Chang et al., NAACL-10; inter aliaPrior Work on Tree Edit Distance1. Local edits without reordering.• insert, relabel, delete2. No learning of associations between labels and features of edit sequences.lti6Chawathe et al., 97; Punyakanok et al., 04; Wan et al., 06; Bernard et al., 08; inter aliaOur Method1. Includes edits for reordering children and moving subtrees.2. Learns associations between edit sequences and features of labeled data.3.Does not require:lti3.Does not require:• WordNet• Distributional Similarity• NER• Heavy task-specific tuning• Coreference resolution• Etc.7Possible future workOutline Introduction Connections to Prior Work Finding & Classifying Edit Sequences Experimentslti8Bush shot back: “You're looking pretty young these days.”DELETE (smile)DELETE (a)DELETE (wry)Feature Value#edits8With a wry smile, Mr. Bush replied, “You're looking pretty young these days.”θlti9DELETE (with)DELETE (smile)DELETE (Mr.)RELABEL (replied, shot)INSERT (back, shot)RELABEL (comma, :)#edits8# unedited nodes 11# DELETE 5# INSERT 1# delete subject 0…PARAPHRASEθTypes of Tree Edits Inserting, Deleting, Relabeling Nodes• INSERT-CHILD• INSERT-PARENT• DELETE-LEAF• DELETE-AND-MERGE• RELABEL-NODESocrates taught to Plato philosophy.Socrates taught philosophy to Plato.MOVE-SIBLINGlti• RELABEL-EDGE  Reordering Children• MOVE-SIBLING Moving Subtrees• MOVE-SUBTREE• NEW-ROOT10MOVE-SUBTREEI saw the man with the telescopeI saw the man with the telescopeComplexity Tree edit distance with insert, relabel, delete edits:O(n3logn)Klein, 98lti With reordering and moving subtrees:Polynominal runtime algorithms not available11Greedy Best-First Search We choose the next tree according to the heuristic function only.• We ignore path cost.Target TreePearl, 8412Initial Tree(e.g., premise)Target Tree(e.g., hypothesis)Tree Kernel Search Heuristic Heuristic compares current tree to target tree ( ). Tree kernel: similarity measure between trees based on similarities of all their subtrees.• Efficient dynamic programming solution.13D. Haussler, 99;Collins & Duffy, 01; Zanzotto & Moschitti, 06;Zelenko et al., 06Tree Kernel Search Heuristic In general, larger trees will have larger kernel values. So we “normalize” to [0, 1]:),(1)(XXKXH−=14),(),(),(1)(XXKXXKXXKXH×−=heuristicfunctiontree kernelfunctionFinding Edit Sequences Operations are very expressive.• Search rarely fails (< 0.5%). Resulting sequences:•Succinct and plausible upon inspectionlti•Succinct and plausible upon inspection• Internally consistent representation• Lead to good performance15Example Edit SequencePremiselti16HypothesisExample Edit SequenceRELABEL-NODE(nearby)MOVE-SUBTREE(Blvd.)lti17MOVE-SUBTREE(Pierce)Multiple RELABEL-EDGE, DELETE-LEAF, DELETE-AND-MERGE editsClassifying by Edit Sequences Logistic Regression with 33 features.• total number of edits• number of X edits• number of edits removing a subject• number of unedited nodesetc.lti•etc. We learn separate parameters for each task from labeled sentence pairs.18Outline Introduction Connections to Prior Work Finding & Classifying Edit Sequences Experimentslti19Recognizing Textual EntailmentChallenge: Decide whether a hypothesis follows from a premise. Testing: RTE-3 test data.Training: RTE-3 dev. data and data from Giampiccolo et al., 07ltiTraining: RTE-3 dev. data and data from previous RTE tasks.206065707580Accuracy (%)RTE-3 Resultsde Marneffe et al. 06Syntactic alignment + classificationTree edit modelMacCartney & Manning 08: Hybrid21505508: Hybridde Marneffe et al. 06+ Natural Logic techniqueParaphrase Identification Paraphrase ≈ bidirectional entailment.Microsoft ResearchParaphrase CorpusChallenge: Decide whether 2 sentences are paraphrases of each other.ltiMicrosoft ResearchParaphrase Corpus Standard training and testing splits22Dolan et al., 046065707580Accuracy (%)Paraphrase Identification ResultsTree edit modelWan et al. 06SVM with syntactic dependency overlap, BLEU scores, tree edit distance, etc.235055Accuracy (%)distance, etc.Das & Smith 09Quasi-synchronous Grammar to model syntactic alignments + n-gram overlapAnswer Selection for QAChallenge: rank sentences by correctness as answers to a given question. We find edit sequences from answers to questions.24 We rank by the estimated probabilities of correctness.Answer Selection Data Q&A pairs from TREC-8 through TREC-13. Training, Dev., Testing data sets: about 100 questions and 500-1500 answers eachlti25Answer Selection ResultsPunyakanok et al. 04Tree edit distanceWang et al. 07Quasi-synchronous Grammar to model syntactic alignments0.350.450.550.650.75Ranking Quality(Mean Average Precision)26syntactic alignmentsWang et al. 07 + WNplus lexical semantics from WordNetTree edit model0.250.35Ranking Quality(Mean Average Precision)Answer Selection ResultsPunyakanok et al. 04Tree edit distanceWang et al. 07Quasi-synchronous Grammar to model syntactic alignments0.350.450.550.650.75Ranking Quality(Mean Average Precision)27syntactic alignmentsWang et al. 07 + WNplus lexical semantics from WordNetTree edit model0.250.35Ranking Quality(Mean Average Precision)Answer Selection ResultsPunyakanok et al. 04Tree edit distanceWang et al. 07Quasi-synchronous Grammar to model