TY - JOUR

T1 - Computing most probable worlds of action probabilistic logic programs

T2 - Scalable estimation for 1030,000 worlds

AU - Khuller, Samir

AU - Martinez, M. Vanina

AU - Nau, Dana

AU - Sliva, Amy

AU - Simari, Gerardo I.

AU - Subrahmanian, V. S.

N1 - Funding Information:
Acknowledgements This work was supported by AFOSR grants FA95500610405 and FA95500510298, by ARO grant DAAD190310202, by NSF grant 0540216 and by DoD grant N6133906C0149.

PY - 2007/12

Y1 - 2007/12

N2 - The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called HOP and SemiHOP to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a "binary" algorithm that applies a binary search style heuristic in conjunction with the Naive, HOP and SemiHOP algorithms to quickly find worlds that may not be "most probable." We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of SemiHOP are very accurate and also very fast: more than 1030,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups.

AB - The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called HOP and SemiHOP to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a "binary" algorithm that applies a binary search style heuristic in conjunction with the Naive, HOP and SemiHOP algorithms to quickly find worlds that may not be "most probable." We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of SemiHOP are very accurate and also very fast: more than 1030,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups.

KW - Most probable worlds

KW - Probabilistic logic programs

KW - Scalable approximations

KW - Uncertainty

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

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

U2 - 10.1007/s10472-008-9089-2

DO - 10.1007/s10472-008-9089-2

M3 - Article

AN - SCOPUS:41149102316

VL - 51

SP - 295

EP - 331

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

SN - 1012-2443

IS - 2-4

ER -