Abstract
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-byexample, and demonstrate significant improvements
in learning complex programs with recursive rules,
invented predicates, and relations of arbitrary arity