TY - JOUR

T1 - Focused most probable world computations in probabilistic logic programs

AU - Simari, Gerardo I.

AU - Martinez, Maria Vanina

AU - Sliva, Amy

AU - Subrahmanian, V. S.

N1 - Funding Information:
Acknowledgements The authors gratefully acknowledge funding support for this work provided to the Lab for Computational Cultural Dynamics (LCCD) by the Army Research Office under grants W911NF0910206 W911NF1110344, the Army Research Lab under grant W911NF0920072, the Air Force Office of Scientific Research under grant FA95500610405 and the National Science Foundation under grants 0540216 and SES0826886.

PY - 2012/3

Y1 - 2012/3

N2 - 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.

AB - 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.

KW - Imprecise probabilities

KW - Most probable worlds

KW - Probabilistic logic programming

UR - http://www.scopus.com/inward/record.url?scp=84861230862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861230862&partnerID=8YFLogxK

U2 - 10.1007/s10472-012-9285-y

DO - 10.1007/s10472-012-9285-y

M3 - Article

AN - SCOPUS:84861230862

SN - 1012-2443

VL - 64

SP - 113

EP - 143

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

IS - 2-3

ER -