CAREER: Relational generalization in integrated learning and reasoning

在许多领域中，知识可以通过各种实体之间的关系和表示这些关系是否对这些实体中的一些或全部成立的量词来有效地表达。这个项目将开发使用这样的表达式来解决组合学习和推理任务的算法，并在理论上保证效率和正确性。这些保证将有助于我们理解算法何时可以安全使用，并确保它们可以作为更大系统的一部分成功使用。此外，作为该项目的一部分，学生将接受研究方面的培训。最后，该项目包括开发一门新的本科核心算法课程，该课程借鉴了最近的教育研究，以加强学生对算法的掌握，并促进未被充分代表的群体参与计算机科学。具体地说，该项目中使用的表达式是一阶逻辑公式，因此该项目寻求在一阶公式集合上进行推理的算法，这些一阶公式是从包含表达式的部分真值的数据中学习的。例如，为问题回答或规划应用程序(例如)制定这样的表达式来获取足够逼真的域是一项艰巨的任务。对于其他类型的表征，将学习和推理任务相结合，使得能够为组合任务设计正确而高效的算法，其中个别任务被认为是难以正确解决的，就像它们在这里一样。作为这项工作的一部分，研究人员还将寻求使用这种表示进行推理的改进算法。该项目还包括开发这种综合学习和推理在规划问题中的应用。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

In many domains, knowledge may be efficiently expressed in terms of relationships between various entities and quantifiers expressing whether those relationship holds for some or all of those entities. This project will develop algorithms with theoretical guarantees of efficiency and correctness for solving combined learning and reasoning tasks using such expressions. The guarantees will aid our understanding of when the algorithms are safe to use and ensure that they can be used successfully as part of a larger system. Furthermore, students will be trained in research as part of this project. Finally, this project includes the development of a new core undergraduate algorithms course that draws on recent education research to strengthen students' grasp of algorithms and promote participation in computer science among underrepresented groups.Concretely, the expressions used in this project are formulas of first-order logic, and so the project seeks algorithms for reasoning over a collection of first-order formulas that are learned from data consisting of partial truth valuations of the expressions. Formulating such expressions to capture a domain with adequate fidelity for question-answering or planning applications (for example) is a daunting task. Combining the tasks of learning and reasoning has, for other kinds of representations, enabled the design of correct and efficient algorithms for the combined task where the individual tasks were believed to be intractable to solve correctly, as they are here. As part of this work, the researchers will also seek improved algorithms for reasoning with such representations. The project furthermore includes the development of applications of such integrated learning and reasoning in planning problems.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.