tailieunhanh - Báo cáo khoa học: "Efficient Tree-based Approximation for Entailment Graph Learning"

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. | Efficient Tree-based Approximation for Entailment Graph Learning Jonathan Berant Ido Dagan Meni Adler Jacob Goldberger The Blavatnik School of Computer Science Tel Aviv University t Department of Computer Science Bar-Ilan University ị Faculty of Engineering Bar-Ilan University jonatha6@ dagan goldbej @ cs eng . adlerm@ Abstract 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. 1 Introduction 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 117 and Hovy 2002 Shinyama and Sekine 2006 or equivalently inference rules that is rules that describe a directional inference relation between two fragments .