Reproduce “A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, Guy Van den Broeck
A compositional atlas of tractable circuit operations is presented, establishing structural conditions on probabilistic circuits that enable efficient and exact computation of fundamental transformations and complex information-theoretic queries. This work systematically characterizes tractability boundaries for operations like products, powers, and logarithms, as well as for Shannon entropy and Kullback-Leibler divergence.
Key insights
- The tractability of complex information-theoretic queries can be systematically determined by composing and analyzing the tractability of elementary circuit operations.
- Specific structural properties, particularly determinism for operations like power and logarithm, and compatibility for product and quotient, are crucial for achieving polynomial-time exact computation.
- The framework unifies and generalizes existing inference algorithms across various tractable model classes, extending their applicability to broader non-deterministic distributions within the PC framework.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.