Robust Textual Inference via Graph Matching

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 387–394, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Robust Textual Inference via Graph Matching Aria D. Haghighi Dept. of Computer Science Stanford University Stanford, CA aria42@stanford.edu Andrew Y. Ng Dept. of Computer Science Stanford University Stanford, CA ang@cs.stanford.edu Christopher D. Manning Dept. of Computer Science Stanford University Stanford, CA manning@cs.stanford.edu Abstract We present a system for deciding whether a given sentence can be inferred from text. Each sentence is represented as a directed graph (extracted from a depen- dency parser) in which the nodes repre- sent words or phrases, and the links repre- sent syntactic and semantic relationships. We develop a learned graph matching ap- proach to approximate entailment using the amount of the sentence’s semantic content which is contained in the text. We present results on the Recognizing Textual Entailment dataset (Dagan et al., 2005), and show that our approach outperforms Bag-Of-Words and TF-IDF models. In ad- dition, we explore common sources of er- rors in our approach and how to remedy them. 1 Introduction A fundamental stumbling block for several NLP ap- plications is the lack of robust and accurate seman- tic inference. For instance, question answering sys- tems must be able to recognize, or infer, an answer which may be expressed differently from the query. Information extraction systems must also be able recognize the variability of equivalent linguistic ex- pressions. Document summarization systems must generate succinct sentences which express the same content as the original document. In Machine Trans- lation evaluation, we must be able to recognize legit- imate translations which structurally differ from our reference translation. One sub-task underlying these applications is the ability to recognize semantic entailment; whether one piece of text follows from another. In contrast to recent work which has successfully utilized logic- based abductive approaches to inference (Moldovan et al., 2003; Raina et al., 2005b), we adopt a graph- based representation of sentences, and use graph matching approach to measure the semantic over- lap of text. Graph matching techniques have proven to be a useful approach for tractable approximate matching in other domains including computer vi- sion. In the domain of language, graphs provide a natural way to express the dependencies between words and phrases in a sentence. Furthermore, graph matching also has the advantage of providing a framework for structural matching of phrases that would be difficult to resolve at the level of individual words. 2 Task Definition and Data We describe our approach in the context of the 2005 Recognizing Textual Entailment (RTE) Challenge (Dagan et al., 2005), but note that our approach eas- ily extends to other related inference tasks. The sys- tem presented here was one component of our re- search group’s 2005 RTE submission (Raina et al., 2005a) which was the top-ranking system according to one of the two evaluation metrics. In the 2005 RTE domain, we are given a set of pairs, each consisting of two parts: 1) …

Content truncated to 500 words