Optimizing probabilities in probabilistic logic programs. (English) Zbl 1522.68097
Summary: 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.
MSC:
| 68N17 | Logic programming |
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 90C15 | Stochastic programming |
| 90C90 | Applications of mathematical programming |
References:
| [1] | 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. |
| [2] | Azzolini, D., Riguzzi, F. and Lamma, E.2021. A semantics for hybrid probabilistic logic programs with function symbols. Artificial Intelligence294, 103452. · Zbl 1519.68040 |
| [3] | 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. |
| [4] | 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. |
| [5] | 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. · Zbl 1379.68269 |
| [6] | Bollig, B. and Wegener, I.1996. Improving the variable ordering of OBDDs is NP-complete. IEEE Transaction on Computers45, 9, 993-1002. · Zbl 1048.68571 |
| [7] | Darwiche, A. and Marquis, P.2002. A knowledge compilation map. Journal of Artificial Intelligence Research17, 229-264. · Zbl 1045.68131 |
| [8] | De Raedt, L., Frasconi, P., Kersting, K. and Muggleton, S., Eds. 2008. Probabilistic Inductive Logic Programming. LNCS, vol. 4911. Springer. · Zbl 1132.68007 |
| [9] | 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. |
| [10] | 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 Programming15, 3, 358-401. · Zbl 1379.68062 |
| [11] | 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. |
| [12] | 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. · Zbl 1222.68010 |
| [13] | 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. |
| [14] | Johnson, S. G.2020. The nlopt nonlinear-optimization package. |
| [15] | 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. |
| [16] | Koller, D. and Friedman, N.2009. Probabilistic Graphical Models: Principles and Techniques. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA. · Zbl 1183.68483 |
| [17] | Kraft, D.1994. Algorithm 733: Tomp-Fortran modules for optimal control calculations. 20, 3 (Sept.), 262-281. · Zbl 0888.65079 |
| [18] | 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. |
| [19] | Lombardi, M. and Milano, M.2010. Allocation and scheduling of conditional task graphs. Artificial Intelligence174, 7, 500-529. · Zbl 1186.90054 |
| [20] | 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. |
| [21] | Orsini, F., Frasconi, P., and De Raedt, L.2017. kProbLog: An algebraic prolog for machine learning. Machine Learning106, 12, 1933-1969. · Zbl 1457.68237 |
| [22] | Riguzzi, F.2018. Foundations of Probabilistic Logic Programming. River Publishers, Gistrup, Denmark. · Zbl 1420.68003 |
| [23] | 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. · Zbl 1237.68049 |
| [24] | Rossi, R. A. and Ahmed, N. K.2015. The network data repository with interactive graph analytics and visualization. In AAAI. |
| [25] | 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. |
| [26] | Sato, T. and Kameya, Y.2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research15, 391-454. · Zbl 0994.68025 |
| [27] | Somenzi, F.2015. CUDD: CU Decision Diagram Package Release 3.0.0. University of Colorado. |
| [28] | Svanberg, K.2002. A class of globally convergent optimization methods based on conservative convex separable approximations. SIAM Journal on Optimization, 555-573. · Zbl 1035.90088 |
| [29] | 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. |
| [30] | 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. · Zbl 1104.68391 |
| [31] | Walsh, T.2002. Stochastic constraint programming. Proceedings of the 15th European Conference on Artificial Intelligence1, 111-115. |
| [32] | Wielemaker, J., Schrijvers, T., Triska, M. and Lager, T.2012. SWI-Prolog. Theory and Practice of Logic Programming12, 1-2, 67-96. · Zbl 1244.68023 |
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.
