Symmetry breaking for inductive logic programming
This addresses a computational bottleneck for researchers and practitioners in logic programming and AI, offering a significant speedup, though it is an incremental improvement on existing methods.
The paper tackles the challenge of searching vast hypothesis spaces in inductive logic programming, where many logically equivalent hypotheses exist, by introducing a symmetry-breaking method implemented in answer set programming, reducing solving times from over an hour to 17 seconds in experiments.
The goal of inductive logic programming is to search for a hypothesis that generalises training data and background knowledge. The challenge is searching vast hypothesis spaces, which is exacerbated because many logically equivalent hypotheses exist. To address this challenge, we introduce a method to break symmetries in the hypothesis space. We implement our idea in answer set programming. Our experiments on multiple domains, including visual reasoning and game playing, show that our approach can reduce solving times from over an hour to just 17 seconds.