×

A new probabilistic constraint logic programming language based on a generalised distribution semantics. (English) Zbl 1346.68054

Summary: Probabilistic logics combine the expressive power of logic with the ability to reason with uncertainty. Several probabilistic logic languages have been proposed in the past, each of them with their own features. We focus on a class of probabilistic logic based on Sato’s distribution semantics, which extends logic programming with probability distributions on binary random variables and guarantees a unique probability distribution. For many applications binary random variables are, however, not sufficient and one requires random variables with arbitrary ranges, e.g. real numbers. We tackle this problem by developing a generalised distribution semantics for a new probabilistic constraint logic programming language. In order to perform exact inference, imprecise probabilities are taken as a starting point, i.e. we deal with sets of probability distributions rather than a single one. It is shown that given any continuous distribution, conditional probabilities of events can be approximated arbitrarily close to the true probability. Furthermore, for this setting an inference algorithm that is a generalisation of weighted model counting is developed, making use of SMT solvers. We show that inference has similar complexity properties as precise probabilistic inference, unlike most imprecise methods for which inference is more complex. We also experimentally confirm that our algorithm is able to exploit local structure, such as determinism, which further reduces the computational complexity.

MSC:

68N17 Logic programming
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Getoor, L.; Taskar, B., An Introduction to Statistical Relational Learning (2007), MIT Press) · Zbl 1141.68054
[2] Kimmig, A.; Costa, F., Link and node prediction in metabolic networks with probabilistic logic, (Bisociative Knowledge Discovery (2012), Springer), 407-426
[3] Moldovan, B.; Moreno, P.; van Otterlo, M.; Santos-Victor, J.; De Raedt, L., Learning relational affordance models for robots in multi-object manipulation tasks, (2012 IEEE International Conference on Robotics and Automation. 2012 IEEE International Conference on Robotics and Automation, ICRA (2012), IEEE), 4373-4378
[4] Michels, S.; Velikova, M.; Hommersom, A.; Lucas, P. J., A decision support model for uncertainty reasoning in safety and security tasks, (2013 IEEE International Conference on Systems, Man, and Cybernetics. 2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC (2013), IEEE), 663-668
[5] Sato, T., A statistical learning method for logic programs with distribution semantics, (ICLP (1995)), 715-729
[6] Raedt, L. D.; Kimmig, A.; Toivonen, H., ProbLog: a probabilistic prolog and its application in link discovery, (Proc. of the 20th International Joint Conference on Artificial Intelligence (2007), AAAI Press), 2468-2473
[7] Sato, T.; Kameya, Y., PRISM: a language for symbolic-statistical modeling, (Proc. of the 15th International Joint Conference on Artificial Intelligence (1997)), 1330-1335
[8] Poole, D., The independent choice logic and beyond, (De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 222-243 · Zbl 1137.68596
[9] Vennekens, J.; Denecker, M.; Bruynooghe, M., CP-logic: a language of causal probabilistic events and its relation to logic programming, Theory Pract. Log. Program., 9, 245-308 (2009) · Zbl 1179.68025
[10] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann
[11] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 1-2, 107-136 (2006) · Zbl 1470.68221
[12] Wang, J.; Domingos, P., Hybrid Markov logic networks, (Proceedings of the 23rd National Conference on Artificial Intelligence, vol. 2. Proceedings of the 23rd National Conference on Artificial Intelligence, vol. 2, AAAI’08 (2008), AAAI Press), 1106-1111
[13] Gutmann, B.; Jaeger, M.; De Raedt, L., Extending ProbLog with continuous distributions, (Frasconi, P.; Lisi, F. A., Proc. of the 20th International Conference on Inductive Logic Programming. Proc. of the 20th International Conference on Inductive Logic Programming, ILP-10, Firenze, Italy (2010)) · Zbl 1329.68057
[14] Gutmann, B.; Thon, I.; Kimmig, A.; Bruynooghe, M.; Raedt, L. D., The magic of logical inference in probabilistic programming, Theory Pract. Log. Program., 11, 663-680 (2011) · Zbl 1222.68060
[15] Jaffar, J.; Lassez, J., Constraint logic programming, (Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (1987), ACM), 111-119
[16] Nilsson, N., Probabilistic logic, Artif. Intell., 28, 1, 71-87 (1986) · Zbl 0589.03007
[17] Michels, S.; Hommersom, A.; Lucas, P. J.F.; Velikova, M.; Koopman, P. W.M., Inference for a new probabilistic constraint logic, (Rossi, F., IJCAI, IJCAI/AAAI (2013))
[18] Chavira, M.; Darwiche, A., On probabilistic inference by weighted model counting, Artif. Intell., 172, 6-7, 772-799 (2008) · Zbl 1182.68297
[19] Fierens, D.; Van den Broeck, G.; Thon, I.; Gutmann, B.; De Raedt, L., Inference in probabilistic logic programs using weighted CNF’s, (Gagliardi Cozman, F.; Pfeffer, A., Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, UAI, 14-17 July 2011, Barcelona, Spain (2011)), 211-220
[20] Binder, J.; Koller, D.; Russell, S.; Kanazawa, K.; Smyth, P., Adaptive probabilistic networks with hidden variables, Mach. Learn., 213-244 (1997) · Zbl 0892.68079
[21] Valdez, R.; Yoon, P.; Liu, T.; Khoury, M., Family history and prevalence of diabetes in the us population the 6-year results from the national health and nutrition examination survey (1999-2004), Diabetes Care, 30, 10, 2517-2522 (2007)
[22] Lloyd, J., Foundations of Logic Programming (1987), Springer · Zbl 0668.68004
[23] Grädel, E., On transitive closure logic, (Computer Science Logic: 5th Workshop. Computer Science Logic: 5th Workshop, CSL’91, vol. 626 (1992), Springer), 149-163 · Zbl 0783.03012
[24] Apt, K. R.; Blair, H. A.; Walker, A., Towards a theory of declarative knowledge (1986), IBM TJ Watson Research Center
[25] Van Gelder, A.; Ross, K. A.; Schlipf, J. S., The well-founded semantics for general logic programs, J. ACM, 38, 3, 619-649 (1991) · Zbl 0799.68045
[26] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (ICLP/SLP, vol. 88 (1988)), 1070-1080
[27] Kolmogorov, A. N., Foundations of the Theory of Probability (1960) · Zbl 0074.12202
[28] Walley, P., Towards a unified theory of imprecise probability, Int. J. Approx. Reason., 24, 2, 125-148 (2000) · Zbl 1007.28015
[29] Levi, I., The Enterprise of Knowledge (1980)
[30] Neveu, J., Mathematical Foundations of the Calculus of Probability (1965), Holden-Day: Holden-Day San Francisco · Zbl 0137.11301
[31] Sato, T.; Kameya, Y., New advances in logic-based probabilistic modeling by prism, (Probabilistic Inductive Logic Programming (2008), Springer), 118-155 · Zbl 1137.68617
[32] Weichselberger, K.; Augustin, T., On the symbiosis of two concepts of conditional interval probability, (ISIPTA, vol. 3 (2003)), 608-629
[33] Papadimitriou, C. H., On the complexity of integer programming, J. ACM, 28, 4, 765-768 (1981) · Zbl 0468.68050
[34] Davenport, J. H.; Heintz, J., Real quantifier elimination is doubly exponential, J. Symb. Comput., 5, 1, 29-35 (1988) · Zbl 0663.03015
[35] Hentenryck, P. V., Constraint Satisfaction in Logic Programming (1989), The MIT Press
[36] Jaffar, J.; Michaylov, S.; Stuckey, P. J.; Yap, R. H.C., The CLP(R) language and system, ACM Trans. Program. Lang. Syst., 14, 3, 339-395 (1992)
[37] Jaffar, J.; Maher, M. J.; Marriott, K.; Stuckey, P. J., The semantics of constraint logic programs, J. Funct. Logic Program., 37, 1-3, 1-46 (1998) · Zbl 0920.68068
[38] Janhunen, T., Representing normal programs with clauses, (ECAI, vol. 16 (2004)), 358
[39] Mantadelis, T.; Janssens, G., Dedicated tabling for a probabilistic setting, (ICLP (Technical Communications) (2010)), 124-133 · Zbl 1237.68190
[40] Poole, D.; Zhang, N. L., Exploiting contextual independence in probabilistic inference, J. Artif. Intell. Res., 18, 263-313 (2003) · Zbl 1056.68144
[41] Darwiche, A., Recursive conditioning, Artif. Intell., 126, 1, 5-41 (2001) · Zbl 0969.68150
[42] Jensen, F.; Anderson, S., Approximations in Bayesian belief universe for knowledge based systems, (Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence. Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence, UAI-90 (1990), AUAI Press: AUAI Press Corvallis, Oregon), 162-169
[43] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence (1996), Morgan Kaufmann Publishers Inc.), 115-123
[44] Bayardo, R. J.; Pehoushek, J. D., Counting models using connected components, (AAAI/IAAI (2000)), 157-162
[45] Sang, T.; Beame, P.; Kautz, H., Heuristics for fast exact model counting, (Theory and Applications of Satisfiability Testing (2005), Springer), 226-240 · Zbl 1128.68481
[46] De Moura, L.; Bjørner, N., Z3: an efficient SMT solver, (Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS’08/ETAPS’08 (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 337-340
[47] Dutertre, B.; Moura, L. D., The Yices SMT solver (2006), Computer Science Laboratory, SRI International, Tech. rep.
[48] De Campos, C. P.; Cozman, F. G., The inferential complexity of Bayesian and credal networks, (IJCAI, vol. 5 (2005)), 1313-1318
[49] Downey, P. J.; Sethi, R.; Tarjan, R. E., Variations on the common subexpression problem, J. ACM, 27, 4, 758-771 (1980) · Zbl 0458.68026
[50] Karmarkar, N., A new polynomial-time algorithm for linear programming, (Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (1984), ACM), 302-311 · Zbl 0557.90065
[51] Matiyasevich, Y. V., Diophantine representation of recursively enumerable predicates, (Fenstad, J., Second Scandinavian Logic Symposium (1971), North-Holland Publishing Company), 171-177 · Zbl 0235.02039
[52] Bodlaender, H. L., A tourist guide through treewidth (1992), Technical report RUU-CS 92 · Zbl 0804.68101
[53] Samer, M.; Szeider, S., Algorithms for propositional model counting, J. Discrete Algorithms, 8, 1, 50-64 (2010) · Zbl 1214.05166
[54] Diestel, R., Graph Theory, Grad. Texts Math., vol. 173 (2005), Springer-Verlag: Springer-Verlag Berlin · Zbl 1074.05001
[55] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in ak-tree, SIAM J. Algebr. Discrete Methods, 8, 2, 277-284 (1987) · Zbl 0611.05022
[56] Bodlaender, H. L., A linear time algorithm for finding tree-decompositions of small treewidth, (Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (1993), ACM), 226-234 · Zbl 1310.05194
[57] Sang, T.; Beame, P.; Kautz, H., Solving Bayesian networks by weighted model counting, (Proceedings of the Twentieth National Conference on Artificial Intelligence. Proceedings of the Twentieth National Conference on Artificial Intelligence, AAAI-05, vol. 1 (2005)), 475-482
[58] Fierens, D.; Van den Broeck, G.; Renkens, J.; Shterionov, D.; Gutmann, B.; Thon, I.; Janssens, G.; De Raedt, L., Inference and learning in probabilistic logic programs using weighted Boolean formulas, Theory Pract. Log. Program., 1-44 (2014), First view
[59] Darwiche, A., New advances in compiling CNF to decomposable negation normal form, (Proc. of ECAI (2004), Citeseer), 328-332
[60] Muise, C.; Mcilraith, S. A.; Beck, J. C.; Hsu, E., DSHARP: fast d-DNNF compilation with sharpSAT, (Canadian Conference on Artificial Intelligence (2012))
[61] Laskey, K., MEBN: a language for first-order Bayesian knowledge bases, Artif. Intell., 172, 2-3, 140-178 (2008) · Zbl 1182.68288
[62] McCallum, A.; Schultz, K.; Singh, S., Factorie: probabilistic programming via imperatively defined factor graphs, (Advances in Neural Information Processing Systems (2009)), 1249-1257
[63] Pfeffer, A., Figaro: an object-oriented probabilistic programming language (2009), Charles River Analytics, p. 137
[64] Goodman, N.; Mansinghka, V.; Roy, D.; Bonawitz, K.; Tenenbaum, J., Church: a language for generative models, (Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, UAI 2008 (2008)), 220-229
[65] Milch, B.; Marthi, B.; Russell, S. J.; Sontag, D.; Ong, D. L.; Kolobov, A., BLOG: probabilistic models with unknown objects, (Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05, July 30-August 5, 2005, Edinburgh, Scotland, UK (2005)), 1352-1359
[66] Lauritzen, S. L., Propagation of probabilities, means, and variances in mixed graphical association models, J. Am. Stat. Assoc., 87, 420, 1098-1108 (1992) · Zbl 0850.62094
[67] Cozman, F. G., Credal networks, Artif. Intell., 120, 2, 199-233 (2000) · Zbl 0945.68163
[68] Ng, R.; Subrahmanian, V. S., Probabilistic logic programming, Inf. Comput., 101, 2, 150-201 (1992) · Zbl 0781.68038
[69] Michels, S.; Hommersom, A.; Lucas, P. J.F.; Velikova, M., Imprecise probabilistic horn clause logic, (ECAI 2014: 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014. ECAI 2014: 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, 18-22 August 2014, Prague, Czech Republic (2014)), 621-626 · Zbl 1366.68292
[70] Domingos, P.; Kok, S.; Lowd, D.; Poon, H.; Richardson, M.; Singla, P., Markov logic, (Probabilistic Inductive Logic Programming (2008)), 92-117 · Zbl 1137.68531
[71] Costa, V. S.; Page, D.; Qazi, M.; Cussens, J., CLP (BN): constraint logic programming for probabilistic knowledge, (Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (2002), Morgan Kaufmann Publishers Inc.), 517-524
[72] Costa, V. S.; Paes, A., On the relationship between PRISM and \(CLP(BN)\), (Proc. of the Int. Workshop on Statistical Relational Learning. Proc. of the Int. Workshop on Statistical Relational Learning, SRL-2009 (2009))
[73] Angelopoulos, N., clp(pdf(y)): constraints for probabilistic reasoning in logic programming, (Rossi, F., Principles and Practice of Constraint Programming 2003. Principles and Practice of Constraint Programming 2003, Lect. Notes Comput. Sci., vol. 2833 (2003), Springer: Springer Berlin, Heidelberg), 784-788
[74] Reizler, S., Probabilistic constraint logic programming (1998), University of Tubingen: University of Tubingen Tubingen, Germany, Ph.D. thesis
[75] Sato, T.; Ishihata, M.; Inoue, K., Constraint-based probabilistic modeling for statistical abduction, Mach. Learn., 83, 2, 241-264 (2011) · Zbl 1237.62006
[76] van der Gaag, L., On probability intervals and their updating (1990), Department of Computer Science, University of Utrecht, Technical report
[77] Cozman, F. G.; De Campos, C. P.; Ide, J. S.; da Rocha, J. C.F., Propositional and relational Bayesian networks associated with imprecise and qualitative probabilistic assessments, (Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (2004), AUAI Press), 104-111
[78] Islam, M. A.; Ramakrishnan, C. R.; Ramakrishnan, I. V., Inference in probabilistic logic programs with continuous random variables, Theory Pract. Log. Program., 12, 4-5, 505-523 (2012) · Zbl 1260.68063
[79] Langseth, H.; Nielsen, T. D.; Salmerón, A., Mixtures of truncated basis functions, Int. J. Approx. Reason., 53, 2, 212-227 (2012) · Zbl 1242.68333
[80] Sanner, S.; Abbasnejad, E., Symbolic variable elimination for discrete and continuous graphical models, (AAAI (2012))
[81] Dechter, R., Reasoning with probabilistic and deterministic graphical models: exact algorithms, Synth. Lect. Artif. Intell. Mach. Learn., 7, 3, 1-191 (2013)
[82] Murphy, K. P.; Weiss, Y.; Jordan, M. I., Loopy belief propagation for approximate inference: an empirical study, (Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (1999), Morgan Kaufmann Publishers Inc.), 467-475
[83] Yedidia, J. S.; Freeman, W. T.; Weiss, Y., Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Trans. Inf. Theory, 51, 7, 2282-2312 (2005) · Zbl 1283.94023
[84] Tatikonda, S. C.; Jordan, M. I., Loopy belief propagation and Gibbs measures, (Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (2002), Morgan Kaufmann Publishers Inc.), 493-500
[85] Mooij, J. M.; Kappen, H. J., Sufficient conditions for convergence of loopy belief propagation, (Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence. Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, UAI ’05, July 26-29, 2005, Edinburgh, Scotland (2005)), 396-403
[86] Poole, D., Logic programming, abduction and probability, New Gener. Comput., 11, 3-4, 377-400 (1993) · Zbl 0788.68025
[87] Renkens, J.; Kimmig, A.; Van den Broeck, G.; De Raedt, L., Explanation-based approximate weighted model counting for probabilistic logics, (Proceedings of the 28th AAAI Conference on Artificial Intelligence (2014))
[88] Kullback, S.; Leibler, R. A., On information and sufficiency, Ann. Math. Stat., 22, 1, 79-86 (1951) · Zbl 0042.38403
[89] Arora, N. S.; de Salvo Braz, R.; Sudderth, E. B.; Russell, S. J., Gibbs sampling in open-universe stochastic languages, (Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence. Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2010, July 8-11, 2010, Catalina Island, CA, USA (2010)), 30-39
[90] Nitti, D.; Laet, T. D.; Raedt, L. D., A particle filter for hybrid relational domains, (2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, November 3-7, 2013, Tokyo, Japan (2013)), 2764-2771
[91] Hoffman, M. D.; Gelman, A., The no-u-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo, J. Mach. Learn. Res., 15, 1, 1593-1623 (2014) · Zbl 1319.60150
[92] Li, L.; Ramsundar, B.; Russell, S., Dynamic scaled sampling for deterministic constraints, (Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics (2013)), 397-405
[93] Propp, J. G.; Wilson, D. B., Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Struct. Algorithms, 9, 1-2, 223-252 (1996) · Zbl 0859.60067
[94] Brooks, S.; Gelman, A.; Jones, G.; Meng, X.-L., Handbook of Markov Chain Monte Carlo (2011), CRC Press · Zbl 1218.65001
[95] Kersting, K., Lifted probabilistic inference, (ECAI (2012)), 33-38
[96] Choi, J.; Amir, E.; Hill, D. J., Lifted inference for relational continuous models, (UAI, vol. 10 (2010)), 126-134
[97] Hendriks, T.; van de Laar, P., Metis: dependable cooperative systems for public safety, Proc. Comput. Sci., 16, 542-551 (2013)
[98] Velikova, M.; Novák, P.; Huijbrechts, B.; Laarhuis, J.; Hoeksma, J.; Michels, S., An integrated reconfigurable system for maritime situational awareness, (ECAI 2014: 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014. ECAI 2014: 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, 18-22 August 2014, Prague, Czech Republic (2014)), 1197-1202
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.