Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models
Preprint
Abstract
Structure learning is a core problem in AI central to the fields of neuro-symbolic AI and statistical relational learning. It consists in automatically learning a logical theory from data. The basis for structure learning is mining repeating patterns in the data, known as structural motifs. Finding these patterns reduces the exponential search space and therefore guides the learning of formulas. Despite the importance of motif learning, it is still not well understood. We present the first principled approach for mining structural motifs in lifted graphical models, languages that blend first-order logic with probabilistic models, which uses a stochastic process to measure the similarity of entities in the data. Our first contribution is an algorithm, which depends on two intuitive hyperparameters: one controlling the uncertainty in the entity similarity measure, and one controlling the softness of the resulting rules. Our second contribution is a preprocessing step where we perform hierarchical clustering on the data to reduce the search space to the most relevant data. Our third contribution is to introduce an O(n ln n) (in the size of the entities in the data) algorithm for clustering structurally-related data. We evaluate our approach using standard benchmarks and show that we outperform state-of-the-art structure learning approaches by up to 6% in terms of accuracy and up to 80% in terms of runtime.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- TensorLog: A Probabilistic Database Implemented Using Deep-Learning InfrastructureJournal of Artificial Intelligence Research, 2020
- Learning Explanatory Rules from Noisy DataJournal of Artificial Intelligence Research, 2018
- Deep Probabilistic Logic: A Unifying Framework for Indirect Supervision2018
- Cheeger’s cut, maxcut and the spectral theory of 1-Laplacian on graphsScience China Mathematics, 2017
- Harnessing Deep Neural Networks with Logic Rules2016
- Unifying logic and probabilityCommunications of the ACM, 2015
- Gradient-based boosting for statistical relational learning: the Markov logic network and missing data casesMachine Learning, 2015
- Prediction of protein β-residue contacts by Markov logic networks with grounding-specific weightsBioinformatics, 2009
- Greedy function approximation: A gradient boosting machine.The Annals of Statistics, 2001
- The distribution function of a linear combination of chi-squaresComputers & Mathematics with Applications, 1984