期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于全条件独立的贝叶斯网络MPD-JT构造算法 被引量：4

Construction algorithm of MPD-JT for Bayesian networks based on full conditional independence
下载PDF
导出
摘要 针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题,提出了一种基于全条件独立结构的最大主子图连接树(maximal prime sub-graph decomposition junction tree,MPD-JT)构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图,并利用构成这些最大主子图的节点作为簇节点构造连接树,避免了三角化过程,而且在求解过程中通过删除一些符合条件的点,大大降低了算法复杂度。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。 As the decomposition of Bayesian networks（BN） into their maximal prime sub-graph is a NP-hard problem,a new method for constructing the maximal prime sub-graph junction tree（MPD-JT） of BN is presented.This approach obtains the MPD of BN motivated by the full conditional independence information encoded in the moral graph of the original BN and uses these MPDs as a cluster of nodes to construct a junction tree,it also avoids the process of triangulation and reduces the time complexity by eliminating some coincident nodes.The correctness of the method is proven and the validity of the algorithm is analyzed by an example.
作者 朱明敏 刘蔚 杨有龙
机构地区 西安电子科技大学数学系
出处 《系统工程与电子技术》 EI CSCD 北大核心 2010年第6期1325-1328,共4页 Systems Engineering and Electronics
基金 国家自然科学基金(60674108 60705004)资助课题
关键词 贝叶斯网络 最大主子图 连接树 全条件独立 Bayesian network（BN） maximal prime sub-graph junction tree full conditional independence
分类号 TP181 [自动化与计算机技术—控制理论与控制工程]
  • 相关文献

参考文献13

  • 1Chickering D M,Meek C.On the incompatibility of faithfulness and monotone DAG faithfulness[J].Artificial Intelligence,2006,170:653-666.
  • 2Namasivayam V K,Prasanna V K.Scalable parallel implemen-tation of exact inference in Bayesian networks.[C] //Twelfth International Conference on Parallel and Distributed Systems,2006.
  • 3Olesen K,Madsen A.Maximal prime sub-graph decomposition of Bayesian networks[J].IEEE Trans.on Systems,Man and Cybernetics,Part B,2002,32:21-31.
  • 4Madsen A L,Jensen F V.Lazy propagation in junction trees[C] //Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence,Morgan Kaufmann,1998:362-369.
  • 5Madsen A L.Variations over the message computation algorithm of lazy propagation[J].IEEE Trans.on Systems,Man and Cybernetics,Part B:2006,36(36):636-648.
  • 6Chickering D.M,Meek C,Heckerman D.Large-sample learning of Bayesian networks is NP-hard[J].Journal of Machine Learning Research,2004:1287-1330.
  • 7Tarjan R E.Decomposition by clique separators[J].Discrete Mathematics,1985,55:221-232.
  • 8Leimer H G.Optimal decomposition by clique separators[J].Discrete Mathematics,1993,113:99-123.
  • 9Badsberg J H.Decomposition of graphs and hypergraphs with identification of eonformal hypergraphs[R].Department of Mathematics and Computer Science,Aalhorg Umiversing,Research Report,R-96-2032,1996.
  • 10Flores M J,Gámez J A.A review on distinct methods and approaches to perform triangulation for Bayesian networks[J].Advances in Probabilistic graphical Models,Studies in Fuzziness and Soft Computing,Springer-Verlag,213:127-152.

二级参考文献24

  • 1Gamez J,Puerta J. Searching for the best elimination sequence in Bayesian networks by using Ant Colony based optimization:[Technical Report # DIAB-01-04-13]. Department of Computer Science,University of Castilla-La Mancha, Jan. 2000
  • 2Huang C,Darwiche A. Inference in belief networks: A procedural guide. Intl. J of Approximate Reasoning,1996,15(3) :225～263
  • 3Jensen F V,Jensen F. Optimal junction trees. In Uncertainty in Artificial Intelligance. In: Proc. of the Tenth Conf. San Mareo,CA,Morgan Kaufman,July 1994. 360～366
  • 4Jensen F V, Lauritzen S L, Olesen K G. Bayesian updating in causal probabilistic networks by local computations. Computational Statistics Quarterly, 1990,4: 269～282
  • 5Kjaerulff U. Triangulation of Graphs - Algorithms Giving Small Total State Space: [Technical Report R 90-09]. Department of Mathematics and Computer Science, Aalborg University, Denmark, 1990
  • 6Lauritzen S L,Spiegelhalter D J. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society,Series B (Methodological), 1988,50 (2): 157,224
  • 7Lekkerkerker C G,Boland J C. Representation of a finite graph by a set of intervals on the real line. Fund. Math. ,1962,51:45～64
  • 8Murphy K. The Bayes Net Toolbox for Matlab. Computing Science and Statistics. Available at: http:∥citeseer. ist. psu. edu/murphy01bayes. html. 2001,33
  • 9Pearl J. Probabilistic Reasoning in Intelligent Systems:Networks of Plausible Inference. In:Proc. National Conf. on AI,Pittsburgh.Morgan Kaufmann,San Mateo,CA,1988. 133～136
  • 10Pearl J. Probabilistic Reasoning in Intelligent Systems. MorganKaufmann,San Mateo,California, 1988

同被引文献63

  • 1龚淑华,刘祥官.模糊贝叶斯网络应用于预测高炉铁水含硅量变化趋势[J].冶金自动化,2005,29(5):30-32. 被引量：13
  • 2杨帆,萧德云.概率SDG模型及故障分析推理方法[J].控制与决策,2006,21(5):487-491. 被引量：15
  • 3邓歆,孟洛明.基于贝叶斯网络的通信网告警相关性和故障诊断模型[J].电子与信息学报,2007,29(5):1182-1186. 被引量：24
  • 4Takens F.Detecting strange attractors in turbulence[J].Lecture Notes in Math,1981,898:361-381.
  • 5Pearl J F.Propagation and structuring in belief networks[J].Artificial,Intelligence,1986,29(3):241-288.
  • 6Packard N H,Crutchfield J P,Farmer J D,et al.Geometry from a time series[J].Phys Rev Lett,1980,45(3):712-716.
  • 7Anita L,Kalnapa M,Bhavanath J.Biosorption of heavymetals by amarine bacterium[J].Marine Pollution Bulletin,2005,50(3):340-343.
  • 8Kim H,Eykholt R J,Salas D.Nonlinear dynamics,delay times,and embeddmg window[J].Physica:D,1999,127(1):48-60.
  • 9Gooper G F,Herskovits E.A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning,1992,9(4):309-347.
  • 10Duda R O,Hart P E,Stack D G.Pattern classification[M].New York:John Wiley&Sons Inc,2001.

引证文献4

二级引证文献14

系统工程与电子技术
2010年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部