Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T07:15:08.115Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimizing Probabilities in Probabilistic Logic Programs

Published online by Cambridge University Press:  23 September 2021

DAMIANO AZZOLINI Open the ORCID record for DAMIANO AZZOLINI [Opens in a new window]  and
FABRIZIO RIGUZZI Open the ORCID record for FABRIZIO RIGUZZI [Opens in a new window]
DAMIANO AZZOLINI
Affiliation:
Dipartimento di Ingegneria - University of Ferrara, Via Saragat 1, I-44122, Ferrara, Italy (e-mail: [email protected])
FABRIZIO RIGUZZI
Affiliation:
Dipartimento di Matematica e Informatica - University of Ferrara, Via Saragat 1, I-44122, Ferrara, Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Probabilistic logic programming is an effective formalism for encoding problems characterized by uncertainty. Some of these problems may require the optimization of probability values subject to constraints among probability distributions of random variables. Here, we introduce a new class of probabilistic logic programs, namely probabilistic optimizable logic programs, and we provide an effective algorithm to find the best assignment to probabilities of random variables, such that a set of constraints is satisfied and an objective function is optimized.

Keywords

probabilistic logic programmingoptimizationconstraints
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 21 , Issue 5: 37th International Conference on Logic Programming Special Issue I , September 2021 , pp. 543 - 556
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

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

Antuori, V. and Richoux, F. 2019. Constrained optimization under uncertainty for decision-making problems: Application to real-time strategy games. In 2019 IEEE Congress on Evolutionary Computation (CEC), 458–465.Google Scholar
Azzolini, D., Riguzzi, F. and Lamma, E. 2021. A semantics for hybrid probabilistic logic programs with function symbols. Artificial Intelligence 294, 103452.CrossRefGoogle Scholar
Azzolini, D., Riguzzi, F., Lamma, E. and Masotti, F. 2019. A comparison of MCMC sampling for probabilistic logic programming. In Proceedings of the 18th Conference of the Italian Association for Artificial Intelligence (AI*IA 2019), Rende, Italy 19-22 November 2019, Alviano, M., Greco, G., and Scarcello, F., Eds. Lecture Notes in Computer Science. Springer, Heidelberg, Germany.Google Scholar
Babaki, B., Guns, T. and de Raedt, L. 2017. Stochastic constraint programming with and-or branch-and-bound. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-2017, 539–545.Google Scholar
Bellodi, E. and Riguzzi, F. 2012. Learning the structure of probabilistic logic programs. In 22nd International Conference on Inductive Logic Programming, Muggleton, S., Tamaddoni-Nezhad, A. and Lisi, F., Eds. Lecture Notes in Computer Science, vol. 7207. Springer Berlin Heidelberg, 61–75.Google Scholar
Bollig, B. and Wegener, I. 1996. Improving the variable ordering of OBDDs is NP-complete. IEEE Transaction on Computers 45, 9, 993–1002.CrossRefGoogle Scholar
Darwiche, A. and Marquis, P. 2002. A knowledge compilation map. Journal of Artificial Intelligence Research 17, 229–264.CrossRefGoogle Scholar
De Raedt, L., Frasconi, P., Kersting, K. and Muggleton, S., Eds. 2008. Probabilistic Inductive Logic Programming. LNCS, vol. 4911. Springer.CrossRefGoogle Scholar
De Raedt, L., Kimmig, A. and Toivonen, H. 2007. Problog: A probabilistic prolog and its application in link discovery. In IJCAI, M. M. Veloso, Ed., 2462–2467.Google Scholar
Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D. S., 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.CrossRefGoogle Scholar
Gutmann, B., Kimmig, A., Kersting, K. and De Raedt, L. 2008. Parameter learning in probabilistic databases: A least squares approach. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD 2008). Lecture Notes in Computer Science, vol. 5211. Springer, 473–488.Google Scholar
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 Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD 2011), Gunopulos, D., Hofmann, T., Malerba, D., and Vazirgiannis, M., Eds. Lecture Notes in Computer Science, vol. 6911. Springer, 581–596.Google Scholar
Jiang, C., Babar, J., Ciardo, G., Miner, A. S. and Smith, B. 2017. Variable reordering in binary decision diagrams. In 26th International Workshop on Logic and Synthesis, 1–8.Google Scholar
Johnson, S. G. 2020. The nlopt nonlinear-optimization package.Google Scholar
Kimmig, A., Van den Broeck, G. and De Raedt, L. 2011. An algebraic prolog for reasoning about possible worlds. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. Vol. 1. AAAI Press, 209–214.Google Scholar
Koller, D. and Friedman, N. 2009. Probabilistic Graphical Models: Principles and Techniques . Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA.Google Scholar
Kraft, D. 1994. Algorithm 733: Tomp–Fortran modules for optimal control calculations. 20, 3 (Sept.), 262–281.Google Scholar
Latour, A. L. D., Babaki, B., Dries, A., Kimmig, A., Van den Broeck, G. and Nijssen, S. 2017. Combining stochastic constraint optimization and probabilistic programming. In Principles and Practice of Constraint Programming, J. C. Beck, Ed. Springer International Publishing, Cham, 495–511.Google Scholar
Lombardi, M. and Milano, M. 2010. Allocation and scheduling of conditional task graphs. Artificial Intelligence 174, 7, 500–529.CrossRefGoogle Scholar
Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., Rathnayake, T., Vig, S., Granger, B. E., Muller, R. P., Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F., Curry, M. J., Terrel, A. R., Roučka, V., Saboo, A., Fernando, I., Kulal, S., Cimrman, R. and Scopatz, A. 2017. Sympy: Symbolic computing in python. PeerJ Computer Science 3, e103.Google Scholar
Orsini, F., Frasconi, P., and De Raedt, L. 2017. kProbLog: An algebraic prolog for machine learning. Machine Learning 106, 12, 1933–1969.CrossRefGoogle Scholar
Riguzzi, F. 2018. Foundations of Probabilistic Logic Programming. River Publishers, Gistrup, Denmark.Google Scholar
Riguzzi, F. and Swift, T. 2010. Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions. In Technical Communications of the 26th International Conference on Logic Programming (ICLP 2010. LIPIcs, vol. 7. Schloss Dagstuhl, 162–171.Google Scholar
Rossi, R. A. and Ahmed, N. K. 2015. The network data repository with interactive graph analytics and visualization. In AAAI.Google Scholar
Sato, T. 1995. A statistical learning method for logic programs with distribution semantics. In Logic Programming, Proceedings of the Twelfth International Conference on Logic Programming, L. Sterling, Ed. MIT Press, 715–729.Google Scholar
Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research 15, 391–454.CrossRefGoogle Scholar
Somenzi, F. 2015. CUDD: CU Decision Diagram Package Release 3.0.0. University of Colorado.Google Scholar
Svanberg, K. 2002. A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM Journal on Optimization, 555–573.CrossRefGoogle Scholar
Van den Broeck, G., Thon, I., van Otterlo, M. and De Raedt, L. 2010. DTProbLog: A decision-theoretic probabilistic Prolog. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, Fox, M. and Poole, D., Eds. AAAI Press, 1217–1222.Google Scholar
Vennekens, J., Verbaeten, S. and Bruynooghe, M. 2004. Logic programs with annotated disjunctions. In 20th International Conference on Logic Programming (ICLP 2004), Demoen, B. and Lifschitz, V., Eds. Lecture Notes in Computer Science, vol. 3131. Springer, 431–445.Google Scholar
Walsh, T. 2002. Stochastic constraint programming. Proceedings of the 15th European Conference on Artificial Intelligence 1, 111–115.Google Scholar
Wielemaker, J., Schrijvers, T., Triska, M. and Lager, T. 2012. SWI-Prolog. Theory and Practice of Logic Programming 12, 1–2, 67–96.CrossRefGoogle Scholar