证明树形概率电路与图结构电路在表达能力上无指数差距
On the Expressive Power of Tree-Structured Probabilistic Circuits
- 构建树形电路可高效逼近任意有向无环图结构电路
- 对n变量分布，树形电路大小上限为n^{O(log n)}
- 适用于研究概率电路结构学习的理论分析
概率电路（PC）作为紧凑表示概率分布的强大框架，支持高效精确的推断。已有研究表明，具有通用有向无环图（DAG）结构的PC可被理解为指数级（以高度为指数）多个分量的混合，每个分量是单变量边缘分布的乘积。然而，现有结构学习算法常生成树形电路或将其作为压缩为DAG电路的中间步骤，引发一个关键问题：树形与DAG结构之间是否存在指数级表达能力差距？本文通过证明：对于n个变量，存在一个准多项式上界n^{O(log n)}，使得等价的树形电路可计算相同概率分布，从而给出了否定回答。另一方面，我们还证明，在限制树深度的情况下，树形与DAG结构的PC间存在超多项式分离。本工作推进了对树形概率电路表达能力的理解，其技术方法可能对概率电路结构学习算法研究具有独立意义。
原文摘要 · Abstract (English)
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 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。