A differential approach to inference in Bayesian networks

By Adnan Darwiche. JACM, 2000

658 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Signal Processing

View Paper: https://www.semanticscholar.org/paper/2da7c1872f2a18ae7187fe1b53ef62e727e3cf22

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Signal Processing

Citations in the corpus

Sum-product networks: A new deep architecture (2011, methodology): “The marginals for the nodes can be derived from these partial derivatives [7].”
Learning the Structure of Sum-Product Networks (2013, background): “SPNs are related to multilinear formulas (Raz, 2004), arithmetic circuits (Darwiche, 2003), AND-OR graphs (Dechter & Mateescu, 2007), and other compact representations.”
On the Robustness of Most Probable Explanations (2006, methodology): “circuit for any Bayesian network in O(n exp(w)) time and space, where n is the number of network variables and w is its treewidth [10].”
A Deep Sum-Product Architecture for Robust Facial Attributes Analysis (2013, methodology): “SPN can be learned with an EM-like algorithm following [5].”
Learning Bayesian networks: approaches and issues (2011, methodology): “2.8 Polynomial compilation A recent technique by Darwiche (2003) and Park and Darwiche (2004) shows that Bayesian networks can be represented as a polynomial.”
Bayesian Networks (2008, positive): “…one to use any variable order instead of insisting on a constrained variable order [121] The probability distribution induced by a Bayesian network can be compiled into an arithmetic circuit, allowing various probabilistic queries to be answered in time linear in the compiled circuit size [41].”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, methodology): “…the space of possible inside algorithms (Eisner and Blatz, 2007); • how to convert an inside algorithm into variant algorithms such as Viterbi parsing, k -best parsing, and recognition (Goodman, 1999); • how to apply the same ideas to graphical models (Aji and McEliece, 2000; Darwiche, 2003).”
Propositional Knowledge Representation and Reasoning in Restricted Boltzmann Machines. (2017, background): “Besides the logical knowledge we study here, some other work also show the advantage of learning structural knowledge in graphical models, especially for tractable inference (Poon and Domingos 2011; Darwiche 2003).”
Discriminative Learning of Sum-Product Networks (2012, methodology): “The foundation for their work lies in Darwiche’s network polynomial [14].”
Faster Attend-Infer-Repeat with Tractable Probabilistic Models (2019, methodology): “This way, SPNs can be scaled to sizes similar to neural networks, and can fit highdimensional densities, despite using a random structure.”
Right for the Right Concept: Revising Neuro-Symbolic Concepts by Interacting with their Explanations (2020, background): “Truly rule-based classifiers [38, 29], logic circuits [26], or probabilistic approaches [5, 37, 19, 30], are principally viable alternatives for the Set Transformer, though it remains preferable for this module to handle unordered sets.”
A Semantic Loss Function for Deep Learning with Symbolic Knowledge (2017, background): “Furthermore, we know of circuit languages that compute WMCs, and that are amenable to backpropagation (Darwiche, 2003).”
Importance sampling-based estimation over AND/OR search spaces for graphical models (2012, background): “…that for a given set of samples, the variance of the AND/OR sample tree mean is less than or equal to the variance of the AND/OR sample tree mean defined relative to any topological linearization w.r.t. any node in the pseudo tree, and in particular to the variance of the OR sample tree mean.”
Online Algorithms for Sum-Product Networks with Continuous Variables (2016, methodology): “In fact, SPNs are equivalent to arithmetic circuits (ACs) (Darwiche, 2003; Rooshenas and Lowd, 2014) and SPNs can be converted into Bayesian networks (BNs) (Zhao et al., 2015) (and vice-versa).”
Three Modern Roles for Logic in AI (2020, methodology): “If they are also smooth [25], a property that can be enforced in quadratic time, d-DNNF circuits allow one to perform weighted model counting (WMC) in linear time.”
On probabilistic inference by weighted model counting (2008, methodology): “This allows the AC to simultaneously compute the probability of evidence and posterior marginals over all network variables, in time linear in the AC size [36].”