Scalable Bayesian Network Structure Learning Using Tsetlin Machine to Constrain the Search Space

• URL: http://arxiv.org/abs/2511.19273v1
• Date: Mon, 24 Nov 2025 16:23:19 GMT
• Title: Scalable Bayesian Network Structure Learning Using Tsetlin Machine to Constrain the Search Space
• Authors: Kunal Dumbre, Lei Jiao, Ole-Christoffer Granmo,
• Abstract summary: The PC algorithm is a widely used method in causal inference for learning the structure of Bayesian networks.<n>Despite its popularity, the PC algorithm suffers from significant time complexity, particularly as the size of the dataset increases.<n>We propose a novel approach that utilise the Tsetlin Machine (TM) to construct Bayesian structures more efficiently.
• Score: 10.753354249346073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The PC algorithm is a widely used method in causal inference for learning the structure of Bayesian networks. Despite its popularity, the PC algorithm suffers from significant time complexity, particularly as the size of the dataset increases, which limits its applicability in large-scale real-world problems. In this study, we propose a novel approach that utilises the Tsetlin Machine (TM) to construct Bayesian structures more efficiently. Our method leverages the most significant literals extracted from the TM and performs conditional independence (CI) tests on these selected literals instead of the full set of variables, resulting in a considerable reduction in computational time. We implemented our approach and compared it with various state-of-the-art methods. Our evaluation includes categorical datasets from the bnlearn repository, such as Munin1, Hepar2. The findings indicate that the proposed TM-based method not only reduces computational complexity but also maintains competitive accuracy in causal discovery, making it a viable alternative to traditional PC algorithm implementations by offering improved efficiency without compromising performance.

Related papers

• Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
  Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge.<n>Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data.<n>We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
  arXiv  Detail & Related papers  (2024-12-10T12:36:35Z)
• An Efficient Procedure for Computing Bayesian Network Structure Learning [0.9208007322096532]
  We propose a globally optimal Bayesian network structure discovery algorithm based on a progressively leveled scoring approach. Experimental results indicate that our method, when using only memory, not only reduces peak memory usage but also improves computational efficiency.
  arXiv  Detail & Related papers  (2024-07-24T07:59:18Z)
• Machine Learning Training Optimization using the Barycentric Correction Procedure [0.0]
  This study proposes combining machine learning algorithms with an efficient methodology known as the barycentric correction procedure (BCP) It was found that this combination provides significant benefits related to time in synthetic and real data without losing accuracy when the number of instances and dimensions increases.
  arXiv  Detail & Related papers  (2024-03-01T13:56:36Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Scalable Batch Acquisition for Deep Bayesian Active Learning [70.68403899432198]
  In deep active learning, it is important to choose multiple examples to markup at each step. Existing solutions to this problem, such as BatchBALD, have significant limitations in selecting a large number of examples. We present the Large BatchBALD algorithm, which aims to achieve comparable quality while being more computationally efficient.
  arXiv  Detail & Related papers  (2023-01-13T11:45:17Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• A Sparse Structure Learning Algorithm for Bayesian Network Identification from Discrete High-Dimensional Data [0.40611352512781856]
  This paper addresses the problem of learning a sparse structure Bayesian network from high-dimensional discrete data. We propose a score function that satisfies the sparsity and the DAG property simultaneously. Specifically, we use a variance reducing method in our optimization algorithm to make the algorithm work efficiently in high-dimensional data.
  arXiv  Detail & Related papers  (2021-08-21T12:21:01Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  Kolmogorov model (KM) is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. We propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. It is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds $80%$.
  arXiv  Detail & Related papers  (2021-07-11T10:33:02Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
  arXiv  Detail & Related papers  (2020-05-22T23:07:42Z)

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.