zbMATH — the first resource for mathematics

Using histograms to better answer queries to probabilistic logic programs. (English) Zbl 1251.68052
Hill, Patricia M. (ed.) et al., Logic programming. 25th international conference, ICLP 2009, Pasadena, CA, USA, July 14–17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02845-8/pbk). Lecture Notes in Computer Science 5649, 40-54 (2009).
Summary: 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.
For the entire collection see [Zbl 1167.68003].

68N17 Logic programming
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI
[1] Shapiro, E.Y.: Logic programs with uncertainties: A tool for implementing rule-based systems. In: IJCAI, pp. 529–532 (1983)
[2] van Emden, M.: Quantitative deduction and its fixpoint theory. Journal of Logic Programming 4, 37–53 (1986) · Zbl 0609.68068 · doi:10.1016/0743-1066(86)90003-8
[3] Ng, R.: A semantical framework for supporting subjective and conditional probabilities in deductive databases. Journal of Automated Reasoning 10, 565–580 (1993) · Zbl 0784.68082 · doi:10.1007/BF00881836
[4] Hailperin, T.: Probability logic. Notre Dame J. of Formal Logic 25(3), 198–212 (1984) · Zbl 0547.03018 · doi:10.1305/ndjfl/1093870625
[5] Fagin, R., Halpern, J.Y., Megiddo, N.: A logic for reasoning about probabilities. Information and Computation 87(1/2), 78–128 (1990) · Zbl 0811.03014 · doi:10.1016/0890-5401(90)90060-U
[6] Nilsson, N.: Probabilistic logic. Artificial Intelligence 28, 71–87 (1986) · Zbl 0589.03007 · doi:10.1016/0004-3702(86)90031-7
[7] Lukasiewicz, T.: Probabilistic logic programming. In: ECAI, pp. 388–392 (1998)
[8] Lukasiewicz, T., Kern-Isberner, G.: Probabilistic logic programming under maximum entropy. In: Hunter, A., Parsons, S. (eds.) ECSQARU 1999. LNCS (LNAI), vol. 1638, p. 279. Springer, Heidelberg (1999) · Zbl 1085.68170 · doi:10.1007/3-540-48747-6_26
[9] Dekhtyar, A., Dekhtyar, M.I.: Possible worlds semantics for probabilistic logic programs. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 137–148. Springer, Heidelberg (2004) · Zbl 1104.68372 · doi:10.1007/978-3-540-27775-0_10
[10] Ng, R.T., Subrahmanian, V.S.: Probabilistic logic programming. Information and Computation 101(2), 150–201 (1992) · Zbl 0781.68038 · doi:10.1016/0890-5401(92)90061-J
[11] Cohen, J., Hickey, T.: Two algorithms for determining volumes of convex polyhedra. Journal of the ACM 26(3), 401–414 (1979) · Zbl 0403.68067 · doi:10.1145/322139.322141
[12] Khachiyan, L.: The problem of calculating the volume of a polyhedron is enumerably hard. Russian Mathematical Surveys 44(3), 199–200 (1989) · Zbl 0692.68034 · doi:10.1070/RM1989v044n03ABEH002136
[13] Dyer, M.E., Frieze, A.M.: On the complexity of computing the volume of a polyhedron. SIAM Journal on Computing 17(5), 967–974 (1988) · Zbl 0668.68049 · doi:10.1137/0217060
[14] Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM 38(1), 1–17 (1991) · Zbl 0799.68107 · doi:10.1145/102782.102783
[15] Lovász, L., Vempala, S.: Simulated annealing in convex bodies and an O *(n 4) volume algorithm. Journal of Computer and System Sciences 72(2), 392–417 (2006) · Zbl 1090.68112 · doi:10.1016/j.jcss.2005.08.004
[16] Biieler, B., Enge, A., Fukuda, K.: Exact volume computation for polytopes: A practical study. In: Polytopes: Combinatorics and Computation. Birkhauser, Basel (2000) · Zbl 0960.68162
[17] Montenegro, R., Tetali, P.: Mathematical aspects of mixing times in markov chains. Foundations and Trends in Theoretical Computer Science 1(3), 237–354 (2006) · Zbl 1193.68138 · doi:10.1561/0400000003
[18] Applegate, D., Kannan, R.: Sampling and integration of near log-concave functions. In: ACM STOC, New Orleans, USA, pp. 156–163. ACM, New York (1991)
[19] Lovász, L., Vempala, S.: Hit-and-run from a corner. In: ACM STOC, Chicago, IL, USA, pp. 310–314. ACM, New York (2004) · Zbl 1192.68371
[20] Khuller, S., Martinez, M.V., Nau, D., Simari, G., Sliva, A., Subrahmanian, V.: Computing most probable worlds of action probabilistic logic programs: Scalable estimation for 1030,000 worlds. AMAI 51(2–4), 295–331 (2007) · Zbl 1138.68054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.