Sum-Product Graphical Models: a Graphical Model Perspective on Sum-Product Networks

The trade off between expressiveness of representation and tractability of inference is a key issue of probabilistic models. On the one hand, probabilistic Graphical Models (GMs) provide a high level representation of distributions, but exact inference with cyclic graphs is in general intractable. On the other hand, Sum-Product Networks (SPNs) allow tractable exact inference with probability distributions that are more complex than tractable GMs, but they employ a low level representation of the underlying distribution, which is much harder to read and interpret than in GMs. The objective of this thesis is to close this gap and to achieve simultaneously the high level representation of GMs and the efficiency of SPNs. To this aim, new models and procedures are introduced. We first investigate SPNs that include GMs as a submodule, obtaining a derivation of Expectation-Maximization for SPNs which is the first allowing to learn the GM part alongside the SPN parameters. Then, we introduce a new architecture called Sum-Product Graphical Model (SPGM). This new architecture is the first to combine the semantics of graphical models with the evaluation efficiency of SPNs: SPGMs always enable tractable inference using a class of models that incorporate context specific independence (like SPNs), and they provide a high-level model interpretation in terms of conditional independence assumptions and corresponding factorizations (like GMs). An algorithm for learning both the structure and the model parameters of SPGMs is also introduced. Finally, several applications that illustrate and empirically motivate the introduction of the new models are described. SPGMs are applied to real-world discrete density estimation datasets, to augment a graphical model for segmenting scans of the human retina and detecting local pathologies, and to model very large mixtures of Quadtrees for image denoising. Strong empirical results and novel application areas denote promise for future applications of SPGMs