Enhancing linear algebraic computation of logic programs using sparse representation
Enhancing linear algebraic computation of logic programs using sparse representation
复制标题
使用稀疏表示增强逻辑程序的线性代数计算
DOI：
10.1007/s00354-021-00142-2
复制
发表时间：
2021
影响因子：
2.6
通讯作者：
Chiaki Sakama
中科院分区：
文献类型：
--
作者：
Nguyen Tuan Quoc;Katsumi Inoue;Chiaki Sakama
近年来，逻辑程序的代数表征受到越来越多的关注。研究人员试图利用线性代数计算和符号计算之间的联系在大规模知识库中进行逻辑推理。在本文中，我们分析了逻辑程序的线性代数方法的复杂性，并提出了通过使用稀疏矩阵将逻辑程序嵌入向量空间的进一步改进。我们展示了它在达到立即结果算子的固定点方面的强大计算能力。特别是，使用稀疏矩阵表示显着提高了计算确定程序的最小模型的性能。我们还将该方法应用于正常程序的稳定模型的计算，其中猜测与初始矩阵相关，并在否定数较少时验证其效果。这些结果显示出程序计算结果的性能得到了良好的增强，并描绘了张量逻辑程序的潜在能力。
Algebraic characterization of logic programs has received increasing attention in recent years. Researchers attempt to exploit connections between linear algebraic computation and symbolic computation to perform logical inference in large-scale knowledge bases. In this paper, we analyze the complexity of the linear algebraic methods for logic programs and propose further improvement by using sparse matrices to embed logic programs in vector spaces. We show its great power of computation in reaching the fixed point of the immediate consequence operator. In particular, performance for computing the least models of definite programs is dramatically improved using the sparse matrix representation. 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.