zbMATH — the first resource for mathematics

\(T_{\mathcal{P}}\)-compilation for inference in probabilistic logic programs. (English) Zbl 1386.68174
Summary: We propose \(T_{\mathcal{P}}\)-compilation, a new inference technique for probabilistic logic programs that is based on forward reasoning. \(T_{\mathcal{P}}\)-compilation proceeds incrementally in that it interleaves the knowledge compilation step for weighted model counting with forward reasoning on the logic program. This leads to a novel anytime algorithm that provides hard bounds on the inferred probabilities. The main difference with existing inference techniques for probabilistic logic programs is that these are a sequence of isolated transformations. Typically, these transformations include conversion of the ground program into an equivalent propositional formula and compilation of this formula into a more tractable target representation for weighted model counting. An empirical evaluation shows that \(T_{\mathcal{P}}\)-compilation effectively handles larger instances of complex or cyclic real-world problems than current sequential approaches, both for exact and anytime approximate inference. Furthermore, we show that \(T_{\mathcal{P}}\)-compilation is conducive to inference in dynamic domains as it supports efficient updates to the compiled model.

68T37 Reasoning under uncertainty in the context of artificial intelligence
68N17 Logic programming
Full Text: DOI
[1] Aziz, Rehan Abdul; Chu, Geoffrey; Muise, Christian; Stuckey, Peter J., Stable model counting and its application in probabilistic logic programming, (Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI, (2015)) · Zbl 06512569
[2] Bogaerts, Bart; Van den Broeck, Guy, Knowledge compilation of logic programs using approximation fixpoint theory, Theory Pract. Log. Program., 15, 4-5, 464-480, (2015) · Zbl 1379.68045
[3] Boyen, X.; Koller, D., Tractable inference for complex stochastic processes, (Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, UAI, (1998))
[4] Chavira, Mark; Darwiche, Adnan, Compiling Bayesian networks with local structure, (Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI, (2005)) · Zbl 1096.68747
[5] Chavira, Mark; Darwiche, Adnan, On probabilistic inference by weighted model counting, Artif. Intell., 172, 6-7, 772-799, (2008) · Zbl 1182.68297
[6] Chavira, Mark; Darwiche, Adnan; Jaeger, Manfred, Compiling relational Bayesian networks for exact inference, Int. J. Approx. Reason., 42, 1, 4-20, (2006) · Zbl 1096.68747
[7] Choi, Arthur; Kisa, Doga; Darwiche, Adnan, Compiling probabilistic graphical models using sentential decision diagrams, (Proceedings of the 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU, (2013)) · Zbl 1390.68640
[8] Clark, Keith L., Negation as failure, (Logic and Databases, (1978)), 293-322
[9] Darwiche, Adnan; Marquis, Pierre, A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264, (2002) · Zbl 1045.68131
[10] Darwiche, Adnan, New advances in compiling CNF into decomposable negation normal form, (Proceedings of the 16th European Conference on Artificial Intelligence, ECAI, (2004))
[11] Darwiche, Adnan, Modeling and reasoning with Bayesian networks, (2009), Cambridge University Press · Zbl 1231.68003
[12] Darwiche, Adnan, SDD: a new canonical representation of propositional knowledge bases, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI, (2011))
[13] Davis, Jesse; Domingos, Pedro, Deep transfer via second-order Markov logic, (Proceedings of the 26th International Conference on Machine Learning, ICML, (2009))
[14] De Raedt, Luc; Kimmig, Angelika, Probabilistic (logic) programming concepts, Mach. Learn., 100, 1, 5-47, (2015) · Zbl 1346.68050
[15] De Raedt, Luc; Kimmig, Angelika; Toivonen, Hannu, Problog: a probabilistic prolog and its application in link discovery, (Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI, (2007)) · Zbl 1201.68035
[16] (De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming — Theory and Applications, Lecture Notes in Artificial Intelligence, vol. 4911, (2008), Springer) · Zbl 1132.68007
[17] de Salvo Braz, Rodrigo; Arora, Nimar; Sudderth, Erik; Russell, Stuart, Open-universe state estimation with dblog, (NIPS 2008 Workshop, (2008))
[18] Fierens, Daan; Van den Broeck, Guy; Renkens, Joris; Shterionov, Dimitar; Gutmann, Bernd; Thon, Ingo; Janssens, Gerda; De Raedt, Luc, Inference and learning in probabilistic logic programs using weighted Boolean formulas, Theory Pract. Log. Program., 15, 03, 358-401, (May 2015)
[19] Geier, Thomas; Biundo, Susanne, Approximate online inference for dynamic Markov logic networks, (Proceedings of the 23rd International Conference on Tools with Artificial Intelligence, ICTAI, (2011))
[20] (Getoor, L.; Taskar, B., An Introduction to Statistical Relational Learning, (2007), MIT Press) · Zbl 1141.68054
[21] Goodman, Noah D.; Mansinghka, Vikash K.; Roy, Daniel M.; Bonawitz, Keith; Tenenbaum, Joshua B., Church: a language for generative models, (Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, UAI, (2008))
[22] Gutmann, Bernd; Thon, Ingo; Kimmig, Angelika; Bruynooghe, Maurice; De Raedt, Luc, The magic of logical inference in probabilistic programming, Theory Pract. Log. Program., 11, 663-680, (2011) · Zbl 1222.68060
[23] Kersting, Kristian; Ahmadi, Babak; Natarajan, Sriraam, Counting belief propagation, (Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI, (2009)) · Zbl 1273.68293
[24] Milch, Brian; Marthi, Bhaskara; Russell, Stuart J.; Sontag, David; Ong, Daniel L.; Kolobov, Andrey, BLOG: probabilistic models with unknown objects, (Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI, (2005))
[25] Muggleton, S. H., Stochastic logic programs, (De Raedt, L., Advances in Inductive Logic Programming, (1996), IOS Press), 254-264
[26] Murphy, Kevin, Dynamic Bayesian networks: representation, inference and learning, (July 2002), UC Berkeley, Computer Science Division, PhD thesis
[27] Nilsson, Ulf; Maluszynski, Jan, Logic, programming, and PROLOG, (1995), John Wiley & Sons, Inc. New York, NY, USA · Zbl 0722.68023
[28] Nitti, Davide; De Laet, Tinne; De Raedt, Luc, A particle filter for hybrid relational domains, (IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, (2013)) · Zbl 1362.68247
[29] Nitti, Davide; De Laet, Tinne; De Raedt, Luc, Relational object tracking and learning, (IEEE International Conference on Robotics and Automation, ICRA, (2014)) · Zbl 06843619
[30] Ourfali, Oved; Shlomi, Tomer; Ideker, Trey; Ruppin, Eytan; Sharan, Roded, SPINE: a framework for signaling-regulatory pathway inference from cause-effect experiments, Bioinformatics, 23, 13, 359-366, (2007)
[31] Pfeffer, Avi, Practical probabilistic programming, (2014), Manning Publications
[32] Poole, David, Logic programming, abduction and probability, New Gener. Comput., 11, 377-400, (1993) · Zbl 0788.68025
[33] Poon, Hoifung; Domingos, Pedro, Sound and efficient inference with probabilistic and deterministic dependencies, (Proceedings of the 21st National Conference on Artificial Intelligence, AAAI, (2006))
[34] Renkens, Joris; Van den Broeck, Guy; Nijssen, Siegfried, K-optimal: a novel approximate inference algorithm for problog, Mach. Learn., 89, 3, 215-231, (2012) · Zbl 1260.68067
[35] Renkens, Joris; Kimmig, Angelika; Van den Broeck, Guy; De Raedt, Luc, Explanation-based approximate weighted model counting for probabilistic logics, (Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI, (2014))
[36] Riguzzi, Fabrizio; Swift, Terrance, The PITA system: tabling and answer subsumption for reasoning under uncertainty, Theory Pract. Log. Program., 11, 4-5, 433-449, (2011) · Zbl 1218.68169
[37] Riguzzi, Fabrizio, A top down interpreter for LPAD and CP-logic, (Proceedings of the 10th Congress of the Italian Association for Artificial Intelligence, AI*IA, (2007))
[38] Riguzzi, Fabrizio, The distribution semantics for normal programs with function symbols, Special Issue on Probabilistic Logic Programming, Int. J. Approx. Reason., (2016), in press · Zbl 1385.68022
[39] Sato, Taisuke, A statistical learning method for logic programs with distribution semantics, (Proceedings of the 12th International Conference on Logic Programming, ICLP, (1995))
[40] Suciu, Dan; Olteanu, Dan; Christopher, R.; Koch, Christoph, Probabilistic databases, (2011), Morgan & Claypool Publishers · Zbl 1237.68012
[41] Thon, Ingo; Niels, Landwehr; De Raedt, Luc, Stochastic relational processes: efficient inference and applications, Mach. Learn., 82, 2, 239-272, (February 2011)
[42] Van den Broeck, Guy; Darwiche, Adnan, On the role of canonicity in knowledge compilation, (Proceedings of the 29th Conference on Artificial Intelligence, AAAI, (2015))
[43] Van Emden, Maarten H.; Kowalski, Robert A., The semantics of predicate logic as a programming language, J. ACM, 23, 569-574, (1976)
[44] Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S., The well-founded semantics for general logic programs, J. ACM, 38, 3, 619-649, (July 1991)
[45] Vennekens, Joost; Verbaeten, Sofie; Bruynooghe, Maurice, Logic programs with annotated disjunctions, (Proceedings of the 20th International Conference on Logic Programming, ICLP, (2004)) · Zbl 1104.68391
[46] Vennekens, Joost; Denecker, Marc; Bruynooghe, Maurice, CP-logic: a language of causal probabilistic events and its relation to logic programming, Theory Pract. Log. Program., 9, 3, (2009) · Zbl 1179.68025
[47] Vlasselaer, Jonas; Van den Broeck, Guy; Kimmig, Angelika; Meert, Wannes; De Raedt, Luc, Anytime inference in probabilistic logic programs with tp-compilation, (Proceedings of 24th International Joint Conference on Artificial Intelligence, IJCAI, (July 2015)) · Zbl 1386.68174
[48] Vlasselaer, Jonas; Meert, Wannes; Van den Broeck, Guy; De Raedt, Luc, Exploiting local and repeated structure in dynamic Bayesian networks, Artif. Intell., 232, 43-53, (March 2016)
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.