Modeling Variations of First-Order Horn Abduction in Answer Set Programming

• Autorzy: Schüller P.

Identyfikatory

DOI

10.3233/FI-2016-1446

• Konferencja: Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (22; 22.09.2015; Ferrara; Italy)
• Języki publikacji: EN

Abstrakty

EN

We study abduction in First Order Horn logic theories where all atoms can be abduced and we are looking for preferred solutions with respect to three objective functions: cardinality minimality, coherence, and weighted abduction. We represent this reasoning problem in Answer Set Programming (ASP), in order to obtain a flexible framework for experimenting with global constraints and objective functions, and to test the boundaries of what is possible with ASP. Realizing this problem in ASP is challenging as it requires value invention and equivalence between certain constants, because the Unique Names Assumption does not hold in general. To permit reasoning in cyclic theories, we formally describe fine-grained variations of limiting Skolemization. We identify term equivalence as a main instantiation bottleneck, and improve the efficiency of our approach with on-demand constraints that were used to eliminate the same bottleneck in state-of-the-art solvers. We evaluate our approach experimentally on the ACCEL benchmark for plan recognition in Natural Language Understanding. Our encodings are publicly available, modular, and our approach is more efficient than state-of-the-art solvers on the ACCEL benchmark.

Słowa kluczowe

EN

first order horn abduction; weighted abduction; answer set programming; natural language understanding

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 1/2
• Strony: 159--207
• Opis fizyczny: Bibliogr. 52 poz., rys., tab.

Twórcy

autor

Schüller P.

• Computer Engineering Department, Faculty of Engineering, Marmara University, Turkey

Bibliografia

• [1] Schüller P. Modeling Abduction over Acyclic First-Order Logic Horn Theories in Answer Set Programming: Preliminary Experiments. In: International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA). vol. 1451. CEUR-WS.org; 2015. p. 76–90.
• [2] Peirce CS. Abduction and Induction. In: Philosophical Writings of Peirce. Dover Publications; 1955. p. 150–156.
• [3] Ng HT, Mooney RJ. On the Role of Coherence in Abductive Explanation. In: National Conference on Artificial Intelligence; 1990. p. 337–342. ISBN: 0-262-51057-X .
• [4] Ng HT. A General Abductive System with Applications to Plan Recognition and Diagnosis [PhD Thesis]. University of Texas at Austin; 1992.
• [5] Stickel M. Rationale and methods for abductive reasoning in natural-language interpretation. In: Natural Language and Logic; 1989. p. 233–252. doi: 10.1007/3-540-53082-7_26.
• [6] Hobbs JR, Stickel M, Martin P, Edwards D. Interpretation as abduction. Artificial Intelligence. 1993;63(1-2):69–142. doi:10.1016/0004-3702(93)90015-4.
• [7] Singla P, Mooney RJ. Abductive Markov Logic for Plan Recognition. In: AAAI Conference on Artificial Intelligence; 2011. p. 1069–1075. Available from: http://dl.acm.org/citation.cfm?id=2900423.2900593.
• [8] Yamamoto K, Inoue N, Inui K, Arase Y, Tsujii J. Boosting the Efficiency of First-Order Abductive Reasoning Using Pre-estimated Relatedness between Predicates. International Journal of Machine Learning and Computing. 2015;5(2):114–120. doi:10.7763/IJMLC.2015.V5.493.
• [9] Inoue N, Inui K. ILP-based Inference for Cost-based Abduction on First-order Predicate Logic. Journal of Natural Language Processing. 2013;20(5):629–656. doi:10.5715/jnlp.20.629.
• [10] Blythe J, Hobbs JR, Domingos P, Kate RJ, Mooney RJ. Implementing Weighted Abduction in Markov Logic. In: International Conference on Computational Semantics (IWCS); 2011. p. 55–64. Available from: http://dl.acm.org/citation.cfm?id=2002669.2002676.
• [11] Lifschitz V. What Is Answer Set Programming? In: AAAI Conference on Artificial Intelligence; 2008. p. 1594–1597. Available from: http://dl.acm.org/citation.cfm?id=1620270.1620340.
• [12] Schüller P. Tackling Winograd Schemas by Formalizing Relevance Theory in Knowledge Graphs. In: International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press; 2014. p. 358–367. Available from: http://dblp.l3s.de/d2r/resource/publications/conf/kr/Schuller14.
• [13] Ng HT, Mooney RJ. Abductive Plan Recognition and Diagnosis: A Comprehensive Empirical Evaluation. In: Knowledge Representation and Reasoning (KR); 1992. p. 499–508. Available from: http://www.cs.utexas.edu/users/ai-lab/?accel-kr-92.
• [14] Gebser M, Kaminski R, Kaufmann B, Schaub T. Clingo = ASP + Control: Extended Report. University of Potsdam; 2014.
• [15] Gebser M, Kaminski R, König A, Schaub T. Advances in gringo series 3. In: International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR); 2011. p. 345–351. doi:10.1007/978-3-642-20895-9_39.
• [16] Gebser M, Kaminski R, Kaufmann B, Romero J, Schaub T. Progress in clasp Series 3. In: International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR); 2015. p. 368–383. doi:10.1007/978-3-319-23264-5_31.
• [17] Alviano M, Dodaro C, Leone N, Ricca F. Advances in WASP. In: International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR); 2015. p. 40–54. doi:10.1007/978-3-319-23264-5_5.
• [18] Inoue N, Ovchinnikova E, Inui K, Hobbs J. Weighted Abduction for Discourse Processing Based on Integer Linear Programming. In: Plan, Activity, and Intent Recognition. Elsevier; 2014. p. 33–55. doi:10.1016/b978-0-12-398532-3.00002-6.
• [19] Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming. In: International Conference and Symposium on Logic Programming (ICLP/SLP); 1988. p. 1070–1080. Available from: http://www.cs.utexas.edu/users/ai-lab/?gel88.
• [20] Eiter T, Ianni G, Krennwallner T. Answer Set Programming: A Primer. In: Reasoning Web Summer School. Lecture Notes in Computer Science. Springer; 2009. p. 40–110. doi:10.1007/978-3-642-03754-2_2.
• [21] Gebser M, Kaminski R, Kaufmann B, Schaub T. Answer Set Solving in Practice. Morgan Claypool; 2012. doi:10.2200/s00457ed1v01y201211aim019.
• [22] Eiter T, Fink M, Ianni G, Krennwallner T, Redl C, Schüller P. A model building framework for Answer Set Programming with external computations. Theory and Practice of Logic Programming. 2016;16(04):418–464. doi:10.1017/S1471068415000113.
• [23] Calimeri F, Faber W, Gebser M, Ianni G, Kaminski R, Krennwallner T, et al. ASP-Core-2 Input language format. ASP Standardization Working Group; 2012. Available from: https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.03c.pdf.
• [24] Faber W, Pfeifer G, Leone N. Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence. 2011;175(1):278–298. doi:10.1016/j.artint.2010.04.002.
• [25] Lifschitz V, Turner H. Splitting a Logic Program. International Conference on Logic Programming (ICLP). 1994;19(1):23–37.
• [26] Eiter T, Ianni G, Schindlauer R, Tompits H. Effective Integration of Declarative Rules with External Evaluations for Semantic-Web Reasoning. In: European Semantic Web Conference (ESWC); 2006. p. 273–287. doi:10.1007/11762256_22.
• [27] Lifschitz V. Answer set programming and plan generation. Artificial Intelligence. 2002;138(1-2):39–54. doi:10.1016/s0004-3702(02)00186-8.
• [28] Alviano M, Dodaro C, Marques-Silva J, Ricca F. Optimum stable model search: algorithms and implementation. Journal of Logic and Computation. 2015;doi:10.1093/logcom/exv061.
• [29] Kakas AC, Kowalski RA, Toni F. Abductive Logic Programming. Journal of Logic and Computation. 1992;2(6):719–770. doi:10.1093/logcom/2.6.719.
• [30] Fung TH, Kowalski R. The IFF proof procedure for abductive logic programming. The Journal of Logic Programming. 1997;33(2):151–165. doi:10.1016/s0743-1066(97)00026-5.
• [31] Denecker M, de Schreye D. SLDNFA: An abductive procedure for abductive logic programs. The Journal of Logic Programming. 1998;34(2):111–167. doi:10.1016/s0743-1066(97)00074-5.
• [32] Kakas AC, Van Nuffelen B, Denecker M. A-System: Problem solving through abduction. In: International Joint Conference on Artificial Intelligence (IJCAI); 2001. p. 591–596. doi:10.1007/3-540-45402-0_29.
• [33] Mancarella P, Terreni G, Sadri F, Toni F, Endriss U. The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Theory, Implementation and Experiments. Theory and Practice of Logic Programming. 2009;9(6):691–750. doi:10.1017/S1471068409990093.
• [34] Alberti M, Chesani F, Gavanelli M, Lamma E, Mello P, Torroni P. Verifiable agent interaction in abductive logic programming: The SCIFF framework. ACM Transactions on Computational Logic. 2008;9(4):Article No. 29. doi:10.1145/1380572.1380578.
• [35] Gavanelli M, Lamma E, Riguzzi F, Bellodi E, Zese R, Cota G. An abductive Framework for Datalog+/-Ontologies. In: International Conference on Logic Programming (ICLP), Technical Communications. 1433. CEUR-WS.org; 2015.
• [36] Calì A, Gottlob G, Lukasiewicz T. Datalog+/-: A Unified Approach to Ontologies and Integrity Constraints. In: International Conference on Database Theory; 2009. p. 14–30. doi:10.1145/1514894.1514897.
• [37] Lefèvre C, Béatrix C, Stéphan I, Garcia L. ASPeRiX, a First Order Forward Chaining Approach for Answer Set Computing. Theory and Practice of Logic Programming. 2015;To appear, arXiv:1503.07717.
• [38] Dao-tran M, Eiter T, Fink M, Weidinger G, Weinzierl A. OMiGA: An Open Minded Grounding On-The-Fly Answer Set Solver. In: Logics in Artificial Intelligence (JELIA); 2012. p. 480–483. doi:10.1007/978-3-642-33353-8_38.
• [39] Marple K, Gupta G. Galliwasp: A goal-directed answer set solver. In: Logic-Based Program Synthesis and Transformation (LoPSTR); 2013. p. 122–136. doi:10.1007/978-3-642-38197-3_9.
• [40] De Cat B, Denecker M, Stuckey P, Bruynooghe M. Lazy Model Expansion: Interleaving Grounding with Search. Journal of Artificial Intelligence Research. 2015;52(1):235–286. Available from: http://dl.acm.org/citation.cfm?id=2831407.2831412.
• [41] Richardson M, Domingos P. Markov logic networks. Machine Learning. 2006 jan;62(1-2):107–136. doi:10.1007/s10994-006-5833-1.
• [42] Kok S, Sumner M, Richardson M, Singla P, Poon H, D L, et al. The Alchemy system for statistical relational AI. Department of Computer Science and Engineering, University of Washington; 2010.
• [43] Eiter T, Fink M, Krennwallner T, Redl C. Liberal Safety for Answer Set Programs with External Sources. In: AAAI Conference on Artificial Intelligence; 2013. p. 267–275.
• [44] Sutcliffe G. The TPTP problem library and associated infrastructure: the FOF and CNF parts, v3.5.0. Journal of Automated Reasoning. 2009;43(4):337–362. doi:10.1007/s10817-009-9143-8.
• [45] Baumgartner P, Kühn M. Abducing Coreference by Model Construction. Journal of Language and Computation. 2000;1(2):175–190.
• [46] Bylander T, Allemang D, Tanner MC, Josephson JR. The computational complexity of abduction. Artificial Intelligence. 1991;49(1-3):25–60. doi:10.1016/0004-3702(91)90005-5.
• [47] Eiter T, Gottlob G. The Complexity of Logic-Based Abduction. Journal of the ACM. 1995;42(1):3–42. doi:10.1145/200836.200838.
• [48] Eiter T, Gottlob G, Leone N. Abduction from logic programs: Semantics and complexity. Theoretical Computer Science. 1997;189(1-2):129–177. doi:10.1016/S0304-3975(96)00179-X.
• [49] Dantsin E, Eiter T, Gottlob G, Voronkov A. Complexity and expressive power of logic programming. ACM Computing Surveys. 2001;33(3):374–425. doi:10.1109/CCC.1997.612304.
• [50] Vorobyov S, Voronkov A. Complexity of nonrecursive logic programs with complex values. Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. 1998;p. 253. doi:http://doi.acm.org/10.1145/275487.275515.
• [51] Liu G, Janhunen T, Niemelä I. Answer set programming via mixed integer programming. In: Principles of Knowledge Representation and Reasoning (KR); 2012. p. 32–42.
• [52] Dagan I, Glickman O, Magnini B. The PASCAL Recognising Textual Entailment Challenge. In: Machine Learning Challenges. Springer; 2006. p. 177–190. doi:10.1007/11736790_9.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).