Probabilistic circuits (PCs) are computational graphs encoding probability distributions. PCs guarantee tractable computation of a query class, e.g., marginals, MAP inference, expectations, etc..., if their computational graphs satisfy certain well-defined properties.

Moreover, PCs unify and abstract from several tractable model formalisms proposed so far, e.g., sum-product networks, cutset networks, probabilistic sentential decision diagrams, arithmetic circuits, And/Or graphs, etc...
You can read more about these properties and PCs in this gentle introduction.

This page is a systematic view of the current body of work on PCs, organizing papers by year, model and topic.
To contribute to it, send a pull request to this repo.


Latest publications

[ last update on 07/15/2021]
  • IEEE International Solid- State Circuits Conference (ISSCC)
    PIU: A 248GOPS/W Stream-Based Processor for Irregular Probabilistic Inference Networks Using Precision-Scalable Posit Arithmetic in 28nm
    Shah, Nimish and Galindez Olascoaga, Laura Isabel and Zhao, Shirui and Meert, Wannes and Verhelst, Marian
    [ paper | bibtex | abstract ]
    
              
          
    
              @inproceedings{shah2021piu,
    author= {Shah, Nimish and Olascoaga, Laura Isabel Galindez and Zhao, Shirui and Meert, Wannes and Verhelst, Marian},
    booktitle={2021 IEEE International Solid- State Circuits Conference (ISSCC)},
    title={PIU: A 248GOPS/W Stream-Based Processor for Irregular Probabilistic Inference Networks Using Precision-Scalable Posit Arithmetic in 28nm},
    year={2021},
    volume={64},
    number={},
    pages={150-152},
    doi={10.1109/ISSCC42613.2021.9366061}}
  • PLDI 2021
    SPPL: Probabilistic Programming With Fast Exact Symbolic Inference
    Saad, Feras A. and Rinard, Martin C. and Mansinghka, Vikash K.
    [ paper | code | bibtex | abstract ]
    
              We present the Sum-Product Probabilistic Language (SPPL), a new probabilistic programming language that automatically delivers exact solutions to a broad range of probabilistic inference queries. SPPL translates probabilistic programs into sum-product expressions, a new symbolic representation and associated semantic domain that extends standard sum-product networks to support mixed-type distributions, numeric transformations, logical formulas, and pointwise and set-valued constraints. We formalize SPPL via a novel translation strategy from probabilistic programs to sum-product expressions and give sound exact algorithms for conditioning on and computing probabilities of events. SPPL imposes a collection of restrictions on probabilistic programs to ensure they can be translated into sum-product expressions, which allow the system to leverage new techniques for improving the scalability of translation and inference by automatically exploiting probabilistic structure. We implement a prototype of SPPL with a modular architecture and evaluate it on benchmarks the system targets, showing that it obtains up to 3500x speedups over state-of-the-art symbolic systems on tasks such as verifying the fairness of decision tree classifiers, smoothing hidden Markov models, conditioning transformed random variables, and computing rare event probabilities.
          
    
              @inproceedings{saad2021sppl,
    title = {{SPPL:} Probabilistic Programming with Fast Exact Symbolic Inference},
    author = {Saad, Feras A. and Rinard, Martin C. and Mansinghka, Vikash K.},
    booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
    pages = {804--819},
    numpages = {16},
    year = {2021},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    doi = {10.1145/3453483.3454078},
    isbn = {9781450383912},
    keywords = {probabilistic programming, symbolic execution},
    location = {Virtual, Canada},
    }
  • AAAI Demo track 2021
    Juice: A Julia Package for Logic and Probabilistic Circuits
    Dang, Meihua and Khosravi, Pasha and Liang, Yitao and Vergari, Antonio and Van den Broeck, Guy
    [ paper | bibtex | abstract ]
    
              JUICE is an open-source Julia package providing tools for logic and probabilistic reasoning and learning based on logic circuits (LCs) and probabilistic circuits (PCs). It provides arange of efficient algorithms for probabilistic inference queries, such as computing marginal probabilities (MAR), as well as many more advanced queries. Certain structural circuit proper-ties are needed to achieve this tractability, which JUICE helps validate. Additionally, it supports several parameter and struc-ture learning algorithms proposed in the recent literature. By leveraging parallelism (on both CPU and GPU), JUICE provides a fast implementation of circuit-based algorithms, which makes it suitable for tackling large-scale datasets and models.
          
    
              @inproceedings{dang2021juice, 
    title = {Juice: A Julia Package for Logic and Probabilistic Circuits},
    author = {Dang, Meihua and Khosravi, Pasha and Liang, Yitao and Vergari, Antonio and Van den Broeck, Guy},
    booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (Demo Track)},
    month = {Feb},
    year = {2021}
    }
  • AAAI 2021
    On the Tractability of SHAP Explanations
    Van den Broeck, Guy and Lykov, Anton and Schleich, Maximilian and Suciu, Dan
    [ paper | bibtex | abstract ]
    
              SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.
          
    
              @inproceedings{vandenbroeck2020tractability,
    author = {Van den Broeck, Guy and Lykov, Anton and Schleich, Maximilian and Suciu, Dan},
    title = {On the Tractability of {SHAP} Explanations},
    booktitle = {AAAI},
    year = {2021}
    }
  • AAAI 2021
    Group Fairness by Probabilistic Modeling with Latent Fair Decisions
    Choi, YooJung and Dang, Meihua and Van den Broeck, Guy
    [ paper | bibtex | abstract ]
    
              Machine learning systems are increasingly being used to make impactful decisions such as loan applications and criminal justice risk assessments, and as such, ensuring fairness of these systems is critical. This is often challenging as the labels in the data are biased. This paper studies learning fair probability distributions from biased data by explicitly modeling a latent variable that represents a hidden, unbiased label. In particular, we aim to achieve demographic parity by enforcing certain independencies in the learned model. We also show that group fairness guarantees are meaningful only if the distribution used to provide those guarantees indeed captures the real-world data. In order to closely model the data distribution, we employ probabilistic circuits, an expressive and tractable probabilistic model, and propose an algorithm to learn them from incomplete data. We evaluate our approach on a synthetic dataset in which observed labels indeed come from fair labels but with added bias, and demonstrate that the fair labels are successfully retrieved. Moreover, we show on real-world datasets that our approach not only is a better model than existing methods of how the data was generated but also achieves competitive accuracy.
          
    
              @inproceedings{choi2020group,
    author = {Choi, YooJung and Dang, Meihua and Van den Broeck, Guy},
    title = {Group Fairness by Probabilistic Modeling with Latent Fair Decisions},
    booktitle = {AAAI},
    year = {2020}
    }
  • Thesis
    Sum-Product Networks for Complex Modelling Scenarios
    Trapp, Martin
    [ paper | bibtex | abstract ]
    
              Sum-Product Networks (SPNs) are flexible general-purpose probabilistic models that have received increasing attention due to their attractive inference properties. Even though there exists a large body of work on parameter and structure learning in SPNs, many of the existing approaches focus on rather simple modelling scenarios. For example, in the case of discriminative parameter learning, the labelled training examples are assumed to be abundant, and we generally consider SPNs to be defined only over a finite set of random variables. Moreover, most approaches to construct SPNs in a data-agnostic way rely on heuristic and ad-hoc strategies rather than proposing a principled solution. In this thesis, we examine SPNs for complex modelling scenarios. We are particularly interested in: i) principled semi-supervised parameter learning in SPNs, which guarantees that the learner cannot deteriorate in performance when adding additional unlabelled data, ii) principled structure learning in SPNs that is mathematically sound, protects us from overfitting and enables learning under missing data, and iii) extending the framework of SPNs to model possibly infinitely many random variables, and thus, establishing SPNs as a stochastic process model. As a first main contribution, we introduce an extension of the contrastive pessimistic likelihood for safe semi-supervised parameter learning in SPNs. Our approach is the first semi- supervised learning technique for SPNs, and often obtains a performance that is similar to an SPN trained on a fully labelled datasets. We first derive an objective for generative learning and later extend the approach to discriminative parameter learning. Lastly, we show empirical evidence that safe semi-supervised SPNs perform favourably compared to existing semi-supervised techniques on various classification tasks. The second main contribution of this thesis is the introduction of principled structure learning in SPNs. While there exists a large body of work on structure learning, none of the approaches asks either of the two essential questions: “What is a good structure?” or “What is a principle to derive a good structure?”. We aim to change this practice and introduce a sound, Bayesian formulation for joint parameter and structure learning in SPNs. Our experiments show that this principled approach competes well with the prior art and that we gain several benefits, such as automatic protection against overfitting, robustness under missing data and a natural extension to nonparametric formulations. As a third main contribution, we introduce deep structured mixtures of Gaussian processes, which combine tractable inference in SPNs with exact posterior inference in Gaussian processes. Our approach directly extends SPNs to the stochastic process case by equipping SPNs with Gaussian measures, which correspond to Gaussian processes, as leaves. We show that the resulting model allows a natural interpretation as exact Bayesian model averaging over a rich collection of naive-local expert models. In a series of experiments, we show that the proposed technique outperforms existing expert-based approaches and provides low approximation errors when used as an approximation to a Gaussian process. In addition to the main contributions, we show that gradient-based optimisation in overparameterised SPNs results in intrinsic acceleration effects, which depend directly on the depth of the network. Furthermore, we introduce two formulations for nonparametric SPNs and discuss their advantages and limitations.
          
    
              @phdthesis{trapp2020thesis, 
    title={Sum-Product Networks for Complex Modelling Scenarios},
    author={Trapp, Martin},
    year={2020},
    school={PhD thesis, Graz University of Technology}
    }
  • UAI 2020
    On the Relationship Between Probabilistic Circuits and Determinantal Point Processes
    Zhang, Honghua and Holtzen, Steven and Van den Broeck, Guy
    [ paper | bibtex | abstract ]
    
              Scaling probabilistic models to large realistic problems and datasets is a key challenge in machine learning. Central to this effort is the development of tractable probabilistic models (TPMs): models whose structure guarantees efficient probabilistic inference algorithms. The current landscape of TPMs is fragmented: there exist various kinds of TPMs with different strengths and weaknesses. Two of the most prominent classes of TPMs are determinantal point processes (DPPs) and probabilistic circuits (PCs). This paper provides the first systematic study of their relationship. We propose a unified analysis and shared language for discussing DPPs and PCs. Then we establish theoretical barriers for the unification of these two families, and prove that there are cases where DPPs have no compact representation as a class of PCs. We close with a perspective on the central problem of unifying these tractable models.
          
    
              @inproceedings{zhang2020relationship,
    author = {Zhang, Honghua and Holtzen, Steven and Van den Broeck, Guy},
    title = {On the Relationship Between Probabilistic Circuits and Determinantal
    Point Processes},
    booktitle = {{UAI}},
    series = {Proceedings of Machine Learning Research},
    volume = {124},
    pages = {1188--1197},
    publisher = {{AUAI} Press},
    year = {2020}
    }
  • NeurIPS 2020
    Probabilistic Circuits for Variational Inference in Discrete Graphical Models
    Shih, Andy and Ermon, Stefano
    [ paper | bibtex | abstract ]
    
              Inference in discrete graphical models with variational methods is difficult because of the inability to re-parameterize gradients of the Evidence Lower Bound (ELBO). Many sampling-based methods have been proposed for estimating these gradients, but they suffer from high bias or variance. In this paper, we propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN), to compute ELBO gradients exactly (without sampling) for a certain class of densities. In particular, we show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is a polynomial the corresponding ELBO can be computed analytically. To scale to graphical models with thousands of variables, we develop an efficient and effective construction of selective-SPNs with size O(kn), where n is the number of variables and k is an adjustable hyperparameter. We demonstrate our approach on three types of graphical models -- Ising models, Latent Dirichlet Allocation, and factor graphs from the UAI Inference Competition. Selective-SPNs give a better lower bound than mean-field and structured mean-field, and is competitive with approximations that do not provide a lower bound, such as Loopy Belief Propagation and Tree-Reweighted Belief Propagation. Our results show that probabilistic circuits are promising tools for variational inference in discrete graphical models as they combine tractability and expressivity.
          
    
              @inproceedings{shih2020probabilistic,
    author = {Shih, Andy and Ermon, Stefano},
    title = {Probabilistic Circuits for Variational Inference in Discrete Graphical
    Models},
    booktitle = {NeurIPS},
    year = {2020}
    }
  • DATE 2020
    Acceleration of probabilistic reasoning through custom processor architecture
    Shah, Nimish and Galindez Olascoaga, Laura Isabel and Meert, Wannes and Verhelst, Marian
    [ paper | bibtex | abstract ]
    
              Probabilistic reasoning is an essential tool for robust decision-making systems because of its ability to explicitly handle real-world uncertainty, constraints and causal relations. Consequently, researchers are developing hybrid models by combining Deep Learning with probabilistic reasoning for safety-critical applications like self-driving vehicles, autonomous drones, etc. However, probabilistic reasoning kernels do not execute efficiently on CPUs or GPUs. This paper, therefore, proposes a custom programmable processor to accelerate sum-product networks, an important probabilistic reasoning execution kernel. The processor has an optimized datapath architecture and memory hierarchy optimized for sum-product networks execution. Experimental results show that the processor, while requiring fewer computational and memory units, achieves a 12x throughput benefit over the Nvidia Jetson TX2 embedded GPU platform.
          
    
              @inproceedings{shah2020acceleration,
    author = {Shah, Nimish and Olascoaga, Laura Isabel Galindez and Meert, Wannes and Verhelst, Marian},
    title = {Acceleration of probabilistic reasoning through custom processor architecture},
    booktitle = {{DATE}},
    pages = {322--325},
    publisher = {{IEEE}},
    year = {2020}
    }
  • IDA 2020
    Discriminative Bias for Learning Probabilistic Sentential Decision Diagrams
    Olascoaga, Laura Isabel Galindez and Meert, Wannes and Shah, Nimish and Van den Broeck, Guy and Verhelst, Marian
    [ paper | bibtex | abstract ]
    
              Methods that learn the structure of Probabilistic Sentential Decision Diagrams (PSDD) from data have achieved state-of-the-art performance in tractable learning tasks. These methods learn PSDDs incrementally by optimizing the likelihood of the induced probability distribution given available data and are thus robust against missing values, a relevant trait to address the challenges of embedded applications, such as failing sensors and resource constraints. However PSDDs are outperformed by discriminatively trained models in classification tasks. In this work, we introduce D-LearnPSDD, a learner that improves the classification performance of the LearnPSDD algorithm by introducing a discriminative bias that encodes the conditional relation between the class and feature variables.
          
    
              @inproceedings{olascoaga2020discriminative,
    author = {Olascoaga, Laura Isabel Galindez and Meert, Wannes and Shah, Nimish and Van den Broeck, Guy and Verhelst, Marian},
    title = {Discriminative Bias for Learning Probabilistic Sentential Decision
    Diagrams},
    booktitle = {{IDA}},
    series = {Lecture Notes in Computer Science},
    volume = {12080},
    pages = {184--196},
    publisher = {Springer},
    year = {2020}
    }