Finding Most Probable Worlds of Probabilistic Logic Programs

TitleFinding Most Probable Worlds of Probabilistic Logic Programs
Publication TypeBook Chapters
Year of Publication2007
AuthorsKhuller S, Martinez V, Nau DS, Simari G, Sliva A, Subrahmanian V
EditorPrade H, Subrahmanian V
Book TitleScalable Uncertainty Management
Series TitleLecture Notes in Computer Science
Pagination45 - 59
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-75407-7
KeywordsComputer science

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.