A generalization of hierarchical exchangeability on trees to directed acyclic graphs

Jung, Paul; Lee, Jiho; Staton, Sam; Yang, Hongseok

Annales Henri Lebesgue, Volume 4 (2021), pp. 325-368.

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 ${\mathbb{N}}^{\left|V\right|}$ 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.

Motivés par le problème de la conception de modèles bayésiens non paramétriques à inférence pour les langages de programmation probabilistes, nous introduisons une classe générale de tableaux aléatoires partiellement échangeables, qui généralise la notion d’échangeabilité hiérarchique introduite par Austin et Panchenko (2014). Nous disons que nos tableaux partiellement échangeables sont DAG-échangeables puisque leur structure partiellement échangeable est gouvernée par une collection de graphes dirigés acycliques (DAG). Plus spécifiquement, un tel tableau aléatoire est indexé par ${\mathbb{N}}^{\left|V\right|}$ pour un certain DAG $G=(V,E)$, et sa structure d’échangeabilité est gouvernée par l’ensemble d’arêtes $E$. Nous démontrons un théorème de représentation pour de tels tableaux, qui généralise les théorèmes de représentation d’Aldous–Hoover et Austin–Panchenko.

Classification: 60G09
Mots-clés : Bayesian nonparametrics, exchangeability, hierarchical exchangeability, Aldous–Hoover representation, de Finetti representation

[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 | Zbl

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

[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

[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, Cambridge University Press (2010), pp. 35-63 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

[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

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

[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) (McAllester, David; Myllymaki, Petri, eds.), AUAI Press (2008)

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

[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 | DOI | Zbl

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

[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), AAAI Press (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 (Schrijvers, Tom, ed.), Association for Computing Machinery (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

[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 | DOI

[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 | DOI | MR | Zbl

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

[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 (Chatzigiannakis, Ioannis; Kaklamanis, Christos; Dániel, Marx; Sanella, Donald, eds.) (Leibniz International Proceedings in Informatics), Volume 107, Schloss Dagstuhl (2018) | MR

[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 (Kaski, Samuel; Corander, Jukka, eds.) (Proceedings of Machine Learning Research), Volume 33, PMLR (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) (Dechter, Rina; Richardson, Thomas S., eds.), AUAI Press (2006), pp. 544-551