This content will become publicly available on March 25, 2025
Probabilistic circuits (PCs) such as sumproduct networks efficiently represent large multivariate probability distributions. They are preferred in practice over other probabilistic representations, such as Bayesian and Markov networks, because PCs can solve marginal inference (MAR) tasks in time that scales linearly in the size of the network. Unfortunately, the most probable explanation (MPE) task and its generalization, the marginal maximumaposteriori (MMAP) inference task remain NPhard in these models. Inspired by the recent work on using neural networks for generating nearoptimal solutions to optimization problems such as integer linear programming, we propose an approach that uses neural networks to approximate MMAP inference in PCs. The key idea in our approach is to approximate the cost of an assignment to the query variables using a continuous multilinear function and then use the latter as a loss function. The two main benefits of our new method are that it is selfsupervised, and after the neural network is learned, it requires only linear time to output a solution. We evaluate our new approach on several benchmark datasets and show that it outperforms three competing linear time approximations: maxproduct inference, maxmarginal inference, and sequential estimation, which are used in practice to solve MMAP tasks in PCs.
more » « less Award ID(s):
 1652835
 NSFPAR ID:
 10497335
 Publisher / Repository:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Date Published:
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 38
 Issue:
 10
 ISSN:
 21595399
 Page Range / eLocation ID:
 10918 to 10926
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

It is well known that the problems of stochastic planning and probabilistic inference are closely related. This paper makes two contributions in this context. The first is to provide an analysis of the recently developed SOGBOFA heuristic planning algorithm that was shown to be effective for problems with large factored state and action spaces. It is shown that SOGBOFA can be seen as a specialized inference algorithm that computes its solutions through a combination of a symbolic variant of belief propagation and gradient ascent. The second contribution is a new solver for Marginal MAP (MMAP) inference. We introduce a new reduction from MMAP to maximum expected utility problems which are suitable for the symbolic computation in SOGBOFA. This yields a novel algebraic gradientbased solver (AGS) for MMAP. An experimental evaluation illustrates the potential of AGS in solving difficult MMAP problems.more » « less

null (Ed.)
Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly.However, it often requires exponentially high levels of memory (in the inducedwidth) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE.The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function.We provide a proofofconcept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current stateoftheart approaches for approximating BE (e.g. the minibucket schemes), especially when problems are sufficiently hard.

Sumproduct networks have recently emerged as an attractive representation due to their dual view as a special type of deep neural network with clear semantics and a special type of probabilistic graphical model for which inference is always tractable. Those properties follow from some conditions (i.e., completeness and decomposability) that must be respected by the structure of the network. As a result, it is not easy to specify a valid sumproduct network by hand and therefore structure learning techniques are typically used in practice. This paper describes a new online structure learning technique for feedforward and recurrent SPNs. The algorithm is demonstrated on realworld datasets with continuous features for which it is not clear what network architecture might be best, including sequence datasets of varying length.more » « less

A streaming probabilistic program receives a stream of observations and produces a stream of distributions that are conditioned on these observations. Efficient inference is often possible in a streaming context using RaoBlackwellized particle filters (RBPFs), which exactly solve inference problems when possible and fall back on sampling approximations when necessary. While RBPFs can be implemented by hand to provide efficient inference, the goal of streaming probabilistic programming is to automatically generate such efficient inference implementations given input probabilistic programs. In this work, we propose semisymbolic inference, a technique for executing probabilistic programs using a runtime inference system that automatically implements RaoBlackwellized particle filtering. To perform exact and approximate inference together, the semisymbolic inference system manipulates symbolic distributions to perform exact inference when possible and falls back on approximate sampling when necessary. This approach enables the system to implement the same RBPF a developer would write by hand. To ensure this, we identify closed families of distributions – such as linearGaussian and finite discrete models – on which the inference system guarantees exact inference. We have implemented the runtime inference system in the ProbZelus streaming probabilistic programming language. Despite an average 1.6× slowdown compared to the state of the art on existing benchmarks, our evaluation shows that speedups of 3×87× are obtainable on a new set of challenging benchmarks we have designed to exploit closed families.more » « less

null (Ed.)Sumproduct networks (SPN) are knowledge compilation models and are related to other graphical models for efficient probabilistic inference such as arithmetic circuits and AND/OR graphs. Recent investigations into generalizing SPNs have yielded sumproductmax networks (SPMN) which offer a datadriven alternative for decision making that has predominantly relied on handcrafted models. However, SPMNs are not suited for decisiontheoretic planning which involves sequential decision making over multiple time steps. In this paper, we present recurrent SPMNs (RSPMN) that learn from and model decisionmaking data over time. RSPMNs utilize a template network that is unfolded as needed depending on the length of the data sequence. This is significant as RSPMNs not only inherit the benefits of SPNs in being data driven and mostly tractable, they are also well suited for planning problems. We establish soundness conditions on the template network, which guarantee that the resulting SPMN is valid, and present a structure learning algorithm to learn a sound template. RSPMNs learned on a testbed of data sets, some generated using RDDLSim, yield MEUs and policies that are close to the optimal on perfectlyobserved domains and easily improve on a recent batchconstrained RL method, which is important because RSPMNs offer a new modelbased approach to offline RL.more » « less