Learning entailment rules is fundamental in many semantic-inference applications and has been an active field of research in recent years . In this paper we address the problem of learning transitive graphs that describe entailment rules between predicates ( termed entailment graphs ) . We first identify that entailment graphs exhibit a " tree-like " property and are very similar to a novel type of graph termed forest-reducible graph . We utilize this property to develop an iterative efficient approximation algorithm for learning the graph edges , where each iteration takes linear time . We compare our approximation algorithm to a recently-proposed state-of-the-art exact algorithm and show that it is more efficient and scalable both theoretically and empirically , while its output quality is close to that given by the optimal solution of the exact algorithm . Performing textual inference is in the heart of many semantic inference applications such as Question Answering ( QA ) and Information Extraction ( IE ) . A prominent generic paradigm for textual inference is Textual Entailment ( TUE ) ( Dagan et al . , 2009 ) . In TUE , the goal is to recognize , given two text fragments termed text and hypothesis , whether the hypothesis can be inferred from the text . For example , the text " Cyprus was invaded by the Ottoman Empire in 1571 " implies the hypothesis " The Ottomans attacked Cyprus " . Semantic inference applications such as QA and IE crucially rely on entailment rules ( Ravichandran and Hovy , 2002 ; Shinyama and Sekine , 2006 ) or equivalently inference rules , that is , rules that describe a directional inference relation between two fragments of text . An important type of entailment rule specifies the entailment relation between natural language predicates , e.g. , the entailment rule ' X invade Y → X attack Y ' can be helpful in inferring the aforementioned hypothesis . Consequently , substantial effort has been made to learn such rules ( Lin and Pantel , 2001 ; Sekine , 2005 ; Szpektor and Dagan , 2008 ; Schoenmackers et al . , 2010 ) . Textual entailment is inherently a transitive relation , that is , the rules ' x → y ' and ' y → z ' imply the rule ' x → z ' . Accordingly , Berant et al . ( 2010 ) formulated the problem of learning entailment rules as a graph optimization problem , where nodes are predicates and edges represent entailment rules that respect transitivity . Since finding the optimal set of edges respecting transitivity is NP-hard , they employed Integer Linear Programming ( ILP ) to find the exact solution . Indeed , they showed that applying global transitivity constraints improves rule learning comparing to methods that ignore graph structure . More recently , Berant et al . ( Berant et al . , 2011 ) introduced a more efficient exact algorithm , which decomposes the graph into connected components and then applies an ILP solver over each component . Despite this progress , finding the exact solution remains NP-hard -the authors themselves report they were unable to solve some graphs of rather moderate size and that the coverage of their method is limited . Thus , scaling their algorithm to data sets with tens of thousands of predicates ( e.g. , the extractions of Fader et al . ( 2011 ) ) is unlikely . In this paper we present a novel method for learning the edges of entailment graphs . Our method computes much more efficiently an approximate solution that is empirically almost as good as the exact solution . To that end , we first ( Section 3 ) conjecture and empirically show that entailment graphs exhibit a " tree-like " property , i.e. , that they can be reduced into a structure similar to a directed forest . Then , we present in Section 4 our iterative approximation algorithm , where in each iteration a node is removed and re-attached back to the graph in a locally-optimal way . Combining this scheme with our conjecture about the graph structure enables a linear algorithm for node re-attachment . Section 5 shows empirically that this algorithm is by orders of magnitude faster than the state-of-the-art exact algorithm , and that though an optimal solution is not guaranteed , the area under the precision-recall curve drops by merely a point . To conclude , the contribution of this paper is twofold : First , we define a novel modeling assumption about the tree-like structure of entailment graphs and demonstrate its validity . Second , we exploit this assumption to develop a polynomial approximation algorithm for learning entailment graphs that can scale to much larger graphs than in the past . Finally , we note that learning entailment graphs bears strong similarities to related tasks such as Taxonomy Induction ( Snow et al . , 2006 ) and Ontology induction ( Poon and Domingos , 2010 ) , and thus our approach may improve scalability in these fields as well . Learning large and accurate resources of entailment rules is essential in many semantic inference applications . Employing transitivity has been shown to improve rule learning , but raises issues of efficiency and scalability . The first contribution of this paper is a novel modeling assumption that entailment graphs are very similar to FRGs , which is analyzed and validated empirically . The main contribution of the paper is an efficient polynomial approximation algorithm for learning entailment rules , which is based on this assumption . We demonstrate empirically that our method is by orders of magnitude faster than the state-of-the-art exact algorithm , but still produces an output that is almost as good as the optimal solution . We suggest our method as an important step towards scalable acquisition of precise entailment resources . In future work , we aim to evaluate TNF on large graphs that are automatically generated from huge corpora . This of course requires substantial efforts of pre-processing and test-set annotation . We also plan to examine the benefit of TNF in learning similar structures , e.g. , taxonomies or ontologies .
Current inefficient algorithms aim to obtain entailment rules for semantic inference hindering the use of large resources.
They propose an efficient polynomial approximation algorithm that exploits their observation, entailment graphs have a "tree-like" property.
Their iterative algorithm runs by orders of magnitude faster than current exact state-of-the-art solutions while keeping close quality.