Efficient Program Synthesis Using Constraint Satisfaction in Inductive Logic Programming

摘要

We present NrSample, a framework for program synthesis ininductive logic programming. NrSample uses propositional logicconstraints to exclude undesirable candidates from the search.This is achieved by representing constraints as propositionalformulae and solving the associated constraint satisfactionproblem. We present a variety of such constraints: pruning,input-output, functional (arithmetic), and variable splitting.NrSample is also capable of detecting search space exhaustion,leading to further speedups in clause induction and optimality.We benchmark NrSample against enumeration search (Aleph'sdefault) and Progol's $A^{*}$ search in the context of programsynthesis. The results show that, on large program synthesisproblems, NrSample induces between 1 and 1358 times faster thanenumeration (236 times faster on average), always with similaror better accuracy. Compared to Progol $A^{*}$, NrSample is 18times faster on average with similar or better accuracy exceptfor two problems: one in which Progol $A^{*}$ substantiallysacrificed accuracy to induce faster, and one in which Progol$A^{*}$ was a clear winner. Functional constraints provide aspeedup of up to 53 times (21 times on average) with similar orbetter accuracy. We also benchmark using a few concept learning(non-program synthesis) problems. The results indicate thatwithout strong constraints, the overhead of solving constraintsis not compensated for. color="gray">