Exchangeable sequences are models for homogeneous data sets and serve as building blocks from which more interesting dependency structures in statistical models are produced. A sequence of random variables is exchangeable when its distribution does not depend on the ordering of its elements. In programming terms, exchangeable sequences behave as if they were the result of a repeated evaluation of a closure in a probabilistic language, where the closure itself contains a random variable. Exchangeability therefore licenses a programmer or compiler to commute and even remove expressions. Few languages have any special support for exchangeable expressions, with the notable exception of Church [GMRBT08] and its descendants. Church possessed exchangeable random primitives (XRPs), abstract data types that exposed the operations necessary for a compiler to construct advanced Markov chain Monte Carlo algorithms that take advantage of the additional laws that exchangeable sequences satisfy. For further details on XRPs, see [AFR16] and the references therein.
A fundamental question for probabilistic programming is whether or not support for exchangeability is in some sense necessary on the grounds of efficiency or even computability. In our extended abstract, we give partial answers to this question for sequences, but also look ahead to more complicated structures beyond sequences, namely arrays, where the story is much more complicated. In particular, we describe several results on the computable content of the Aldous–Hoover theorem, and its consequences for probabilistic programming languages.
Extended abstract: On computable representations of exchangeable data by Nathanael L. Ackerman, Jeremy Avigad, Cameron E. Freer, Daniel M. Roy, and Jason M. Rute
Related work by the authors:
[AFR16] N. L. Ackerman, C. E. Freer, and D. M. Roy. Exchangeable Random Primitives, PPS 2016.
[FR10] C. E. Freer and D. M. Roy. Posterior distributions are computable from predictive distributions. In: Proc. 13th Int. Conf. on Artificial Intelligence and Statistics (AISTATS 2010). Vol. 9. J. Machine Learning Research W&CP. 2010.
[FR12] C. E. Freer and D. M. Roy. Computable de Finetti measures. Ann. Pure Appl. Logic 163.5 (2012), pp. 530–546.
[GMRBT08] N. D. Goodman, V. K. Mansinghka, D. M. Roy, K. Bonawitz, and J. B. Tenenbaum. Church: A language for generative models. In: Proc. 24th Conf. on Uncertainty in Artificial Intelligence (UAI 2008). Corvalis, Oregon: AUAI Press, 2008, pp. 220–229.