Article

Learning the structure of Markov logic networks

Authors:

Pedro DomingosAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 441 - 448

https://doi.org/10.1145/1102351.1102407

Published: 07 August 2005 Publication History

Abstract

Markov logic networks (MLNs) combine logic and probability by attaching weights to first-order clauses, and viewing these as templates for features of Markov networks. In this paper we develop an algorithm for learning the structure of MLNs from relational databases, combining ideas from inductive logic programming (ILP) and feature induction in Markov networks. The algorithm performs a beam or shortest-first search of the space of clauses, guided by a weighted pseudo-likelihood measure. This requires computing the optimal weights for each candidate structure, but we show how this can be done efficiently. The algorithm can be used to learn an MLN from scratch, or to refine an existing knowledge base. We have applied it in two real-world domains, and found that it outperforms using off-the-shelf ILP systems to learn the MLN structure, as well as pure ILP, purely probabilistic and purely knowledge-based approaches.

References

[1]

Besag, J. (1975). Statistical analysis of non-lattice data. The Statistician, 24, 179--195.]]

[2]

Bilenko, M., & Mooney, R. (2003). Adaptive duplicate detection using learnable string similarity measures. Proc. KDD-03 (pp. 39--48).]]

Digital Library

[3]

De Raedt, L., & Dehaspe, L. (1997). Clausal discovery. Machine Learning, 26, 99--146.]]

Digital Library

[4]

DeGroot, M. H., & Schervish, M. J. (2002). Probability and statistics. Boston, MA: Addison Wesley. 3rd edition.]]

[5]

Dehaspe, L. (1997). Maximum entropy modeling with clausal constraints. Proc. ILP-97 (pp. 109--125).]]

Digital Library

[6]

Della Pietra, S., Della Pietra, V., & Lafferty, J. (1997). Inducing features of random fields. IEEE Trans. on Pattern Analysis and Machine Intelligence, 19, 380--392.]]

Digital Library

[7]

Dietterich, T., Getoor, L., & Murphy, K. (Eds.). (2003). Proc. ICML-2004 Wkshp. on Statistical Relational Learning. Banff, Canada.]]

[8]

Domingos, P., & Pazzani, M. (1997). On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 29, 103--130.]]

Digital Library

[9]

Friedman, N., Getoor, L., Koller, D., & Pfeffer, A. (1999). Learning probabilistic relational models. Proc. IJCAI-99 (pp. 1300--1307).]]

Digital Library

[10]

Genesereth, M. R., & Nilsson, N. J. (1987). Logical foundations of artificial intelligence. San Mateo, CA: Morgan Kaufmann.]]

Digital Library

[11]

Heckerman, D., Geiger, D., & Chickering, D. M. (1995). Learning Bayesian networks: The combination of knowledge & statistical data. Machine Learning, 20, 197--243.]]

Digital Library

[12]

Hulten, G., & Domingos, P. (2002). Mining complex models from arbitrarily large databases in constant time. Proc. KDD-02 (pp. 525--531).]]

Digital Library

[13]

Karp, R., & Luby, M. (1983). Monte Carlo algorithms for enumeration and reliability problems. Proc. FOCS-83 (pp. 56--64).]]

Digital Library

[14]

Kersting, K., & De Raedt, L. (2001). Towards combining inductive logic programming with Bayesian networks. Proc. ILP-01 (pp. 118--131).]]

Digital Library

[15]

Lavrač, N., & D&ccaron;čeroski, S. (1994). Inductive logic programming: Techniques and applications. Chichester, UK: Ellis Horwood.]]

Digital Library

[16]

McCallum, A. (2003). Efficiently inducing features of conditional random fields. Proc. UAI-03 (pp. 403--410).]]

[17]

Quinlan, J. R. (1990). Learning logical definitions from relations. Machine Learning, 5, 239--266.]]

Digital Library

[18]

Richardson, M., & Domingos, P. (2004). Markov logic networks (Tech. Rept.). Dept. Comp. Sci. & Eng., Univ. Washington, Seattle. http://www.cs.washington.edu/homes/pedrod/mln.pdf.]]

[19]

Sanghai, S., Domingos, P., & Weld, D. (2005). Learning models of relational stochastic processes (Tech. Rept.). Dept. Comp. Sci. & Eng., Univ. Washington, Seattle. http://www.-cs.washington.edu/homes/pedrod/Imrsp.pdf.]]

[20]

Sebag, M., & Rouveirol, C. (1997). Tractable induction and classification in first-order logic via stochastic matching. Proc. IJCAI-97 (pp. 888--893).]]

[21]

Sha, F., & Pereira, F. (2003). Shallow parsing with conditional random fields. Proc. HLT-NAACL-03 (pp. 134--141).]]

Digital Library

[22]

Singla, P., & Domingos, P. (2005). Discriminative training of Markov logic networks. Proc. AAAI-05 (to appear).]]

Digital Library

[23]

Srinivasan, A. (2000). The Aleph manual (Tech. Rept.). Computing Laboratory, Oxford University.]]

[24]

Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. Proc. UAI-02 (pp. 485--492).]]

Cited By

Gao MTian SYu L(2024)CONHyperKGE: Using Contrastive Learning in Hyperbolic Space for Knowledge Graph EmbeddingInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S021800142451005438:04Online publication date: 18-Apr-2024
https://doi.org/10.1142/S0218001424510054
Zeng ZCheng QSi YLiu Z(2024)RuMER-RL: A Hybrid Framework for Sparse Knowledge Graph Explainable ReasoningInformation Sciences10.1016/j.ins.2024.121144(121144)Online publication date: Jul-2024
https://doi.org/10.1016/j.ins.2024.121144
Liu RYin GLiu Z(2024)Learning to walk with logical embedding for knowledge reasoningInformation Sciences: an International Journal10.1016/j.ins.2024.120471667:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120471
Show More Cited By

Learning the structure of Markov logic networks
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Logic

Recommendations

Structure learning in markov logic networks
Discriminative structure and parameter learning for Markov logic networks
ICML '08: Proceedings of the 25th international conference on Machine learning

Markov logic networks (MLNs) are an expressive representation for statistical relational learning that generalizes both first-order logic and graphical models. Existing methods for learning the logical structure of an MLN are not discriminative; however,...
Markov logic networks

We propose a simple approach to combining first-order logic and probabilistic graphical models in a single representation. A Markov logic network (MLN) is a first-order knowledge base with a weight attached to each formula (or clause). Together with a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

154
Total Citations
View Citations
884
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao MTian SYu L(2024)CONHyperKGE: Using Contrastive Learning in Hyperbolic Space for Knowledge Graph EmbeddingInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S021800142451005438:04Online publication date: 18-Apr-2024
https://doi.org/10.1142/S0218001424510054
Zeng ZCheng QSi YLiu Z(2024)RuMER-RL: A Hybrid Framework for Sparse Knowledge Graph Explainable ReasoningInformation Sciences10.1016/j.ins.2024.121144(121144)Online publication date: Jul-2024
https://doi.org/10.1016/j.ins.2024.121144
Liu RYin GLiu Z(2024)Learning to walk with logical embedding for knowledge reasoningInformation Sciences: an International Journal10.1016/j.ins.2024.120471667:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120471
Luttermann MMöller RHartwig M(2024)Towards Privacy-Preserving Relational Data Synthesis via Probabilistic Relational ModelsKI 2024: Advances in Artificial Intelligence10.1007/978-3-031-70893-0_13(175-189)Online publication date: 30-Aug-2024
https://doi.org/10.1007/978-3-031-70893-0_13
Ellis KOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Human-like few-shot learning via Bayesian reasoning over natural languageProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666699(13149-13178)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666699
Zeng ZCheng QSi Y(2023)Logical Rule-Based Knowledge Graph Reasoning: A Comprehensive SurveyMathematics10.3390/math1121448611:21(4486)Online publication date: 30-Oct-2023
https://doi.org/10.3390/math11214486
Cui SZhu TZhang XChen LMao LNing H(2023)Generating Markov Logic Networks Rulebase Based on Probabilistic Latent Semantics AnalysisTsinghua Science and Technology10.26599/TST.2022.901007228:5(952-964)Online publication date: Oct-2023
https://doi.org/10.26599/TST.2022.9010072
Dash SGonçalves JWilliams BChen YNeville J(2023)Rule induction in knowledge graphs using linear programmingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25541(4233-4241)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25541
Gentili EBizzarri AAzzolini DZese RRiguzzi F(2023)Regularization in Probabilistic Inductive Logic ProgrammingInductive Logic Programming10.1007/978-3-031-49299-0_2(16-29)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49299-0_2
Goyal ABengio Y(2022)Inductive biases for deep learning of higher-level cognitionProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences10.1098/rspa.2021.0068478:2266Online publication date: 12-Oct-2022
https://doi.org/10.1098/rspa.2021.0068
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents