×

zbMATH — the first resource for mathematics

Modelling relational statistics with Bayes nets. (English) Zbl 1319.68190
Summary: Class-level models capture relational statistics over object attributes and their connecting links, answering questions such as ”what is the percentage of friendship pairs where both friends are women?” Class-level relationships are important in themselves, and they support applications like policy making, strategic planning, and query optimization. We represent class statistics using Parametrized Bayes Nets (PBNs), a first-order logic extension of Bayes nets. Queries about classes require a new semantics for PBNs, as the standard grounding semantics is only appropriate for answering queries about specific ground facts. We propose a novel random selection semantics for PBNs, which does not make reference to a ground model, and supports class-level queries. The parameters for this semantics can be learned using the recent pseudo-likelihood measure [the first author, “A tractable pseudo-likelihood function for Bayes nets applied to relational data”, in: Proceedings of the 2011 SIAM international conference on data mining. Philadelphia, PA: SIAM. 462–473 (2011; doi:10.1137/1.9781611972818.40)] as the objective function. This objective function is maximized by taking the empirical frequencies in the relational data as the parameter settings. We render the computation of these empirical frequencies tractable in the presence of negated relations by the inverse Möbius transform. Evaluation of our method on four benchmark datasets shows that maximum pseudo-likelihood provides fast and accurate estimates at different sample sizes.

MSC:
68T05 Learning and adaptive systems in artificial intelligence
Software:
BLOG; CrossMine
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, T. V.; Singh, A.; Greiner, R.; Hooper, P., Quantifying the uncertainty of a belief net response: Bayesian error-bars for belief net inference, Artificial Intelligence, 172, 483-513, (2008) · Zbl 1182.68304
[2] Babcock, B.; Chaudhuri, S., Towards a robust query optimizer: a principled and practical approach, New York, NY, USA, New York
[3] Bacchus, F. (1990). Representing and reasoning with probabilistic knowledge: a logical approach to probabilities. Cambridge: MIT Press.
[4] Bacchus, F.; Grove, A. J.; Koller, D.; Halpern, J. Y., From statistics to beliefs, 602-608, (1992)
[5] Buchman, D.; Schmidt, M. W.; Mohamed, S.; Poole, D.; Freitas, N., On sparse, spectral and other parameterizations of binary probabilistic models, Journal of Machine Learning Research—Proceedings Track, 22, 173-181, (2012)
[6] Chiang, M.; Poole, D., Reference classes and relational learning, International Journal of Approximate Reasoning, 53, 326-346, (2012) · Zbl 1242.68323
[7] Cussens, J., Logic-based formalisms for statistical relational learning, (2007)
[8] Domingos, P., & Lowd, D. (2009). Markov logic: an interface layer for artificial intelligence. Seattle: Morgan and Claypool Publishers. · Zbl 1202.68403
[9] Domingos, P.; Richardson, M., Markov logic: a unifying framework for statistical relational learning, (2007)
[10] Drton, M.; Richardson, T. S., Binary models for marginal independence, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70, 287-309, (2008) · Zbl 1148.62043
[11] Frank, O., Estimation of graph totals, Scandinavian Journal of Statistics, 4, 81-89, (1977) · Zbl 0358.62008
[12] Getoor, L. (2001). Learning statistical models from relational data. Ph.D. thesis, Department of Computer Science, Stanford University.
[13] Getoor, L.; Taskar, B., Introduction, 1-8, (2007) · Zbl 1142.68391
[14] Getoor, L., & Taskar, B. (2007b). Introduction to statistical relational learning. Cambridge: MIT Press. · Zbl 1141.68054
[15] Getoor, L.; Taskar, B.; Koller, D., Selectivity estimation using probabilistic models, ACM SIGMOD Record, 30, 461-472, (2001)
[16] Getoor, L.; Friedman, N.; Koller, D.; Pfeffer, A.; Taskar, B., Probabilistic relational models, 129-173, (2007)
[17] Halpern, J. Y., An analysis of first-order logics of probability, Artificial Intelligence, 46, 311-350, (1990) · Zbl 0723.03007
[18] Hoff, P. D., Multiplicative latent factor models for description and prediction of social networks, (2007)
[19] Kennes, R.; Smets, P., Computational aspects of the Möbius transformation, 401-416, (1990) · Zbl 0742.68069
[20] Khosravi, H.; Schulte, O.; Man, T.; Xu, X.; Bina, B., Structure learning for Markov logic networks with many descriptive attributes, 487-493, (2010)
[21] Khosravi, H., Man, T., Hu, J., Gao, E., & Schulte, O. (2012). Learn and join algorithm code. http://www.cs.sfu.ca/ oschulte/jbn/.
[22] Khot, T.; Natarajan, S.; Kersting, K.; Shavlik, J. W., Learning Markov logic networks via functional gradient boosting, 320-329, (2011), Los Alamitos
[23] Kok, S.; Domingos, P., Learning Markov logic networks using structural motifs, 551-558, (2010)
[24] Kok, S., Summer, M., Richardson, M., Singla, P., Poon, H., Lowd, D., Wang, J., & Domingos, P. (2009). The Alchemy system for statistical relational AI. Technical report, University of Washington. Version 30.
[25] Koller, D., & Friedman, N. (2009). Probabilistic graphical models. Cambridge: MIT Press. · Zbl 1183.68483
[26] Maier, M.; Taylor, B.; Oktay, H.; Jensen, D., Learning causal models of relational domains, (2010)
[27] Milch, B.; Marthi, B.; Russell, S.; Sontag, D.; Ong, D.; Kolobov, A., BLOG: probabilistic models with unknown objects, 373-395, (2007), Cambridge
[28] Namata, G. M.; Kok, S.; Getoor, L., Collective graph identification, New York, NY, USA, New York
[29] Poole, D., First-order probabilistic inference, 985-991, (2003)
[30] Russell, S., & Norvig, P. (2010). Artificial intelligence: a modern approach. New York: Prentice Hall. · Zbl 0835.68093
[31] Schulte, O., A tractable pseudo-likelihood function for Bayes nets applied to relational data, 462-473, (2011)
[32] Schulte, O. (2012). Challenge paper: Marginal probabilities for instances and classes. ICML-SRL Workshop on Statistical Relational Learning.
[33] Schulte, O.; Khosravi, H., Learning graphical models for relational data via lattice search, Machine Learning, 88, 331-368, (2012)
[34] The Tetrad Group: The Tetrad project (2008). http://www.phil.cmu.edu/projects/tetrad/.
[35] Ullman, J. D. (1982). Principles of database systems (2nd ed.). New York: Freeman · Zbl 0558.68078
[36] Yang, S. H.; Long, B.; Smola, A.; Sadagopan, N.; Zheng, Z.; Zha, H., Like like alike: joint friendship and interest propagation in social networks, New York, NY, USA, New York
[37] Yin, X.; Han, J.; Yang, J.; Yu, P. S., Crossmine: efficient classification across multiple database relations, 399-410, (2004), Los Alamitos
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.