摘要
概率电路(PCs)已成为一种强大的框架,可以紧凑地表示概率分布,从而实现高效且精确的概率推理。研究表明,具有通用有向无环图(DAG)结构的 PCs 可以理解为指数级(以其高度为底)多个分量的混合,每个分量都是对单变量边缘分布的乘积分布。然而,现有的 PC 结构学习算法通常会生成树状结构的电路,或使用树状结构的电路作为中间步骤将其压缩成 DAG 结构的电路。这引出了一个有趣的问题,即 PC 结构的 DAG 与树之间是否存在指数级的差距。在本文中,我们通过证明对于 $n$ 个变量,存在一个次指数级上限 $n^{O(\log n)}$ 来否定这一猜想,该上限是等效树的大小,该树计算相同的概率分布。另一方面,我们还表明,在对树的深度进行限制的情况下,树状结构的 PC 与 DAG 结构的 PC 之间存在超多项式分离。我们的工作朝着理解树状结构的 PC 的表达能力迈出了重要的一步,并且我们的技术在研究 PC 的结构学习算法中可能具有独立的意义。