Probabilistic logic learning

Abstract

The past few years have witnessed an significant interest in probabilistic logic learning, i.e. in research lying at the intersection of probabilistic reasoning, logical representations, and machine learning. A rich variety of different formalisms and learning techniques have been developed. This paper provides an introductory survey and overview of the state-of-the-art in probabilistic logic learning through the identification of a number of important probabilistic, logical and learning concepts.

References

1. J. Allen. Natural Language Understanding. Benjamin/Cummings Series in Computer Science. Benjamin/Cummings Publishing Company, 1987.]]
2. C. R. Anderson, P. Domingos, and D. S. Weld. Relational Markov Models and their Application to Adaptive Web Navigation. In D. Hand, D. Keim, O. R. Zaine, and R. Goebel, editors, Proceedings of the Eighth International Conference on Knowledge Discovery and Data Mining (KDD-02), pages 143--152, Edmonton, Canada, 2002. ACM Press.]]
3. N. Angelopoulos and J. Cussens. Markov chain Monte Carlo using tree-based priors on model structure. In J. Breese and D. Koller, editors, Proceedings of the Seventeenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-01), pages 16--23, Seattle, Washington, USA, 2001. Morgan Kaufmann.]]
4. F. Bacchus. Using first-order probability logic for the construction of bayesian networks. In D. Heckerman and A. Mamdani, editors, Proceedings of the Ninth Annual Conference on Uncertainty in Artificial Intelligence (UAI-93), pages 219--226, Providence, Washington, DC, USA, 1993. Morgan Kaufmann.]]
5. F. Bergadano and D. Gunetti. Inductive Logic Programming: From Machine Learning to Software Engeneering. MIT Press, 1996.]]
6. J. S. Breese. Construction of Belief and decision networks. Computational Intelligence, 8(4):624--647, 1992.]]
7. J. S. Breese, R. P. Goldman, and M. P. Wellman. Introduction to the special section on knowledge-based construction of probabilistic and decision models. Cybernetics, 24(11):1577--1579, 1994.]]
8. W. Buntine. A guide to the literature on learning probabilistic networks from data. IEEE Transaction on Knowledge and Data Engineering, 8:195--210, 1996.]]
9. K. L. Clark and F. G. McCabe. PROLOG: A Language for Implementing Expert Systems. In J. E. Hayes, D. Michie, and Y. H. Pao, editors, Machine Intelligence, volume 10, pages 455--470. Ellis Horwood, Chichester, 1982.]]
10. R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probabilistic networks and expert systems. Springer-Verlag, 1999.]]
11. M. Craven and S. Slattery. Relational Learning with Statistical Predicate Invention: Better Models for Hypertext. Machine Learning, 43(1--2):97--119, 2001.]]
12. J. Cussens. Loglinear models for first-order probabilistic reasoning. In K. B. Laskey and H. Prade, editors, Proceedings of the Fifteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-99), pages 126--133, Stockholm, Sweden, 1999. Morgan Kaufmann.]]
13. J. Cussens. Stochastic logic programs: Sampling, inference and applications. In C. Boutilier and M. Goldszmidt, editors, Proceedings of the Sixteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-00), pages 115--122, Stanford, CA USA, 2000. Morgan Kaufmann.]]
14. J. Cussens. Parameter estimation in stochastic logic programs. Machine Learning, 44(3):245--271, 2001.]]
15. J. Cussens. Statistical aspects of stochastic logic programs. In T. Jaakkola and T. Richardson, editors, Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics 2001, pages 181--186, Key West, Florida, USA, 2001. Morgan Kaufmann.]]
16. L. De Raedt. Interactive Theory Revision: An Inductive Logic Programming Approach. Academic Press, 1992.]]
17. L. De Raedt. Logical settings for concept-learning. Artificial Intelligence, 95(1):197--201, 1997.]]
18. L. De Raedt and L. Dehaspe. Clausal discovery. Machine Learning, 26(2--3):99--146, 1997.]]
19. T. Dean and K. Kanazawa. Probabilistic temporal reasoning. In T. M. Mitchell and R. G. Smith, editors, Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88), pages 524--528, St. Paul, MN, USA, 1988. AAAI Press / The MIT Press.]]
20. A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc., B 39 :1--39, 1977.]]
21. M. Diligenti, P. Frasconi, and M. Gori. Hidden Tree Markov Models for Document Image Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(4):519--523, 2003.]]
22. R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.]]
23. S. Džeroski and N. Lavrač. Relational Data Mining. Springer-Verlag, 2001.]]
24. A. Eisele. Towards probabilistic extensions of contraint-based grammars. In J. Dörne, editor, Computational Aspects of Constraint-Based Linguistics Decription-II. DYNA-2 deliverable R1.2.B, 1994.]]
25. William Feller. An Introduction to Probability Theory and its Applications: Volume 1. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, 3rd edition, 1968.]]
26. P. Flach. Simply logical: intelligent reasoning by example. John Wiley and Sons Ltd., 1994.]]
27. P. Flach and N. Lachiche. 1BC: A first-order Bayesian classifier. In S. Džeroski and P. Flach, editors, Proceedings of the Ninth International Workshop on Inductive Logic Programming (ILP-99), volume 1634 of LNAI, pages 92--103, Bled, Slovenia, 1999. Springer.]]
28. P. Frasconi, M. Gori, and A. Sperduti. A general framework for adaptive processing of data structures. IEEE Transactions on Neural Networks, 9(5):768--786, 1998.]]
29. N. Friedman. The Bayesian Structural EM Algorithm. In G. F. Cooper and S. Moral, editors, Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 129--138, Madison, Wisconsin, USA, 1998. Morgan Kaufmann.]]
30. N. Friedman, L. Getoor, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In T. Dean, editor, Proceedings of the Sixteenth International Joint Conferences on Artificial Intelligence (IJCAI-99), pages 1300--1309, Stockholm, Sweden, 1999. Morgan Kaufmann.]]
31. L. Getoor. Learning Statistical Models from Relational Data. PhD thesis, Stanford University, 2001.]]
32. L. Getoor, N. Friedman, and D. Koller. Learning Structured Statistical Models from Relational Data. Linköping Electronic Articles in Computer and Information Science, 7(13), 2002.]]
33. L. Getoor, N. Friedman, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In S. Džeroski and N. Lavrač, editors, Relational Data Mining. Springer-Verlag, 2001.]]
34. L. Getoor, N. Friedman, D. Koller, and B. Taskar. Learning Probabilistic Models of Relational Structure. In C. E. Brodley and A. Pohoreckyj Danyluk, editors, Proceedings of the Eighteenth International Conference on Machine Learning (ICML-01), pages 170--177, Williamstown, MA, USA, 2001. Morgan Kaufmann.]]
35. L. Getoor, D. Koller, and B. Taskar. Statistical Models for Relational Data. In S. Džeroski and L. De Raedt, editors, Workshop Notes of the KDD-02 Workshop on Multi-Relational Data Mining (MRDM-O2), 2002.]]
36. L. Getoor, D. Koller, B. Taskar, and N. Friedman. Learning probabilistic relational models with structural uncertainty. In L. Getoor and D. Jensen, editors, Proceedings of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data, pages 13--20, 2000.]]
37. L. Getoor, E. Segal, B. Taskar, and D. Koller. Probabilistic Models of Text and Link Structure for Hypertext Classification. In Workshop Notes of IJCAI-01 Workshop on 'Text Learning: Beyond Supervision', Washington, USA, 2001.]]
38. L. Getoor, B. Taskar, and D. Koller. Selectivity Estimation using Probabilistic Relational Models. In W. G. Aref, editor, Proceedings of the ACM Special Interest Group on Management of Data Conference (SIGMOD-01), Santa Barbara, CA, USA, 2001.]]
39. S. Glesner and D. Koller. Constructing Flexible Dynamic Belief Networks from First-Order Probabilistic Knowledge Bases. In Ch. Froidevaux and J. Kohlas, editors, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU-95), volume 946 of LNCS, pages 217--226, Fribourg, Switzerland, 1995. Springer-Verlag.]]
40. R. P. Goldman and E. Charniak. Dynamic construction of belief networks. In P. P. Bonissone, M. Henrion, L. N. Kanal, and J. F. Lemmer, editors, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence (UAI-90), pages '171--184, Cambridge, MA, USA, 1990. Elsevier.]]
41. P. Haddawy. Generating Bayesian networks from probabilistic logic knowledge bases. In R. Löpez de Mántaras and D. Poole, editors, Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-1994), pages 262--269, Seattle, Washington, USA, 1994. Morgan Kaufmann.]]
42. P. Haddawy, J. W. Helwig, L. Ngo, and R. A. Krieger. Clinical Simulation using Context-Sensitive Temporal Probability Models. In Proceedings of the Nineteenth Annual Symposium on Computer Applications an Medical Care (SCAMC-95), 1995.]]
43. J. Y. Halpern. An analysis of first-order logics of probability. Artificial Intelligence, 46:311--350, 1989.]]
44. D. Heckerman. A Tutorial on Learning with Bayesian Networks. Technical Report MSR-TR-95-06, Microsoft Research, 1995.]]
45. M. Jaeger. Relational Bayesian networks. In D. Geiger and P. P. Shenoy, editors, Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), pages 266--273, Providence, Rhode Island, USA, 1997. Morgan Kaufmann.]]
46. D. Jensen and J. Neville. Linkage and autocorrelation cause feature selection bias in relational learning. In C. Sammut and A. G. Hoffmann, editors, Proceedings of the Nineteenth International Conference on Machine Learning (ICML-OL2), pages 259--266, Sydney, Australia, 2002. Morgan Kaufmann.]]
47. F. V. Jensen. Bayesian networks and decision graphs. Springer-Verlag New, 2001.]]
48. M. I. Jordan, editor. Learning in Graphical Models. Kluwer Academic Publishers. Reprinted by MIT Press, 1998.]]
49. Y. Kameya and T. Sato. Efficient EM learning with tabulation for parameterized logic programs. In J. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. M. Pereira, Y. Sagiv, and P. J. Stuckey, editors, Proceedings of the First International Conference on Computational Logic (CL-00), volume 1861 of LNAI, pages 269--294. Springer-Verlag, 2000.]]
50. Y. Kameya, N. Ueda, and T. Sato. A graphical method for parameter learning of symbolic-statistical models. In Proceedings of the Second International Conference on Discovery Science (DS-99), volume 1721 of LNAI, pages 254--276, Kanagawa, Japan, 1999. Springer-Verlag.]]
51. K. Kersting and L. De Raedt. Adaptive Bayesian Logic Programs. In C. Rouveirol and M. Sebag, editors, Proceedings of the Eleventh Conference on Inductive Logic Programming (ILP-01), volume 2157 of LNCS, Strasbourg, France, 2001. Springer.]]
52. K. Kersting and L. De Raedt. Bayesian logic programs. Technical Report 151, University of Freiburg, Institute for Computer Science, April 2001. (submitted).]]
53. K. Kersting and L. De Raedt. Towards Combining Inductive Logic Programming and Bayesian Networks. In C. Rouveirol and M. Sebag, editors, Proceedings of the Eleventh Conference on Inductive Logic Programming (ILP-01), volume 2157 of LNCS, Strasbourg, France, 2001. Springer.]]
54. K. Kersting and L. De Raedt. Principles of Learning Bayesian Logic Programs. Technical Report 174, University of Freiburg, Institute for Computer Science, June 2002. (submitted).]]
55. K. Kersting, T. Raiko, S. Kramer, and L. De Raedt. Towards discovering structural signatures of protein folds based on logical hidden markov models. In R. B. Altman, A. K. Dunker, L. Hunter, T. A. Jung, and T. E. Klein, editors, Proceedings of the Pacific Symposium on Biocomputing, pages 192--203, Kauai, Hawaii, USA, 2003. World Scientific.]]
56. K. Kersting, T. Raiko, and L. De Raedt. A Structural GEM for Learning Logical Hidden Markov Models. In S. Džeroski, L. De Raedt, and S. Wrobel, editors, Workshop Notes of the KDD-03 Workshop on Multi-Relational Data Mining (MRDM-03), 2003. (to appear).]]
57. D. Koller. Probabilistic relational models. In S. Džeroski and P. Flach, editors, Proceedings of Ninth International Workshop on Inductive Logic Programming (ILP-99), volume 1634 of LNAI, pages 3--13, Bled, Slovenia, 1999. Springer.]]
58. D. Koller, A. Levy, and A. Pfeffer. P-classic: A tractable probabilistic description logic. In Proceedings of the Fourteenth National Conference on AI, pages 390--397, Providence, Rhode Island, August 1997.]]
59. D. Koller and A. Pfeffer. Learning probabilities for noisy first-order rules. In Proceedings of the Fifteenth Joint Conference on Artificial Intelligence (IJCAI-97), pages 1316--1321, Nagoya, Japan, 1997.]]
60. D. Koller and A. Pfeffer. Object-oriented Bayesian networks. In D. Geiger and P. P. Shenoy, editors, Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), pages 302--313, Providence, Rhode Island, USA, 1997. Morgan Kaufmann.]]
61. D. Koller and A. Pfeffer. Probabilistic frame-based systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 580--587, Madison, Wisconsin, USA, July 1998. AAAI Press.]]
62. N. Lachiche and P. Flach. 1BC2: A True First-Order Bayesian Classifier. In S. Matwin and C. Sammut, editors, Proceedings of the Twelfth International Conference on Inductive Logic Prgramming (ILP-02), volume 2583 of LNCS, pages 133--148, Sydney, Australia, 2002. Springer.]]
63. J. W. Lloyd. Foundations of Logic Programming. Springer, Berlin, 2. edition, 1989.]]
64. C. H. Manning and H. Schütze. Foundations of Statistical Natural Language Processing. The MIT Press, 1999.]]
65. G. J. McKachlan and T. Krishnan. The EM Algorithm and Extensions. John Eiley & Sons, Inc., 1997.]]
66. S. Muggleton. Stochastic logic programs. In L. De Raedt, editor, Advances in Inductive Logic Programming. IOS Press, 1996.]]
67. S. Muggleton. Learning stochastic logic programs. Electronic Transactions in Artificial Intelligence, 4(041), 2000.]]
68. S. Muggleton. Learning structure and parameters of stochastic logic programs. In S. Matwin and C. Sammut, editors, Proceedings of the Twelfth International Conference on Inductive Logic Prgramming (ILP-02), volume 2583 of LNCS, pages 198--206, Sydney, Australia, 2002. Springer.]]
69. S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 19(20):629--679, 1994.]]
70. S. H. Muggleton. Learning stochastic logic programs. In L. Getoor and D. Jensen, editors, Working Notes of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data (SRL-00), pages 36--41, Austin, Texas, 2000. AAAI Press.]]
71. R. Ng and V. S. Subrahmanian. Probabilistic Logic Programming. Information and Computation, 101(2):150--201, 1992.]]
72. L. Ngo and P. Haddawy. A Knowledge-Based Model Construction Approach to Medical Decision Making. In Proceedings of the Twentieth American Medical Informatics Association Annual Fall Symposium (AMIA-96), Washington DC, USA, 1996.]]
73. L. Ngo and P. Haddawy. Answering queries from context-sensitive probabilistic knowledge bases. Theoretical Computer Science, 171:147--177, 1997.]]
74. S.-H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Programming. Springer-Verlag, 1997.]]
75. N. J. Nilsson. Principles of Artificial Intelligence. Springer-Verlag, New York, 1986. Reprint, Originally published: Tioga Publishing Co., 1980.]]
76. H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity Uncertainty and Citation Matching. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15. MIT Press, 2003.]]
77. H. Pasula and S. Russell. Approximate inference for first-order probabilistic languages. In B. Nebel, editor, Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pages 741--748, Seattle, Washington, USA, 2001. Morgan Kaufmann.]]
78. J. Pearl. Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 2. edition, 1991.]]
79. A. Pfeffer and D. Koller. Semantics and Inference for Recursive Probability Models. In H. Kautz and B. Porter, editors, Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-00), pages 538--544., Austin, Texas, USA, 2000. AAAI Press.]]
80. A. Pfeffer, D. Koller, B. Milch, and K. T. Takusagawa. Spook: A system for probabilistic object-oriented knowledge representation. In Proceedings of the Fifteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-1999), 1999.]]
81. A. J. Pfeffer. Probabilistic Reasoning for Complex Systems. PhD thesis, Stanford University, 2000.]]
82. D. Poole. Probabilistic Horn abduction and Bayesian networks. Artificial Intelligence, 64:81--129, 1993.]]
83. F. Provost and P. Domingos. Tree induction for probability-based ranking. Machine Learning, 2003. (to appear).]]
84. L. R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77(2):257--286, 1989.]]
85. L. R. Rabiner and B. H. Juang. An introduction to hidden Markov models. IEEE ASSP Magazine, pages 4--15, January 1986.]]
86. S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Inc., 1995.]]
87. V. Santos Costa, D. Page, M. Qazi, and J. Cussens. CLP(BN): Constraint Logic Programming for Probabilistic Knowledge. In Proceedings of the Nineteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-03), Mexico, 2003. Morgan Kaufman. (to appear).]]
88. T. Sato. A Statistical Learning Method for Logic Programs with Distribution Semantics. In L. Sterling, editor, Proceedings of the Twelfth International Conference on Logic Programming (ICLP-1995), pages 715--729, Tokyo, Japan, 1995. MIT Press.]]
89. T. Sato. Parameterized logic programs where computing meets learning. In H. Kuchen. and K. Ueda, editors, Proceedings of Fifth International Symposium on Functional and Logic Programming (FLOPS-01), volume 2024 of LNCS, pages 40--60, Tokyo, Japan, 2001. Springer-Verlag.]]
90. T. Sato and Y. Kameya. PRISM: A Symbolic-Statistical Modeling Language. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), pages 1330--1339, Nagoya, Japan, 1997. Morgan Kaufmann.]]
91. T. Sato and Y. Kameya. A Viterbi-like algorithm and EM learning for statistical abduction. In R. Dybowski, J. Myers, and S. Parsons, editors, Workshop Notes of UAI-00 Workshop on Fusion of Domain Knowledge with Data for Decision Support, Stanford, CA, USA, 2000.]]
92. T. Sato and Y. Kameya. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, 15:391--454, 2001.]]
93. E. Segal, Y. Barash, I. Simon, N. Friedman, and D. Koller. From Promoter Sequence to Expression: A Probabilistic Framework. In Proceedings of the Sixth International Conference on Research in Computational Molecular Biology (RECOMB-02), pages 263--272, Washington, DC, USA, 2002.]]
94. E. Segal, A. Battle, and D. Koller. Decomposing Gene Expression into Cellular Processes. In R. B. Altman, A. K. Dunker, L. Hunter, T. A. Jung, and T. E. Klein, editors, Proceedings of the Pacific Symposium on Biocomputing, pages 89--100, Kauai, Hawaii, USA, 2003. World Scientific.]]
95. E. Segal, B. Taskar, A. Gasch, N. Friedman, and D. Koller. Rich Probabilistic Models for Gene Expression. Bioinformatics, 17:S243--S252, 2001.]]
96. E. Y. Shapiro. Algorithmic Program Debugging. MIT Press, 1983.]]
97. E. Y. Shapiro. Logic Programs with Uncertainties: A Tool for Implementing Expert Systems. In A. Bundy, editor, Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-1983), pages 529--532, Karlsruhe, Germany, 1983. William Kaufmann.]]
98. B. Taskar, E. Segal, and D. Koller. Probabilistic clustering in relational data. In B. Nebel, editor, Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), pages 870--87, Seattle, Washington, USA, 2001. Morgan Kaufmann.]]
99. R. J. Williams and D. Zipser. Gradient-Based Learning Algorithms for Recurrent Networks and Their Computatinal Complexity. In Y. Chauvin and D. E. Rumelhart, editors, Back-propagation:Theory, Architectures and Applications. Lawrence Erlbaum, Hills-dale, NJ: Erlbaum, 1995.]]
100. S. Wrobel. First Order Theory Refinement. In L. De Raedt, editor, Advances in Inductive Logic Programming. IOS Press, 1996.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Logic programming and answer set programming

  • Machine learning

• Theory of computation

  • Logic

    • Constraint and logic programming