Optimising Tree Edit Distance with Subtrees for Textual Entailment

Proceedings of Recent Advances in Natural Language Processing, pages 9–17, Hissar, Bulgaria, 7-13 September 2013. Optimising Tree Edit Distance with Subtrees for Textual Entailment Maytham Alabbas Department of Computer Science, College of Science, Basrah University, Basrah, Iraq maytham.alabbas@gmail.com Allan Ramsay School of Computer Science, University of Manchester, Manchester, M13 9PL, UK Allan.Ramsa@manchester.ac.uk Abstract This paper introduces a method for im- proving tree edit distance (TED) for tex- tual entailment. We explore two ways of improving TED: we extend the standard TED to use edit operations that apply to subtrees as well as to single nodes; and we use the ‘artificial bee colony’ algorithm (ABC) to estimate the cost of edit oper- ations for single nodes and subtrees and to determine thresholds. The preliminary results of the current work for checking entailment between two texts are encour- aging compared with the common bag-of- words, string edit distance and standard TED algorithms. 1 Introduction One key task for natural language systems is to determine whether one natural language sentence entails another. Entailment can be defined as a re- lationship between two sentences where the truth of one sentence, the entailing expression, forces the truth of another sentence, what is entailed. Many natural language processing (NLP) tasks such as information extraction and question an- swering have to cope with this notion. An alternative formulation for the entailment between two texts is given by the recognising tex- tual entailment (RTE) paradigm, which contrasts with the standard definition of entailment above. Dagan et al. (2005) describe RTE as a task of de- termining, for two sentences text T and hypothe- sis H, whether “. . . typically, a human reading T would infer that H is most likely true.” According to these authors, entailment holds if the truth of H, as interpreted by a typical language user, can be inferred from the meaning of T. This notion of en- tailment is less rigorous, and less clearly defined, than the standard notion, but it can be useful for a number of tasks, and has been investigated very extensively in recent times. Tree edit distance (TED), which models T-H pairs by explicitly transforming T into H via a minimal cost sequence of editing operations, has been widely used for this task. Using TED poses two challenges: the standard three operations (i.e. deletion, insertion and exchange) apply only to single nodes, rather than to subtrees; and estimat- ing a combination of costs for these operations with threshold(s) is hard when dealing with com- plex problems. This is because alterations in these costs or choosing a different combination of them can lead to drastic changes in TED performance (Mehdad and Magnini, 2009). In order to overcome these challenges, we have extended the standard TED to deal with subtree operations as well as operations on single nodes. This allows the algorithm to treat semantically co- herent parts of the tree as single items, thus allow- ing for instance entire modifiers (such as prepo- sitional phrase (PPs)) to be inserted or …

Content truncated to 500 words