MCINTYRE : A Monte Carlo System for Probabilistic Logic Programming

• Autorzy: Riguzzi F.
• Języki publikacji: EN

Abstrakty

EN

Probabilistic Logic Programming is receiving an increasing attention for its ability to model domains with complex and uncertain relations among entities. In this paper we concentrate on the problem of approximate inference in probabilistic logic programming languages based on the distribution semantics. A successful approximate approach is based on Monte Carlo sampling, that consists in verifying the truth of the query in a normal program sampled from the probabilistic program. The ProbLog system includes such an algorithm and so does the cplint suite. In this paper we propose an approach for Monte Carlo inference that is based on a program transformation that translates a probabilistic program into a normal program to which the query can be posed. The current sample is stored in the internal database of the Yap Prolog engine. The resulting system, called MCINTYRE for Monte Carlo INference wiTh Yap REcord, is evaluated on various problems: biological networks, artificial datasets and a hidden Markov model. MCINTYRE is compared with the Monte Carlo algorithms of ProbLog and cplint and with the exact inference of the PITA system. The results show that MCINTYRE is faster than the other Monte Carlo systems.

Słowa kluczowe

EN

logic programs with annotated disjunctions; Monte Carlo methods; probabilistic logic programming; ProbLog

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 4
• Strony: 521--541
• Opis fizyczny: Bibliogr. 46 poz., wykr.

Twórcy

autor

Riguzzi F.

• Dipartimento di Matematica e Informatica, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy

Bibliografia

• [1]. Bellodi, E., Riguzzi, F.: EM over Binary Decision Diagrams for Probabilistic Logic Programs, Italian Conference on Computational Logic, vol. 810 of CEUR Workshop Proceedings, Sun SITE Central Europe, 2011, ISSN 1613-0073.
• [2]. Bellodi, E., Riguzzi, F.: Experimentation of an Expectation Maximization Algorithm for Probabilistic Logic Programs, Intelligenza Artificiale, 8(1), 2012, 3-18, doi10.3233/IA-2012-0027.
• [3]. Bellodi, E., Riguzzi, F.: Learning the Structure of Probabilistic Logic Programs, International Conference on Inductive Logic Programming, vol. 7207 of LNCS, Springer, 2012, doi10.1007/978-3-642-31951-8_10.
• [4]. Bellodi, E., Riguzzi, F.: Expectation Maximization over Binary Decision Diagrams for Probabilistic Logic Programs, Intelligent Data Analysis, 17(2), 2013.
• [5]. Bragaglia, S., Riguzzi, F.: Approximate Inference for Logic Programs with Annotated Disjunctions, International Conference on Inductive Logic Programming, vol. 6489 of LNCS, Springer, 2011, doi10.1007/978- 3-642-21295-6_7.
• [6]. Christiansen, H., Gallagher, J. P.: Non-discriminating Arguments and Their Uses, International Conference on Logic Programming, vol. 5649 of LNCS, Springer, 2009, doi10.1007/978-3-642-02846-5_10.
• [7]. Costa, V. S., Damas, L., Rocha, R.: The YAP Prolog System, Theory and Practice of Logic Programming, 12(1-2), 2012, 5-34, doi10.1017/S1471068411000512.
• [8]. Dantsin, E.: Probabilistic Logic Programs and their Semantics, Russian Conference on Logic Programming, vol. 592 of LNCS, Springer, 1991, doi10.1007/3-540-55460-2_11.
• [9]. 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., Vennekens, J.: Towards Digesting the Alphabet-Soup of Statistical Relational Learning, Workshop on Probabilistic Programming: Universal Languages, Systems and Applications, in NIPS (D. Roy, J. Winn, D. McAllester, V. Mansinghka, J. Tenenbaum, Eds.), 2008.
• [10]. De Raedt, L., Frasconi, P., Kersting, K., Muggleton, S., Eds.: Probabilistic Inductive Logic Programming - Theory and Applications, vol. 4911 of LNCS, Springer, 2008.
• [11]. De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: A Probabilistic Prolog and Its Application in Link Discovery., International Joint Conference on Artificial Intelligence, AAAI Press, 2007.
• [12]. Fierens, D., Van den Broeck, G., Thon, I., Gutmann, B., De Raedt, L.: Inference in probabilistic logic programs using weighted CNF’s, Conference on Uncertainty in Artificial Intelligence, AUAI Press, 2011.
• [13]. Fuhr, N.: Probabilistic datalog: Implementing logical information retrieval for advanced applications, Journal of the American Society for Information Science, 51(2), 2000, 95-110.
• [14]. Gavanelli, M., Riguzzi, F., Milano, M., Cagnoli, P.: Logic-Based Decision Support for Strategic Environmental Assessment, Theory and Practice of Logic Programming, International Conference on Logic Programming Special Issue, 10(4-6), July 2010, 643-658, doi10.1017/S1471068410000335.
• [15]. Getoor, L., Taskar, B., Eds.: Introduction to Statistical Relational Learning, MIT Press, 2007.
• [16]. Gutmann, B., Kimmig, A., Kersting, K., Raedt, L. D.: Parameter Learning in Probabilistic Databases: A Least Squares Approach, European Conference on Machine Learning, vol. 5211 of LNCS, Springer, 2008, doi10.1007/978-3-540-87479-9_49.
• [17]. Gutmann, B., Thon, I., Kimmig, A., Bruynooghe, M., De Raedt, L.: The magic of logical inference in probabilistic programming, Theory and Practice of Logic Programming, 11(4-5), 2011, 663-680, doi10.1017/S1471068411000238.
• [18]. Gutmann, B., Thon, I., Raedt, L. D.: Learning the Parameters of Probabilistic Logic Programs from Interpretations, European Conference on Machine Learning and Knowledge Discovery in Databases, vol. 6911 of LNCS, Springer, 2011, doi10.1007/978-3-642-23780-5_47.
• [19]. Kimmig, A., Demoen, B., De Raedt, L., Costa, V. S., Rocha, R.: On the implementation of the probabilistic logic programming language ProbLog, Theory and Practice of Logic Programming, 11(2-3), 2011, 235-262, doi10.1017/S1471068410000566.
• [20]. Meert, W., Struyf, J., Blockeel, H.: CP-Logic Theory Inference with Contextual Variable Elimination and Comparison to BDD Based Inference Methods, International Conference on Inductive Logic Programming, vol. 5989 of LNCS, Springer, 2010, doi10.1007/978-3-642-13840-9_10.
• [21]. Poole, D.: Logic Programming, Abduction and Probability - A Top-Down Anytime Algorithm for Estimating Prior and Posterior Probabilities, New Generation Computing, 11(3-4), 1993, 377-400, doi10.1007/BF03037184.
• [22]. Poole, D.: The Independent Choice Logic for Modelling Multiple Agents under Uncertainty, Artificial Intelligence, 94(1-2), 1997, 7-56, doi10.1016/S0004-3702(97)00027-1.
• [23]. De Raedt, L., Kersting, K., Kimmig, A., Revoredo, K., Toivonen, H.: Compressing probabilistic Prolog programs, Machine Learning, 70(2-3), 2008, 151-168, doi10.1007/s10994-007-5030-x.
• [24]. Riguzzi, F.: Learning Logic Programs with Annotated Disjunctions, International Conference on Inductive Logic Programming, vol. 3194 of LNCS, Springer, September 2004, doi10.1007/978-3-540-30109-7^1.
• [25]. Riguzzi, F.: ALLPAD: Approximate Learning of Logic Programs with Annotated Disjunctions, International Conference on Inductive Logic Programming, vol. 4455 of LNCS, Springer, 2007, doi10.1007/978-3-540- 73847-3-11.
• [26]. Riguzzi, F.: A Top Down Interpreter for LPAD and CP-logic, Congress of the Italian Association for Artificial Intelligence, vol. 4733 of LNCS, Springer, 2007, doi10.1007/978-3-540-74782-6_11.
• [27]. Riguzzi, F.: ALLPAD: Approximate Learning of Logic Programs with Annotated Disjunctions, Machine Learning, 70(2-3), March 2008, 207-223, doi10.1007/s10994-007-5032-8.
• [28]. Riguzzi, F.: Inference with Logic Programs with Annotated Disjunctions under the Well Founded Semantics, International Conference on Logic Programming, vol. 5366 of LNCS, Springer, 2008, doi10.1007/978-3- 540-89982-2_54.
• [29]. Riguzzi, F.: Extended Semantics and Inference for the Independent Choice Logic, Logic Journal of the IGPL, 17(6), 2009, 589-629, doi10.1093/jigpal/jzp025.
• [30]. Riguzzi, F.: SLGAD Resolution for Inference on Logic Programs with Annotated Disjunctions, Fundamenta Informaticae, 102(3-4), October 2010, 429-466, doi10.3233/FI-2010-392.
• [31]. Riguzzi, F.: Optimizing Inference for Probabilistic Logic Programs Exploiting Independence and Exclusiveness, Italian Conference on Computational Logic, vol. 857 of CEUR Workshop Proceedings, Sun SITE Central Europe, 2012, ISSN 1613-0073.
• [32]. Riguzzi, F., Bellodi, E., Lamma, E.: Probabilistic Datalog+/- under the Distribution Semantics, International Workshop on Description Logics, vol. 846 of CEUR Workshop Proceedings, Sun SITE Central Europe, 2012, ISSN 1613-0073.
• [33]. Riguzzi, F., Di Mauro, N.: Applying the Information Bottleneck to Statistical Relational Learning, Machine Learning, 86(1), 2012, 89-114, doi10.1007/s10994-011-5247-6.
• [34]. Riguzzi, F., Swift, T.: An Extended Semantics for Logic Programs with Annotated Disjunctions and its Efficient Implementation, Italian Conference on Computational Logic, vol. 598 of CEUR Workshop Proceedings, Sun SITE Central Europe, Aachen, Germany, 2010, ISSN 1613-0073.
• [35]. Riguzzi, F., Swift, T.: Tabling and Answer Subsumption for Reasoning on Logic Programs with Annotated Disjunctions, International Conference on Logic Programming, vol. 7 of LIPIcs, Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, July 2010, doi10.4230/LIPIcs.ICLP.2010.162.
• [36]. Riguzzi, F., Swift, T.: The PITA System: Tabling and Answer Subsumption for Reasoning under Uncertainty, Theory and Practice of Logic Programming, International Conference on Logic Programming Special Issue, 11(4-5), 2011, 433-449, doi10.1017/S147106841100010X.
• [37]. Riguzzi, F., Swift, T.: The PITA System for Logical-Probabilistic Inference, Latest Advances in Inductive Logic Programming, Inductive Logic Programming, 21th International Conference, Imperial College Press, 2012.
• [38]. Riguzzi, F., Swift, T.: Well-Definedness and Efficient Inference for Probabilistic Logic Programming under the Distribution Semantics, Theory and Practice of Logic Programming, 13 (Special Issue 02 - 25th Annual GULP Conference): 279-302, 2013, doi10.1017/S1471068411000664.
• [39]. Ryan, T. P.: Modern Engineering Statistics, John Wiley & Sons, 2007.
• [40]. Sato, T.: A Statistical Learning Method for Logic Programs with Distribution Semantics, International Conference on Logic Programming, MIT Press, 1995.
• [41]. Sato, T., Kameya, Y.: Parameter Learning of Logic Programs for Symbolic-Statistical Modeling, Journal of Artificial Intelligence Research, 15, 2001, 391-454.
• [42]. Sevon, P., Eronen, L., Hintsanen, P., Kulovesi, K., Toivonen, H.: Link Discovery in Graphs Derived from Biological Databases, International Workshop on Data Integration in the Life Sciences, vol. 4075 of LNCS, Springer, 2006, doi10.1007/11799511_5.
• [43]. Valiant, L. G.: The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, 8(3), 1979,410-421, doi10.1137/0208032.
• [44]. Vennekens, J., Denecker, M., Bruynooghe, M.: CP-logic: A language of causal probabilistic events and its relation to logic programming, Theory and Practice of Logic Programming, 9(3), 2009, 245-308, doi10.1017/S1471068409003767.
• [45]. Vennekens, J., Verbaeten, S.: Logic Programs With Annotated Disjunctions, Technical Report CW386, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 2003.
• [46]. Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic Programs With Annotated Disjunctions, International Conference on Logic Programming, vol. 3131 of LNCS, Springer, 2004, doi10.1007/978-3-540-27775-0_30.