Learning algorithms using logic

I will present recent work on learning algorithms using logic. Given example input/outputs of an algorithm and background knowledge (BK) which contains auxiliary concepts, our goal is to induce an algorithm that explains the examples with respect to BK. For instance, given example pairs of unsorted/sorted lists and BK containing useful helper concepts, such as head, tail, etc, our goal is to induce a sorting algorithm. Our approach is based on logic, where the examples are atoms, and the background knowledge and induced algorithms are logical theories. I will focus on our recent on meta-interpretive learning (MIL) a form of inductive logic programming that works by constructing proofs for the atoms, and then extracting an algorithm from the proof. MIL is novel for its support of predicate invention, learning recursive algorithms, and even learning efficient algorithms.