Maximum A Posteriori Inference in Sum-Product Networks


  • Jun Mei ShanghaiTech University
  • Yong Jiang ShanghaiTech University
  • Kewei Tu ShanghaiTech University


Sum-Product Networks


Sum-product networks (SPNs) are a class of probabilistic graphical models that allow tractable marginal inference. However, the maximum a posteriori (MAP) inference in SPNs is NP-hard. We investigate MAP inference in SPNs from both theoretical and algorithmic perspectives. For the theoretical part, we reduce general MAP inference to its special case without evidence and hidden variables; we also show that it is NP-hard to approximate the MAP problem to 2 for fixed 0 ≤ ε < 1, where n is the input size. For the algorithmic part, we first present an exact MAP solver that runs reasonably fast and could handle SPNs with up to 1k variables and 150k arcs in our experiments. We then present a new approximate MAP solver with a good balance between speed and accuracy, and our comprehensive experiments on real-world datasets show that it has better overall performance than existing approximate solvers.




How to Cite

Mei, J., Jiang, Y., & Tu, K. (2018). Maximum A Posteriori Inference in Sum-Product Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from



AAAI Technical Track: Knowledge Representation and Reasoning