Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-19T07:01:36.807Z Has data issue: false hasContentIssue false
  • English
  • Français

The magic of logical inference in probabilistic programming

Published online by Cambridge University Press:  06 July 2011

BERND GUTMANN ,
INGO THON ,
ANGELIKA KIMMIG ,
MAURICE BRUYNOOGHE  and
LUC DE RAEDT
BERND GUTMANN
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A-bus 2402, 3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected], [email protected], [email protected])
INGO THON
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A-bus 2402, 3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected], [email protected], [email protected])
ANGELIKA KIMMIG
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A-bus 2402, 3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected], [email protected], [email protected])
MAURICE BRUYNOOGHE
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A-bus 2402, 3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected], [email protected], [email protected])
LUC DE RAEDT
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A-bus 2402, 3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Today, there exist many different probabilistic programming languages as well as more inference mechanisms for these languages. Still, most logic programming-based languages use backward reasoning based on Selective Linear Definite resolution for inference. While these methods are typically computationally efficient, they often can neither handle infinite and/or continuous distributions nor evidence. To overcome these limitations, we introduce distributional clauses, a variation and extension of Sato's distribution semantics. We also contribute a novel approximate inference method that integrates forward reasoning with importance sampling, a well-known technique for probabilistic inference. In order to achieve efficiency, we integrate two logic programming techniques to direct forward sampling. Magic sets are used to focus on relevant parts of the program, while the integration of backward reasoning allows one to identify and avoid regions of the sample space that are inconsistent with the evidence.

Keywords

probabilistic logicforward reasoningsamplingcontinuous distributions
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 663 - 680
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Angelopoulos, N. and Cussens, J. 2003. Prolog issues and experimental results of an MCMC algorithm. In Web Knowledge Management and Decision Support, Bartenstein, O., Geske, U., Hannebauer, M. and Yoshie, O., Eds. Lecture Notes in Computer Science, vol. 2543. Springer, Berlin, Germany 186–196.CrossRefGoogle Scholar
Bancilhon, F., Maier, D., Sagiv, Y. and Jeffrey, D. Ullman. 1986. Magic sets and other strange ways to implement logic programs (extended abstract). In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS 1986). ACM, Cambridge, MA, 1–15.Google Scholar
Baral, C., Gelfond, M. and Rushton, N. 2009. Probabilistic reasoning with answer sets. Theory and Practice of Logic Programming 9, 1, 57–144.Google Scholar
De Raedt, L., Demoen, B., Fierens, D., Gutmann, B., Janssens, G., Kimmig, A., Landwehr, N., Mantadelis, T., Meert, W., Rocha, R., Santos Costa, V., Thon, I. and Vennekens, J. 2008. Towards digesting the alphabet-soup of statistical relational learning. In Proceedings of the 1st Workshop on Probabilistic Programming: Universal Languages, Systems and Applications, Roy, D., Winn, J., McAllester, D., Mansinghka, V. and Tenenbaum, J., Eds. Whistler, British Columbia, Canada.Google Scholar
De Raedt, L., Frasconi, P., Kersting, K. and Muggleton, S. 2008. Probabilistic Inductive Logic Programming – Theory and Applications. LNCS, vol. 4911. Springer, Berlin, Germany.CrossRefGoogle Scholar
De Raedt, L., Kimmig, A. and Toivonen, H. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI) Hyderabad, India, January 6–12. 2462–2467.Google Scholar
Eisner, J., Goldlust, E. and Smith, N. 2005. Compiling comp ling: Weighted dynamic programming and the Dyna language. In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP-05), Vancouver, BC, Canada, October 6–8.Google Scholar
Fuhr, N. 2000. Probabilistic Datalog: Implementing logical information retrieval for advanced applications. Journal of the American Society for Information Science (JASIS) 51, 2, 95–110.3.0.CO;2-H>CrossRefGoogle Scholar
Getoor, L. and Taskar, B. 2007. An Introduction to Statistical Relational Learning. MIT Press, Cambridge, MA.CrossRefGoogle Scholar
Gogate, V. and Dechter, R. 2011. SampleSearch: Importance sampling in presence of determinism. Artificial Intelligence 175, 694–729.CrossRefGoogle Scholar
Goodman, N., Mansinghka, V. K., Roy, D. M., Bonawitz, K. and Tenenbaum, J. B. 2008. Church: A language for generative models. In Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, July 9–12. AUAI Press, Helsinki, Finland, 220–229.Google Scholar
Gutmann, B., Jaeger, M. and De Raedt, L. 2010. Extending ProbLog with continuous distributions. In Proceedings of the 20th International Conference on Inductive Logic Programming (ILP–10), Firenze, Italy, June 27–30, Frasconi, P. and Lisi, F. A., Eds. Springer, Berlin, Germany.Google Scholar
Kersting, K. and De Raedt, L. 2008. Basic principles of learning Bayesian logic programs. See De Raedt et al. (2008), 189–221.Google Scholar
Kimmig, A., Demoen, B., DeRaedt, L. Raedt, L., Santos Costa, V. and Rocha, R. 2011. On the implementation of the probabilistic logic programming language ProbLog. Theory and Practice of Logic Programming (TPLP) 11, 235–262.CrossRefGoogle Scholar
Koller, D. and Friedman, N. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA.Google Scholar
Mantadelis, T. and Janssens, G. 2010. Dedicated tabling for a probabilistic setting. In Technical Communications of the 26th International Conference on Logic Programming (ICLP-10), Hermenegildo, M. V. and Schaub, T., Eds. LIPIcs, vol. 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 124–133.Google Scholar
Milch, B., Marthi, B., Russell, S., Sontag, D., Ong, D. and Kolobov, A. 2005. BLOG: Probabilistic models with unknown objects. In Proceedings of THE Nineteenth International Joint Conference on Artificial Intelligence (IJCAI), Edinburgh, Scotland, UK, July 30–August 5. Springer Verlag, Berlin, Germany, 1352–1359.Google Scholar
Milch, B., Marthi, B., Sontag, D., Russell, S., Ong, D. L. and Kolobov, A. 2005. Approximate inference for infinite contingent Bayesian networks. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, January 6–8, Barbados, Cowell, R. G. and Ghahramani, Z., Eds. Society for Artificial Intelligence and Statistics, New Jersey, 238–245. (Available electronically at http://www.gatsby.ucl.ac.uk/aistats/)Google Scholar
Nilsson, U. and Małiszyński, J. 1996. Logic, Programming And Prolog, 2nd ed. Wiley, Hoboken, NJ.Google Scholar
Pfeffer, A. 2001. IBAL: A probabilistic rational programming language. In Seventeenth International Joint Conference on Artificial Intelligence (IJCAI), Seattle, Washington, August 4–10. Springer, Berlin, Germany, 733–740.Google Scholar
Poole, D. 2008. The independent choice logic and beyond. In Probabilistic Inductive Logic Programming – Theory and Applications, De Raedt, L., Frasconi, P., Kersting, K. and Muggleton, S., Eds. LNCS, vol. 4911. Springer, Berlin, Germany, 222–243.CrossRefGoogle Scholar
Richardson, M. and Domingos, P. 2006. Markov logic networks. Machine Learning 62, 1–2, 107–136.CrossRefGoogle Scholar
Santos Costa, V., Page, D. and Cussens, J. 2008. CLP(BN): Constraint logic programming for probabilistic knowledge. See De Raedt et al. (2008), 156–188.Google Scholar
Sato, T. 1995. A statistical learning method for logic programs with distribution semantics. In Proceedings of the Twelth International Conference on Logic Programming (ICLP 1995). MIT Press, Cambridge, MA, 715–729.Google Scholar
Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Resesearch (JAIR) 15, 391–454.CrossRefGoogle Scholar
Vennekens, J., Denecker, M. and Bruynooghe, M. 2009. CP-logic: A language of causal probabilistic events and its relation to logic programming. Theory and Practice of Logic Programming 9, 3, 245–308.CrossRefGoogle Scholar
Wasserman, L. 2003. All of Statistics: A Concise Course in Statistical Inference (Springer Texts in Statistics). Springer, Berlin, Germany.Google Scholar