acl acl2012 acl2012-80 acl2012-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jonathan Berant ; Ido Dagan ; Meni Adler ; Jacob Goldberger
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.
Alfred V. Aho, Michael R. Garey, and Jeffrey D. Ullman. 1972. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2): 13 1–137. Roni Ben Aharon, Idan Szpektor, and Ido Dagan. 2010. Generating entailment rules from framenet. In Proceedings ofthe 48thAnnual Meeting ofthe Association for Computational Linguistics. Jonathan Berant, Ido Dagan, and Jacob Goldberger. 2010. Global learning of focused entailment graphs. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. Jonathan Berant, Ido Dagan, and Jacob Goldberger. 2011. Global learning of typed entailment rules. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics. Coyne Bob and Owen Rambow. 2009. Lexpar: A freely available english paraphrase lexicon automatically extracted from framenet. In Proceedings of IEEE International Conference on Semantic Computing. Timothy Chklovski and Patrick Pantel. 2004. Verb ocean: Mining the web for fine-grained semantic verb relations. In Proceedings of Empirical Methods in Natural Language Processing. Thomas H. Cormen, Charles E. leiserson, Ronald L. Rivest, and Clifford Stein. 2002. Introduction to Algorithms. The MIT Press. Ido Dagan, Bill Dolan, Bernardo Magnini, and Dan Roth. 2009. Recognizing textual entailment: Rational, evaluation and approaches. Natural Language Engineering, 15(4): 1–17. Quang Do and Dan Roth. 2010. Constraints based taxonomic relation classification. In Proceedings of Empirical Methods in Natural Language Processing. Anthony Fader, Stephen Soderland, and Oren Etzioni. 2011. Identifying relations for open information extraction. In Proceedings of Empirical Methods in Natural Language Processing. J. R. Finkel and C. D. Manning. 2008. Enforcing transitivity in coreference resolution. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman. Dekang Lin and Patrick Pantel. 2001. Discovery ofinference rules for question answering. Natural Language Engineering, 7(4):343–360. Xiao Ling and Dan S. Weld. 2010. Temporal information extraction. In Proceedings of the 24th AAAI Conference on Artificial Intelligence. 125 Andre Martins, Noah Smith, and Eric Xing. 2009. Con- cise integer linear programming formulations for dependency parsing. In Proceedings of the 47th Annual Meeting of the Association for Computational Linguistics. Hoifung Poon and Pedro Domingos. 2010. Unsupervised ontology induction from text. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. Deepak Ravichandran and Eduard Hovy. 2002. Learning surface text patterns for a question answering system. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proceedings of Empirical Methods in Natural Language Processing. Stefan Schoenmackers, Jesse Davis, Oren Etzioni, and Daniel S. Weld. 2010. Learning first-order horn clauses from web text. In Proceedings of Empirical Methods in Natural Language Processing. Satoshi Sekine. 2005. Automatic paraphrase discovery based on context and keywords between ne pairs. In Proceedings of IWP. Yusuke Shinyama and Satoshi Sekine. 2006. Preemptive information extraction using unrestricted relation discovery. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference. Rion Snow, Dan Jurafsky, and Andrew Y. Ng. 2006. Semantic taxonomy induction from heterogenous evidence. In Proceedings of the 44th Annual Meeting of the Association for Computational Linguistics. Idan Szpektor and Ido Dagan. 2008. Learning entailment rules for unary templates. In Proceedings of the 22nd International Conference on Computational Linguistics. Idan Szpektor and Ido Dagan. 2009. Augmenting wordnet-based inference with argument mapping. In Proceedings of TextInfer. Idan Szpektor, Hristo Tanev, Ido Dagan, and Bonaventura Coppola. 2004. Scaling web-based acquisition of entailment relations. In Proceedings of Empirical Methods in Natural Language Processing. Alexander Yates and Oren Etzioni. 2009. Unsupervised methods for determining object and relation synonyms on the web. Journal ofArtificial Intelligence Research, 34:255–296.