CAREER: Robustness of Inductive Reasoning Engines

Purdue University, West Lafayette IN

Investigators

Abstract

The past decade has seen a renaissance in the field of machine learning and simultaneously witnessed an explosion of interest in the related area of Programming by Example (PBE). While both fields have enjoyed spectacular successes, their algorithms can be brittle and can drive applications to unexpected failures. The cause of many failures in both machine-learning and PBE systems can be traced back to their shared task of inductive reasoning: learning some artifact in a hypothesis space from a set of examples. Since examples are inherently incomplete specifications, there can be a large number of artifacts that fit a set of examples but fail to generalize to an unseen example. This project advocates for a more principled approach to constructing such inductive reasoning engines based on a formal characterization of their reliability. The project casts the problem of reliability of these systems as one of robustness: is the change in the artifact learnt acceptable, or, at least predictable, in the presence of small changes to the set of examples? The project integrates concepts from formal methods, logic, relational reasoning, and computational learning theory to develop new foundations, algorithms and tools for the design and analysis of robust inductive reasoning engines. The multi-faceted project will impact formal methods and programming languages (through contributions to inductive synthesis and relational reasoning), machine learning (through automated techniques for addressing the dataset shift problem), and society (through users of inductive reasoning engines, and education activities targeting expansion of scientific literacy and computer science pathways). The investigator plans broad dissemination of results (through a workshop on robustness co-founded by the investigator, talks at outreach platforms and a graduate course). This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.