arXiv:2610.34747v2 cs.AI

리프티드 추론을 위한 질의 주도 학습

Query-Driven Learning for Lifted Reasoning

Luise Ge, Brendan Juba

제출 2026-11-19

한국어 초록

학습과 추론은 지능형 에이전트에 모두 필수적이지만, 전통적으로 두 개의 별개 단계로 취급되어 왔다. 즉 먼저 데이터로부터 지식 베이스를 학습하거나 주어진 것으로 받아들이고, 이후 지식 베이스가 완전하다고 가정하여 질의를 검증한다. 이러한 분리는 하위 목표가 소수의 질의만 검증하는 것일 때 비효율적임이 밝혀져 있다. 더욱이 데이터와 지식 베이스가 부분적이지만 상호 보완적인 정보를 담고 있을 가능성을 간과하므로, 에이전트는 질의를 정당화하거나 반박하기 위해 두 출처를 결합해야 한다. 학습과 추론을 더 긴밀히 통합할 필요성에 동기를 얻어, 본 논문은 추론을 위한 질의 주도 학습 문제를 연구한다. 보다 구체적으로, 기존 연구를 일차 논리 설정으로 확장하는데, 이는 기저 원자의 수가 일반적으로 급격히 증가하기 때문에 실용적 응용에 중요하다. 먼저 부분적인 데이터와 지식 베이스가 주어졌을 때 전칭 질의를 검증하거나 반박하는 것이 언제 가능한지를 묻고, 경계 은닉(bounded concealment)이라는 필요충분조건을 규명한다. 이어서 이 과제를 리프티드 수준에서 해결하는 준다항 시간 알고리즘을 제안한다. 마지막으로 공간 제한 리프티드 증명에 대한 건전성과 완전성 보장을 준다항 표본 및 실행 시간 한계와 함께 증명하여, 제약 없는 지식 베이스 학습이 효율적이지 않은 경우에도 리프티드 질의 주도 추론은 효율적일 수 있음을 보인다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.34747v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.