一句话：证明可计算采样的可交换随机图其 graphon 表示不可计算，揭示条件独立性表示存在算法障碍。
论文研究用概率核乘积表示条件独立性时，这种表示是否可计算。作者在可交换随机变量序列与阵列的框架下，利用 de Finetti 定理和 Aldous-Hoover 定理，将条件独立性表示为 graphon 等对象。特别地，针对无向图的对称二值阵列，论文证明存在可计算采样的可交换随机图，但其对应的 graphon 既不能作为函数可计算，甚至也不能作为 L1 等价类可计算。论文还给出若干特殊情况下 graphon 可逼近性的结果，从而揭示条件独立性表示存在算法障碍。
We define a represention of conditional independence in terms of products of probability kernels, and ask when such representations are computable. We pursue this question in the context of exchangeable sequences and arrays of random variables, which arise in statistical contexts. Exchangeable sequences are conditionally i.i.d. by de Finetti's theorem. Known results about the computability of de Finetti's theorem imply that these conditional independences are computable. The conditional independences underlying exchangeable arrays are characterized by the Aldous-Hoover theorem. In the special case of adjacency matrices of undirected graphs, i.e., symmetric binary arrays, this representation theorem expresses the conditional independences in terms of graphons. We prove that there exist exchangeable random graphs that can be computably sampled but whose corresponding graphons are not computable as functions or even as L1equivalence classes. We also give results on the approximability of graphons in certain special cases.
DOI 原文 ·
@inproceedings{paperbot4996,
title = {Algorithmic barriers to representing conditional independence},
author = {Nathanael L. Ackerman and Jeremy Avigad and Cameron E. Freer and Daniel M. Roy and Jason M. Rute},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785762}
}