Efficiently Learning Probabilistic Logical Models by Cheaply Ranking Mined Rules
This work addresses the high cost and error-proneness of handcrafting logical models, making them more applicable in real-world settings for tasks requiring explainability, though it is incremental in improving scalability.
The paper tackles the problem of efficiently learning probabilistic logical models from data by introducing SPECTRUM, a scalable framework that uses linear-time algorithms for mining and ranking rules, resulting in learning more accurate logical theories on CPUs in less than 1% the runtime of state-of-the-art neural network approaches on GPUs.
Probabilistic logical models are a core component of neurosymbolic AI and are important in their own right for tasks that require high explainability. Unlike neural networks, logical theories that underlie the model are often handcrafted using domain expertise, making their development costly and prone to errors. While there are algorithms that learn logical theories from data, they are generally prohibitively expensive, limiting their applicability in real-world settings. Here, we introduce precision and recall for logical rules and define their composition as rule utility - a cost-effective measure of the predictive power of logical theories. We also introduce SPECTRUM, a scalable framework for learning logical theories from relational data. Its scalability derives from a linear-time algorithm for mining recurrent subgraphs in the data graph along with a second algorithm that, using a utility measure that can be computed in linear time, efficiently ranks rules derived from these subgraphs. Finally, we prove theoretical guarantees on the utility of the learnt logical theory. As a result, we demonstrate across various tasks that SPECTRUM scales to larger datasets, often learning more accurate logical theories on CPUs in < 1% the runtime of SOTA neural network approaches on GPUs.