A Compact Forest for Scalable Inference over Entailment and Paraphrase Rules

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1056–1065, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP A Compact Forest for Scalable Inference over Entailment and Paraphrase Rules Roy Bar-Haim§, Jonathan Berant⋆, Ido Dagan§ §Computer Science Department, Bar-Ilan University, Ramat Gan 52900, Israel {barhair,dagan}@cs.biu.ac.il ⋆The Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel jonatha6@post.tau.ac.il Abstract A large body of recent research has been investigating the acquisition and applica- tion of applied inference knowledge. Such knowledge may be typically captured as entailment rules, applied over syntactic representations. Efficient inference with such knowledge then becomes a funda- mental problem. Starting out from a for- malism for entailment-rule application we present a novel packed data-structure and a corresponding algorithm for its scalable implementation. We proved the validity of the new algorithm and established its effi- ciency analytically and empirically. 1 Introduction Applied semantic inference is concerned with de- riving target meanings from texts. In the textual entailment framework, this is reduced to infer- ring a textual statement (the hypothesis h) from a source text (t). Traditional formal semantics approaches perform such inferences over logi- cal forms derived from the text. By contrast, most practical NLP applications operate over shal- lower representations such as parse trees, possibly supplemented with limited semantic information about named entities, semantic roles etc. Most commonly, inference over such represen- tations is made by applying some kind of transfor- mations or substitutions to the tree or graph rep- resenting the text. Such transformations may be generally viewed as entailment (inference) rules, which capture semantic knowledge about para- phrases, lexical relations such as synonyms and hyponyms, syntactic variations etc. Such knowl- edge is either composed manually, e.g. WordNet (Fellbaum, 1998), or learned automatically. A large body of work has been dedicated to learning paraphrases and entailment rules, e.g. (Lin and Pantel, 2001; Shinyama et al., 2002; Szpektor et al., 2004; Bhagat and Ravichandran, 2008), identifying appropriate contexts for their application (Pantel et al., 2007) and utilizing them for inference (de Salvo Braz et al., 2005; Bar- Haim et al., 2007). Although current avail- able rule bases are still quite noisy and incom- plete, the progress made in recent years suggests that they may become increasingly valuable for text understanding applications. Overall, applied knowledge-based inference is a prominent line of research gaining much interest, with recent exam- ples including the series of workshops on Knowl- edge and Reasoning for Answering Questions (KRAQ)1 and the planned evaluation of knowledge resources in the forthcoming 5th Recognizing Tex- tual Entailment challenge (RTE-5)2. While many applied systems utilize semantic knowledge via such inference rules, their use is typically limited, application-specific, and quite heuristic. Formalizing these practices seems im- portant for applied semantic inference research, analogously to the role of well-formalized mod- els in parsing and machine translation. Bar-Haim et al. (2007) made a step in this direction by in- troducing a generic formalism for semantic infer- ence over parse trees. Their formalism uses entail- ment rules as a unifying …

Content truncated to 500 words