On Theoretical Properties of Sum-Product Networks


Robert Peharz, Sebastian Tschiatschek, Franz Pernkopf, Pedro Domingos ;
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:744-752, 2015.


Sum-product networks (SPNs) are a promising avenue for probabilistic modeling and have been successfully applied to various tasks. However, some theoretic properties about SPNs are not yet well understood. In this paper we fill some gaps in the theoretic foundation of SPNs. First, we show that the weights of any complete and consistent SPN can be transformed into locally normalized weights without changing the SPN distribution. Second, we show that consistent SPNs cannot model distributions significantly (exponentially) more compactly than decomposable SPNs. As a third contribution, we extend the inference mechanisms known for SPNs with finite states to generalized SPNs with arbitrary input distributions.

Related Material