Finding most probable worlds of probabilistic logic programs

TitleFinding most probable worlds of probabilistic logic programs
Publication TypeJournal Articles
Year of Publication2007
AuthorsKhuller S, Martinez V, Nau DS, Simari G, Sliva A, Subrahmanian V
JournalScalable Uncertainty Management
Pagination45 - 59
Date Published2007///

Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a possible world that is most probable. Our first result shows that the problem of computing such ”maximally probable worlds” (MPW) is intractable. We subsequently show that we can often greatly reduce the size of the linear program used in past work (by Ng and Subrahmanian) and yet solve the problem exactly. However, the intractability results still make computational efficiency quite impossible. We therefore also develop several heuristics to solve the MPW problem and report extensive experimental results on the accuracy and efficiency of such heuristics.