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: Corin R. Anderson , Pedro Domingos , Daniel S. Weld, Relational Markov models and their application to adaptive web navigation, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775068]
• 3: Nicos Angelopoulos , James Cussens, Markov Chain Monte Carlo using Tree-Based Priors on Model Structure, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.16-23, August 02-05, 2001
• 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: Francesco Bergadano , Daniele Gunetti, Inductive Logic Programming: From Machine Learning to Software Engineering, MIT Press, Cambridge, MA, 1995
• 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: Wray Buntine, A Guide to the Literature on Learning Probabilistic Networks from Data, IEEE Transactions on Knowledge and Data Engineering, v.8 n.2, p.195-210, April 1996 [doi>10.1109/69.494161 ]
• 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: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 11: Mark Craven , Seán Slattery, Relational Learning with Statistical Predicate Invention: Better Models for Hypertext, Machine Learning, v.43 n.1-2, p.97-119, April-May 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: James Cussens, Stochastic Logic Programs: Sampling, Inference and Applications, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.115-122, June 30-July 03, 2000
• 14: James Cussens, Parameter Estimation in Stochastic Logic Programs, Machine Learning, v.44 n.3, p.245-271, September 2001 [doi>10.1023/A:1010924021315 ]
• 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: Luc De Raedt, Interactive theory revision: an inductive logic programming approach, Academic Press Ltd., London, UK, 1992
• 17: Luc De Raedt, Logical settings for concept-learning, Artificial Intelligence, v.95 n.1, p.187-201, Aug. 1997 [doi>10.1016/S0004-3702(97)00041-6 ]
• 18: Luc De Raedt , Luc Dehaspe, Clausal Discovery, Machine Learning, v.26 n.2-3, p.99-146, Feb./March 1, 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: Michelangelo Diligenti , Paolo Frasconi , Marco Gori, Hidden Tree Markov Models for Document Image Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.519-523, April 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: Saso (Ed.) Dzeroski , Nada Lavrac , Saso Dzeroski, Relational Data Mining, Springer-Verlag New York, Inc., Secaucus, NJ, 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: Peter Flach, Simply logical: intelligent reasoning by example, John Wiley & Sons, Inc., New York, NY, 1994
• 27: Peter A. Flach , Nicolas Lachiche, IBC: A First-Order Bayesian Classifier, Proceedings of the 9th International Workshop on Inductive Logic Programming, p.92-103, June 24-27, 1999
• 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: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 31: Lise Carol Getoor , Daphne Koller, Learning statistical models from relational data, 2002
• 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: Lise Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning Probabilistic Models of Relational Structure, Proceedings of the Eighteenth International Conference on Machine Learning, p.170-177, June 28-July 01, 2001
• 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: Lise Getoor , Benjamin Taskar , Daphne Koller, Selectivity estimation using probabilistic models, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.461-472, May 21-24, 2001, Santa Barbara, California, United States
• 39: Sabine Glesner , Daphne Koller, Constructing Flexible Dynamic Belief Networks from First-Order Probalistic Knowledge Bases, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.217-226, July 03-05, 1995
• 40: Robert P. Goldman , Eugene Charniak, Dynamic construction of belief networks, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, p.171-184, July 27-29, 1990
• 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: Joseph Y. Halpern, An analysis of first-order logics of probability, Artificial Intelligence, v.46 n.3, p.311-350, Dec. 1990 [doi>10.1016/0004-3702(90)90019-V ]
• 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: David Jensen , Jennifer Neville, Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.259-266, July 08-12, 2002
• 47: Finn V. Jensen, Bayesian Networks and Decision Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 48: Michael I. Jordan, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 49: Yoshitaka Kameya , Taisuke Sato, Efficient EM Learning with Tabulation for Parameterized Logic Programs, Proceedings of the First International Conference on Computational Logic, p.269-284, July 01, 2000
• 50: Yoshitaka Kameya , Nobuhisa Ueda , Taisuke Sato, A Graphical Method for Parameter Learning of Symbolic-Statistical Models, Proceedings of the Second International Conference on Discovery Science, p.264-276, December 01, 1999
• 51: Kristian Kersting , Luc De Raedt, Adaptive Bayesian Logic Programs, Proceedings of the 11th International Conference on Inductive Logic Programming, p.104-117, September 09-11, 2001
• 52: Kristian Kersting , Luc De Raedt, Bayesian Logic Programs, Albert-Ludwigs University at Freiburg, 2001
• 53: Kristian Kersting , Luc De Raedt, Towards Combining Inductive Logic Programming with Bayesian Networks, Proceedings of the 11th International Conference on Inductive Logic Programming, p.118-131, September 09-11, 2001
• 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: Daphne Koller, Probabilistic Relational Models, Proceedings of the 9th International Workshop on Inductive Logic Programming, p.3-13, June 24-27, 1999
• 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: Daphne Koller , Avi Pfeffer, Probabilistic frame-based systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.580-587, July 1998, Madison, Wisconsin, United States
• 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-Verlag New York, Inc., New York, NY, 1984
• 64: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 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: Raymond Ng , V. S. Subrahmanian, Probabilistic logic programming, Information and Computation, v.101 n.2, p.150-201, Dec. 1992 [doi>10.1016/0890-5401(92)90061-J]
• 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: Liem Ngo , Peter Haddawy, Answering queries from context-sensitive probabilistic knowledge bases, Theoretical Computer Science, v.171 n.1-2, p.147-177, Jan. 15, 1997
• 74: Shan-Hwei Nienhuys-Cheng , R. De Wolf , Ronald de Wolf , J. Siekmann , J. G. Carbonell, Foundations of Inductive Logic Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 75: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 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: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 79: Avi Pfeffer , Daphne Koller, Semantics and Inference for Recursive Probability Models, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.538-544, July 30-August 03, 2000
• 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: Avrom Jacob Pfeffer , Daphne Koller, Probabilistic reasoning for complex systems, 2000
• 82: David Poole, Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, v.64 n.1, p.81-129, Nov. 1993 [doi>10.1016/0004-3702(93)90061-F ]
• 83: Foster Provost , Pedro Domingos, Tree Induction for Probability-Based Ranking, Machine Learning, v.52 n.3, p.199-215, September 2003 [doi>10.1023/A:1024099825458]
• 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: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 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: Taisuke Sato, Parameterized Logic Programs where Computing Meets Learning, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.40-60, March 07-09, 2001
• 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: Eran Segal , Yoseph Barash , Itamar Simon , Nir Friedman , Daphne Koller, From promoter sequence to expression: a probabilistic framework, Proceedings of the sixth annual international conference on Computational biology, p.263-272, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565231]
• 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: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 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: Ronald J. Williams , David Zipser, Gradient-based learning algorithms for recurrent networks and their computational complexity, Backpropagation: theory, architectures, and applications, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1995
• 100: S. Wrobel. First Order Theory Refinement. In L. De Raedt, editor, Advances in Inductive Logic Programming. IOS Press, 1996.

INDEX TERMS

Keywords:
data mining, inductive logic programming, machine learning, multi-relational data mining, probabilistic reasoning, uncertainty