The solution to Maximum-a-Posteriori Inference problems in Sum-Product Networks provides the most probable configuration of the Random Variables encoded in its structure; a key step in Probabilistic reasoning that can be used for many applications, such as image auto-completion. It has been proven that this problem is NP-Hard (even to approximate) in Sum-Product Networks. Multiple algorithms have been developed to reach either approximate or exact solutions to this problem, but the experiments have been limited. In this Dissertation, we provide descriptions, analysis, and a benchmark for experimental testing for algorithms that solve this problem. We conclude that, given limited time, a Local Search algorithm starting with a solution found by the Argmax-Product algorithm reaches, on average, better results on the tested datasets.

A solução para problemas de Inferência de Maximum-a-Posteriori em redes de Soma-Produto resultam na configuração mais provável das Variáveis Aleatórias representadas em sua estrutura; um passo importante em raciocínio probabilístico que pode ser usado para muitas aplicações, como preenchimento automático de imagens. Já foi provado que este problema é NP-difícil (até para aproximar) em redes de Soma-Produto. Vários algoritmos já foram desenvolvidos para obter uma solução boa ou exata para esse problema, mas os experimentos realizados até agora foram limitados. Nesta dissertação nós fornecemos descrições, análises, e um benchmark para realizar mais testes experimentais para algoritmos que resolvem esse problema. Nós concluímos que, dada uma janela de tempo limitada, um algoritmo de Busca Local iniciado com uma solução retornada pelo algoritmo Argmax-Product alcança, em média, os melhores resultados nos conjuntos de dados testados.