caa a22 4500 463186982 CHVBK 20180406164856.0 cr unu---uuuuu 170326e20071201xx s 000 0 eng 10.1007/s10472-008-9089-2 doi (NATIONALLICENCE)springer-10.1007/s10472-008-9089-2 Computing most probable worlds of action probabilistic logic programs: scalable estimation for 1030,000 worlds [Elektronische Daten] [Samir Khuller, M. Martinez, Dana Nau, Amy Sliva, Gerardo Simari, V. Subrahmanian] 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 $ \textsf{HOP} $ and $ \textsf{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, $ \textsf{HOP} $ and $ \textsf{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 $ \textsf{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. Springer Science+Business Media B.V., 2008 Uncertainty nationallicence Probabilistic logic programs nationallicence Most probable worlds nationallicence Scalable approximations nationallicence Khuller Samir Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Martinez M. Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Nau Dana Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Sliva Amy Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Simari Gerardo Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Subrahmanian V. Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 295-331 1012-2443 51:2-4<295 2007 51 10472 https://doi.org/10.1007/s10472-008-9089-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-008-9089-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Khuller Samir Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Martinez M. Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Nau Dana Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Sliva Amy Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Simari Gerardo Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Subrahmanian V. Department of Computer Science and University of Maryland Institute for Advanced Computer Studies (UMIACS), University of Maryland College Park, 20742, College Park, MD, USA aut NATIONALLICENCE 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/2-4(2007-12-01), 295-331 1012-2443 51:2-4<295 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer