acl acl2012 acl2012-78 acl2012-78-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Asher Stern ; Roni Stern ; Ido Dagan ; Ariel Felner
Abstract: This paper addresses the search problem in textual inference, where systems need to infer one piece of text from another. A prominent approach to this task is attempts to transform one text into the other through a sequence of inference-preserving transformations, a.k.a. a proof, while estimating the proof’s validity. This raises a search challenge of finding the best possible proof. We explore this challenge through a comprehensive investigation of prominent search algorithms and propose two novel algorithmic components specifically designed for textual inference: a gradient-style evaluation function, and a locallookahead node expansion method. Evaluations, using the open-source system, BIUTEE, show the contribution of these ideas to search efficiency and proof quality.
Roy Bar-Haim, Ido Dagan, Iddo Greental, and Eyal Shnarch. 2007. Semantic inference at the lexicalsyntactic level. In Proceedings of AAAI. Philip Bille. 2005. A survey on tree edit distance and related problems. Theoretical Computer Science. Adi Botea, Markus Enzenberger, Martin M ¨uller, and Jonathan Schaeffer. 2005. Macro-FF: Improving ai planning with automatically learned macro-operators. J. Artif. Intell. Res. (JAIR), 24:581–621. Vadim Bulitko and Mitja Lustrek. 2006. Lookahead pathology in real-time path-finding. In proceedings of AAAI. Ido Dagan, Oren Glickman, and Bernardo Magnini. 2005. The pascal recognising textual entailment challenge. In Proceedings of MLCW. Rodrigo de Salvo Braz, Roxana Girju, Vasin Punyakanok, Dan Roth, and Mark Sammons. 2005. An inference model for semantic entailment in natural language. In Proceedings of AAAI. Christiane Fellbaum, editor. 1998. WordNet An Electronic Lexical Database. The MIT Press, May. Ariel Felner, Sarit Kraus, and Richard E. Korf. 2003. KBFS: K-best-first search. Ann. Math. Artif. Intell., 39(1-2): 19–39. David Furcy and Sven Koenig. 2005. Limited discrepancy beam search. In proceedings of IJCAI. Aria Haghighi and Dan Klein. 2009. Simple coreference resolution with rich syntactic and semantic features. In Proceedings of EMNLP. Stefan Harmeling. 2009. Inferring textual entailment with a probabilistically sound calculus. Natural Language Engineering. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Sys- tems Science and Cybernetics, SSC-4(2): 100–107. Michael Heilman and Noah A. Smith. 2010. Tree edit models for recognizing textual entailments, paraphrases, and answers to questions. In Proceedings of NAACL. Levente Kocsis and Csaba Szepesv a´ri. 2006. Bandit based monte-carlo planning. In proceedings of ECML. Richard E. Korf. 1985. Macro-operators: A weak method for learning. Artif. Intell., 26(1):35–77. Richard E. Korf. 1990. Real-time heuristic search. Artif. Intell., 42(2-3):189–21 1. Lili Kotlerman, Ido Dagan, Idan Szpektor, and Maayan Zhitomirsky-geffet. 2010. Directional distributional similarity for lexical inference. Natural Language Engineering. 291 Milen Kouylekov and Bernardo Magnini. 2005. Recognizing textual entailment with tree edit distance algorithms. In Proceedings of Pascal Challenges Workshop on Recognising Textual Entailment. Dekang Lin and Patrick Pantel. 2001. DIRT - discovery of inference rules from text. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Yashar Mehdad. 2009. Automatic cost estimation for tree edit distance using particle swarm optimization. In Proceedings of the ACL-IJCNLP. Shachar Mirkin, Roy Bar-Haim, Jonathan Berant, Ido Dagan, Eyal Shnarch, Asher Stern, and Idan Szpektor. 2009. Addressing discourse and document structure in the rte search task. In Proceedings of TAC. Ira Pohl. 1970. Heuristic search viewed as path finding in a graph. Artificial Intelligence, 1(3-4): 193 204. Stuart Russell and Peter Norvig. 2010. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 3rd edition edition. Asher Stern and Ido Dagan. 2011. A confidence model for syntactically-motivated entailment proofs. In Proceedings of RANLP. Roni Stern, Tamar Kulberis, Ariel Felner, and Robert Holte. 2010. Using lookaheads with optimal best-first search. In proceedings of AAAI. Idan Szpektor, Hristo Tanev, Ido Dagan, and Bonaventura Coppola. 2004. Scaling web-based acquisition of entailment relations. In Proceedings of EMNLP. Richard Anthony Valenzano, Nathan R. Sturtevant, Jonathan Schaeffer, Karen Buro, and Akihiro Kishimoto. 2010. Simultaneously searching with multiple settings: An alternative to parameter tuning for suboptimal single-agent search algorithms. In proceedings of ICAPS. Mengqiu Wang and Christopher D. Manning. 2010. Probabilistic tree-edit models with structured latent variables for textual entailment and question answer– ing. In Proceedings of COLING. Rong Zhou and Eric A. Hansen. 2005. Beam-stack search: Integrating backtracking with beam search. In proceedings of ICAPS.