Global Learning of Focused Entailment Graphs

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1220–1229, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Global Learning of Focused Entailment Graphs Jonathan Berant Tel-Aviv University Tel-Aviv, Israel jonatha6@post.tau.ac.il Ido Dagan Bar-Ilan University Ramat-Gan, Israel dagan@cs.biu.ac.il Jacob Goldberger Bar-Ilan University Ramat-Gan, Israel goldbej@eng.biu.ac.il Abstract We propose a global algorithm for learn- ing entailment relations between predi- cates. We define a graph structure over predicates that represents entailment rela- tions as directed edges, and use a global transitivity constraint on the graph to learn the optimal set of edges, by formulating the optimization problem as an Integer Linear Program. We motivate this graph with an application that provides a hierar- chical summary for a set of propositions that focus on a target concept, and show that our global algorithm improves perfor- mance by more than 10% over baseline al- gorithms. 1 Introduction The Textual Entailment (TE) paradigm (Dagan et al., 2009) is a generic framework for applied se- mantic inference. The objective of TE is to recog- nize whether a target meaning can be inferred from a given text. For example, a Question Answer- ing system has to recognize that ‘alcohol affects blood pressure’ is inferred from ‘alcohol reduces blood pressure’ to answer the question ‘What af- fects blood pressure?’ TE systems require extensive knowledge of en- tailment patterns, often captured as entailment rules: rules that specify a directional inference re- lation between two text fragments (when the rule is bidirectional this is known as paraphrasing). An important type of entailment rule refers to propo- sitional templates, i.e., propositions comprising a predicate and arguments, possibly replaced by variables. The rule required for the previous ex- ample would be ‘X reduce Y → X affect Y’. Be- cause facts and knowledge are mostly expressed by propositions, such entailment rules are central to the TE task. This has led to active research on broad-scale acquisition of entailment rules for predicates, e.g. (Lin and Pantel, 2001; Sekine, 2005; Szpektor and Dagan, 2008). Previous work has focused on learning each en- tailment rule in isolation. However, it is clear that there are interactions between rules. A prominent example is that entailment is a transitive relation, and thus the rules ‘X → Y ’ and ‘Y → Z’ imply the rule ‘X → Z’. In this paper we take advantage of these global interactions to improve entailment rule learning. First, we describe a structure termed an entail- ment graph that models entailment relations be- tween propositional templates (Section 3). Next, we show that we can present propositions accord- ing to an entailment hierarchy derived from the graph, and suggest a novel hierarchical presenta- tion scheme for corpus propositions referring to a target concept. As in this application each graph focuses on a single concept, we term those focused entailment graphs (Section 4). In the core section of the paper, we present an algorithm that uses a global approach to learn the entailment relations of focused entailment graphs (Section …

Content truncated to 500 words