The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Abstract
We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.
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
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Viterbi, A. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1054010 · Cited by 6,759
Exactly Solved Models in Statistical Mechanics
Baxter, R. J. (1985) · Series on Advances in Statistical Mechanics · doi:10.1142/9789814415255_0002 · Cited by 5,611
Verdú, S. (1998) · Cited by 4,682
Combinatorial optimization. Polyhedra and efficiency.
Schrijver, A. (2003) · UvA-DARE (University of Amsterdam) · Cited by 4,637
Exactly Solved Models in Statistical Mechanics
Moore, M. A. (1983) · Physics Bulletin · doi:10.1088/0031-9112/34/4/045 · Cited by 4,413
On the Statistical Analysis of Dirty Pictures
Besag, J. (1986) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1986.tb01412.x · Cited by 4,191
Bollobás, B. (1998) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0619-4 · Cited by 3,772
Mangasarian, O. L. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971255 · Cited by 3,220
Cited by
Collective Classification in Network Data
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., & Eliassi‐Rad, T. (2008) · AI Magazine · doi:10.1609/aimag.v29i3.2157 · Cited by 3,293
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Self-citationMessage-passing algorithms for compressed sensing
Donoho, D. L., Maleki, A., & Montanari, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0909892106 · Cited by 2,416
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000001 · Cited by 1,820
Self-citationConvergent Tree-Reweighted Message Passing for Energy Minimization
Kolmogorov, V. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.200 · Cited by 1,095
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
Robust Higher Order Potentials for Enforcing Label Consistency
Kohli, P., Ladický, L., & Torr, P. H. S. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0202-0 · Cited by 853
Learning Conditional Random Fields for Stereo
Scharstein, D., & Pal, C. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383191 · Cited by 851
BabyTalk: Understanding and Generating Simple Image Descriptions
Kulkarni, G., Premraj, V., Ordonez, V., Dhar, S., Li, S., Choi, Y., Berg, A. C., & Berg, T. L. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.162 · Cited by 839
MSM: a new flexible framework for Multimodal Surface Matching
Robinson, E. C., Jbabdi, S., Glasser, M. F., Andersson, J., Burgess, G. C., Harms, M. P., Smith, S. M., Van Essen, D. C., & Jenkinson, M. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2014.05.069 · Cited by 640
Furukawa, Y., & Hernández, C. (2015) · Foundations and Trends in Computer Graphics and Vision · doi:10.1561/0600000052 · Cited by 598
Using Linear Programming to Decode Binary Linear Codes
Feldman, J., Wainwright, M. J., & Karger, D. R. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.842696 · Cited by 572
Self-citationBaby talk: Understanding and generating simple image descriptions
Kulkarni, G., Premraj, V., Dhar, S., Li, S., Choi, Y., Berg, A. C., & Berg, T. L. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995466 · Cited by 521
Optical flow modeling and computation: A survey
Fortun, D., Bouthemy, P., & Kervrann, C. (2015) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2015.02.008 · Cited by 431
Komodakis, N., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 419
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_44 · Cited by 388
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
Graph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587440 · Cited by 385
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
Kolmogorov, V., & Rother, C. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1031 · Cited by 362
Edge and line oriented contour detection: State of the art
Papari, G., & Petkov, N. (2011) · Image and Vision Computing · doi:10.1016/j.imavis.2010.08.009 · Cited by 357
A Linear Programming Approach to Max-Sum Problem: A Review
Werner, T. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1036 · Cited by 342
Ghamisi, P., Maggiori, E., Li, S., Souza, R., Tarablaka, Y., Moser, G., De Giorgi, A., Fang, L., Chen, Y., Chi, M., et al. (2018) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2018.2854840 · Cited by 325
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
Discriminative models for multi-class object layout
Desai, C., Ramanan, D., & Fowlkes, C. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459256 · Cited by 274
Furukawa, Y., & Hernández, C. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781601988379 · Cited by 268
MRF Optimization via Dual Decomposition: Message-Passing Revisited
Komodakis, N., Paragios, N., & Tziritas, G. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408890 · Cited by 256
A convex relaxation approach for computing minimal partitions
Pock, T., Chambolle, A., Cremers, D., & Bischof, H. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206604 · Cited by 253
A study on continuous max-flow and min-cut approaches
Yuan, J., Bae, E., & Tai, X.-C. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539903 · Cited by 237
Discriminative Models for Multi-Class Object Layout
Desai, C., Ramanan, D., & Fowlkes, C. C. (2011) · International Journal of Computer Vision · doi:10.1007/s11263-011-0439-x · Cited by 208
Utilizing Variational Optimization to Learn Markov Random Fields
Tappen, M. F. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383037 · Cited by 54
Metadata
- Authors
- Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2005-11
- Volume
- 51
- Issue
- 11
- Pages
- 3697-3717
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2108619558
- Cited by
- 654
- References
- 41
- FWCI
- 35.73
- 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.