Query-driven learning speeds up reasoning in complex knowledge bases
Query-Driven Learning for Lifted Reasoning
Artificial Intelligence
Summary
Verifying information by first learning a full knowledge base and then testing questions can be slow and wasteful when only a few questions need answers. The paper explains how to combine learning and checking answers more closely, especially when data and known facts each cover only parts of the picture. The authors identify a key condition needed to decide statements when using partial information, and they create an efficient algorithm for reasoning without having to look at every specific detail. This helps computers think more quickly when dealing with many possible facts.
What this means in practice
- •For knowledge engineers: Decide if a universal property can be efficiently verified using partial data and knowledge base without exhaustive grounding.
- •For ai system designers: Design reasoning components that combine learned and incomplete knowledge to answer specific queries faster.
A theory result. No direct application yet.
Authors
Luise Ge, Brendan Juba
Abstract
Learning and reasoning are both essential to intelligent agents, but have traditionally been treated as two separate stages: first learning a knowledge base from data (or taking one as given), and then verifying queries as if the knowledge base were complete. This separation has been shown to be inefficient when the downstream goal is to verify only a small set of queries. Moreover, it neglects the possibility that data and a knowledge base contain partial yet complementary information, requiring an agent to combine both sources to justify or refute a query. Motivated by the need to integrate learning and reasoning more tightly, we study the problem of query-driven learning for reasoning. More specifically, we extend prior work to the first-order setting, which is critical for practical applications as the number of ground atoms typically grows rapidly. We begin by asking when validating or refuting a universal query given partial data and knowledge base is even possible, and identify a necessary and sufficient condition called bounded concealment. We then propose a quasi-polynomial-time algorithm that solves the task at the lifted level. Finally, we establish soundness and completeness guarantees relative to space-bounded lifted proofs, along with quasipolynomial sample and runtime bounds, demonstrating that lifted query-driven reasoning can be efficient even when unrestricted knowledge-base learning is not.