A benchmark for Maximum-a-Posteriori Inference algorithms in discrete Sum-Product Networks
Heitor Reis Ribeiro · 2021
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.