TY - GEN
T1 - Using histograms to better answer queries to probabilistic logic programs
AU - Broecheler, Matthias
AU - Simari, Gerardo I.
AU - Subrahmanian, V. S.
PY - 2009
Y1 - 2009
N2 - Probabilistic logic programs (PLPs) define a set of probability distribution functions (PDFs) over the set of all Herbrand interpretations of the underlying logical language. When answering a query Q, a lower and upper bound on Q is obtained by optimizing (min and max) an objective function subject to a set of linear constraints whose solutions are the PDFs mentioned above. A common critique not only of PLPs but many probabilistic logics is that the difference between the upper bound and lower bound is large, thus often providing very little useful information in the query answer. In this paper, we provide a new method to answer probabilistic queries that tries to come up with a histogram that "maps" the probability that the objective function will have a value in a given interval, subject to the above linear constraints. This allows the system to return to the user a histogram where he can directly "see" what the most likely probability range for his query will be. We prove that computing these histograms is #P-hard, and show that computing these histograms is closely related to polyhedral volume computation. We show how existing randomized algorithms for volume computation can be adapted to the computation of such histograms. A prototype experimental implementation is discussed.
AB - Probabilistic logic programs (PLPs) define a set of probability distribution functions (PDFs) over the set of all Herbrand interpretations of the underlying logical language. When answering a query Q, a lower and upper bound on Q is obtained by optimizing (min and max) an objective function subject to a set of linear constraints whose solutions are the PDFs mentioned above. A common critique not only of PLPs but many probabilistic logics is that the difference between the upper bound and lower bound is large, thus often providing very little useful information in the query answer. In this paper, we provide a new method to answer probabilistic queries that tries to come up with a histogram that "maps" the probability that the objective function will have a value in a given interval, subject to the above linear constraints. This allows the system to return to the user a histogram where he can directly "see" what the most likely probability range for his query will be. We prove that computing these histograms is #P-hard, and show that computing these histograms is closely related to polyhedral volume computation. We show how existing randomized algorithms for volume computation can be adapted to the computation of such histograms. A prototype experimental implementation is discussed.
KW - Imprecise Probabilities
KW - Probabilistic Logic Programming
UR - http://www.scopus.com/inward/record.url?scp=69949148077&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69949148077&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02846-5_9
DO - 10.1007/978-3-642-02846-5_9
M3 - Conference contribution
AN - SCOPUS:69949148077
SN - 3642028454
SN - 9783642028458
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 40
EP - 54
BT - Logic Programming - 25th International Conference, ICLP 2009, Proceedings
T2 - 25th International Conference on Logic Programming, ICLP 2009
Y2 - 14 July 2009 through 17 July 2009
ER -