On Relaxing Determinism in Arithmetic Circuits

Abstract

The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).

In Proceedings of the Thirty-fourth International Conference on Machine Learning (ICML)

References in corpus (2)

• Sum-Product Networks: A New Deep Architecture
• Learning Arithmetic Circuits

Cited by in corpus (9)

• SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks
• Sum-product networks: A survey
• Approximate Knowledge Compilation by Online Collapsed Importance Sampling
• Interventions and Counterfactuals in Tractable Probabilistic Models: Limitations of Contemporary Transformations
• Sum-Product Network Decompilation
• On Constraint Definability in Tractable Probabilistic Models
• Lossless Compression with Probabilistic Circuits
• Sum-Product Networks for Hybrid Domains
• Explaining Deep Tractable Probabilistic Models: The sum-product network case