Synthesizing Datalog Programs using Numerical Relaxation

Synthesizing Datalog Programs using Numerical Relaxation

Xujie Si, Mukund Raghothaman, Kihong Heo, Mayur Naik

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Understanding Intelligence and Human-level AI in the New Machine Learning era. Pages 6117-6124. https://doi.org/10.24963/ijcai.2019/847

The problem of learning logical rules from examples arises in diverse fields, including program synthesis, logic programming, and machine learning. Existing approaches either involve solving computationally difficult combinatorial problems, or performing parameter estimation in complex statistical models. In this paper, we present Difflog, a technique to extend the logic programming language Datalog to the continuous setting. By attaching real-valued weights to individual rules of a Datalog program, we naturally associate numerical values with individual conclusions of the program. Analogous to the strategy of numerical relaxation in optimization problems, we can now first determine the rule weights which cause the best agreement between the training labels and the induced values of output tuples, and subsequently recover the classical discrete-valued target program from the continuous optimum. We evaluate Difflog on a suite of 34~benchmark problems from recent literature in knowledge discovery, formal verification, and database query-by-example, and demonstrate significant improvements in learning complex programs with recursive rules, invented predicates, and relations of arbitrary arity.
Keywords:
Special Track on Understanding Intelligence and Human-level AI in the New Machine Learning era: Neural Methods in Inductive Logic Programming (Special Track on Human AI and Machine Learning)
Special Track on Understanding Intelligence and Human-level AI in the New Machine Learning era: Neuro-Symbolic methods (Special Track on Human AI and Machine Learning)
Special Track on Understanding Intelligence and Human-level AI in the New Machine Learning era: Neuro Statistical Relational Learning (Special Track on Human AI and Machine Learning)