Query-driven PAC-Learning for Reasoning
This addresses the challenge of automated reasoning by integrating learning into proof search, though it appears incremental as it builds on existing algorithms and semantics.
The paper tackles the problem of learning rules from data to support proofs under PAC-Semantics, showing that backward proof search algorithms can be modified to learn these rules during proof search, with applications to standard logics like chaining and resolution.
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.