A Generalization to DAGs for Hierarchical Exchangeability
Motivated by problems in Bayesian nonparametrics and
probabilistic programming discussed in Staton et al. (2018), we
present a new kind of partial exchangeability for random arrays which
we call DAG-exchangeability. In our setting, a given random array is
indexed by certain subgraphs of a directed acyclic graph (DAG) of
finite depth, where each nonterminal vertex has infinitely many
outgoing edges. We prove a representation theorem for such arrays
which generalizes the Aldous-Hoover representation theorem.
In the case that the DAGs are finite collections of certain rooted
trees, our arrays are hierarchically exchangeable in the sense of
Austin and Panchenko (2014), and we recover the representation theorem
proved by them. Additionally, our representation is fine-grained in
the sense that representations at higher levels of the hierarchy are
also available. This latter feature is important in applications to
probabilistic programming, thus offering an improvement over the
Austin-Panchenko representation even for hierarchical exchangeability.