Abducing Relations in Continuous Spaces

Taisuke Sato, Katsumi Inoue and Chiaki Sakama

Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-18), pages 1956-1962, 2018.

Abstract

We propose a new approach to abduction, i.e., non-deductive inference to find a hypothesis H for an observation O such that H, KB |- O where KB is background knowledge. We reformulate it linear algebraically in vector spaces to abduce relations, not logical formulas, to realize approximate but scalable abduction that can deal with web-scale knowledge bases. More specifically we consider the problem of abducing relations for Datalog programs with binary predicates. We treat two cases, the non-recursive case and the recursive case. In the non-recursive case, given r1(X,Y) and r3(X,Z), we abduce r2(Y,Z) so that r3(X,Z) <= r1(X,Y)&r2(Y,Z) approximately holds, by computing a matrix R2 that approximately satisfies a matrix equation R3 = min1(R1R2) containing a nonlinear function min1(x). Here R1, R2 and R3 encode as adjacency matrix r1(X,Y), r2(Y,Z) and r3(Y,Z) respectively. We apply this matrix-based abduction to rule discovery and relation discovery in a knowledge graph. The recursive case is mathematically more involved and computationally more difficult but solvable by deriving a recursive matrix equation and solving it. We illustrate concrete recursive cases including a transitive closure relation.

Slide (pdf 300K)