AI Lunch and Seminar

Han Zhao - Sum-Product Networks: A New Probabilistic Inference Machine

Abstract: Sum-product networks (SPNs) are new deep inference machines that admit exact probabilistic inference in linear time in the size of the network. In this talk I will establish some theoretical connections between SPNs and traditional graphical models like Bayesian Networks (BNs). Specifically, I will show 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. I will also discuss some 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. I will conclude the talk by discussing some algorithms for learning the parameters of SPNs based on maximum-likelihood principle and Bayesian approaches.

This is joint work with Geoff Gordon, Mazen Melibari and Pascal Poupart.