AI seminar: On the relationship between sum product networks and Bayesian networks

Friday, July 3, 2015 10:00 am - 10:00 am EDT (GMT -04:00)

Speaker: Han Zhao, University of Waterloo MSc graduate

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 normal SPN and present a theoretical analysis of the consistency and decomposability properties. We conclude 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.

This is joint work with Mazen Melibari and Pascal Poupart. This work will be presented at ICML 2015 in Lille, France.