On the Expressive Power of Tree-Structured Probabilistic Circuits
Authors: Lang Yin, Han Zhao
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide a negative answer to this conjecture by proving that, for n variables, there exists a quasi-polynomial upper bound n O(log n) on the size of an equivalent tree computing the same probability distribution. On the other hand, we also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs. |
| Researcher Affiliation | Academia | Lang Yin Department of Computer Science University of Illinois Urbana-Champaign langyin2@illinois.edu Han Zhao Department of Computer Science University of Illinois Urbana-Champaign hanzhao@illinois.edu |
| Pseudocode | Yes | Algorithm 1: Construction of Ψ Algorithm 2: Transforming a rooted DAG to a tree Algorithm 3: Construction of P , an efficient PC for P without a depth constraint |
| Open Source Code | No | The paper does not state that code is provided or link to a repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training with datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation with datasets. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments requiring hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments requiring specific software dependencies. |
| Experiment Setup | No | The paper is theoretical and does not report on experiments that would require an experimental setup description. |