×

Scalable learning and inference in Markov logic networks. (English) Zbl 1404.68120

Summary: Markov logic networks (MLNs) have emerged as a powerful representation that incorporates first-order logic and probabilistic graphical models. They have shown very good results in many problem domains. However, current implementations of MLNs do not scale well due to the large search space and the intractable clause groundings, which is preventing their widespread adoption. In this paper, we propose a general framework named Ground Network Sampling (GNS) for scaling up MLN learning and inference. GNS offers a new instantiation perspective by encoding ground substitutions as simple paths in the Herbrand universe, which uses the interactions existing among the objects to constrain the search space. To further make this search tractable for large scale problems, GNS integrates random walks and subgraph pattern mining, gradually building up a representative subset of simple paths. When inference is concerned, a template network is introduced to quickly locate promising paths that can ground given logical statements. The resulting sampled paths are then transformed into ground clauses, which can be used for clause creation and probabilistic inference. The experiments on several real-world datasets demonstrate that our approach offers better scalability while maintaining comparable or better predictive performance compared to state-of-the-art MLN techniques.

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

Tuffy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 1-2, 107-136 (2006) · Zbl 1470.68221
[2] Domingos, P.; Lowd, D., Markov Logic: An Interface Layer for Artificial Intelligence, Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 3, 1-155 (2009)
[3] Huynh, T. N.; Mooney, R. J., Discriminative structure and parameter learning for Markov logic networks, (Proceedings of the 25th International Conference on Machine Learning (2008), ACM), 416-423
[4] Riedel, S.; Chun, H.-W.; Takagi, T.; Tsujii, J., Bio-molecular event extraction with Markov logic, Computat. Intell., 27, 558-582 (2011)
[5] Zhu, Y.; Fathi, A.; Li, F.-F., Reasoning about object affordances in a knowledge base representation, (Proceedings of the 13th European Conference on Computer Vision (2014)), 408-424
[6] Tran, S. D.; Davis, L. S., Event modeling and recognition using Markov logic networks, (Proceedings of the 10th European Conference on Computer Vision (2008)), 610-623
[7] Sorower, M. S.; Dietterich, T. G.; Doppa, J. R.; Orr, W.; Tadepall, P.; Fern, X., Inverting Grice’s maxims to learn rules from natural language extractions, (Advances in Neural Information Processing Systems, vol. 24 (2011)), 1053-1061
[8] Poon, H.; Domingos, P., Unsupervised semantic parsing, (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing (2009)), 1-10
[9] Schoenmackers, S.; Etzioni, O.; Weld, D. S., Scaling textual inference to the web, (Proceedings of the Conference on Empirical Methods in Natural Language Processing and Natural Language Learning (2008)), 79-88
[10] Kok, S.; Domingos, P., Learning the structure of Markov logic networks, (Proceedings of the 22 International Conference on Machine Learning (2005), ACM), 441-448
[11] Mihalkova, L.; Mooney, R. J., Bottom-up learning of Markov logic network structure, (Proceedings of the 24th International Conference on Machine Learning (2007), ACM), 625-632
[12] Khot, T.; Natarajan, S.; Kersting, K.; Shavlik, J., Learning Markov logic networks via functional gradient boosting, (Proceedings of the IEEE International Conference on Data Mining (2011), IEEE), 320-329
[13] Singla, P.; Domingos, P., Lifted first-order belief propagation, (Proceedings of the 23rd AAAI Conference on Artificial Intelligence (2008), AAAI Press), 1094-1099
[14] Poon, H.; Domingos, P.; Sumner, M., A general method for reducing the complexity of relational inference and its application to MCMC, (Proceedings of the 23rd National Conference on Artificial Intelligence (2008), AAAI Press), 1075-1080
[15] Niu, F.; Re, C.; Doan, A.; Shavlik, J., Tuffy: scaling up statistical inference in Markov logic networks using an RDBMS, (Proceedings of the 37th International Conference on Very Large Data Bases (2011)), 373-384
[16] Dietterich, T. G.; Domingos, P.; Getoor, L.; Muggleton, S.; Tadepalli, P., Structured machine learning: the next ten years, Mach. Learn., 73, 3-23 (2008) · Zbl 1470.68098
[17] Kok, S., Structure Learning in Markov Logic Networks (2010), University of Washington, Ph.D. thesis
[18] Richards, B. L.; Mooney, R. J., Learning relations by pathfinding, (Proceedings of the Tenth National Conference on Artificial Intelligence (1992)), 50-55
[19] Kok, S.; Domingos, P., Learning Markov logic network structure via hypergraph lifting, (Proceedings of the 26 International Conference on Machine Learning (2009), ACM), 505-512
[20] Kok, S.; Domingos, P., Learning Markov logic networks using structural motifs, (Proceedings of the 27 International Conference on Machine Learning (2010)), 551-558
[21] Jaimovich, A.; Meshi, O.; Nir, F., Template based inference in symmetric relational Markov random fields, (Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (2007)), 191-199
[22] Poon, H.; Domingos, P., Sound and efficient inference with probabilistic and deterministic dependencies, (Proceedings of the Twenty-First National Conference on Artificial Intelligence (2006)), 458-463
[23] Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov Chain Monte Carlo in Practice (1996), Chapman and Hall: Chapman and Hall London, UK · Zbl 0832.00018
[24] Milch, B.; Russell, S., General-purpose MCMC inference over relational structures, (Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (2006)), 349-358
[25] Niepert, M., Markov chains on orbits of permutation groups, (Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence (2012)), 624-633
[26] Venugopal, D.; Gogate, V., On lifting the Gibbs sampling algorithm, Adv. Neural Inf. Process. Syst., 25, 1655-1663 (2012)
[27] Singla, P.; Domingos, P., Memory-efficient inference in relational domains, (Proceedings of the 21st AAAI Conference on Artificial Intelligence (2006), AAAI Press), 488-493
[28] Huynh, T. N.; Mooney, R. J., Online structure learning for Markov logic networks, (Machine Learning and Knowledge Discovery in Databases (2011), Springer), 81-96
[29] Michelioudakis, E.; Skarlatidis, A.; Paliouras, G.; Artikis, A., Osl \(α\): online structure learning using background knowledge axiomatization, (European Conference of Machine Learning and Knowledge Discovery in Databases (2016))
[30] Van Haaren, J.; Van den Broeck, G.; Meert, W.; Davis, J., Tractable learning of liftable Markov logic networks, (Proceedings of the ICML-14 Workshop on Learning Tractable Probabilistic Models (2014))
[31] Van Haaren, J.; Van den Broeck, G.; Meert, W.; Davis, J., Lifted generative learning of Markov logic networks, Mach. Learn., 103, 27-55 (2016) · Zbl 1357.68187
[32] Khot, T.; Natarajan, S.; Kersting, K.; Shavlik, J. W., Gradient-based boosting for statistical relational learning: the Markov logic network and missing data cases, (Mach. Learn., vol. 100 (2015)), 75-100 · Zbl 1346.68159
[33] Shavlik, J.; Natarajan, S., Speeding up inference in Markov logic networks by preprocessing to reduce the size of the resulting grounded network, (Proceedings of the 21st International Joint Conference on Artificial Intelligence (2009)), 1951-1956
[34] de Salvo Braz, R.; Amir, E.; Roth, D., Lifted first-order probabilistic inference, (Proceedings of the 19th International Joint Conference on Artificial Intelligence (2005), Morgan Kaufmann), 1319-1325
[35] Jha, A.; Gogate, V.; Meliou, A.; Suciu, D., Lifted inference from the other side: the tractable features, (Proceedings of the 24th Annual Conference on Neural Information Processing Systems (2010), MIT Press), 973-981
[36] Gogate, V.; Domingos, P., Probabilistic theorem proving, (Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (2011), AUAI), 256-265
[37] Bui, H. H.; Huynh, T. N.; de Salvo Braz, R., Exact lifted inference with distinct soft evidence on every object, (Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (2012)), 1875-1881
[38] Riedel, S., Improving the accuracy and efficiency of map inference for Markov logic, (Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (2008)), 468-475
[39] Glass, M.; Barker, K., Focused grounding for Markov logic networks, (Proceedings of the Twenty-Fifth International Florida Artificial Intelligence Research Society Conference (2012)), 531-536
[40] Van den Broeck, G.; Darwiche, A., On the complexity and approximation of binary evidence in lifted inference, (Proceedings of the 27th Annual Conference on Neural Information Processing Systems (2013), MIT Press), 2868-2876
[41] Al Hasan, M.; Zaki, M. J., Output space sampling for graph patterns, Proc. Int. Conf. Very Large Data Bases (2009), 2, 1, 730-741 (2009)
[42] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press · Zbl 0849.68039
[43] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Prob., 1, 36-61 (1991) · Zbl 0731.60061
[44] Chung, F. R.K., Spectral Graph Theory (1997), American Mathematical Society · Zbl 0872.05052
[45] Duchi, J.; Shalev-Shwartz, S.; Singer, Y.; Chandra, T., Efficient projections onto the \(\ell_1\)-ball for learning in high dimensions, (Proceedings of the 25th International Conference on Machine Learning (2008), ACM), 272-279
[46] Davis, J.; Goadrich, M., The relationship between precision-recall and ROC curves, (Proceedings of the 23rd International Conference on Machine Learning (2006), ACM), 233-240
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.