GENSYNTH: Synthesizing Datalog Programs without Language Bias

Authors

  • Jonathan Mendelson University of Pennsylvania
  • Aaditya Naik University of Pennsylvania
  • Mukund Raghothaman University of Southern California
  • Mayur Naik University of Pennsylvania

Keywords:

Logic Programming

Abstract

Techniques for learning logic programs from data typically rely on language bias mechanisms to restrict the hypothesis space. These methods are therefore limited by the user's ability to tune them such that the hypothesis space is simultaneously large enough to include the target program but small enough to admit a tractable search. We propose a technique to learn Datalog programs from input-output examples without requiring the user to specify any language bias. It employs an evolutionary search strategy that mutates candidate programs and evaluates their fitness on the examples using an off-the-shelf Datalog interpreter. We have implemented our approach in a tool called GenSynth and evaluate it on diverse tasks from knowledge discovery, program analysis, and relational queries. Our experiments show that GenSynth can learn correct programs from few examples, including for tasks that require recursion and invented predicates, and is robust to noise.

Downloads

Published

2021-05-18

How to Cite

Mendelson, J., Naik, A., Raghothaman, M., & Naik, M. (2021). GENSYNTH: Synthesizing Datalog Programs without Language Bias. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6444-6453. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16799

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning