A generalization of hierarchical exchangeability on trees to directed acyclic graphs
Annales Henri Lebesgue, Volume 4 (2021) , pp. 325-368.


KeywordsBayesian nonparametrics, exchangeability, hierarchical exchangeability, Aldous–Hoover representation, de Finetti representation


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 |V| for some DAG G=(V,E), and its exchangeability structure is governed by the edge set E. We prove a representation theorem for such arrays which generalizes the Aldous-Hoover and Austin–Panchenko representation theorems.


[AAF + 18] Ackerman, Nathanael Leedom; Avigad, Jeremy; Freer, Cameron E.; Roy, Daniel M.; Rute, Jason M. On the computability of graphons (2018) (https://arxiv.org/abs/1801.10387)

[Ack15] Ackerman, Nathanael L. Representations of Aut(M)-invariant measures: Part I (2015) (https://arxiv.org/abs/1509.06170)

[AFP16] Ackerman, Nathanael L.; Freer, Cameron E.; Patel, Rehana Invariant measures concentrated on countable structures, Forum Math. Sigma, Volume 4 (2016), 17 | MR 3515800 | Zbl 06601292

[Ald81] Aldous, David J. Representations for partially exchangeable arrays of random variables, J. Multivariate Anal., Volume 11 (1981) no. 4, pp. 581-598 | Article | MR 637937 | Zbl 0474.60044

[Ald85] Aldous, David J. 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 0562.60042

[Ald10] Aldous, David J. 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 (2010), pp. 35-63 | Article | MR 2744234 | Zbl 1213.60068

[AP14] Austin, Tim D.; Panchenko, Dmitry A hierarchical version of the de Finetti and Aldous–Hoover representations, Probab. Theory Relat. Fields, Volume 159 (2014) no. 3-4, pp. 809-823 | Article | MR 3230009 | Zbl 1306.60027

[Aus08] Austin, Tim On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv., Volume 5 (2008), pp. 80-145 | Article | MR 2426176 | Zbl 1189.60020

[Aus12] Austin, Tim Exchangeable random arrays, 2012 (Notes for IAS workshop,https://www.math.ucla.edu/~tim/ExchnotesforIISc.pdf)

[BC12] Bordenave, Charles; Chafaï, Djalil Around the circular law, Probab. Surv., Volume 9 (2012), pp. 1-89 | Article | MR 2908617 | Zbl 1243.15022

[BCC11] Bordenave, Charles; Caputo, Pietro; Chafaï, Djalil Spectrum of non-Hermitian heavy tailed random matrices, Commun. Math. Phys., Volume 307 (2011) no. 2, pp. 513-560 | Article | MR 2837123 | Zbl 1235.60008

[BR97] Bratteli, Ola; Robinson, Derek W. Operator Algebras and Quantum Statistical Mechanics. Vol. 2: Equilibrium States Models in Quantum Statistical Mechanics, Texts and Monographs in Physics, Springer, 1997 | Zbl 0903.46066

[CCB16] Cai, Diana; Campbell, Trevor; Broderick, Tamara Edge-exchangeable graphs and sparsity, Advances in Neural Information Processing Systems 29 (NIPS 2016) (2016), pp. 4249-4257

[CD18] Crane, Harry; Dempsey, Walter Edge exchangeable models for interaction networks, J. Amer. Statist. Assoc., Volume 113 (2018) no. 523, pp. 1311-1326 | Article | MR 3862359 | Zbl 1402.90027

[CF17] Caron, François; Fox, Emily B. Sparse graphs using exchangeable random measures, J. R. Stat. Soc. Ser. B. Stat. Methodol., Volume 79 (2017) no. 5, pp. 1295-1366 | Article | MR 3731666 | Zbl 1381.62072

[CGZ15] Chao Gao, Yu Lu; Zhou, Harrison H. Rate-optimal graphon estimation, Ann. Stat., Volume 43 (2015) no. 6, pp. 2625-2652 | MR 3405606 | Zbl 1332.60050

[CT17] Crane, Harry; Towsner, Henry Relative exchangeability with equivalence relations, Arch. Math. Logic, Volume 57 (2017) no. 5-6, pp. 1-24 | MR 3828877 | Zbl 06919823

[CT18] Crane, Harry; Towsner, Henry Relatively exchangeable structures, J. Symb. Log., Volume 83 (2018) no. 2, pp. 416-442 | Article | MR 3835071 | Zbl 06915707

[DJ08] Diaconis, Persi W.; Janson, Svante Graph limits and exchangeable random graphs, Rend. Mat. Appl., Volume 28 (2008) no. 1, pp. 33-61 | MR 2463439 | Zbl 1162.60009

[Fin75] Finetti, Bruno de 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 0328.60002

[FR12] Freer, Cameron E.; Roy, Daniel M. Computable de Finetti measures, Ann. Pure Appl. Logic, Volume 163 (2012) no. 5, pp. 530-546 | Article | MR 2880271 | Zbl 1247.03098

[GMR + 08] Goodman, Noah D.; Mansinghka, Vikash; Roy, Daniel M.; Bonawitz, Keith; Tenenbaum, Joshua B. Church: a language for generative models, Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (2008) (2008)

[GvdV17] Ghosal, Subhashis; van der Vaart, Aad Fundamentals of nonparametric Bayesian inference, Cambridge Series in Statistical and Probabilistic Mathematics, Volume 44, Cambridge University Press, 2017 | MR 3587782 | Zbl 1376.62004

[Hoo79] Hoover, Douglas N. Relations on probability spaces and arrays of random variables, Volume 2, 1979 (Preprint)

[Kal02] Kallenberg, Olav Foundations of modern probability, Probability and Its Applications, Springer, 2002 | Article | Zbl 0996.60001

[Kal05] Kallenberg, Olav Probabilistic Symmetries and Invariance Principles, Probability and Its Applications, Springer, 2005 | Zbl 1084.60003

[KTG + 06] Kemp, Charles; Tenenbaum, Joshua B.; Griffiths, Thomas L.; Yamada, Takeshi; Ueda, Naonori Learning Systems of Concepts with an Infinite Relational Model, Proceedings of the Twenty-First National Conference on Artificial In-telligence (AAAI-06) (2006), pp. 381-388

[MMYW16] Meent, David T.; Meent, Jan-Willem van de; Yang, Hongseok; Wood, Frank D. Design and Implementation of Probabilistic Programming Language Anglican, IFL 2016: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages (2016), 6, pp. 1-12

[MP01] Mézard, Marc; Parisi, Giorgio The Bethe lattice spin glass revisited, Eur. Phys. J. B Condens. Matter Phys., Volume 20 (2001) no. 2, pp. 217-233 | MR 1832936

[OR15] Orbanz, Peter; Roy, Daniel M. Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures, IEEE Trans. Pattern Anal. Mach. Intell., Volume 37 (2015) no. 2, pp. 437-461 | Article

[Pan15] Panchenko, Dmitry Hierarchical exchangeability of pure states in mean field spin glass models, Probab. Theory Relat. Fields, Volume 161 (2015) no. 3-4, pp. 619-650 | Article | MR 3334277 | Zbl 1320.60159

[Res14] Resnick, Sidney Ira A probability path, Modern Birkhäuser Classics, Springer, 2014 | Zbl 1280.60001

[SSY + 18] Staton, Sam; Stein, Dario; Yang, Hongseok; Ackerman, Nathanael L.; Freer, Cameron; Roy, Daniel M. The Beta–Bernoulli Process and Algebraic Effects, 45th International Colloquium on Automata, Languages, and Programming: ICALP 2018 (Leibniz International Proceedings in Informatics) Volume 107 (2018) | MR 3830072

[SYA + 17] Staton, Sam; Yang, Hongseok; Ackerman, Nathanael L.; Freer, Cameron; Roy, Daniel M. 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] Veitch, Victor; Roy, Daniel M. The Class of Random Graphs Arising from Exchangeable Random Measures (2015) (https://arxiv.org/abs/1512.03099)

[WMM14] Wood, Frank D.; Meent, Jan Willem van de; Mansinghka, Vikash A New Approach to Probabilistic Programming Inference, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research) Volume 33 (2014), pp. 1024-1032

[XTYK06] Xu, Zhao; Tresp, Volker; Yu, Kai; Kriegel, Hans-Peter Infinite hidden relational models, Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (2006) (2006), pp. 544-551