Probabilistic circuits (PCs) have emerged as a powerful framework to compactly represent probability distributions for efficient and exact probabilistic inference. It has been shown that PCs with a general directed acyclic graph (DAG) structure can be understood as a mixture of exponentially (in its height) many components, each of which is a product distribution over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits or use tree-structured circuits as intermediate steps to compress them into DAG-structured circuits. This leads to the intriguing question of whether there exists an exponential gap between DAGs and trees for the PC structure. In this paper, we provide a negative answer to this conjecture by proving that, for $n$ variables, there exists a sub-exponential 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.

本研究解决了树结构概率电路与有向无环图（DAG）概率电路之间的表达能力差距问题。我们提出了一种新的方法，证明对于$n$个变量，存在一个次指数上限的树可以计算相同的概率分布，同时证明在树的深度限制下，树与DAG结构之间有超多项式的差异。此研究对理解树结构概率电路的表达能力具有重要意义，并且我们的技术可能对概率电路的结构学习算法研究具有独立的价值。