[PL Seminar] Learning relational specifications

Monday, October 31, 2016 -
12:00pm to 1:00pm

Speaker Name: 

Calvin Smith




We present preliminary work on Bach, a tool for learning relational specifications of procedures from a set of data. These relational specifications correlate the behavior of compositions of functions across multiple executions, allowing Bach to learn, for example, that an ordering function is transitive, or that two functions are inverses on certain inputs. Bach operates as an unsupervised learning algorithm, and in several phases. In the first phase, we explore the space of hypotheses to produce likely equations and formulas to explain the data. In the second phase, we utilize classification algorithms to refine imprecise hypotheses up to correctness. Bach is able to learn specifications quickly, as verifying an equation on a set of data reduces to the evaluation of a union of conjunctive queries. This allows us to scale efficiently by utilizing existing SQL or Datalog engines.