Learning the Structure of Sum-Product Networks

Robert Gens, Domingos Pedro
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):873-880, 2013.

Abstract

Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-gens13, title = {Learning the Structure of Sum-Product Networks}, author = {Gens, Robert and Pedro, Domingos}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {873--880}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/gens13.pdf}, url = {https://proceedings.mlr.press/v28/gens13.html}, abstract = {Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy.} }
Endnote
%0 Conference Paper %T Learning the Structure of Sum-Product Networks %A Robert Gens %A Domingos Pedro %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-gens13 %I PMLR %P 873--880 %U https://proceedings.mlr.press/v28/gens13.html %V 28 %N 3 %X Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy.
RIS
TY - CPAPER TI - Learning the Structure of Sum-Product Networks AU - Robert Gens AU - Domingos Pedro BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-gens13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 873 EP - 880 L1 - http://proceedings.mlr.press/v28/gens13.pdf UR - https://proceedings.mlr.press/v28/gens13.html AB - Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy. ER -
APA
Gens, R. & Pedro, D.. (2013). Learning the Structure of Sum-Product Networks. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):873-880 Available from https://proceedings.mlr.press/v28/gens13.html.

Related Material