Sum-product networks (SPN) is a deep probabilistic graphical model which has the characteristic of fast inference in multilayer networks, and it has wide application prospect in the field of artificial intelligence. The validity of SPN is that it can be used to represent the probability distribution correctly so that SPN can be used to represent the distribution functions of some graph models and all the marginal distributions. Since SPN is not always valid, it is necessary to determine the effectiveness of SPN quickly. In this paper, we consider the problem of validity verification in the SPN theoretical system, reveal the internal structure properties of SPN, and propose two algorithms for verifying the validity of SPN. The correctness proofs and the complexity of the proposed algorithms are given. We also verify the reliability of the proposed algorithms by giving a new method of calculating the number of generation trees in SPN.
LIU Yang
,
LUO Chenxi
,
LUO Tiejian
. Property analysis and validity verification algorithms of sum-product network[J]. Journal of University of Chinese Academy of Sciences, 2020
, 37(1)
: 136
-143
.
DOI: 10.7523/j.issn.2095-6134.2020.01.016
[1] Poon H, Domingos P. Sum-product networks:a new deep architecture[C]//Proceedings of 12th Conf on Uncertainty in Artificial Intelligence, Barcelona, Spain:AUAI, 2011:2551-2558.
[2] Peharz R. Foundations of sum-product networks for probabilistic modeling[D]. Graze:Medical University of Graz, 2015.
[3] Roth D. On the hardness of approximate reasoning[J]. Artificial Intelligence, 1996, 82:273-302.
[4] Peharz R, Geiger B, Pernkopf F. Greedy part-wise learning of sum-product networks[C]//Machine Learning and Knowledge Discovery in Databases, Berlin, German:Springer, 2013, 8189:612-627.
[5] Peharz R, Kapeller G, Mowlaee P, et al. Modeling speech with sum-product networks:application to bandwidth extension[C]//International Conference on Acoustics, Speech and Signal Processing, Piscataway, NJ:IEEE, 2014:3699-3703.
[6] Cheng W C, Kok S, Pham H V, et al. Language modeling with sum-product networks[C]//Interspeech, Singapore, 2014:2098-2102.
[7] Gens R, Domingos P. Learning the structure of sum-product networks[C]//Proceedings of the International Conference on Machine Learning, Atlanta, GA, USA:ACM, 2013:873-880.
[8] Vergari A, Mauro N D, Esposito F. Simplifying, regularizing and strengthening sum-product network structure learning[C]//Proceedings of Machine Learning and Knowledge Discovery in Databases, Berlin, German:Springer, 2015:343-358.
[9] Rooshenas A, Lowd D. Learning sum-product networks with direct and indirect variable interactions[C]//International Conference on Machine Learning, Atlanta, GA, USA:ACM, 2014, 32:710-718.
[10] Zhao H, Melibari M, Poupart P. On the Relationship between Sum-Product Networks and Bayesian Networks[C]//Proceedings of International Conference on Machine Learning, Atlanta, GA, USA:ACM, 2015:116-124.
[11] Martens J, Medabalimi V. On the expressive efficiency of sum product networks[J]. Computer Science, 2014, 1:102-110.
[12] Peharz R, Tschiatschek S, Pernkopf F, et al. On theoretical properties of sum-product networks[J]. Journal of Machine Learning Research, 2015, 38:744-752.
[13] Zhao H, Poupart P, Gordon G. A unified approach for learning the parameters of sum-product networks[C]//Proceedings of the 29th Advances in Neural Information Processing Systems, Barcelona, Spain:MIT Press, 2016, 12:146-153.
[14] Dennis A, Ventura D. Learning the architecture of sum-product networks using clustering on varibles[C]//Advances in Neural Information Processing Systems, Lake Tahoe, Nevada, USA:MIT Press, 2012:2033-2041.
[15] Adel T, Balduzzi D, Ghodsi A. Learning the structure of sum-product networks via an svd-based algorithm[C]//Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain:AUAI, 2015:32-41.
[16] Rashwan A, Zhao H, Poupart P. Online and distributed Bayesian moment matching for parameter learning in sum-product networks[C]//Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, Cadiz, Spain:JMLR, 2016:1469-1477.
[17] Nath A, Domingos P. Learning tractable probabilistic models for fault localization[C]//Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, New Orleans, LA, USA:AAAI, 2016:1294-1301.
[18] Lecun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11):2278-2324.
