Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-18T22:52:39.680Z Has data issue: false hasContentIssue false
  • English
  • Français

On the implementation of the probabilistic logic programming language ProbLog

Published online by Cambridge University Press:  27 January 2011

ANGELIKA KIMMIG ,
BART DEMOEN ,
LUC DE RAEDT ,
VÍTOR SANTOS COSTA  and
RICARDO ROCHA
ANGELIKA KIMMIG
Affiliation:
Departement Computerwetenschappen, K.U. Leuven, Celestijnenlaan 200A - Bus 2402, B-3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected])
BART DEMOEN
Affiliation:
Departement Computerwetenschappen, K.U. Leuven, Celestijnenlaan 200A - Bus 2402, B-3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected])
LUC DE RAEDT
Affiliation:
Departement Computerwetenschappen, K.U. Leuven, Celestijnenlaan 200A - Bus 2402, B-3001 Heverlee, Belgium (e-mail: [email protected], [email protected], [email protected])
VÍTOR SANTOS COSTA
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal (e-mail: [email protected], [email protected])
RICARDO ROCHA
Affiliation:
CRACS & INESC-Porto LA, Faculty of Sciences, University of Porto, R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The past few years have seen a surge of interest in the field of probabilistic logic learning and statistical relational learning. In this endeavor, many probabilistic logics have been developed. ProbLog is a recent probabilistic extension of Prolog motivated by the mining of large biological networks. In ProbLog, facts can be labeled with probabilities. These facts are treated as mutually independent random variables that indicate whether these facts belong to a randomly sampled program. Different kinds of queries can be posed to ProbLog programs. We introduce algorithms that allow the efficient execution of these queries, discuss their implementation on top of the YAP-Prolog system, and evaluate their performance in the context of large networks of biological entities.

Keywords

Probabilistic logic programmingExact and approximative inferenceImplementation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 2-3: The 24th International Conference on Logic Programming (ICLP 2008) , March 2011 , pp. 235 - 262
Copyright
Copyright © Cambridge University Press 2011

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

Bachmair, L., Chen, T. and Ramakrishnan, I. V. 1993. Associative commutative discrimination nets. In International Joint Conference on Theory and Practice of Software Development, Gaudel, M.-C. and Jouannaud, J.-P., Eds. LNCS, Vol. 668. Springer, New Mexico, 61–74.Google Scholar
Bryant, R. E. 1986. Graph-based algorithms for boolean function manipulation. IEEE Transactions Computers 35 (8), 677–691.CrossRefGoogle Scholar
Cussens, J. 2000. Stochastic logic programs: Sampling, inference and applications. In Uncertainty in Artificial Intelligence, Boutilier, C. and Goldszmidt, M., Eds. Morgan Kaufmann, Massachusetts, 115–122.Google Scholar
Dalvi, N. N. and Suciu, D. 2004. Efficient query evaluation on probabilistic databases. In International Conference on Very Large Databases, Nascimento, M. A., Özsu, M. T., Kossmann, D., Miller, R. J., Blakeley, J. A. and Schiefer, K. B., Eds. Morgan Kaufmann, Massachusetts, 864–875.Google Scholar
Dantsin, E. 1991. Probabilistic logic programs and their semantics. In Russian Conference on Logic Programming, Voronkov, A., Ed., LNCS, Vol. 592. Springer, 152–164.Google Scholar
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. 2008a. Towards digesting the alphabet-soup of statistical relational learning [online]. In NIPS Workshop on Probabilistic Programming. URL: http://probabilistic-programming.org/wiki/NIPS*2008_Workshop.Google Scholar
De Raedt, L., Frasconi, P., Kersting, K. and Muggleton, S., Eds. 2008b. Probabilistic Inductive Logic Programming – Theory and Applications, LNCS, Vol. 4911. Springer.CrossRefGoogle Scholar
De Raedt, L., Kersting, K., Kimmig, A., Revoredo, K. and Toivonen, H. 2008c. Compressing probabilistic Prolog programs. Machine Learning 70 (2–3), 151–168.CrossRefGoogle Scholar
De Raedt, L., Kimmig, A., Gutmann, B., Kersting, K., SantosCosta, V. Costa, V. and Toivonen, H. 2009. Probabilistic Inductive Querying Using ProbLog, Tech. Rep. CW 552. Department of Computer Science, Katholieke Universiteit Leuven.Google Scholar
De Raedt, L., Kimmig, A. and Toivonen, H. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In International Joint Conference on Artificial Intelligence, Veloso, M. M., Ed. AAAI Press/The MIT Press, 2462–2467.Google Scholar
Fredkin, E. 1962. Trie Memory. Communications of the ACM 3, 490–499.CrossRefGoogle Scholar
Fuhr, N. 2000. Probabilistic Datalog: Implementing logical information retrieval for advanced applications. Journal of the American Society for Information Science (JASIS) 51 (2), 95–110.3.0.CO;2-H>CrossRefGoogle Scholar
Getoor, L. and Taskar, B., Eds. 2007. Statistical Relational Learning. The MIT Press, Cambridge, MA.Google Scholar
Graf, P. 1996. Term Indexing. LNAI, Vol. 1053. Springer, New Mexico.Google Scholar
Gutmann, B., Kimmig, A., Kersting, K. and DeRaedt, L. Raedt, L. 2008. Parameter learning in probabilistic databases: A least squares approach. In European Conference on Machine Learning, Daelemans, W., Goethals, B., and Morik, K., Eds., LNCS, Vol. 5211 Springer, New Mexico, 473–488.Google Scholar
Ishihata, M., Kameya, Y., Sato, T. and ichi Minato, S. 2008. Propositionalizing the EM algorithm by BDDs. In Proceedings of Inductive Logic Programming (ILP 2008), Late Breaking Papers, Železný, F. and Lavrač, N., Eds. Prague, Czech Republic, 44–49.Google Scholar
Kersting, K. and De Raedt, L. 2008. Basic principles of learning bayesian logic programs. In Probabilistic Inductive Logic Programming, De Raedt, L., Frasconi, P., Kersting, K., and Muggleton, S., Eds., LNCS, Vol. 4911. Springer, New Mexico, 189–221.CrossRefGoogle Scholar
Kimmig, A. and De Raedt, L. 2009. Local query mining in a probabilistic Prolog. In International Joint Conference on Artificial Intelligence, Boutilier, C., Ed. AAAI Press, 1095–1100.Google Scholar
Kimmig, A., De Raedt, L. and Toivonen, H. 2007. Probabilistic explanation based learning. In European Conference on Machine Learning, Kok, J. N., Koronacki, J., de Mántaras, R. L., Matwin, S., Mladenic, D. and Skowron, A., Eds., LNCS, Vol. 4701. Springer, New Mexico, 176–187.Google Scholar
Kimmig, A., Gutmann, B. and Santos Costa, V. 2009. Trading memory for answers: Towards tabling ProbLog [online]. In International Workshop on Statistical Relational Learning, Domingos, P. and Kersting, K., Eds. URL: http://dtai.cs.kuleuven.be/ilp-mlg-srl/index.phpGoogle Scholar
Kimmig, A., Santos Costa, V., Rocha, R., Demoen, B. and De Raedt, L. 2008. On the Efficient Execution of ProbLog Programs. In International Conference on Logic Programming, de la Banda, M. G. and Pontelli, E., Eds., Number 5366 in LNCS. Springer, New Mexico, 175–189.CrossRefGoogle Scholar
Lakshmanan, L. V. S., Leone, N., Ross, R. B. and Subrahmanian, V. S. 1997. ProbView: A flexible probabilistic database system. ACM Transactions on Database Systems 22 (3), 419–469.CrossRefGoogle Scholar
Mantadelis, T. and Janssens, G. 2009. Tabling relevant parts of SLD proofs for ground goals in a probabilistic setting [online]. In International Colloquium on Implementation of Constraint and Logic Programming Systems, Tarau, P., Moura, P. and Zhou, N.-F., Eds. 36–50. URL: http://www.cse.unt.edu/~tarau/ciclops09/Google Scholar
Muggleton, S. 1995. Stochastic logic programs. In Advances in ILP, De Raedt, L., Ed. IOS Press, 254–264.Google Scholar
Poole, D. 1993a. Logic programming, abduction and probability. New Generation Computing 11, 377–400.CrossRefGoogle Scholar
Poole, D. 1993b. Probabilistic Horn abduction and Bayesian networks. Artificial Intelligence 64, 81–129.CrossRefGoogle Scholar
Poole, D. 2000. Abducing through negation as failure: Stable models within the independent choice logic. Journal of Logic Programming 44 (1–3), 5–35.CrossRefGoogle Scholar
Ramakrishnan, I. V., Rao, P., Sagonas, K., Swift, T. and Warren, D. S. 1999. Efficient access mechanisms for tabled logic programs. Journal of Logic Programming 38 (1), 31–54.CrossRefGoogle Scholar
Riguzzi, F. 2007. A top down interpreter for LPAD and CP-logic. In Congress of the Italian Association for Artificial Intelligence (AI*IA), Basili, R. and Pazienza, M. T., Eds., LNCS, Vol. 4733. Springer, New Mexico, 109–120.Google Scholar
Santos Costa, V. 2007. Prolog performance on larger datasets. In Practical Aspects of Declarative Languages, 9th International Symposium, PADL 2007, Nice, France, January 14–15, 2007, Hanus, M., Ed., LNCS, Vol. 4354. Springer, New Mexico, 185–199.Google Scholar
SantosCosta, V. Costa, V., Page, D., Qazi, M. and Cussens, J. 2003. CLP(BN): Constraint logic programming for probabilistic knowledge. In Conference on Uncertainty in Artificial Intelligence, Meek, C. and Kjærulff, U., Eds. Morgan Kaufmann, Massachusetts, 517–524.Google Scholar
Santos Costa, V., Sagonas, K. and Lopes, R. 2007. Demand-driven indexing of prolog clauses. In International Conference on Logic Programming, Dahl, V. and Niemelä, I., Eds. LNCS, Vol. 4670. Springer, New Mexico, 305–409.Google Scholar
Sato, T. 1995. A statistical learning method for logic programs with distribution semantics. In International Conference on Logic Programming, Sterling, L., Ed. MIT Press, Cambridge, MA, 715–729.CrossRefGoogle Scholar
Sato, T. and Kameya, Y. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research (JAIR) 15, 391–454.CrossRefGoogle Scholar
Sevon, P., Eronen, L., Hintsanen, P., Kulovesi, K. and Toivonen, H. 2006. Link discovery in graphs derived from biological databases. In Data Integration in the Life Sciences, Leser, U., Naumann, F., and Eckman, B. A., Eds., LNCS, Vol. 4075. Springer, New Mexico, 35–49.CrossRefGoogle Scholar
Valiant, L. G. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8 (3), 410–421.CrossRefGoogle Scholar
Vennekens, J., Verbaeten, S. and Bruynooghe, M. 2004. Logic programs with annotated disjunctions. In International Conference on Logic Programming, Demoen, B. and Lifschitz, V., Eds., LNCS, Vol. 3132. Springer, New Mexico, 431–445.CrossRefGoogle Scholar
Widom, J. 2005. Trio: A system for integrated management of data, accuracy, and lineage [online]. In Conference on Innovative Data Systems Research, Stonebraker, M., Weikum, G. and DeWitt, D., Eds. 262–276. URL: http://www.cidrdb.org/cidr2005/Google Scholar