Maximum A Posteriori Inference in 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^{n^\epsilon}$ for fixed $0 \leq \epsilon < 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.
