和积网络的性质分析及其有效性验证算法

doi:10.7523/j.issn.2095-6134.2020.01.016

中国科学院大学学报 ›› 2020, Vol. 37 ›› Issue (1): 136-143.DOI: 10.7523/j.issn.2095-6134.2020.01.016

• 简报 • 上一篇

和积网络的性质分析及其有效性验证算法

刘洋¹, 罗晨希², 罗铁坚¹

1 中国科学院大学计算机与控制学院, 北京 101408;
2 中国科学院软件所, 北京 100080

收稿日期:2018-04-23 修回日期:2018-07-18 发布日期:2020-01-15
通讯作者: 刘洋
基金资助:
中国科学院仪器共享设备管理系统（Y42901VED2）资助

Property analysis and validity verification algorithms of sum-product network

LIU Yang¹, LUO Chenxi², LUO Tiejian¹

1 School of Computer and Control, University of Chinese Academy of Sciences, Beijing 101408, China;
2 Institute of Software, Chinese Academy of Sciences, Beijing 100080, China

Received:2018-04-23 Revised:2018-07-18 Published:2020-01-15

摘要/Abstract

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

关键词: 深度学习, 概率图模型, 和积网络, 有效性

Abstract: 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.

Key words: deep learning, probabilistic graphical models, sum-product networks, validity

中图分类号:

TP305

刘洋, 罗晨希, 罗铁坚. 和积网络的性质分析及其有效性验证算法[J]. 中国科学院大学学报, 2020, 37(1): 136-143.

LIU Yang, LUO Chenxi, LUO Tiejian. Property analysis and validity verification algorithms of sum-product network[J]. , 2020, 37(1): 136-143.

参考文献

[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.

和积网络的性质分析及其有效性验证算法

Property analysis and validity verification algorithms of sum-product network

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	周龙, 王伟强, 吕科. FACR：一种快速且准确的车辆识别器[J]. 中国科学院大学学报, 2021, 38(1): 130-136.
[2]	李森, 彭玲, 胡媛, 池天河. 基于FD-RCF的高分辨率遥感影像耕地边缘检测[J]. 中国科学院大学学报, 2020, 37(4): 483-489.
[3]	卢凯旋, 李国清, 陈正超, 昝露洋, 李柏鹏, 高建威. 基于负样本多通道优化SSD网络的钢铁厂提取[J]. 中国科学院大学学报, 2020, 37(3): 352-359.
[4]	闫凯, 沈汀, 陈正超, 闫弘轩. 基于深度学习的SSD模型尾矿库自动提取[J]. 中国科学院大学学报, 2020, 37(3): 360-367.
[5]	宋旭鸣, 沈逸飞, 石远明. 基于深度学习的智能移动边缘网络缓存[J]. 中国科学院大学学报, 2020, 37(1): 128-135.
[6]	陶玉强, 张淑贞, 薛滨. 土壤中多环芳烃生物有效性及其评价方法[J]. 中国科学院大学学报, 2010, 27(4): 568-576.
[7]	刘务华; 罗铁坚; 王文杰. 文本聚类算法的质量评价[J]. 中国科学院大学学报, 2006, 23(5): 640-646.