Article

Bottom-up learning of Markov logic network structure

Authors:

Lilyana Mihalkova,

Raymond J. MooneyAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 625 - 632

https://doi.org/10.1145/1273496.1273575

Published: 20 June 2007 Publication History

Abstract

Markov logic networks (MLNs) are a statistical relational model that consists of weighted firstorder clauses and generalizes first-order logic and Markov networks. The current state-of-the-art algorithm for learning MLN structure follows a top-down paradigm where many potential candidate structures are systematically generated without considering the data and then evaluated using a statistical measure of their fit to the data. Even though this existing algorithm outperforms an impressive array of benchmarks, its greedy search is susceptible to local maxima or plateaus. We present a novel algorithm for learning MLN structure that follows a more bottom-up approach to address this problem. Our algorithm uses a "propositional" Markov network learning method to construct "template" networks that guide the construction of candidate clauses. Our algorithm significantly improves accuracy and learning time over the existing topdown approach in three real-world domains.

References

[1]

Bromberg, F., Margaritis, D., & Honavar, V. (2006). Efficient Markov network structure discovery using independence tests. SDM-06.

Digital Library

[2]

Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., & Slattery, S. (1998). Learning to extract symbolic knowledge from the World Wide Web. AAAI-98.

Digital Library

[3]

Getoor, L., & Taskar, B. (Eds.). (to appear 2007). Statistical relational learning. Cambridge, MA: MIT Press.

Digital Library

[4]

Heckerman, D. (1995). A tutorial on learning Bayesian networks (Technical Report MSR-TR-95-06). Microsoft Research, Redmond, WA.

[5]

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

Digital Library

[6]

Kok, S., & Domingos, P. (2005). Learning the structure of Markov logic networks. ICML-2005.

Digital Library

[7]

Kok, S., Singla, P., Richardson, M., & Domingos, P. (2005). The Alchemy system for statistical relational AI (Technical Report). Department of Computer Science and Engineering, University of Washington. http://www.cs.washington.edu/ai/alchemy.

[8]

Lavrač, N., & D&zcaron;žeroski, S. (1994). Inductive logic programming: Techniques and applications. Ellis Horwood.

Digital Library

[9]

Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing Journal, 13, 245--286.

[10]

Muggleton, S., & Feng, C. (1992). Efficient induction of logic programs. In S. Muggleton (Ed.), Inductive logic programming, 281--297. New York: Academic Press.

[11]

Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausible inference. San Mateo, CA: Morgan Kaufmann.

Digital Library

[12]

Poon, H., & Domingos, P. (2006). Sound and efficient inference with probabilistic and deterministic dependencies. AAAI-2006.

[13]

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

Digital Library

[14]

Richards, B. L., & Mooney, R. J. (1992). Learning relations by pathfinding. AAAI-92.

[15]

Richardson, M., & Domingos, P. (2006). Markov logic networks. Machine Learning, 62, 107--136.

Digital Library

[16]

Russell, S., & Norvig, P. (2003). Artificial intelligence: A modern approach. Upper Saddle River, NJ: Prentice Hall. 2 edition.

Digital Library

[17]

Van Laer, W., & De Raedt, L. (2001). How to upgrade propositional learners to first order logic: Case study. In S. D&zcaron;žeroski and N. Lavrač (Eds.), Relational data mining, 235--256. Berlin: Springer Verlag.

Digital Library

[18]

Zelle, J. M., Mooney, R. J., & Konvisser, J. B. (1994). Combining top-down and bottom-up methods in inductive logic programming. ICML-94.

Cited By

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
Chen FWeitkämper FMalhotra S(2024)Understanding Domain-Size Generalization in Markov Logic NetworksMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70368-3_18(297-314)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70368-3_18
Fang HLiu YCai YSun M(2023)MLN4KB: an efficient Markov logic network engine for large-scale knowledge bases and structured logic rulesProceedings of the ACM Web Conference 202310.1145/3543507.3583248(2423-2432)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583248
Show More Cited By

Recommendations

Learning Markov logic network structure via hypergraph lifting
ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning

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. Learning MLN structure from a relational database involves learning the clauses and ...
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,...
Learning the structure of Markov logic networks
ICML '05: Proceedings of the 22nd international conference on Machine learning

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 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]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

91
Total Citations
View Citations
637
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Chen FWeitkämper FMalhotra S(2024)Understanding Domain-Size Generalization in Markov Logic NetworksMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-031-70368-3_18(297-314)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70368-3_18
Fang HLiu YCai YSun M(2023)MLN4KB: an efficient Markov logic network engine for large-scale knowledge bases and structured logic rulesProceedings of the ACM Web Conference 202310.1145/3543507.3583248(2423-2432)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583248
Sun LWan LWang JLin LGen M(2023)Joint Resource Scheduling for UAV-Enabled Mobile Edge Computing System in Internet of VehiclesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.322432024:12(15624-15632)Online publication date: Dec-2023
https://doi.org/10.1109/TITS.2022.3224320
Yu DYang BLiu DWang HPan S(2023)A survey on neural-symbolic learning systemsNeural Networks10.1016/j.neunet.2023.06.028166(105-126)Online publication date: Sep-2023
https://doi.org/10.1016/j.neunet.2023.06.028
Yan SNatarajan SJoshi SKhardon RTadepalli P(2023)Explainable models via compression of tree ensemblesMachine Learning10.1007/s10994-023-06463-1113:3(1303-1328)Online publication date: 29-Nov-2023
https://doi.org/10.1007/s10994-023-06463-1
Luca TPaes AZaverucha G(2023)Word embeddings-based transfer learning for boosted relational dependency networksMachine Language10.1007/s10994-023-06404-y113:3(1269-1302)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1007/s10994-023-06404-y
Luca TPaes AZaverucha G(2023)Select First, Transfer Later: Choosing Proper Datasets for Statistical Relational Transfer LearningInductive Logic Programming10.1007/978-3-031-49299-0_5(62-76)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49299-0_5
Yu DYang BWei QLi APan S(2022)A Probabilistic Graphical Model Based on Neural-symbolic Reasoning for Visual Relationship Detection2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52688.2022.01035(10599-10608)Online publication date: Jun-2022
https://doi.org/10.1109/CVPR52688.2022.01035
Shah MSarkhel SVenugopal D(2022)Evaluating Captioning Models using Markov Logic Networks2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020793(127-134)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020793
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