Explanation-based Approximate Inference in Stratified Probabilistic Logic Programs
Resumo
We introduce two novel search-based algorithms for approximate inference in stratified probabilistic logic programs. Both methods build upon the concept of explanations: minimal conjunctions of literals over probabilistic atoms that logically entail a query. Our first contribution is an algorithm that computes bounds on query probabilities by simultaneously searching for explanations and refutations. The second contribution is an algorithm that transforms probabilistic logic programs into an ASP encoding and uses solution enumeration by optimality to enumerate explanations in order of probability. Finally, experiments across two domains demonstrate that our approaches often outperform existing methods, offering a tradeoff between reliability and accuracy.Referências
Apt, K. R. and Doets, K. (1994). A new definition of SLDNF-resolution. The Journal of Logic Programming, 18(2):177–190.
Cozman, F. G. and Mauá, D. D. (2017). On the semantics and complexity of probabilistic logic programs. Journal of Artificial Intelligence Research, 60:221–262.
De Raedt, L. and Kimmig, A. (2015). Probabilistic (logic) programming concepts. Machine Learning, 100(1):5–47.
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), pages 2462–2467.
Dierckx, L., Dubray, A., and Nijssen, S. (2025). Learning from logical constraints with lower- and upper-bound arithmetic circuits. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 5012–5020.
Domingos, P., Kok, S., Lowd, D., Poon, H., Richardson, M., and Singla, P. (2008). Markov logic. In Probabilistic Inductive Logic Programming: Theory and Applications, pages 92–117. Springer.
Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D., Gutmann, B., Thon, I., Janssens, G., and De Raedt, L. (2015). Inference and learning in probabilistic logic programs using weighted Boolean formulas. Theory and Practice of Logic Programming, 15(3):358–401.
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2019). Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming, 19(1):27–82.
Geh, R. L., Gonçalves, J., Silveira, I. C., Mauá, D. D., and Cozman, F. G. (2024). dPASP: A probabilistic logic programming environment for neurosymbolic learning and reasoning. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, pages 731–742.
Gutmann, B., Thon, I., and De Raedt, L. (2011). Learning the parameters of probabilistic logic programs from interpretations. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 581–596. Springer.
Hahn, S., Janhunen, T., Kaminski, R., Romero, J., Rühling, N., and Schaub, T. (2022). Plingo: A system for probabilistic reasoning in clingo based on LP MLN. In International Joint Conference on Rules and Reasoning, pages 54–62. Springer.
Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song, L., and Si, X. (2021). Scallop: From probabilistic deductive databases to scalable differentiable reasoning. Advances in Neural Information Processing Systems, 34:25134–25145.
Li, Z., Huang, J., Liu, J., Zhu, F., Zhao, E., Dodds, W., Velingker, N., Alur, R., and Naik, M. (2024). Relational programming with foundational models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10635–10644.
Li, Z., Huang, J., and Naik, M. (2023). Scallop: A language for neurosymbolic programming. Proceedings of the ACM on Programming Languages, 7(PLDI):1463–1487.
Lloyd, J. W. (2012). Foundations of Logic Programming. Springer Science & Business Media.
Manhaeve, R., Marra, G., and De Raedt, L. (2021). Approximate inference for neural probabilistic logic programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pages 475–486.
Mantadelis, T. and Rocha, R. (2017). Using iterative deepening for probabilistic logic inference. In Practical Aspects of Declarative Languages, pages 198–213. Springer.
Pajunen, J. and Janhunen, T. (2021). Solution enumeration by optimality in answer set programming. Theory and Practice of Logic Programming, 21(6):750–767.
Renkens, J., Kimmig, A., Van den Broeck, G., and De Raedt, L. (2014). Explanation-based approximate weighted model counting for probabilistic logics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, pages 2490–2496.
Renkens, J., Van den Broeck, G., and Nijssen, S. (2012). k-optimal: A novel approximate inference algorithm for ProbLog. Machine Learning, 89(3):215–231.
Sato, T. (1995). A statistical learning method for logic programs with distribution semantics. In Proceedings of the 12th International Conference on Logic Programming (ICLP), pages 715–729.
van Krieken, E., Thanapalasingam, T., Tomczak, J., Van Harmelen, F., and Ten Teije, A. (2023). A-NeSI: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36:24586–24609.
Cozman, F. G. and Mauá, D. D. (2017). On the semantics and complexity of probabilistic logic programs. Journal of Artificial Intelligence Research, 60:221–262.
De Raedt, L. and Kimmig, A. (2015). Probabilistic (logic) programming concepts. Machine Learning, 100(1):5–47.
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), pages 2462–2467.
Dierckx, L., Dubray, A., and Nijssen, S. (2025). Learning from logical constraints with lower- and upper-bound arithmetic circuits. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 5012–5020.
Domingos, P., Kok, S., Lowd, D., Poon, H., Richardson, M., and Singla, P. (2008). Markov logic. In Probabilistic Inductive Logic Programming: Theory and Applications, pages 92–117. Springer.
Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D., Gutmann, B., Thon, I., Janssens, G., and De Raedt, L. (2015). Inference and learning in probabilistic logic programs using weighted Boolean formulas. Theory and Practice of Logic Programming, 15(3):358–401.
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. (2019). Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming, 19(1):27–82.
Geh, R. L., Gonçalves, J., Silveira, I. C., Mauá, D. D., and Cozman, F. G. (2024). dPASP: A probabilistic logic programming environment for neurosymbolic learning and reasoning. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, pages 731–742.
Gutmann, B., Thon, I., and De Raedt, L. (2011). Learning the parameters of probabilistic logic programs from interpretations. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 581–596. Springer.
Hahn, S., Janhunen, T., Kaminski, R., Romero, J., Rühling, N., and Schaub, T. (2022). Plingo: A system for probabilistic reasoning in clingo based on LP MLN. In International Joint Conference on Rules and Reasoning, pages 54–62. Springer.
Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song, L., and Si, X. (2021). Scallop: From probabilistic deductive databases to scalable differentiable reasoning. Advances in Neural Information Processing Systems, 34:25134–25145.
Li, Z., Huang, J., Liu, J., Zhu, F., Zhao, E., Dodds, W., Velingker, N., Alur, R., and Naik, M. (2024). Relational programming with foundational models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10635–10644.
Li, Z., Huang, J., and Naik, M. (2023). Scallop: A language for neurosymbolic programming. Proceedings of the ACM on Programming Languages, 7(PLDI):1463–1487.
Lloyd, J. W. (2012). Foundations of Logic Programming. Springer Science & Business Media.
Manhaeve, R., Marra, G., and De Raedt, L. (2021). Approximate inference for neural probabilistic logic programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pages 475–486.
Mantadelis, T. and Rocha, R. (2017). Using iterative deepening for probabilistic logic inference. In Practical Aspects of Declarative Languages, pages 198–213. Springer.
Pajunen, J. and Janhunen, T. (2021). Solution enumeration by optimality in answer set programming. Theory and Practice of Logic Programming, 21(6):750–767.
Renkens, J., Kimmig, A., Van den Broeck, G., and De Raedt, L. (2014). Explanation-based approximate weighted model counting for probabilistic logics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, pages 2490–2496.
Renkens, J., Van den Broeck, G., and Nijssen, S. (2012). k-optimal: A novel approximate inference algorithm for ProbLog. Machine Learning, 89(3):215–231.
Sato, T. (1995). A statistical learning method for logic programs with distribution semantics. In Proceedings of the 12th International Conference on Logic Programming (ICLP), pages 715–729.
van Krieken, E., Thanapalasingam, T., Tomczak, J., Van Harmelen, F., and Ten Teije, A. (2023). A-NeSI: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36:24586–24609.
Publicado
19/10/2026
Como Citar
MACIEL, Anahí Coimbra; MAUÁ, Denis Deratani.
Explanation-based Approximate Inference in Stratified Probabilistic Logic Programs. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 23. , 2026, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 2277-2288.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2026.31568.
