Paper: Efficient Tree-based Approximation for Entailment Graph Learning

ACL ID P12-1013
Title Efficient Tree-based Approximation for Entailment Graph Learning
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2012

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 learn- ing 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 prop- erty to develop an iterative efficient approxi- mation 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 algo- rithm and show that it is more efficient and scalable both theoretically and empirically, while its output quality is...