Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation

• URL: http://arxiv.org/abs/2312.01520v3
• Date: Mon, 15 Jan 2024 09:03:19 GMT
• Title: Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation
• Authors: Marco Scutari
• Abstract summary: We show how to compute Shannon's entropy and the Kullback-Leibler divergence for BNs under their most common distributional assumptions. We show it is possible to reduce the computational complexity of KL from cubic to quadratic for Gaussian BNs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian networks (BNs) are a foundational model in machine learning and causal inference. Their graphical structure can handle high-dimensional problems, divide them into a sparse collection of smaller ones, underlies Judea Pearl's causality, and determines their explainability and interpretability. Despite their popularity, there are almost no resources in the literature on how to compute Shannon's entropy and the Kullback-Leibler (KL) divergence for BNs under their most common distributional assumptions. In this paper, we provide computationally efficient algorithms for both by leveraging BNs' graphical structure, and we illustrate them with a complete set of numerical examples. In the process, we show it is possible to reduce the computational complexity of KL from cubic to quadratic for Gaussian BNs.

Related papers

• Convergence Guarantees for the DeepWalk Embedding on Block Models [9.898607871253775]
  We show how to use the DeepWalk algorithm on graphs obtained from the Block Model (SBM) Despite being simplistic, the SBM has proved to be a classic model for analyzing algorithms on large graphs.
  arXiv  Detail & Related papers  (2024-10-26T18:35:11Z)
• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  Graph clustering is a fundamental problem in machine learning. Deep learning methods achieve the state-of-the-art results in recent years, but they still cannot work without predefined cluster numbers. We propose to address this problem from a fresh perspective of graph information theory.
  arXiv  Detail & Related papers  (2024-05-20T05:46:41Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Reconstructing Bayesian Networks on a Quantum Annealer [0.0]
  O'Gorman et al. have proposed an algorithm to encode this task, but they have not provided an experimental evaluation of it. We present (i) an implementation in Python of O'Gorman's algorithm, (ii) a divide et impera approach that allows addressing BNSL problems of larger sizes. Results have shown the effectiveness of O'Gorman's formulation for BNSL instances of small sizes, and the superiority of the divide et impera approach on the direct execution of O'Gorman's algorithm.
  arXiv  Detail & Related papers  (2022-04-07T15:53:05Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task. In this work, we propose a new time algorithm for discovering a subset of all possible cluster cuts. We show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem.
  arXiv  Detail & Related papers  (2021-06-23T09:46:11Z)
• Efficient Inference via Universal LSH Kernel [35.22983601434134]
  We propose mathematically provable Representer Sketch, a concise set of count arrays that can approximate the inference procedure with simple hashing computations and aggregations. Representer Sketch builds upon the popular Representer Theorem from kernel literature, hence the name. We show that Representer Sketch achieves up to 114x reduction in storage requirement and 59x reduction in complexity without any drop in accuracy.
  arXiv  Detail & Related papers  (2021-06-21T22:06:32Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  We present a model-agnostic explanation method for image classification based on a hierarchical extension of Shapley coefficients. Unlike other Shapley-based explanation methods, h-Shap is scalable and can be computed without the need of approximation. We compare our hierarchical approach with popular Shapley-based and non-Shapley-based methods on a synthetic dataset, a medical imaging scenario, and a general computer vision problem.
  arXiv  Detail & Related papers  (2021-04-13T13:11:02Z)
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation [1.4416132811087747]
  We propose a parallel algorithm for the contraction of tensor networks using probabilistic models. We apply the resulting algorithm to the simulation of random quantum circuits.
  arXiv  Detail & Related papers  (2020-04-22T23:00: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.