Sum-Product Network (SPN) is a relatively new class of probabilistic graphical models. They differ from other probabilistic graphical models by allowing explicit representation of context-sensitive independence and marginal inference computation in linear time. Bayesian Networks and Markov Networks, for example, require #P-hard effort for performing marginal inference. However, it is still NP-hard to find the most probable configuration for a set of variables in an SPN, and there is currently a shortage of efficient techniques to solve the problem. A widely employed technique for solving NP-hard optimization problems consists in translating them into Mixed-Integer Linear Programming (MILP) programs, which hence can be solved by highly efficient commercial solvers. Besides harvesting the power of current solvers, formulating the problem as a MILP program immediately allows us to obtain an anytime algorithm that continuously improves its solution as more resources are given (time and memory), and can be stopped at any time with a feasible solution with error bounds. In this work, we developed a new algorithm that finds the most probable configuration for a set of variables in SPNs (Maximum A Posteriori inference) by reformulating it as a MILP program. This translation is rather intricate and relies on several results scattered throughout this field of study, such as the reformulation of SPNs as Bayesian Networks with latent variables, the compact representation of conditional probability tables through Algebraic Decision Diagrams and the symbolic manipulation of multilinear expressions by Parameterized Algebraic Decision Diagrams.

Rede Soma-Produto (SPN) é uma classe de modelos probabilísticos baseados em grafos relativamente nova. Elas diferem de outros modelos probabilísticos por permitir a representação explícita de independência sensível a contexto e a computação de inferência marginal em tempo linear. Redes Bayesianas e redes de Markov, por exemplo, exigem esforço #P-difícil para computar inferência marginal. Entretanto, continua sendo NP-difícil encontrar a configuração mais provável para um conjunto de variáveis em uma SPN, e atualmente há uma escassez de técnicas eficientes que solucionam o problema. Uma técnica amplamente utilizada para solucionar problemas de otimização NP-difíceis consiste em transformá-los em um programa de Programação Linear Inteira Mista (MILP), que então poderia ser solucionado por otimizadores de alta performance disponíveis comercialmente. Além de aproveitar o potencial dos otimizadores atuais, formular o problema como um programa MILP nos permite obter um algoritmo anytime que continuamente encontra soluções melhores quanto mais recursos (tempo e memória) forem disponibilizados, e pode ser interrompido a qualquer momento obtendo-se uma solução válida com margens de erro. Neste trabalho nós desenvolvemos um novo algoritmo que soluciona o problema de computar a configuração mais provável (inferência de Máximo A Posteriori) para um conjunto de variáveis em SPNs através de sua reformulação como um programa MILP. Esta reformulação é consideravelmente complexa e se baseia em diversos resultados dispersos pela literatura, tal como a reformulação de SPNs em Redes Bayesianas com variáveis latentes, a representação compacta das tabelas de probabilidades através de Diagramas de Decisão Algébrica, e manipulações simbólicas de expressões multilineares na forma de Diagramas de Decisão Algébrica Parametrizados.