A Framework for Distributed Inference with Emerging Hardware.
NB: A static version of this interactive article has been published on arXiv and can be cited as:
@article{Ortiz2021visualGBP, title = {A visual introduction to Gaussian Belief Propagation}, author = {Ortiz, Joseph and Evans, Talfan and Davison, Andrew J.}, journal={arXiv preprint arXiv:2107.02308}, year = {2021}, }
See our short video introduction to the article here.
In this article, we present a visual introduction to Gaussian Belief Propagation (GBP), a probabilistic inference algorithm that operates by passing messages between the nodes of arbitrarily structured factor graphs. A special case of loopy belief propagation, GBP updates rely only on local information and will converge independently of the message schedule. Our key argument is that, given recent trends in computing hardware, GBP has the right computational properties to act as a scalable distributed probabilistic inference framework for future machine learning systems.
Bayesian probability theory is the fundamental framework for dealing with uncertain data, and is at the core of practical systems in machine learning and robotics
Z. Ghahramani.
Nature, Vol 521(7553), pp. 452--459. Nature Publishing Group. 2015.
A.J. Davison.
arXiv preprint arXiv:1803.11288. 2018.
There are various possible algorithms for probabilistic inference, many of which take advantage of specific problem structure for fast performance.
Efficient inference on models represented by large, dynamic and highly inter-connected graphs however remains computationally challenging and is already a limiting factor in real embodied systems.
Inference on such graphs will only become more important as general purpose perception systems strive towards more heterogeneous and dynamic representations containing abstractions (such as objects or concepts) with continually changing relationships
N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, J. Dean.
Proceedings of the International Conference on Learning Representations (ICLR). 2017.
W. Fedus, B. Zoph, N. Shazeer.
arXiv preprint arXiv:2101.03961. 2021.
D. Lacey. 2019.
As we search for the best algorithms for probabilistic inference, we should recall the "Bitter Lesson" of machine learning (ML) research: "general methods that leverage computation are ultimately the most effective, and by a large margin"
R. Sutton.
2019.
Looking to the future, we anticipate a long-term trend towards a "hardware jungle"
H. Sutter. 2011.
V. Sze, Y. Chen, T. Yang, J.S. Emer.
Proceedings of the IEEE, Vol 105(12), pp. 2295--2329. Ieee. 2017.
To scale arbitrarily and leverage all available computation in this "hardware jungle", our key hypothesis is that we need inference methods which can operate with distributed local processing / storage and message passing communication, without the need for a global view or coordination of the whole model
Fortunately, a well-known inference algorithm exists which has these properties: Loopy Belief Propagation
J. Pearl. Morgan Kaufmann. 1988.
F.R. Kschischang, B.J. Frey, H. Loeliger.
IEEE Transactions on information theory, Vol 47(2), pp. 498--519. IEEE. 2001.
K.P. Murphy, Y. Weiss, M.I. Jordan.
Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence. 1999.
J. Pearl. Morgan Kaufmann. 1988.
F. Dellaert, M. Kaess.
Foundations and Trends in Robotics, Vol 6(1-2), pp. 1--139. Now Publishers, Inc. 2017.
F. Dellaert.
Annual Review of Control, Robotics, and Autonomous Systems, Vol 4. Annual Reviews. 2021.
BP guarantees exact marginal computation with one sequence of forward-backward message passing in tree-structured graphs
C.M. Bishop.
Springer-Verlag New York, Inc. 2006.
K.P. Murphy, Y. Weiss, M.I. Jordan.
Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence. 1999.
F. Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, G. Monfardini.
IEEE transactions on neural networks, Vol 20(1), pp. 61--80. IEEE. 2008.
M.M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, P. Vandergheynst.
IEEE Signal Processing Magazine, Vol 34(4), pp. 18--42. IEEE. 2017.
P.W. Battaglia, J.B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, others.
arXiv preprint arXiv:1806.01261. 2018.
R.J. McEliece, D.J.C. MacKay, J. Cheng.
IEEE Journal on selected areas in communications, Vol 16(2), pp. 140--152. IEEE. 1998.
One issue that has precluded the use of general Loopy BP is that it lacks convergence guarantees. However, a second and perhaps more relevant issue given modern hardware trends, is that its computational properties have not fitted the dominant processing paradigms of recent decades, CPUs and GPUs. Consequently, other factor graph inference algorithms have been preferred which take advantage of global problem structure to operate much more rapidly and robustly than loopy BP on a CPU.
We believe that now is the right time to re-evaluate the properties of loopy BP given the rise of graph-like computing hardware and sparse models.
Indeed there has been a recent resurgence in interest in the algorithm
D. George, W. Lehrach, K. Kansky, M. Lazaro-Gredilla, C. Laan, B. Marthi, X. Lou, Z. Meng, Y. Liu, H. Wang, others.
Science, Vol 358(6368). American Association for the Advancement of Science. 2017.
V.G. Satorras, M. Welling.
International Conference on Artificial Intelligence and Statistics, pp. 685--693. 2021.
J. Kuck, S. Chakraborty, H. Tang, R. Luo, J. Song, A. Sabharwal, S. Ermon.
Neural Information Processing Systems (NeurIPS). 2020.
J. Ortiz, M. Pupilli, S. Leutenegger, A. Davison.
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2020.
A. Opipari, C. Chen, S. Wang, J. Pavlasek, K. Desingh, O.C. Jenkins.
arXiv preprint arXiv:2101.05948. 2021.
J. Ortiz, M. Pupilli, S. Leutenegger, A. Davison.
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2020.
A.J. Davison, J. Ortiz.
arXiv preprint arXiv:arXiv:1910.14139. 2019.
J. Du, S. Ma, Y. Wu, S. Kar, J.M. Moura.
arXiv preprint arXiv:1801.06430. 2018.
D. Bickson. 2008.
In this article, we give an introduction to Gaussian Belief Propagation as a strong general purpose algorithmic and representational framework for large scale distributed inference. Throughout, we present a range of examples across 1D and 2D geometric estimation and image processing in the form of interactive simulations which allow the reader to experiment with and understand the properties of GBP. We hope that these simulations emphasize the key properties of GBP which we summarize below.
In the remainder of the article, we first introduce the GBP algorithm and show that it is intimately linked to solving a linear system of equations
Inference is the problem of estimating statistical properties of unknown variables