The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
Abstract
Graphical models, such as Bayesian networks and Markov random fields (MRFs), represent statistical dependencies of variables by a graph. The max-product "belief propagation" algorithm is a local-message-passing algorithm on this graph that is known to converge to a unique fixed point when the graph is a tree. Furthermore, when the graph is a tree, the assignment based on the fixed point yields the most probable values of the unobserved variables given the observed ones. Good empirical performance has been obtained by running the max-product algorithm (or the equivalent min-sum algorithm) on graphs with loops, for applications including the decoding of "turbo" codes. Except for two simple graphs (cycle codes and single-loop graphs) there has been little theoretical understanding of the max-product algorithm on graphs with loops. Here we prove a result on the fixed points of max-product on a graph with arbitrary topology and with arbitrary probability distributions (discrete- or continuous-valued nodes). We show that the assignment based on a fixed point is a "neighborhood maximum" of the posterior probability: the posterior probability of the max-product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment. The region includes all assignments that differ from the max-product assignment in any subset of nodes that form no more than a single loop in the graph. In some graphs, this neighborhood is exponentially large. We illustrate the analysis with examples.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
(1988) · Cited by 16,582
Low-density parity-check codes
Gallager, R. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,602
Factor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 1×
“As we discuss in the appendix, this belief propagation scheme is equivalent to Pearl's belief propagation algorithm in directed graphs, the Generalized Distributive Law algorithm of [1] and the factor graph propagation algorithm of [12].”
MethodLow-Density Parity-Check Codes
Gallager, R. G. (1963) · The MIT Press eBooks · doi:10.7551/mitpress/4347.001.0001 · Cited by 4,401
Good error-correcting codes based on very sparse matrices
MacKay, D. J. C. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.748992 · Cited by 3,684
Lauritzen, S. L. (1996) · doi:10.1093/oso/9780198522195.001.0001 · Cited by 2,976
Introduction to Bayesian Networks
(2019) · Operational Risk Modelling in Financial Services · doi:10.1002/9781119508557.ch12 · Cited by 2,569
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
Self-citationLoopy Belief Propagation for Approximate Inference: An Empirical Study
Murphy, K. P., Weiss, Y., & Jordan, M. I. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6725 · Cited by 1,397
Self-citation
Cited by
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
Self-citationEfficient Belief Propagation for Early Vision
Felzenszwalb, P. F., & Huttenlocher, D. P. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7899-4 · Cited by 1,345
A Review of Data Fusion Techniques
Castanedo, F. (2013) · The Scientific World Journal · doi:10.1155/2013/704504 · Cited by 1,027
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70844 · Cited by 966
An Introduction to factor graphs
Loeliger, H. (2004) · IEEE Signal Processing Magazine · doi:10.1109/msp.2004.1267047 · Cited by 905
MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856938 · Cited by 654
Codes on graphs: normal realizations
Forney, G. D. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910573 · Cited by 642
Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology
Weiss, Y., & Freeman, W. T. (2001) · Neural Computation · doi:10.1162/089976601750541769 · Cited by 560
Self-citationYang, Q., Wang, L., Yang, R., Stewenius, H., & Nister, D. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.99 · Cited by 529
The Factor Graph Approach to Model-Based Signal Processing
Loeliger, H.-A., Dauwels, J., Hu, J., Korl, S., Ping, L., & Kschischang, F. R. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2007.896497 · Cited by 526
Image completion with structure propagation
Sun, J., Yuan, L., Jia, J., & Shum, H.-Y. (2005) · ACM Transactions on Graphics · doi:10.1145/1073204.1073274 · Cited by 526
Correctness of Local Probability Propagation in Graphical Models with Loops
Weiss, Y. (2000) · Neural Computation · doi:10.1162/089976600300015880 · Cited by 452
Self-citationComparison of graph cuts with belief propagation for stereo, using identical MRF parameters
Tappen, & Freeman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238444 · Cited by 451
Efficient belief propagation for early vision
Felzenszwalb, P. F., & Huttenlocher, D. P. (2004) · Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004. · doi:10.1109/cvpr.2004.1315041 · Cited by 442
A Comparative Study of Energy Minimization Methods for Markov Random Fields
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744047_2 · Cited by 386
Ghahramani, Z. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28650-9_5 · Cited by 346
Creating Large-Scale City Models from 3D-Point Clouds: A Robust Approach with Hybrid Representation
Lafarge, F., & Mallet, C. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-012-0517-8 · Cited by 332
Image and Video Matting: A Survey
Wang, J., & Cohen, M. F. (2007) · Foundations and Trends® in Computer Graphics and Vision · doi:10.1561/0600000019 · Cited by 329
Learning how to inpaint from global image statistics
Levin, Zomet, & Weiss (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238360 · Cited by 324
An iterative optimization approach for unified image segmentation and matting
Wang, J., & Cohen, M. F. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.37 · Cited by 316
Graph Cut Based Inference with Co-occurrence Statistics
Ladicky, L., Russell, C., Kohli, P., & Torr, P. H. S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15555-0_18 · Cited by 308
Multiresolution Markov models for signal and image processing
Willsky, A. S. (2002) · Proceedings of the IEEE · doi:10.1109/jproc.2002.800717 · Cited by 305
Blum, A., Hopcroft, J., & Kannan, R. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108755528 · Cited by 304
MRF Energy Minimization and Beyond via Dual Decomposition
Komodakis, N., Paragios, N., & Tziritas, G. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.108 · Cited by 277
Least Squares and Kalman Filtering on Forney Graphs
Loeliger, H.-A. (2002) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-1-4615-0895-3_7 · Cited by 52
Metadata
- Authors
- Weiss, Y., & Freeman, W. T.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2001
- Volume
- 47
- Issue
- 2
- Pages
- 736-744
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2098387242
- Cited by
- 581
- References
- 21
- FWCI
- 13.14
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.