Focused most probable world computations in probabilistic logic programs

Gerardo I. Simari, Maria Vanina Martinez, Amy Sliva, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


The "Most Probable World" (MPW) problem in probabilistic logic programming (PLPs) is that of finding a possible world with the highest probability. Past work has shown that this problem is computationally intractable and involves solving exponentially many linear programs, each of which is of exponential size. In this paper, we study what happens when the user focuses his interest on a set of atoms in such a PLP. We show that we can significantly reduce the number of worlds to be considered by defining a "reduced" linear program whose solution is in one-one correspondence with the exact solution to the MPW problem. However, the problem is still intractable. We develop a Monte Carlo sampling approach that enables us to build a quick approximation of the reduced linear program that allows us to estimate (inexactly) the solution to the MPW problem. We show experimentally that our approach works well in practice, scaling well to problems where the exact solution is intractable to compute.

Original languageEnglish (US)
Pages (from-to)113-143
Number of pages31
JournalAnnals of Mathematics and Artificial Intelligence
Issue number2-3
StatePublished - Mar 2012
Externally publishedYes


  • Imprecise probabilities
  • Most probable worlds
  • Probabilistic logic programming

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Focused most probable world computations in probabilistic logic programs'. Together they form a unique fingerprint.

Cite this