Finding most probable worlds of probabilistic logic programs

Samir Khuller*, Vanina Martinez, Dana Nau, Gerardo Siman, Amy Sliva, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationScalable Uncertainty Management - 1st International Conference, SUM 2007, Proceedings
Pages45-59
Number of pages15
StatePublished - Dec 1 2007
Event1st International Conference on Scalable Uncertainty Management, SUM 2007 - Washington, DC, United States
Duration: Oct 10 2007Oct 12 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4772 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st International Conference on Scalable Uncertainty Management, SUM 2007
CountryUnited States
CityWashington, DC
Period10/10/0710/12/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Finding most probable worlds of probabilistic logic programs'. Together they form a unique fingerprint.

Cite this