Metadata
Abstract
Motivated by the problem of designing inference-friendly Bayesian nonparametric models in probabilistic programming languages, we introduce a general class of partially exchangeable random arrays which generalizes the notion of hierarchical exchangeability introduced in Austin and Panchenko (2014). We say that our partially exchangeable arrays are DAG-exchangeable since their partially exchangeable structure is governed by a collection of Directed Acyclic Graphs. More specifically, such a random array is indexed by for some DAG , and its exchangeability structure is governed by the edge set . We prove a representation theorem for such arrays which generalizes the Aldous-Hoover and Austin–Panchenko representation theorems.
References
[AAF + 18] On the computability of graphons (2018) (https://arxiv.org/abs/1801.10387)
[Ack15] Representations of Aut(M)-invariant measures: Part I (2015) (https://arxiv.org/abs/1509.06170)
[AFP16] Invariant measures concentrated on countable structures, Forum Math. Sigma, Volume 4 (2016), 17 | MR | Zbl
[Ald81] Representations for partially exchangeable arrays of random variables, J. Multivariate Anal., Volume 11 (1981) no. 4, pp. 581-598 | DOI | MR | Zbl
[Ald85] Exchangeability and related topics, École d’Été de Probabilités de Saint-Flour XIII 1983 (Lecture Notes in Mathematics), Springer, 1985, pp. 1-198 | Zbl
[Ald10] More uses of exchangeability: representations of complex random structures, Probability and mathematical genetics. Papers in honour of Sir John Kingman (London Mathematical Society Lecture Note Series), Volume 378, Cambridge University Press (2010), pp. 35-63 | DOI | MR | Zbl
[AP14] A hierarchical version of the de Finetti and Aldous–Hoover representations, Probab. Theory Relat. Fields, Volume 159 (2014) no. 3-4, pp. 809-823 | DOI | MR | Zbl
[Aus08] On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv., Volume 5 (2008), pp. 80-145 | DOI | MR | Zbl
[Aus12] Exchangeable random arrays, 2012 (Notes for IAS workshop,https://www.math.ucla.edu/~tim/ExchnotesforIISc.pdf)
[BR97] Operator Algebras and Quantum Statistical Mechanics. Vol. 2: Equilibrium States Models in Quantum Statistical Mechanics, Texts and Monographs in Physics, Springer, 1997 | Zbl
[CCB16] Edge-exchangeable graphs and sparsity, Advances in Neural Information Processing Systems 29 (NIPS 2016) (2016), pp. 4249-4257
[CD18] Edge exchangeable models for interaction networks, J. Amer. Statist. Assoc., Volume 113 (2018) no. 523, pp. 1311-1326 | DOI | MR | Zbl
[CF17] Sparse graphs using exchangeable random measures, J. R. Stat. Soc. Ser. B. Stat. Methodol., Volume 79 (2017) no. 5, pp. 1295-1366 | DOI | MR | Zbl
[CGZ15] Rate-optimal graphon estimation, Ann. Stat., Volume 43 (2015) no. 6, pp. 2625-2652 | MR | Zbl
[CT17] Relative exchangeability with equivalence relations, Arch. Math. Logic, Volume 57 (2017) no. 5-6, pp. 1-24 | MR | Zbl
[CT18] Relatively exchangeable structures, J. Symb. Log., Volume 83 (2018) no. 2, pp. 416-442 | DOI | MR | Zbl
[DJ08] Graph limits and exchangeable random graphs, Rend. Mat. Appl., Volume 28 (2008) no. 1, pp. 33-61 | MR | Zbl
[Fin75] Theory of probability. A critical introductory treatment. Vols 1 and 2, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1974-1975 (English translation by Antonio Machi and Adrian Smith) | Zbl
[FR12] Computable de Finetti measures, Ann. Pure Appl. Logic, Volume 163 (2012) no. 5, pp. 530-546 | DOI | MR | Zbl
[GMR + 08] Church: a language for generative models, Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (2008) (McAllester, David; Myllymaki, Petri, eds.), AUAI Press (2008)
[GvdV17] Fundamentals of nonparametric Bayesian inference, Cambridge Series in Statistical and Probabilistic Mathematics, 44, Cambridge University Press, 2017 | MR | Zbl
[Hoo79] Relations on probability spaces and arrays of random variables, Volume 2, 1979 (Preprint)
[Kal02] Foundations of modern probability, Probability and Its Applications, Springer, 2002 | DOI | Zbl
[Kal05] Probabilistic Symmetries and Invariance Principles, Probability and Its Applications, Springer, 2005 | Zbl
[KTG + 06] Learning Systems of Concepts with an Infinite Relational Model, Proceedings of the Twenty-First National Conference on Artificial In-telligence (AAAI-06), AAAI Press (2006), pp. 381-388
[MMYW16] Design and Implementation of Probabilistic Programming Language Anglican, IFL 2016: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages (Schrijvers, Tom, ed.), Association for Computing Machinery (2016), 6, pp. 1-12
[MP01] The Bethe lattice spin glass revisited, Eur. Phys. J. B Condens. Matter Phys., Volume 20 (2001) no. 2, pp. 217-233 | MR
[OR15] Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures, IEEE Trans. Pattern Anal. Mach. Intell., Volume 37 (2015) no. 2, pp. 437-461 | DOI
[Pan15] Hierarchical exchangeability of pure states in mean field spin glass models, Probab. Theory Relat. Fields, Volume 161 (2015) no. 3-4, pp. 619-650 | DOI | MR | Zbl
[Res14] A probability path, Modern Birkhäuser Classics, Springer, 2014 | Zbl
[SSY + 18] The Beta–Bernoulli Process and Algebraic Effects, 45th International Colloquium on Automata, Languages, and Programming: ICALP 2018 (Chatzigiannakis, Ioannis; Kaklamanis, Christos; Dániel, Marx; Sanella, Donald, eds.) (Leibniz International Proceedings in Informatics), Volume 107, Schloss Dagstuhl (2018) | MR
[SYA + 17] Exchangeable random process and data abstraction, 2017 Workshop on Probabilistic Programming Semantics (PPS 2017), available at https://pps2017.luddy.indiana.edu/2017/01/02/exchangeable-random-processes-and-data-abstraction/
[VR15] The Class of Random Graphs Arising from Exchangeable Random Measures (2015) (https://arxiv.org/abs/1512.03099)
[WMM14] A New Approach to Probabilistic Programming Inference, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (Kaski, Samuel; Corander, Jukka, eds.) (Proceedings of Machine Learning Research), Volume 33, PMLR (2014), pp. 1024-1032
[XTYK06] Infinite hidden relational models, Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (2006) (Dechter, Rina; Richardson, Thomas S., eds.), AUAI Press (2006), pp. 544-551