A Compositional Atlas for Algebraic Circuits
Authors: Benjie Wang, Denis Mauá, Guy Van den Broeck, YooJung Choi
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we take an algebraic perspective for compositional inference, and show that a large class of queries including marginal MAP, probabilistic answer set programming inference, and causal backdoor adjustment correspond to a combination of basic operators over semirings: aggregation, product, and elementwise mapping. Using this framework, we uncover simple and general sufficient conditions for tractable composition of these operators, in terms of circuit properties (e.g., marginal determinism, compatibility) and conditions on the elementwise mappings. Applying our analysis, we derive novel tractability conditions for many such compositional queries. |
| Researcher Affiliation | Academia | Benjie Wang University of California, Los Angeles benjiewang@ucla.edu Denis Deratani Mauá University of São Paulo ddm@ime.usp.br Guy Van den Broeck University of California, Los Angeles guyvdb@cs.ucla.edu Yoo Jung Choi Arizona State University yj.choi@asu.edu |
| Pseudocode | Yes | In Algorithms 1-4 we present algorithms for the aggregation, product (with compatibility), product (with support-compatiblity), and elementwise mapping operators respectively (the initial call is to the root of the circuit(s)). |
| Open Source Code | No | The paper does not provide concrete access to source code for the described methodology. It is a theoretical paper that introduces a framework and algorithms. |
| Open Datasets | No | The paper is theoretical and describes a framework and algorithms; it does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments, so no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |