CAREER: Robustness of Inductive Reasoning Engines

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

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.