Abstract
Gaussian graphical models are important undirected graphical models with multivariate Gaussian distribution. A key probabilistic inference problem for the model is to compute the marginals. Exact inference algorithms have cubic computational complexity, which is intolerable for large-scale models. Most of approximate inference algorithms have a form of message iterations, and their computational complexity is closely related to the convergence and convergence rate, which causes the uncertain computational efficiency. In this paper, we design a fixed parameter linear time approximate algorithm — the Gaussian message propagation in d-order neighborhood. First, we define the d-order neighborhood concept to describe the propagation scope of exact Gaussian messages. Then we design the algorithm of Gaussian message propagation in d-order neighborhood, which propagates Gaussian messages in variable’s d-order neighborhood exactly, and in the (d + 1)th-order neighborhood partly to preserve the spread of the Gaussian messages, and computes the approximate marginals in linear time O(n·d 2) with the fixed parameter d. Finally, we present verification experiments and comparison experiments, and analyze the experiment results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Cozman, F.G.: Graphical models for imprecise probabilities. International Journal of Approximate Reasoning 39(2-3), 167–184 (2005)
Rue, H., Held, L.: Gaussian Markov random fields: Theory and applications. Chapman & Hall, London (2005)
de Camposa, L.M., Romero, A.E.: Bayesian network models for hierarchical text classification from a thesaurus. International Journal of Approximate Reasoning 50(7), 932–944 (2009)
Malioutov, D.: Approximate inference in Gaussian graphical models. PhD thesis, Massachusetts Institute of Technology (2008)
Bishop, C.M.: Pattern recognition and machine learning, ch. 10, pp. 461–522. Springer (2006)
Jordan, M.I., Weiss, Y.: Graphical models: probabilistic inference. In: Arbib, M.A. (ed.) The Handbook of Brain Theory and Neural Networks, pp. 490–496. The MIT Press (2002)
Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning 1(1-2), 1–305 (2008)
Yedidia, J.S., Freeman, W.T., Weiss, Y.: Understanding belief propagation and its generalization. Technical Report TR2001-22, Mitsubishi Electric Research Labs (January 2002)
Winn, J.: Variational message passing and its applications. PhD thesis, University of Cambridge (2003)
Winn, J., Bishop, C.M.: Variational message passing. Journal of Machine Learning Research 6, 661–694 (2005)
Johnson, J.K.: Convex relaxation methods for graphical models: lagrangian and maximum entropy approaches. PhD thesis, Massachusetts Institute of Technology (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, Y., Xiong, C., Xie, H. (2013). Gaussian Message Propagation in d-order Neighborhood for Gaussian Graphical Model. In: Guo, C., Hou, ZG., Zeng, Z. (eds) Advances in Neural Networks – ISNN 2013. ISNN 2013. Lecture Notes in Computer Science, vol 7951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39065-4_65
Download citation
DOI: https://doi.org/10.1007/978-3-642-39065-4_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39064-7
Online ISBN: 978-3-642-39065-4
eBook Packages: Computer ScienceComputer Science (R0)