Abstract
Abduction has been applied to various problems in many fields, and computing abductive explanations is an essential task in such applications. Logic programming has been used for both representation languages and computational procedures for abductive computation. This chapter summarizes the novel approach to use linear algebra for abduction in logic programming developed by the authors. The method is built on top of the fixed-point computation of matrix-vector multiplications for deduction in logic programming, where a matrix and vectors, respectively, represent a logic program and interpretations. For abduction, a similar technique is employed for multiplications of an abductive matrix and observation vectors, together with enumeration of minimal hitting sets by avoiding dimension explosion. Compared with logical methods based on symbolic manipulation, the linear algebraic method has an advantage for efficient computation.
Similar content being viewed by others
References
Apt, K. R., & Bezem, M. (1991). Acyclic programs. New Generation Computing, 9, 335–364.
Aspis, Y., Broda, K., & Russo, A. (2018). Tensor-based abduction in horn propositional programs. In ILP 2018 (CEUR Workshop Proceedings, Vol. 2206, pp. 68–75).
Boutilier, C., & Beche, V. (1995). Abduction as belief revision. Artificial Intelligence, 77(1), 43–94.
Console, L., Dupré, D. T., & Torasso, P. (1991). On the relationship between abduction and deduction. Journal of Logic and Computation, 1(5), 661–690.
Dai, W.-Z., Xu, Q., Yu, Y., & Zhou, Z.-H. (2019). Bridging machine learning and logical reasoning by abductive learning. In Neural Information Processing Systems 2019 (Vol. 32). Curran Associates, Inc.
D’Asaro, F. A., Spezialetti, M., Raggioli, L., & Rossi, S. (2020). Towards an inductive logic programming approach for explaining black-box preference learning systems. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (pp. 855–859).
de Kleer, J. (1986a). An assumption-based TMS. Artificial Intelligence, 28(2), 127–162.
de Kleer, J. (1986b). Problem solving with the ATMS. Artificial Intelligence, 28(2), 197–224.
Eiter, T., & Gottlob, G. (1995). The complexity of logic-based abduction. Journal of the ACM (JACM), 42(1), 3–42.
Eshghi, K. (1988). Abductive planning with event calculus. In ICLP/SLP (pp. 562–579).
Gainer-Dewar, A., & Vera-Licona, P. (2017). The minimal hitting set generation problem: Algorithms and computation. SIAM Journal on Discrete Mathematics, 31(1), 63–100.
Gelfond, M., & Lifschitz, V. (1988). The stable model semantics for logic programming. In ICLP/SLP, 88, 1070–1080.
Greiner, R., Smith, B. A., & Wilkerson, R. W. (1989). A correction to the algorithm in Reiter’s theory of diagnosis. Artificial Intelligence, 41(1), 79–88.
Ignatiev, A., Morgado, A., & Marques-Silva, J. (2016). Propositional abduction with implicit hitting sets. In ECAI 2016 (Frontiers in Artificial Intelligence and Applications, Vol. 285, pp. 1327–1335). IOS Press.
Ignatiev, A., Morgado, A., & Marques-Silva, J. (2018). PySAT: A Python toolkit for prototyping with SAT oracles. In International Conference on Theory and Applications of Satisfiability Testing (pp. 428–437).
Ignatiev, A., Narodytska, N., & Marques-Silva, J. (2019). Abduction-based explanations for machine learning models. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, pp. 1511–1519).
Inoue, K. (1992). Linear resolution for consequence finding. Artificial Intelligence, 56(2–3), 301–353.
Inoue, K. (2002). Automated abduction. In A. C. Kakas & F. Sadri (Eds.), Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski Part II (LNAI 2408, pp. 311–341). Springer.
Inoue, K. (2016). Meta-level abduction. IfCoLog Journal of Logics and Their Applications, 3(1), 7–36.
Josephson, J. R., & Josephson, S. G. (1996). Abductive Inference: Computation, Philosophy, Technology. Cambridge University Press.
Kakas, A. C., Kowalski, R. A., & Toni, F. (1998). The role of abduction in logic programming. In D. Gabbay, C. Hogger, & J. Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming (Vol. 5, pp. 235–324). Oxford University Press.
Muggleton, S. (1991). Inductive logic programming. New Generation Computing, 8(4), 295–318.
Nabeshima, H., Iwanuma, K., Inoue, K., & Ray, O. (2010). Solar: An automated deduction system for consequence finding. AI Communications, 23(2–3), 183–203.
Nguyen, T. Q., Inoue, K., & Sakama, C. (2021). Linear algebraic computation of propositional horn abduction. In 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 240–247). IEEE.
Nguyen, T. Q., Inoue, K., & Sakama, C. (2022). Enhancing linear algebraic computation of logic programs using sparse representation. New Generation Computing, 40(1), 225–254. A shorter version is in: EPTCS online proceedings of ICLP (Vol. 325, pp. 192–205) (2020)
Paul, G. (2000). AI approaches to abduction. In D. M. Gabbay, & R. Kruse (Eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems (Vol. 4, pp. 35–98). Springer.
Reiter, R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, 32(1), 57–95.
Rocktäschel, T., Bošnjak, M., Singh, S., & Riedel, S. (2014). Low-dimensional embeddings of logic. In Proceedings of the ACL 2014 Workshop on Semantic Parsing (pp. 45–49).
Rocktäschel, T., & Riedel, S. (2017). End-to-end differentiable proving. In Neural Information Processing Systems 2017 (pp. 3788–3800).
Saikko, P., Wallner, J. P., & Järvisalo, M. (2016). Implicit hitting set algorithms for reasoning beyond NP. In KR (pp. 104–113).
Sakama, C., Inoue, K., & Sato, T. (2017). Linear algebraic characterization of logic programs. In International Conference on Knowledge Science, Engineering and Management (pp. 520–533). Springer.
Sakama, C., Inoue, K., & Sato, T. (2021). Logic programming in tensor spaces. Annals of Mathematics and Artificial Intelligence, 89(12), 1133–1153.
Sato, T. (2017). Embedding tarskian semantics in vector spaces. In Workshops at the Thirty-First AAAI Conference on Artificial Intelligence.
Sato, T., Inoue, K., & Sakama, C. (2018). Abducing relations in continuous spaces. In IJCAI: Proceedings of the Conference (pp. 1956–1962).
Schüller, P. (2016). Modeling variations of first-order horn abduction in answer set programming. Fundamenta Informaticae, 149(1–2), 159–207.
Selman, B., & Levesque, H. J. (1990). Abductive and default reasoning: A computational core. In AAAI (pp. 343–348).
Shakerin, F., & Gupta, G. (2020). White-box induction from SVM models: Explainable AI with logic programming. Theory and Practice of Logic Programming, 20(5), 656–670.
van Emden, M. H., & Kowalski, R. A. (1976). The semantics of predicate logic as a programming language. Journal of the ACM, 23(4), 733–742.
Yang, B., Yih, W., He, X., Gao, J., & Deng, L. (2015). Embedding entities and relations for learning and inference in knowledge bases. In 3rd International Conference on Learning Representations, ICLR 2015, Conference Track Proceedings
Acknowledgements
This work has been supported by JSPS KAKENHI Grant Numbers JP18H03288 and JP21H04905, and by JST CREST Grant Number JPMJCR22D3, Japan.
Tuan Nguyen Quoc has also been supported by Monbukagakusho (MEXT) Scholarship and Japan International Cooperative Agency “Innovative Asia”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this entry
Cite this entry
Nguyen, T.Q., Inoue, K., Sakama, C. (2022). Abductive Logic Programming and Linear Algebraic Computation. In: Magnani, L. (eds) Handbook of Abductive Cognition. Springer, Cham. https://doi.org/10.1007/978-3-030-68436-5_62-1
Download citation
DOI: https://doi.org/10.1007/978-3-030-68436-5_62-1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68436-5
Online ISBN: 978-3-030-68436-5
eBook Packages: Springer Reference Intelligent Technologies and RoboticsReference Module Computer Science and Engineering