Parallel abductive query answering in probabilistic logic programs

Gerardo I. Simari, John P. Dickerson, Amy Sliva, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Action-probabilistic logic programs (ap-programs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in ap-programs have the form "If the environment in which entity E operates satisfies certain conditions, then the probability that E will take some action A is between L and U". Given an ap-program, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity E takes some action (or combination of actions) is maximized. This is called the Basic Abductive Query Answering Problem (BAQA). We first formally define and study the complexity of BAQA, and then go on to provide an exact (exponential time) algorithm to solve it, followed by more efficient algorithms for specific subclasses of the problem. We also develop appropriate heuristics to solve BAQA efficiently. The second problem, called the Cost-based Query Answering (CBQA) problem checks to see if there is some way of achieving a desired action (or set of actions) with a probability exceeding a threshold, given certain costs. We first formally define and study an exact (intractable) approach to CBQA, and then go on to propose a more efficient algorithm for a specific subclass of ap-programs that builds on the results for the basic version of this problem. We also develop the first algorithms for parallel evaluation of CBQA. We conclude with an extensive report on experimental evaluations performed over prototype implementations of the algorithms developed for both BAQA and CBQA, showing that our parallel algorithms work well in practice.

Original languageEnglish (US)
Article number12
JournalACM Transactions on Computational Logic
Volume14
Issue number2
DOIs
StatePublished - Jun 2013
Externally publishedYes

Keywords

  • Imprecise probabilities
  • Probabilistic reasoning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)
  • Logic
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Parallel abductive query answering in probabilistic logic programs'. Together they form a unique fingerprint.

Cite this