{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T23:58:51Z","timestamp":1768435131417,"version":"3.49.0"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T00:00:00Z","timestamp":1600646400000},"content-version":"unspecified","delay-in-days":20,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In Probabilistic Logic Programming (PLP) the most commonly studied inference task is to compute the marginal probability of a query given a program. In this paper, we consider two other important tasks in the PLP setting: the Maximum-A-Posteriori (MAP) inference task, which determines the most likely values for a subset of the random variables given evidence on other variables, and the Most Probable Explanation (MPE) task, the instance of MAP where the query variables are the complement of the evidence variables. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram and applying a dynamic programming procedure on it. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference. Experiments on several synthetic datasets show that PITA outperforms ProbLog in many cases.<\/jats:p>","DOI":"10.1017\/s1471068420000174","type":"journal-article","created":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T05:25:42Z","timestamp":1600665942000},"page":"641-655","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":8,"title":["MAP Inference for Probabilistic Logic Programming"],"prefix":"10.1017","volume":"20","author":[{"given":"ELENA","family":"BELLODI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARCO","family":"ALBERTI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1654-9703","authenticated-orcid":false,"given":"FABRIZIO","family":"RIGUZZI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8352-6304","authenticated-orcid":false,"given":"RICCARDO","family":"ZESE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,9,21]]},"reference":[{"key":"S1471068420000174_ref6","unstructured":"6. De Raedt, L. , Kimmig, A. , and Toivonen, H. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), M. M. Veloso, Ed. Vol. 7. AAAI Press\/IJCAI, 2462\u20132467."},{"key":"S1471068420000174_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00071-0"},{"key":"S1471068420000174_ref20","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"3","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput. 8"},{"key":"S1471068420000174_ref9","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/S0004-3702(97)00027-1","article-title":"The Independent Choice Logic for modelling multiple agents under uncertainty","author":"Poole","year":"1997","journal-title":"Artif. Intell. 94"},{"key":"S1471068420000174_ref23","volume":"3131","author":"Vennekens","year":"2004"},{"key":"S1471068420000174_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s100090100042"},{"key":"S1471068420000174_ref15","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1017\/S147106841100010X","article-title":"The PITA system: Tabling and answer subsumption for reasoning under uncertainty","volume":"4\u20135","author":"Riguzzi","year":"2011","journal-title":"Theor. Pract. Log. Prog. 11,"},{"key":"S1471068420000174_ref13","volume-title":"Foundations of Probabilistic Logic Programming","author":"Riguzzi","year":"2018"},{"key":"S1471068420000174_ref2","unstructured":"2. Darwiche, A. 2004. New advances in compiling CNF into decomposable negation normal form. In 16th European Conference on Artificial Intelligence (ECAI 20014), R. L. de M\u00e1ntaras and L. Saitta, Eds. IOS Press, 328\u2013332."},{"key":"S1471068420000174_ref14","unstructured":"14. 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 - Leibniz-Zentrum fuer Informatik, 162\u2013171."},{"key":"S1471068420000174_ref4","unstructured":"4. 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 NIPS 2008 Workshop on Probabilistic Programming."},{"key":"S1471068420000174_ref21","unstructured":"21. 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\u20131222."},{"key":"S1471068420000174_ref1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"5439","author":"Barabasi","year":"1999","journal-title":"Science 286"},{"key":"S1471068420000174_ref22","unstructured":"22. Vennekens, J. , Verbaeten, S. , and Bruynooghe, M. 2004a. Logic programs with annotated disjunctions. In 24th International Conference on Logic Programming (ICLP 2004), Demoen, B. and Lifschitz, V. , Eds. Lecture Notes in Computer Science, vol. 3131. Springer, 431\u2013445."},{"key":"S1471068420000174_ref11","unstructured":"11. Raedt, L. D. , Kimmig, A. , and Toivonen, H. 2007. Problog: A probabilistic prolog and its application in link discovery. In IJCAI, M. M. Veloso, Ed. 2462\u20132467."},{"key":"S1471068420000174_ref8","unstructured":"8. 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\u20138."},{"key":"S1471068420000174_ref5","volume-title":"LNCS","volume":"4911","author":"De Raedt","year":"2008"},{"key":"S1471068420000174_ref17","unstructured":"17. 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, Tokyo, Japan, June 13-16, 1995, L. Sterling, Ed. MIT Press, 715\u2013729."},{"key":"S1471068420000174_ref18","volume":"9046","author":"Shterionov","year":"2015"},{"key":"S1471068420000174_ref3","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","article-title":"A knowledge compilation map","author":"Darwiche","year":"2002","journal-title":"J. Artif. Intell. Res. 17"},{"key":"S1471068420000174_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000664"},{"key":"S1471068420000174_ref12","first-page":"1","article-title":"The distribution semantics for normal programs with function symbols","author":"Riguzzi","year":"2016","journal-title":"Int. J. Approx. Reason. 77"},{"key":"S1471068420000174_ref7","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1017\/S1471068414000076","article-title":"Inference and learning in probabilistic logic programs using weighted Boolean formulas","volume":"3","author":"Fierens","year":"2015","journal-title":"Theor. Pract. Log. Prog. 15,"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068420000174","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,14]],"date-time":"2021-01-14T08:54:01Z","timestamp":1610614441000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000174\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S1471068420000174"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000174","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}