A differential approach to inference in Bayesian networks

We present a new approach to inference in Bayesian networks, which is based on representing the network using a polynomial and then retrieving answers to probabilistic queries by evaluating and differentiating the polynomial. The network polynomial itself is exponential in size, but we show how it can be computed efficiently using an arithmetic circuit that can be evaluated and differentiated in time and space linear in the circuit size. The proposed framework for inference subsumes one of the most influential methods for inference in Bayesian networks, known as the tree-clustering or jointree method, which provides a deeper understanding of this classical method and lifts its desirable characteristics to a much more general setting. We discuss some theoretical and practical implications of this subsumption.

• Publication year

  2000

• Venue

  JACM

• Publication date

  2000-06-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/765568.765570arXiv 1301.3847
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximations in Bayesian Belief Universe for Knowledge Based Systems

  2013cited by this paper
• A differential semantics for jointree algorithms

  2004cited by this paper
• A Logical Approach to Factoring Belief Networks

  2002cited by this paper
• MAP Complexity Results and Approximation Methods

  2002cited by this paper
• A Knowledge Compilation Map

  2002cited by this paper
• A compiler for deterministic, decomposable negation normal form

  2002cited by this paper
• Approximating MAP using Local Search

  2001cited by this paper
• Probabilistic Networks and Expert Systems

  2001cited by this paper
• Recursive conditioning

  2001cited by this paper
• When do Numbers Really Matter?

  2001cited by this paper
• Making Sensitivity Analysis Computationally Efficient

  2000cited by this paper
• Using sensitivity analysis for efficient quantification of a belief network

  1999cited by this paper
• Probabilistic Networks and Expert Systems

  1999cited by this paper
• Gradient Descent Training of Bayesian Networks

  1999cited by this paper
• Sensitivity analysis in discrete Bayesian networks

  1997cited by this paper
• Goal Oriented Symbolic Propagation in Bayesian Networks

  1996cited by this paper
• Query DAGs: A practical paradigm for implementing belief-network inference

  1996cited by this paper
• Exploiting Causal Independence in Bayesian Network Inference

  1996cited by this paper
• Bucket elimination: A unifying framework for probabilistic inference

  1996cited by this paper
• Inference in belief networks: A procedural guide

  1996cited by this paper
• The EM algorithm for graphical association models with missing data

  1995cited by this paper
• Sensitivity analysis for probability assessments in Bayesian networks

  1995cited by this paper
• Local Learning in Probabilistic Networks with Hidden Variables

  1995cited by this paper
• A Tourist Guide through Treewidth

  1993cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993cited by this paper
• Algebraic Complexity Theory

  1991cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• Graph minors. IV. Tree-width and well-quasi-ordering

  1990cited by this paper
• Symbolic Probabilistic Inference in Belief Networks

  1990cited by this paper
• Probabilistic reasoning in intelligent systems - networks of plausible inference

  1989influential reference
• Path Problems in Graphs

  1989cited by this paper
• Chapter 2 – BAYESIAN INFERENCE

  1988influential reference
• Algebraic complexity theory

  1988cited by this paper
• Graph-Based Algorithms for Boolean Function Manipulation

  1986cited by this paper
• Propagating Belief Functions with Local Computations

  1986cited by this paper
• Simultaneous computation of functions, partial derivatives and estimates of rounding errors —Complexity and practicality—

  1984influential reference
• First Partial Differentiation by Computer With an Application to Categorical Data Analysis

  1984cited by this paper

• Bayesian networks: Exact inference via macro-node polytrees

  2026cites this paper
• Reactive Knowledge Representation and Asynchronous Reasoning

  2026cites this paper
• Causal Neural Probabilistic Circuits

  2026cites this paper
• Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

  2026influential citation
• Probably Approximately Correct Maximum A Posteriori Inference

  2026cites this paper
• Deep probabilistic circuits for efficient uncertainty handling in learning systems

  2026cites this paper
• PAR: Plausibility-aware Amortized Recourse Generation

  2026cites this paper
• On Fast arc-reversal

  2025cites this paper
• Hardware-efficient tractable probabilistic inference for TinyML Neurosymbolic AI applications

  2025cites this paper
• Scaling Probabilistic Circuits via Monarch Matrices

  2025cites this paper
• Structural Causal Circuits: Probabilistic Circuits Climbing All Rungs of Pearl's Ladder of Causation

  2025cites this paper
• Backpropagation from KL Projections: Differential and Exact I-Projection Correspondences

  2025cites this paper
• Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms

  2025cites this paper
• Exact Soft Analytical Side-Channel Attacks using Tractable Circuits

  2025cites this paper
• How to Square Tensor Networks and Circuits Without Squaring Them

  2025cites this paper
• QuantTPM: Efficient Mixed-Precision Quantization Framework for Tractable Probabilistic Models

  2025cites this paper
• The Gradient of Algebraic Model Counting

  2025cites this paper
• On the Hardness of Approximating Distributions with Tractable Probabilistic Models

  2025cites this paper
• Soft learning probabilistic circuits

  2025cites this paper
• Enhancing and Evaluating Probabilistic Circuits for High-Resolution Lossless Image Compression

  2025cites this paper
• The DeepLog Neurosymbolic Machine

  2025cites this paper
• Interplay between Bayesian neural networks and deep learning: A survey

  2025cites this paper
• CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning

  2025cites this paper
• Beyond Dynamic Bayesian Networks: Fusing Temporal Logic Monitors with Probabilistic Diagnosis (Short Paper)

  2025influential citation
• Approximate Bayesian Inference via Bitstring Representations

  2025cites this paper
• On the Hardness of Approximating Distributions with Probabilistic Circuits

  2025cites this paper
• Counterfactual Explanations in Medical Imaging: Exploring SPN-Guided Latent Space Manipulation

  2025cites this paper
• A Quantum Information Theoretic Approach to Tractable Probabilistic Models

  2025cites this paper
• Direction of impact for explainable risk assessment modeling

  2025cites this paper
• Tractable Representation Learning with Probabilistic Circuits

  2025cites this paper
• Tractable Sharpness-Aware Learning of Probabilistic Circuits

  2025cites this paper
• Sum of Squares Circuits

  2024cites this paper
• Exploring Sum-Product Networks for Image Classification. Applications

  2024cites this paper
• On the Importance of the Execution Schedule for Bayesian Inference

  2024cites this paper
• Probabilistic Circuits for Cumulative Distribution Functions

  2024cites this paper
• KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI

  2024cites this paper
• Linear Uncertainty Quantification of Graphical Model Inference

  2024cites this paper
• Constrained Identifiability of Causal Effects

  2024cites this paper
• A Compositional Atlas for Algebraic Circuits

  2024cites this paper
• Optimal Transport for Probabilistic Circuits

  2024cites this paper
• Learning Distributionally Robust Tractable Probabilistic Models in Continuous Domains

  2024cites this paper
• Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs

  2024cites this paper
• Scaling Tractable Probabilistic Circuits: A Systems Perspective

  2024cites this paper
• R2-Guard: Robust Reasoning Enabled LLM Guardrail via Knowledge-Enhanced Logical Reasoning

  2024cites this paper
• Knowledge compilation

  2024cites this paper
• Towards an effective practice of learning from data and knowledge

  2024cites this paper
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming

  2024cites this paper
• What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?

  2024cites this paper
• Restructuring Tractable Probabilistic Circuits

  2024cites this paper
• COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits

  2024cites this paper
• On Hardware-efficient Inference in Probabilistic Circuits

  2024cites this paper
• Building Expressive and Tractable Probabilistic Generative Models: A Review

  2024cites this paper
• Identifying Causal Effects Under Functional Dependencies

  2024cites this paper
• Automated Reasoning in Systems Biology: a Necessity for Precision Medicine

  2024cites this paper
• Neural Network Approximators for Marginal MAP in Probabilistic Circuits

  2024cites this paper
• Probabilistic Circuits with Constraints via Convex Optimization

  2024cites this paper
• Probabilistic Neural Circuits

  2024influential citation
• On the Relationship Between Monotone and Squared Probabilistic Circuits

  2024cites this paper
• A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata

  2024cites this paper
• Logically Consistent Language Models via Neuro-Symbolic Integration

  2024cites this paper
• Polynomial Semantics of Tractable Probabilistic Circuits

  2024influential citation
• Causal Unit Selection using Tractable Arithmetic Circuits

  2024influential citation
• A multidimensional Bayesian architecture for real-time anomaly detection and recovery in mobile robot sensory systems

  2023cites this paper
• Engineering Applications of Artificial Intelligence

  2023cites this paper
• Probabilistic Flow Circuits: Towards Unified Deep Models for Tractable Probabilistic Inference

  2023cites this paper
• Efficient approximation of neural population structure and correlations with probabilistic circuits

  2023cites this paper
• TaxoKnow: Taxonomy as Prior Knowledge in the Loss Function of Multi-class Classification

  2023cites this paper
• SynJax: Structured Probability Distributions for JAX

  2023cites this paper
• Knowledge Intensive Learning of Cutset Networks

  2023cites this paper
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models

  2023cites this paper
• A survey of sum-product networks structural learning

  2023cites this paper
• Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks

  2023cites this paper
• On inference and learning with probabilistic generating circuits

  2023cites this paper
• Bayesian Structure Scores for Probabilistic Circuits

  2023influential citation
• Mixtures of All Trees

  2023cites this paper
• The YODO algorithm: An efficient computational framework for sensitivity analysis in Bayesian networks

  2023cites this paper
• Improved Encoding of Possibilistic Networks in CNF Using Quine-McCluskey Algorithm

  2023cites this paper
• Model Transparency: Why Do We Care?

  2023cites this paper
• Characteristic Circuits

  2023cites this paper
• A Formal Account for Reasoning About Uncertain Probabilities in Intelligence Analysis

  2023cites this paper
• Not All Causal Inference is the Same

  2023cites this paper
• Pruning-Based Extraction of Descriptions from Probabilistic Circuits

  2023cites this paper
• Qualitative global sensitivity analysis for probabilistic circuits

  2023cites this paper
• Explainable Activity Recognition in Videos using Deep Learning and Tractable Probabilistic Models

  2023cites this paper
• Transparency in Sum-Product Network Decompilation

  2023influential citation
• Finding maxima of Gaussian Sum-Product Networks

  2023cites this paper
• Safe Reinforcement Learning via Probabilistic Logic Shields

  2023cites this paper
• Generative Marginalization Models

  2023cites this paper
• Continuously Parameterized Mixture Models

  2023cites this paper
• USING BAYESIAN METHODS IN THE TASK OF MODELING THE PATIENTS' PHARMACORESISTANCE DEVELOPMENT

  2022cites this paper
• Inference and Learning with Model Uncertainty in Probabilistic Logic Programs

  2022cites this paper
• You Only Derive Once (YODO): Automatic Differentiation for Efficient Sensitivity Analysis in Bayesian Networks

  2022cites this paper
• Variational Flow Graphical Model

  2022cites this paper
• Robustness Guarantees for Credal Bayesian Networks via Constraint Relaxation over Probabilistic Circuits

  2022cites this paper
• Learning Tractable Probabilistic Models from Inconsistent Local Estimates

  2022cites this paper
• Gradient-based Counterfactual Explanations using Tractable Probabilistic Models

  2022cites this paper
• Tractable Inference for Hybrid Bayesian Networks with NAT-Modeled Dynamic Discretization

  2022cites this paper
• Tractable Boolean and Arithmetic Circuits

  2022influential citation
• Neuro-Symbolic Entropy Regularization

  2022cites this paper
• Causal Inference Using Tractable Circuits

  2022influential citation