An Algebraic View of MAP Inference in Probabilistic Answer Set Programs

Maximum-a-Posteriori (MAP) inference is a crucial problem in Artificial Intelligence, which requires both marginalization and maximization, and asks for the most probable value for a given set of variables such that an evidence holds. Several languages within the Statistical Relational Artificial Intelligence landscape support the encoding of MAP. Here, we focus on Probabilistic Answer Set Programming, consider the credal and smProbLog semantics, and introduce a three-level algebraic model counting representation for MAP. We implemented our approach on top of a state-of-the-art solver and compared it with existing solutions, showing the competitive performance of our proposal, even against less general tools.