PhD defense Robert Peharz

Ao.Univ.-Prof.Dr. W. RENHART
Assoc.Prof.Dr. F. PERNKOPF
Assoc.Prof.Dr. M. JÄGER (Aalborg University, Dänemark)


Foundations of Sum-Product Networks for Probabilistic Modeling

Sum-product networks (SPNs) are a promising and novel type of probabilistic model, which has been receiving significant attention in recent years. There are, however, several open questions regarding the foundations of SPNs and also some misconceptions in literature. In this thesis we provide new theoretical insights and aim to establish a more coherent picture of the principles of SPNs. As a first main contribution we show that, without loss of generality, SPN parameters can be assumed to be locally normalized, i.e. normalized for each individual sum node. Furthermore, we provide an algorithm which transforms unnormalized SPN-weights into locally normalized weights, without changing the represented distribution. Our second main contribution is concerned with the two notions of consistency and decompos- ability. Consistency, together with completeness, is required to enable efficient inference in SPNs over random variables with finitely many states. Instead of consistency, usually the conceptually easier and stronger condition of decomposability is used. As our second main contribution we show that consistent SPNs can not represent distributions exponentially more compactly than decomposable SPNs. Furthermore, we point out that consistent SPNs are not amenable for Darwiche’s differential approach to inference. SPNs were originally defined over random variables with finitely many states, but can be easily generalized to SPNs over random variables with infinitely many states. As a third main contribution, we formally derive two inference mechanisms for generalized SPNs, which so far have been derived only for finite-state SPNs. These two inference scenarios are marginalization and the so-called evaluation of modified evidence. Our fourth main contribution is to make the latent variable interpretation of sum nodes in SPNs more precise. We point out a weak point about this interpretation in literature and propose a remedy for it. Furthermore, using the latent variable interpretation, we concretize the inference task of finding the most probable explanation (MPE) in the corresponding latent variable model. We show that the MPE inference algorithm proposed in literature suffers from a phenomenon which we call low-depth bias. We propose a corrected algorithm and show that it indeed delivers an MPE solution. While an MPE solution can be efficiently found in the augmented latent variable model, we show that MPE inference in SPNs is generally NP-hard. As another contribution, we point out that the EM algorithm for SPN-weights presented in literature is incorrect, and propose a corrected version. Furthermore, we discuss some learning approaches for SPNs and a rather powerful sub-class of SPNs, called selective SPNs, for which maximum-likelihood parameters can be found in closed form.


Date with Time
27. February 2015 - 8:30
Seminar room IDEG 134 (Inffeldgasse 16c)