CAREER: Robustness of Inductive Reasoning Engines

在过去的十年中，机器学习领域出现了复兴，同时见证了相关领域对示例编程(PBE)的兴趣激增。虽然这两个领域都取得了惊人的成功，但它们的算法可能很脆弱，可能会导致应用程序意外失败。机器学习和PBE系统中许多失败的原因都可以追溯到它们共同的归纳推理任务：从一组例子中学习假设空间中的一些人工产物。由于示例本质上是不完整的规范，因此可能有大量的构件符合一组示例，但不能概括为看不见的示例。这个项目倡导一种更有原则的方法来构建这样的归纳推理引擎，该方法基于对其可靠性的正式表征。该项目将这些系统的可靠性问题作为一个健壮性问题来考虑：学习到的人工制品的变化是可接受的，或者至少在存在对示例集的微小变化的情况下是可预测的？该项目集成了形式化方法、逻辑学、关系推理和计算学习理论的概念，为设计和分析健壮的归纳推理引擎开发了新的基础、算法和工具。这个多方面的项目将影响形式方法和编程语言(通过对归纳综合和关系推理的贡献)、机器学习(通过解决数据集转移问题的自动化技术)和社会(通过归纳推理引擎的用户，以及旨在扩大科学素养和计算机科学途径的教育活动)。研究人员计划广泛传播结果(通过研究人员共同创办的稳健性研讨会、在外展平台上的演讲和研究生课程)。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.