和积网络（sum-product networks，SPN）是一种在多层网络中进行快速推理的深度概率图模型，在人工智能领域有广泛应用前景。SPN的有效性即它可用来正确表示概率分布，使得SPN可以表示一些图模型的配分函数和所有的边缘分布。由于只有部分SPN是有效的，快速判断SPN的有效性很有必要。针对SPN理论体系中的有效性验证问题，讨论并揭示SPN内部结构性质，提出验证SPN有效性的两个算法，并给出算法的正确性证明及其复杂度。还通过给出一种新的SPN中生成树个数的计算方法来验证SPN有效性算法的可靠性。
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.
[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.
