Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models

• URL: http://arxiv.org/abs/2302.04599v3
• Date: Sun, 18 Jun 2023 15:27:50 GMT
• Title: Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models
• Authors: Jonathan Feldstein, Dominic Phillips and Efthymia Tsamoura
• Abstract summary: Structure learning is a core problem in AI central to the fields of neuro-symbolic AI and statistical relational learning. We present the first principled approach for mining structural motifs in lifted graphical models. We 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.
• Score: 5.317624228510748
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Efficiently Learning Probabilistic Logical Models by Cheaply Ranking Mined Rules [9.303501974597548]
  We introduce precision and recall for logical rules and define their composition as rule utility. We introduce SPECTRUM, a scalable framework for learning logical models from relational data.
  arXiv  Detail & Related papers  (2024-09-24T16:54:12Z)
• Surprisal Driven $k$-NN for Robust and Interpretable Nonparametric Learning [1.4293924404819704]
  We shed new light on the traditional nearest neighbors algorithm from the perspective of information theory. We propose a robust and interpretable framework for tasks such as classification, regression, density estimation, and anomaly detection using a single model. Our work showcases the architecture's versatility by achieving state-of-the-art results in classification and anomaly detection.
  arXiv  Detail & Related papers  (2023-11-17T00:35:38Z)
• Homological Convolutional Neural Networks [4.615338063719135]
  We propose a novel deep learning architecture that exploits the data structural organization through topologically constrained network representations. We test our model on 18 benchmark datasets against 5 classic machine learning and 3 deep learning models.
  arXiv  Detail & Related papers  (2023-08-26T08:48:51Z)
• RandomSCM: interpretable ensembles of sparse classifiers tailored for omics data [59.4141628321618]
  We propose an ensemble learning algorithm based on conjunctions or disjunctions of decision rules. The interpretability of the models makes them useful for biomarker discovery and patterns discovery in high dimensional data.
  arXiv  Detail & Related papers  (2022-08-11T13:55:04Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Network Gradient Descent Algorithm for Decentralized Federated Learning [0.2867517731896504]
  We study a fully decentralized federated learning algorithm, which is a novel descent gradient algorithm executed on a communication-based network. In the NGD method, only statistics (e.g., parameter estimates) need to be communicated, minimizing the risk of privacy. We find that both the learning rate and the network structure play significant roles in determining the NGD estimator's statistical efficiency.
  arXiv  Detail & Related papers  (2022-05-06T02:53:31Z)
• Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach [80.8446673089281]
  We propose a new learning paradigm with graph representation and learning. Our framework contains two modules: 1) a backbone network (e.g., feedforward neural nets) as a lower model takes features as input and outputs predicted labels; 2) a graph neural network as an upper model learns to extrapolate embeddings for new features via message passing over a feature-data graph built from observed data.
  arXiv  Detail & Related papers  (2021-10-09T09:02:45Z)
• Learning Neural Causal Models with Active Interventions [83.44636110899742]
  We introduce an active intervention-targeting mechanism which enables a quick identification of the underlying causal structure of the data-generating process. Our method significantly reduces the required number of interactions compared with random intervention targeting. We demonstrate superior performance on multiple benchmarks from simulated to real-world data.
  arXiv  Detail & Related papers  (2021-09-06T13:10:37Z)
• Model-Based Deep Learning [155.063817656602]
  Signal processing, communications, and control have traditionally relied on classical statistical modeling techniques. Deep neural networks (DNNs) use generic architectures which learn to operate from data, and demonstrate excellent performance. We are interested in hybrid techniques that combine principled mathematical models with data-driven systems to benefit from the advantages of both approaches.
  arXiv  Detail & Related papers  (2020-12-15T16:29:49Z)
• A Simple Approach to Case-Based Reasoning in Knowledge Bases [56.661396189466664]
  We present a surprisingly simple yet accurate approach to reasoning in knowledge graphs (KGs) that requires emphno training, and is reminiscent of case-based reasoning in classical artificial intelligence (AI) Consider the task of finding a target entity given a source entity and a binary relation. Our non-parametric approach derives crisp logical rules for each query by finding multiple textitgraph path patterns that connect similar source entities through the given relation.
  arXiv  Detail & Related papers  (2020-06-25T06:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.