Not All Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits
Abstract
Probabilistic modeling is a central task in machine learning. Probabilistic models should be tractable, i.e., allowing tractable probabilistic inference, but also efficient, i.e., being able to represent a large set of probability distributions. Zhang et al. (ICML 2021) recently proposed a new model, probabilistic generating circuits. They raised the question whether every strongly Rayleigh distribution can be efficiently represented by such circuits. We prove that this question has a negative answer, there are strongly Rayleigh distributions that cannot be represented by polynomial-sized probabilistic generating circuits, assuming a widely accepted complexity theoretic conjecture.
Cite
Text
Bläser. "Not All Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits." International Conference on Machine Learning, 2023.Markdown
[Bläser. "Not All Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/blaser2023icml-all/)BibTeX
@inproceedings{blaser2023icml-all,
title = {{Not All Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits}},
author = {Bläser, Markus},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {2592-2602},
volume = {202},
url = {https://mlanthology.org/icml/2023/blaser2023icml-all/}
}