欢迎访问中国科学院大学学报,今天是

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

• 简报 • 上一篇    

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

刘洋1, 罗晨希2, 罗铁坚1   

  1. 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 Yang1, LUO Chenxi2, LUO Tiejian1   

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

摘要: 和积网络(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

中图分类号: