Neural Network Approximators for Marginal MAP in Probabilistic Circuits
Shivvrat Arya Tahrima Rahman Vibhav Gogate
Probabilistic circuits (PCs) such as sum-product networks efficiently
represent large multi-variate 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
maximum-a-posteriori (MAP) and marginal MAP (MMAP) tasks remain NP-hard in
these models. Inspired by the recent work on using neural networks for
generating near-optimal solutions to optimization problems such as integer
linear programming, we propose an approach that uses neural networks to
approximate (M)MAP 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 self-supervised 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, max-product inference,
max-marginal inference and sequential estimation, which are used in practice to
solve MMAP tasks in PCs.