Sum-Product Network structure learning by efficient product nodes discovery

Nicola Di Mauro, Floriana Esposito, Fabrizio Giuseppe Ventola, Antonio Vergari

Research output: Contribution to journalArticlepeer-review


Sum-Product Networks (SPNs) are recently introduced deep probabilistic models providing exact and tractable inference. SPNs have been successfully employed in several application domains, from computer vision to natural language processing, as accurate density estimators. However, learning their structure and parameters from high dimensional data poses a challenge in terms of time complexity. Classical SPNs structure learning algorithms work by repeating several times two high cost operations: determining independencies among random variables (RVs)–introducing product nodes–and finding sub-populations among samples–introducing sum nodes. Even one of the simplest greedy structure learner, LearnSPN , scales quadratically in the number of the variables to determine RVs independencies. In this work, we investigate the trade-off between accuracy and efficiency when employing approximate but fast procedures to determine independencies among RVs. We introduce and evaluate sub-quadratic procedures based on a random subspace approach and leveraging entropy as a proxy criterion to split independent RVs. Experimental results on many benchmark datasets for density estimation show that LearnSPN -like structure learners, when equipped by our splitting procedures, provide reduced learning and/or inference times, generally containing the degradation of inference accuracy. Ultimately, we provide an empirical confirmation of a “no free lunch” when learning the structure of SPNs.
Original languageEnglish
Pages (from-to)143-159
Number of pages17
JournalIntelligenza Artificiale
Issue number2
Publication statusPublished - 29 Jan 2019


  • Machine learning
  • deep learning
  • structure learning
  • probabilistic models
  • density estimation
  • Sum-Product Networks


Dive into the research topics of 'Sum-Product Network structure learning by efficient product nodes discovery'. Together they form a unique fingerprint.

Cite this