2019/06/24 by Brendan Juba, Juba, Brendan
Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1906.10118
openalex publication_date 2019/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of learning rules from a data set that support a proof of a given query, under Valiant's PAC-Semantics. We show how any backward proof search algorithm that is sufficiently oblivious to the contents of its knowledge base can be modified to learn such rules while it searches for a proof using those rules. We note that this gives such algorithms for standard logics such as chaining and resolution.