×

zbMATH — the first resource for mathematics

Structure learning of probabilistic logic programs by searching the clause space. (English) Zbl 1379.68269
Summary: Learning probabilistic logic programming languages is receiving an increasing attention, and systems are available for learning the parameters (PRISM, LeProbLog, LFI-ProbLog and EMBLEM) or both structure and parameters (SEM-CP-logic and SLIPCASE) of these languages. In this paper we present the algorithm SLIPCOVER for “Structure LearnIng of Probabilistic logic programs by searChing OVER the clause space.” It performs a beam search in the space of probabilistic clauses and a greedy search in the space of theories using the log likelihood of the data as the guiding heuristics. To estimate the log likelihood, SLIPCOVER performs Expectation Maximization with EMBLEM. The algorithm has been tested on five real world datasets and compared with SLIPCASE, SEM-CP-logic, Aleph and two algorithms for learning Markov Logic Networks (Learning using Structural Motifs (LSM) and ALEPH++ExactL1). SLIPCOVER achieves higher areas under the precision-recall and receiver operating characteristic curves in most cases.

MSC:
68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beerenwinkel, N.; Rahnenführer, J.; Däumer, M.; Hoffmann, D.; Kaiser, R.; Selbig, J.; Lengauer, T., Learning multiple evolutionary pathways from cross-sectional data., Journal of Computational Biology, 12, 584-598, (2005)
[2] Bellodi, E.; Riguzzi, F., 21st International Conference on Inductive Logic Programming (ILP-2011), Revised Selected Papers, Learning the structure of probabilistic logic programs, 61-75, (2011), Springer: Springer, Berlin, Germany
[3] Bellodi, E.; Riguzzi, F., Experimentation of an expectation maximization algorithm for probabilistic logic programs., Intelligenza Artificiale, 8, 3-18, (2012)
[4] Bellodi, E.; Riguzzi, F., Expectation maximization over binary decision diagrams for probabilistic logic programs., Intelligent Data Analysis, 17, 343-363, (2013)
[5] Berka, P.; Rauch, J.; Tsumoto, S., (2002)
[6] Biba, M.; Ferilli, S.; Esposito, F., Proceedings of the 18th International Conference on Inductive Logic Programming (ILP-2008), Discriminative structure learning of Markov logic networks, 59-76, (2008), Springer: Springer, Berlin, Germany · Zbl 1156.68520
[7] Boyd, K.; Davis, J.; Page, D.; Santos Costa, V., Proceedings of the 29th International Conference on Machine Learning (ICML-2012), Unachievable region in precision-recall space and its effect on empirical evaluation, 639-646, (2012), Edinburgh, Scotland, UK
[8] Bragaglia, S.; Riguzzi, F., 20th International Conference on Inductive Logic Programming (ILP-2010), Approximate inference for logic programs with annotated disjunctions, 30-37, (2011), Springer: Springer, Berlin, Germany · Zbl 1329.68208
[9] Craven, M.; Slattery, S., Relational learning with statistical predicate invention: Better models for hypertext., Machine Learning, 43, 97-119, (2001) · Zbl 0988.68818
[10] Dantsin, E., Russian Conference on Logic Programming (RCLP-1991), Probabilistic logic programs and their semantics, 152-164, (1991), Springer: Springer, Berlin, Germany
[11] Darwiche, A., Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI-2004), New advances in compiling CNF into decomposable negation normal form, 328-332, (2004), IOS Press: IOS Press, Amsterdam, Netherlands
[12] Davis, J.; Goadrich, M., Proceedings of the 23rd International Conference on Machine Learning (ICML-2006), The relationship between precision-recall and ROC curves, 233-240, (2006), ACM: ACM, New York, NY
[13] 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., 1st Workshop on Probabilistic Programming: Universal Languages, Systems and Applications (NIPS 2008), Towards digesting the alphabet-soup of statistical relational learning, 1-3, (2008), Vancouver: Vancouver, British Columbia, Canada
[14] De Raedt, L.; Kersting, K.; Kimmig, A.; Revoredo, K.; Toivonen, H., Compressing probabilistic Prolog programs., Machine Learning, 70, 151-168, (2008)
[15] De Raedt, L.; Kimmig, A.; Toivonen, H., Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), ProbLog: A probabilistic prolog and its application in link discovery, 2462-2467, (2007), AAAI Press: AAAI Press, Menlo Park, CA
[16] De Raedt, L.; Thon, I., 20th International Conference on Inductive Logic Programming (ILP-2010), Revised Papers, Probabilistic rule learning, 47-58, (2010), Springer: Springer, New York, NY
[17] Fawcett, T., An introduction to ROC analysis., Pattern Recognition Letters, 27, 861-874, (2006)
[18] Friedman, N., Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI ’98), The Bayesian structural EM algorithm, 129-138, (1998), Morgan Kaufmann: Morgan Kaufmann, Burlington, MA
[19] Fuhr, N., Probabilistic datalog: Implementing logical information retrieval for advanced applications., Journal of the American Society for Information Science, 51, 95-110, (2000)
[20] Getoor, L.; Friedman, N.; Koller, D.; Pfeffer, A.; Taskar, B.; Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning, Probabilistic relational models, 129-174, (2007), MIT Press: MIT Press, Cambridge, MA
[21] Gutmann, B.; Kimmig, A.; Kersting, K.; De Raedt, L., Machine Learning and Knowledge Discovery in Databases - European Conference (ECML/PKDD-2008), Proceedings, Part I, Parameter learning in probabilistic databases: A least squares approach, 473-488, (2008), Springer: Springer, Berlin, Germany
[22] Gutmann, B.; Kimmig, A.; Kersting, K.; De Raedt, L., Parameter Estimation in ProbLog from Annotated Queries, (2010), KU Leuven: KU Leuven, Belgium
[23] Gutmann, B.; Thon, I.; De Raedt, L., Machine Learning and Knowledge Discovery in Databases - European Conference (ECML/PKDD-2011), Proceedings, Part I, Learning the parameters of probabilistic logic programs from interpretations, 581-596, (2011), Springer: Springer, Berlin, Germany
[24] Huynh, T. N.; Mooney, R. J., Proceedings of the 25th International Conference on Machine Learning (ICML-2008), Discriminative structure and parameter learning for Markov logic networks, 416-423, (2008), ACM: ACM, New York, NY
[25] Inoue, K.; Sato, T.; Ishihata, M.; Kameya, Y.; Nabeshima, H., Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009), Evaluating abductive hypotheses using an EM algorithm on BDDs, 810-815, (2009), Morgan Kaufmann: Morgan Kaufmann, Burlington, MA
[26] Ishihata, M.; Kameya, Y.; Sato, T.; Minato, S., (2008)
[27] Ishihata, M.; Kameya, Y.; Sato, T.; Minato, S., (2008)
[28] Ishihata, M.; Sato, T.; Ichi Minato, S., Proceedings of the 24th Australasian Joint Conference on Advances in Artificial Intelligence (AI 2011), Compiling Bayesian networks for parameter learning based on shared BDDs, 203-212, (2011), Springer: Springer, New York, NY
[29] Kersting, K.; De Raedt, L.; De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming, Basic principles of learning Bayesian logic programs, 189-221, (2008), Springer: Springer, New York, NY · Zbl 1132.68007
[30] Khosravi, H.; Schulte, O.; Hu, J.; Gao, T., Learning compact Markov logic networks with decision trees., Machine Learning, 89, 257-277, (2012)
[31] Kimmig, A.; Demoen, B.; De Raedt, L.; Santos Costa, V.; Rocha, R., On the implementation of the probabilistic logic programming language ProbLog., Theory and Practice of Logic Programming, 11, 235-262, (2011) · Zbl 1220.68037
[32] Kok, S.; Domingos, P., Proceedings of the 22nd International Conference on Machine Learning (ICML-2005), Learning the structure of Markov logic networks, 441-448, (2005), ACM: ACM, New York, NY
[33] Kok, S.; Domingos, P., Proceedings of the 26th Annual International Conference on Machine Learning (ICML-2009), Learning Markov logic network structure via hypergraph lifting, 505-512, (2009), ACM: ACM, New York, NY
[34] Kok, S.; Domingos, P., Proceedings of the 27th International Conference on Machine Learning (ICML-2010), Learning Markov logic networks using structural motifs, 551-558, (2010), Omnipress: Omnipress, Madison, WI
[35] Lowd, D.; Domingos, P., Proceedings of the 18th European Conference on Machine Learning (ECML-2007), Efficient weight learning for Markov logic networks, 200-211, (2007), Springer: Springer, New York, NY
[36] Meert, W.; Struyf, J.; Blockeel, H., Learning ground CP-Logic theories by leveraging Bayesian network learning techniques., Fundamenta Informaticae, 89, 131-160, (2008) · Zbl 1155.68493
[37] Mihalkova, L.; Mooney, R. J., Proceedings of the 24th International Conference on Machine Learning (ICML-2007), Bottom-up learning of Markov logic network structure, 625-632, (2007), ACM: ACM, New York, NY
[38] Minato, S.; Satoh, K.; Sato, T., Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), Compiling Bayesian networks by symbolic probability calculation based on zero-suppressed BDDs, 2550-2555, (2007), AAAI Press: AAAI Press, Palo Alto, CA
[39] Muggleton, S., Inverse entailment and Progol., New Generation Computing, 13, 245-286, (1995)
[40] Ourston, D.; Mooney, R. J., Theory refinement combining analytical and empirical methods., Artificial Intelligence, 66, 273-309, (1994) · Zbl 0807.68089
[41] Paes, A.; Revoredo, K.; Zaverucha, G.; Santos Costa, V., Advances in Artificial Intelligence - Proceedings of the 2nd International Joint Conference, 10th Ibero-American Conference on AI, 18th Brazilian AI Symposium (IBERAMIA-SBIA-2006), PFORTE: Revising probabilistic FOL theories, 441-450, (2006), Springer: Springer, New York, NY
[42] Poole, D., Logic programming, abduction and probability - a top-down anytime algorithm for estimating prior and posterior probabilities., New Generation Computing, 11, 377-400, (1993) · Zbl 0788.68025
[43] Poole, D., The independent choice logic for modelling multiple agents under uncertainty., Artificial Intelligence, 94, 7-56, (1997) · Zbl 0902.03017
[44] Przymusinski, T. C., Proceedings of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-1989), Every logic program has a natural stratification and an iterated least fixed point model, 11-21, (1989), ACM Press: ACM Press, New York, NY
[45] Quinlan, J. R.; Cameron-Jones, R. M., Machine Learning: ECML-93, Proceedings of the European Conference on Machine Learning, FOIL: A midterm report, 3-20, (1993), Springer: Springer, Berlin, Germany
[46] Rauzy, A.; Châtelet, E.; Dutuit, Y.; Bérenguer, C., A practical comparison of methods to assess sum-of-products., Reliability Engineering and System Safety, 79, 33-42, (2003)
[47] Richards, B. L.; Mooney, R. J., Automated refinement of first-order Horn-clause domain theories., Machine Learning, 19, 95-131, (1995)
[48] Richardson, M.; Domingos, P., Markov logic networks., Machine Learning, 62, 107-136, (2006)
[49] Riguzzi, F., Proceedings of the 14th International Conference on Inductive Logic Programming (ILP-2004), Learning logic programs with annotated disjunctions, 270-287, (2004), Springer-Verlag: Springer-Verlag, Berlin, Germany · Zbl 1105.68394
[50] Riguzzi, F., 16th International Conference on Inductive Logic Programming (ILP-2006), Revised Selected Papers, ALLPAD: Approximate Learning of Logic Programs with Annotated Disjunctions, 43-45, (2006), Springer: Springer, Berlin, Germany
[51] Riguzzi, F., AI*IA 2007: Artificial Intelligence and Human-Oriented Computing, Proceedings of the 10th Congress of the Italian Association for Artificial Intelligence, A top-down interpreter for LPAD and CP-Logic, 109-120, (2007), Springer: Springer, Berlin, Germany
[52] Riguzzi, F., ALLPAD: Approximate Learning of Logic Programs with Annotated Disjunctions, Machine Learning, 70, 207-223, (2008)
[53] Riguzzi, F., Proceedings of the 24th International Conference on Logic Programming (ICLP-2008), Inference with Logic Programs with Annotated Disjunctions under the well-founded semantics, 667-771, (2008), Springer: Springer, Berlin, Germany · Zbl 1185.68178
[54] Riguzzi, F., Extended semantics and inference for the independent choice logic., Logic Journal of the IGPL, 17, 589-629, (2009) · Zbl 1189.03039
[55] Riguzzi, F., SLGAD resolution for inference on Logic Programs with Annotated Disjunctions., Fundamenta Informaticae, 102, 429-466, (2010) · Zbl 1220.68040
[56] Riguzzi, F., MCINTYRE: A Monte Carlo system for probabilistic logic programming, Fundamenta Informaticae, 124, 521-541, (2013)
[57] Riguzzi, F., Speeding up inference for probabilistic logic programs, The Computer Journal, (2013)
[58] Riguzzi, F.; Di Mauro, N., Applying the information bottleneck to statistical relational learning., Machine Learning, 86, 89-114, (2012) · Zbl 1243.68247
[59] Riguzzi, F.; Swift, T., Technical Communications of the 26th International Conference on Logic Programming (ICLP-2010), Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions, 162-171, (2010), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany · Zbl 1237.68049
[60] 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 (ICLP) Special Issue, 11, 433-449, (2011) · Zbl 1218.68169
[61] Riguzzi, F.; Swift, T., Well-definedness and efficient inference for probabilistic logic programming under the distribution semantics., Theory and Practice of Logic Programming, 13, 279-302, (2013) · Zbl 1267.68084
[62] Sang, T.; Beame, P.; Kautz, H. A., Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference (AAAI-2005), Performing Bayesian inference by weighted model counting, 475-482, (2005), AAAI Press/The MIT Press: AAAI Press/The MIT Press, Cambridge, MA
[63] Santos Costa, V.; Damas, L.; Rocha, R., The YAP Prolog system., Theory and Practice of Logic Programming, 12, 5-34, (2012) · Zbl 1244.68017
[64] Santos Costa, V.; Page, D.; Qazi, M.; Cussens, J., Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI’03), CLP(BN): Constraint logic programming for probabilistic knowledge, 517-524, (2003), Morgan Kaufmann: Morgan Kaufmann, Burlington, MA
[65] Sato, T., Proceedings of the 12th International Conference on Logic Programming (ICLP-1995), A statistical learning method for logic programs with distribution semantics, 715-729, (1995), MIT Press: MIT Press, Cambridge, MA
[66] Sato, T.; Kameya, Y., Parameter learning of logic programs for symbolic-statistical modeling., Journal of Artificial Intelligence Research, 15, 391-454, (2001) · Zbl 0994.68025
[67] Schwarz, G., Estimating the dimension of a model., The Annals of Statistics, 6, 461-464, (1978) · Zbl 0379.62005
[68] Srinivasan, A., (2012)
[69] Srinivasan, A.; Muggleton, S.; King, R.; Sternberg, M., Proceedings of the 4th International Workshop on Inductive Logic Programming, Mutagenesis: ILP experiments in a non-determinate biological domain, 217-232, (1994), Gesellschaft fur Mathematik und Datenverarbeitung MBH
[70] Srinivasan, A.; Muggleton, S.; Sternberg, M. J. E.; King, R. D., Theories for mutagenicity: A study in first-order and feature-based induction., Artificial Intelligence, 85, 277-299, (1996)
[71] Thayse, A.; Davio, M.; Deschamps, J. P., Proceedings of the 8th International Symposium on Multiple-Valued logic (MLV ’78), Optimization of multivalued decision algorithms, 171-178, (1978), IEEE Computer Society Press: IEEE Computer Society Press, Washington, DC · Zbl 0444.90111
[72] Thon, I.; Landwehr, N.; De Raedt, L., Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD-2008), Part II, A simple model for sequences of relational state descriptions, 506-521, (2008), Springer: Springer, New York, NY
[73] Van Gelder, A.; Ross, K. A.; Schlipf, J. S., The well-founded semantics for general logic programs., Journal of the ACM, 38, 620-650, (1991) · Zbl 0799.68045
[74] 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, 245-308, (2009) · Zbl 1179.68025
[75] Vennekens, J.; Verbaeten, S., Logic Programs with Annotated Disjunctions, (2003), KU Leuven, Netherlands · Zbl 1104.68391
[76] Vennekens, J.; Verbaeten, S.; Bruynooghe, M., Proceedings of the 20th International Conference on Logic Programming (ICLP-2004), Logic programs with annotated disjunctions, 195-209, (2004), Springer: Springer, Berlin, Germany
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.