In this paper, we establish some theoretical connections between Sum-Product Networks (SPNs) and Bayesian Networks (BNs). We prove that every SPN can be converted into a BN in linear time and space in terms of the network size. The key insight is to use Algebraic Decision Diagrams (ADDs) to compactly represent the local conditional probability distributions at each node in the resulting BN by exploiting context-specific independence (CSI). The generated BN has a simple directed bipartite graphical structure. We show that by applying the Variable Elimination algorithm (VE) to the generated BN with ADD representations, we can recover the original SPN where the SPN can be viewed as a history record or caching of the VE inference process. To help state the proof clearly, we introduce the notion of {\em normal} SPN and present a theoretical analysis of the consistency and decomposability properties. We conclude the paper with some discussion of the implications of the proof and establish a connection between the depth of an SPN and the tree-width of its corresponding BN.

本文研究和探讨了和Sum-Product Networks有关的Bayesian Networks的理论联系，并给出了使用Algebraic Decision Diagrams来表示和转换SPN为BN的一个线性时间和空间复杂度的算法。同时，用Variable Elimination算法来恢复原始的SPN，并且介绍了SPN的深度和对应的BN树宽的下界之间的联系。

Sum-Product Networks 与贝叶斯网络之间的关系