Exact marginal and conditional inference in classic probabilistic graphical models (PGMs), including Bayesian Networks (BNs) and Markov Networks (MNs), is #P-complete. As a result, practitioners usually need to resort to various approximate inference schemes to ensure computational tractability. Sum-Product Networks (SPNs) have been proposed as tractable deep models for exact probabilistic inference. They distinguish themselves from other types of probabilistic graphical models by the fact that inference can be done exactly in linear time with respect to the size of the network. This has generated a lot of interest since inference is not only a powerful tool to reason under uncertainty, but also a core task for parameter estimation and structure learning.
In this thesis, we concentrate on both theoretical and practical part of learning tractable probabilistic graphical models. We investigate the representational power of SPNs, the parameter learning of SPNs, and the structure learning of both BNs and SPNs. On the theoretical side, we show an equivalence result between SPNs and BNs and provide a characterization of SPNs through mixture models with exponentially (in the height of the graph) many components. On the practical side, we propose both frequentist's and Bayesian's, batch and online learning algorithms for parameter estimation of SPNs.
Geoff Gordon (Chair)
Tommi Jaakkola (MIT)