×

Enhancing linear algebraic computation of logic programs using sparse representation. (English) Zbl 07455718

Ricca, Francesco (ed.) et al., Proceedings of the 36th international conference on logic programming (technical communications), ICLP 2020, UNICAL, Rende (CS), Italy, September 18–24, 2020. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 325, 192-205 (2020).
Summary: Algebraic characterization of logic programs has received increasing attention in recent years. Researchers attempt to exploit connections between linear algebraic computation and symbolic computation in order to perform logical inference in large scale knowledge bases. This paper proposes further improvement by using sparse matrices to embed logic programs in vector spaces. We show its great power of computation in reaching the fixpoint of the immediate consequence operator from the initial vector. In particular, performance for computing the least models of definite programs is dramatically improved in this way. We also apply the method to the computation of stable models of normal programs, in which the guesses are associated with initial matrices, and verify its effect when there are small numbers of negation. These results show good enhancement in terms of performance for computing consequences of programs and depict the potential power of tensorized logic programs.
For the entire collection see [Zbl 1466.68027].

MSC:

68N17 Logic programming
PDF BibTeX XML Cite
Full Text: arXiv Link

References:

[1] Jose Julio Alferes, Joao Alexandre Leite, Luis Moniz Pereira, Halina Przymusinska & Teodor C. Przymusin-ski (2000): Dynamic updates of non-monotonic knowledge bases. The Journal of Logic Programming 45(1-3), pp. 43-70, doi:10.1016/S0743-1066(99)00065-5. · Zbl 0957.68108
[2] Yaniv Aspis (2018): A Linear Algebraic Approach to Logic Programming. Master thesis at Imperial College London.
[3] Yaniv Aspis, Krysia Broda & Alessandra Russo (2018): Tensor-based abduction in horn propositional pro-grams. 2206, CEUR Workshop Proceedings, pp. 68-75, doi:10.1145/200836.200838. · Zbl 0886.68121
[4] James R Bunch & Donald J Rose (2014): Sparse matrix computations. Academic Press, doi:10.1016/ C2013-0-10439-4.
[5] William W Cohen (2016): Tensorlog: A differentiable deductive database. arXiv preprint arXiv:1605.06523.
[6] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Max Ostrowski, Torsten Schaub & Philipp Wanko (2016): Theory solving made easy with clingo 5. In: OASIcs-OpenAccess Series in Informatics, 52, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, doi:10.4230/OASIcs.ICLP.2016.2.
[7] Gaël Guennebaud, Benoît Jacob et al. (2010): Eigen v3. http://eigen.tuxfamily.org.
[8] Fred G Gustavson (1978): Two fast algorithms for sparse matrices: Multiplication and permuted transpo-sition. ACM Transactions on Mathematical Software (TOMS) 4(3), pp. 250-269, doi:10.1145/355791. 355796. · Zbl 0384.65016
[9] Robert Kowalski (1974): Logic for problem solving. Department of Computational Logic, Edinburgh Uni-versity, doi:10.1145/1005937.1005947.
[10] Jérôme Kunegis (2013): Konect: the koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343-1350, doi:10.1145/2487788.2488173.
[11] Hien D. Nguyen, Chiaki Sakama, Taisuke Sato & Katsumi Inoue (2018): Computing Logic Programming Semantics in Linear Algebra. In: Proceedings of the 12th International Conference on Multi-disciplinary Trends in Artificial Intelligence (MIWAI 2018), Springer International Publishing, Lecture Notes in Artificial Intelligence, Vol. 11248, pp. 32-48, doi:10.1007/978-3-030-03014-8_3.
[12] Tim Rocktäschel, Matko Bosnjak, Sameer Singh & Sebastian Riedel (2014): Low-dimensional embeddings of logic. In: Proceedings of the ACL 2014 Workshop on Semantic Parsing, pp. 45-49, doi:10.3115/v1/ W14-2409.
[13] Chiaki Sakama, Katsumi Inoue & Taisuke Sato (2017): Linear Algebraic Characterization of Logic Pro-grams. In: Proceedings of the 10th International Conference on Knowledge Science, Engineering and Management (KSEM 2017), Springer International Publishing, Lecture Notes in Artificial Intelligence, Vol. 10412, pp. 520-533, doi:10.1007/978-3-319-63558-3_44.
[14] Taisuke Sato (2017): Embedding Tarskian semantics in vector spaces. In: Workshops at the Thirty-First AAAI Conference on Artificial Intelligence.
[15] Taisuke Sato (2017): A linear algebraic approach to Datalog evaluation. Theory and Practice of Logic Programming 17(3), pp. 244-265, doi:10.1017/S1471068417000023. · Zbl 1379.68082
[16] Taisuke Sato, Katsumi Inoue & Chiaki Sakama (2018): Abducing Relations in Continuous Spaces. In: IJCAI, pp. 1956-1962, doi:10.24963/ijcai.2018/270.
[17] Maarten H Van Emden & Robert A Kowalski (1976): The semantics of predicate logic as a programming language. Journal of the ACM (JACM) 23(4), pp. 733-742, doi:10.1145/321978.321991. · Zbl 0339.68004
[18] Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jianfeng Gao & Li Deng (2015): Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In: Proceedings of the International Conference on Learning Representations (ICLR) 2015. Available at https://www.microsoft.com/en-us/research/publication/ embedding-entities-and-relations-for-learning-and-inference-in-knowledge-bases/.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.