On the Relationship between Sum-Product Networks and Bayesian Networks
This provides foundational theoretical insights connecting two probabilistic graphical model frameworks, which is incremental but clarifies their relationship for researchers in machine learning and probabilistic reasoning.
The paper establishes theoretical connections between Sum-Product Networks (SPNs) and Bayesian Networks (BNs), proving that every SPN can be converted into a BN in linear time and space using Algebraic Decision Diagrams (ADDs) to exploit context-specific independence. It shows that applying Variable Elimination to the generated BN recovers the original SPN, linking SPN depth to a lower bound of the BN's tree-width.
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 a lower bound of the tree-width of its corresponding BN.