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...

Click Here to View the Paper In XML Format