Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Expressive Power of Tree-Structured Probabilistic Circuits
Authors: Lang Yin, Han Zhao
NeurIPS 2024 | Venue PDF | 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 EMAIL Han Zhao Department of Computer Science University of Illinois Urbana-Champaign EMAIL |
| 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. |