Projective families of distributions revisited. (English) Zbl 1531.68141
Summary: The behaviour of statistical relational representations across differently sized domains has become a focal area of research from both a modelling and a complexity viewpoint. Recently, projectivity of a family of distributions emerged as a key property, ensuring that marginal probabilities are independent of the domain size. However, the formalisation used currently assumes that the domain is characterised only by its size. This contribution extends the notion of projectivity from families of distributions indexed by domain size to functors taking extensional data from a database. This makes projectivity available for the large range of applications taking structured input. We transfer key known results on projective families of distributions to the new setting. This includes a characterisation of projective fragments in different statistical relational formalisms as well as a general representation theorem for projective families of distributions. Furthermore, we prove a correspondence between projectivity and distributions on countably infinite domains, which we use to unify and generalise earlier work on statistical relational representations in infinite domains. Finally, we use the extended notion of projectivity to define a further strengthening, which we call \(\sigma \)-projectivity, and which allows the use of the same representation in different modes while retaining projectivity.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 62E20 | Asymptotic distribution theory in statistics |
| 68T27 | Logic in artificial intelligence |
Keywords:
infinite domains; projectivity; structured model; statistical relational artificial intelligence; lifted probabilistic inferenceReferences:
| [1] | Poole, D.; Buchman, D.; Kazemi, S. M.; Kersting, K.; Natarajan, S., Population size extrapolation in relational probabilistic modelling, (Straccia, U.; Calì, A., Scalable Uncertainty Management - 8th International Conference, SUM 2014, Oxford, UK, September 15-17, 2014, Proceedings. Scalable Uncertainty Management - 8th International Conference, SUM 2014, Oxford, UK, September 15-17, 2014, Proceedings, Lecture Notes in Computer Science, vol. 8720 (2014), Springer), 292-305 |
| [2] | Beame, P.; den Broeck, G. V.; Gribkoff, E.; Suciu, D., Symmetric weighted first-order model counting, (Milo, T.; Calvanese, D., Proceedings of the 34th ACM Symposium on Principles of Database Systems. Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015 (2015), ACM), 313-328 |
| [3] | Holland, P. W.; Laskey, K. B.; Leinhardt, S., Stochastic blockmodels: first steps, Soc. Netw., 5, 2, 109-137 (1983) |
| [4] | Malhotra, S.; Serafini, L., On projectivity in Markov logic networks (2022) |
| [5] | Lü, L.; Zhou, T., Link prediction in complex networks: a survey, Phys. A, Stat. Mech. Appl., 390, 6, 1150-1170 (2011) |
| [6] | Ahmad, M. A.; Borbora, Z.; Srivastava, J.; Contractor, N., Link prediction across multiple social networks, (2010 IEEE International Conference on Data Mining Workshops (2010)), 911-918 |
| [7] | Danon, L.; Ford, A. P.; House, T.; Jewell, C. P.; Keeling, M. J.; Roberts, G. O.; Ross, J. V.; Vernon, M. C., Networks and the epidemiology of infectious disease, Interdiscip. Perspect. Infect. Dis., 2011, Article 284909 pp. (2011) |
| [8] | Shalizi, C. R.; Rinaldo, A., Consistency under sampling of exponential random graph models, Ann. Stat., 41, 2, 508-535 (2013) · Zbl 1269.91066 |
| [9] | Jaeger, M.; Schulte, O., Inference, learning, and population size: projectivity for SRL models, (Eighth International Workshop on Statistical Relational AI (StarAI) (2018)) |
| [10] | Jaeger, M.; Schulte, O., A complete characterization of projectivity for statistical relational models, (Bessiere, C., Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, ijcai.org (2020)), 4283-4290 |
| [11] | Weitkämper, F., An asymptotic analysis of probabilistic logic programming, with implications for expressing projective families of distributions, Theory Pract. Log. Program., 21, 6, 802-817 (2021) · Zbl 1530.68061 |
| [12] | Singla, P.; Domingos, P. M., Markov logic in infinite domains, (Parr, R.; van der Gaag, L. C., UAI 2007, Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence. UAI 2007, Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, Vancouver, BC, Canada, July 19-22, 2007 (2007), AUAI Press), 368-375 |
| [13] | Jaeger, M., Relational Bayesian networks, (Geiger, D.; Shenoy, P. P., UAI’97: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence. UAI’97: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, Brown University, Providence, Rhode Island, USA, August 1-3, 1997 (1997), Morgan Kaufmann), 266-273 |
| [14] | Richardson, M.; Domingos, P. M., Markov logic networks, Mach. Learn., 62, 1-2, 107-136 (2006) · Zbl 1470.68221 |
| [15] | Raedt, L. D.; Kimmig, A.; Toivonen, H., ProbLog: a probabilistic prolog and its application in link discovery, (Veloso, M. M., IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007 (2007)), 2462-2467 |
| [16] | Sato, T., A statistical learning method for logic programs with distribution semantics, (Sterling, L., Logic Programming, Proceedings of the Twelfth International Conference on Logic Programming. Logic Programming, Proceedings of the Twelfth International Conference on Logic Programming, Tokyo, Japan, June 13-16, 1995 (1995), MIT Press), 715-729 |
| [17] | Ceri, S.; Gottlob, G.; Tanca, L., Logic Programming and Databases, Surveys in Computer Science (1990), Springer |
| [18] | Muggleton, S.; Feng, C., Efficient induction of logic programs, (Arikawa, S.; Goto, S.; Ohsuga, S.; Yokomori, T., Algorithmic Learning Theory, First International Workshop, ALT’90, Tokyo, Japan, October 8-10, 1990, Proceedings (1990), Springer: Springer Ohmsha), 368-381 |
| [19] | Kallenberg, O., Probabilistic Symmetries and Invariance Principles, Probability and Its Applications (New York) (2005), Springer: Springer New York · Zbl 1084.60003 |
| [20] | Jaeger, M., Reasoning about infinite random structures with relational bayesian networks, (Cohn, A. G.; Schubert, L. K.; Shapiro, S. C., Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR’98). Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR’98), Trento, Italy, June 2-5, 1998 (1998), Morgan Kaufmann), 570-581 |
| [21] | Georgii, H.-O., Gibbs Measures and Phase Transitions, De Gruyter Studies in Mathematics, vol. 9 (2011), Walter de Gruyter & Co.: Walter de Gruyter & Co. Berlin · Zbl 1225.60001 |
| [22] | Kallenberg, O., Foundations of Modern Probability, Probability and Its Applications (New York) (2002), Springer-Verlag: Springer-Verlag New York · Zbl 0996.60001 |
| [23] | Hodges, W., Model Theory, Encyclopedia of Mathematics and Its Applications, vol. 42 (1993), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0789.03031 |
| [24] | Kunen, K., Set Theory, Studies in Logic (London), vol. 34 (2011), College Publications: College Publications London · Zbl 1262.03001 |
| [25] | Elstrodt, J., Maß- und Integrationstheorie (2011), Springer-Verlag · Zbl 1259.28001 |
| [26] | (Van den Broeck, G.; Kersting, K.; Natarajan, S.; Poole, D., An Introduction to Lifted Probabilistic Inference (2021), MIT Press) · Zbl 1473.68019 |
| [27] | Khardon, R.; Sanner, S., Stochastic planning and lifted inference, (Van den Broeck, G.; Kersting, K.; Natarajan, S.; Poole, D., An Introduction to Lifted Probabilistic Inference (2021), MIT Press), 373-395 |
| [28] | Niepert, M.; van den Broeck, G., Tractability through exchangeability: the statistics of lifting, (Van den Broeck, G.; Kersting, K.; Natarajan, S.; Poole, D., An Introduction to Lifted Probabilistic Inference (2021), MIT Press), 161-180 |
| [29] | Diaconis, P.; Janson, S., Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7), 28, 1, 33-61 (2008) · Zbl 1162.60009 |
| [30] | Orbanz, P.; Roy, D. M., Bayesian models of graphs, arrays and other exchangeable random structures, IEEE Trans. Pattern Anal. Mach. Intell., 37, 2, 437-461 (2015) |
| [31] | Alvarado, J.; Wang, Y.; Ramon, J., Limits of multi-relational graphs, Mach. Learn., 112, 177-216 (2023) · Zbl 07694483 |
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.
