CAREER: Relational generalization in integrated learning and reasoning

Washington University, Saint Louis MO

Investigators

Abstract

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.