基于Markov毯分解的抽样近似推理算法

Abstract
Figure/Table
References (21)
Related Citation (15)

Download: PDF (670 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract

Current inference algorithms of Bayesian networks are weak on inference precision and inference time to a certain degree. Therefore, in this paper a practical and reliable inference method, samplingapproximate inference algorithm based on Markov blanket (LSIA-MB), is presented. Firstly, HITON_MB algorithm is utilized to obtain the Markov blanket of the query node and then the dynamic programming algorithm is used to learn the posterior probability of edges to get a Markov local network model of the query node.Finally, Gibbs sampling inference algorithm is executed on the Markov local model. The sampling on the local model significantly reduces the calculation dimensions. The inference precision is retained because the Markov local model contains the complete information associated with the query node. Algorithm analysis and experimental results on standard Alarm network show LSIA-MB algorithm significantly reduces the inference time and improves the inference precision. The inference results of LSIA-MB algorithm on the Shanghai stock exchange network show the algorithm has strong practicability.

Key words： Approximate Inference Bayesian Network Markov Blanket Gibbs Sampling

Received: 09 May 2012

ZTFLH:

TP181

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	WANG Hao
	CAO Long-Yu
	YAO Hong-Liang
	LI Jun-Zhao

Cite this article:

WANG Hao,CAO Long-Yu,YAO Hong-Liang等. A Sampling Approximate Inference Algorithm Based on Decomposition of Markov Blanket[J]. , 2013, 26(8): 729-739.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/ OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2013/V26/I8/729

[1] Daly R, Shen Q, Aitken S. Learning Bayesian Networks: Approaches and Issues. Knowledge Engineering Review, 2011, 26(2): 99-157
[2] Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, USA: Morgan Kaufmann, 1988
[3] Yao Hongliang, Wang Hao, Zhang Yousheng, et al. Research on Multi-Agent Dynamic Influence Diagrams and Its Approximate Inference Algorithm. Chinese Journal of Computers, 2008, 31(2): 236-244(in Chinese)
(姚宏亮,王浩,张佑生,等.多Agent 动态影响图及其一种近似推理算法研究.计算机学报, 2008, 31(2): 236-244)
[4] Dagum P, Luby M. Approximating Probabilistic Inference in Baye-sian Belief Networks is NP-Hard. Artificial Intelligence, 1993, 60(1): 141-153
[5] Takaishi T.Bayesian Inference of Stochastic Volatility Model by Hybrid Monte Carlo.Journal of Circuits, Systems and Computers, 2009, 18(8): 1381-1396
[6] Draper D. Clustering without (Thinking about) Triangulation // Proc of the 11th Conference on Uncertainty in Artificial Intelligence. Montreal, Canada, 1995: 378-385
[7] Tsamardinos I, Aliferis C F. Towards Principled Feature Selection: Relevancy, Filters and Wrappers[EB/OL].[2012-05-01]. http://research.microsoft.com/enus/um/cambridge/events/aistats 2003/proceedings/133.pdf
[8] Jin K H, Wu Dan, Wu Libing. On Designing Approximate Inference Algorithms for Multiply Sectioned Bayesian Networks // Proc of the IEEE International Conference on Granular Computing. Nanchang, China, 2009: 294-299
[9] Neal R M. Probabilistic Inference Using Markov Chain Monte Carlo Methods[EB/OL].[2012-05-01]. http://www.cs.toronto.edu/pub/radford/review.pdf
[10] Yu Binbing. A Bayesian MCMC Approach to Survival Analysis with Doubly-Censored Data. Computational Statistics and Data Analysis, 2010, 54(8): 1921-1929
[11] Geman S, Geman D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Trans on Pattern Analysis and Machine Intelligence, 1984, 6(6): 721-741
[12] Bac F R, Jordan M I. Thin Junction Tree // Dietterich T G, Becher S, Ghahramani Z, eds. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2002: 569-576
[13] Aliferis C F, Tsamardinos I, Statnikov A. HITON: A Novel Markov Blanket Algorithm for Optimal Variable Selection[EB/OL]. [2012-05-01]. http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1480117
[14] Koivisto M, Sood K. Exact Bayesian Structure Discovery in Baye-sian Networks[EB/OL]. [2012-05-01]. http://pdf.aminer.org/000/984/996/exact_bayesian_structure_discovery_in_baye-sian_networks.pdf
[15] Ferguson T S. A Bayesian Analysis of Some Nonparametric Pro-blems. The Annals of Statistics, 1973, 1(2): 209-230
[16] Heckerman D, Geiger D, Chickering M. Learning Bayesian Networks: the Combination of Knowledge and Statistical Data. Machine Learning, 1995, 20(3): 197-243
[17] Strens M J A. Evolutionary MCMC Sampling and Optimization in Discrete Spaces // Proc of the 20th International Conference on Machine Learning. Washington, USA, 2003: 736-743
[18] Zhou Bo, Okamura H, Dohi T. Markov Chain Monte Carlo Random Testing // Proc of the AST/UCMA/ISA/ACN Conference on Advances in Computer Science and Information Technology. Miyazaki, Japan, 2010: 447-456
[19] Eaton D, Murphy K. BDAGL: Bayesian DAG Learning[EB/OL]. [ 2012-05-01]. http://www.cs.ubc.ca/~murphyk/Software/BDAGL
[20] Aliferis C F, Statnikov A, Tsamardinos I, et al. Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification-Part I: Algorithms and Empirical Evaluation[EB/OL]. [2012-05-01].http://jmlr.org/papers/volume11/aliferis10a/aliferis10a.pdf
[21] Eaton D, Murphy K. Exact Bayesian Structure Learning from Uncertain Interventions[EB/OL]. [2012-05-01]. http://www.cs.ubc.ca/~murphyk/papers/aistats07.pdf