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
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
Combinatorial optimization. Polyhedra and efficiency.
Schrijver, A. (2003) · UvA-DARE (University of Amsterdam) · Cited by 3,045
Lauritzen, S. L. (1996) · doi:10.1093/oso/9780198522195.001.0001 · Cited by 2,976
Biggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
Convex Analysis and Minimization Algorithms I
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02796-7 · Cited by 2,378
Probabilistic Networks and Expert Systems
(1999) · Information Science and Statistics · doi:10.1007/b97670 · Cited by 1,727
Understanding belief propagation and its generalizations
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2003) · Cited by 1,288
Convergent 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
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
Deza, M. M., & Laurent, M. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-04295-9 · Cited by 1,014
Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
Odentrantz, J. (2000) · Technometrics · doi:10.1080/00401706.2000.10485734 · Cited by 973
Turbo decoding as an instance of Pearl's "belief propagation" algorithm
McEliece, R. J., MacKay, D. J. C., & Cheng, J.-F. (1998) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.661103 · Cited by 904
Codes and Decoding on General Graphs
Wiberg, N. (1996) · Cited by 869
Matroids and the greedy algorithm
Edmonds, J. (1971) · Mathematical Programming · doi:10.1007/bf01584082 · Cited by 866
The generalized distributive law
Aji, S. M., & McEliece, R. J. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825794 · Cited by 735
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
Weiss, Y., & Freeman, W. T. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910585 · Cited by 581
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-citationInformation and Exponential Families: In Statistical Theory
Barndorff-Nielsen, O. E. (2014) · Wiley series in probability and statistics · doi:10.1002/9781118857281 · Cited by 434
Information geometry on hierarchy of probability distributions
Amari, S.-I. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.930911 · Cited by 401
A New Class of Upper Bounds on the Log Partition Function
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850091 · Cited by 381
Self-citationRoof duality, complementation and persistency in quadratic 0–1 optimization
Hammer, P. L., Hansen, P., & Simeone, B. (1984) · Mathematical Programming · doi:10.1007/bf02612354 · Cited by 316
Applications of a general propagation algorithm for probabilistic expert systems
Dawid, A. P. (1992) · Statistics and Computing · doi:10.1007/bf01890546 · Cited by 239
Tree-based reparameterization framework for analysis of sum-product and related algorithms
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.810642 · Cited by 232
Self-citationMarkov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
Odencrantz, J. R., Bremaud, P., & Bremaud, P. (2000) · Technometrics · doi:10.2307/1270970 · Cited by 219
宮沢, 政. (2000) · オペレーションズ・リサーチ : 経営の科学 · Cited by 183
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations
Wainwright, M. J., Jaakkola, T., & Willsky, A. S. (2004) · Statistics and Computing · doi:10.1023/b:stco.0000021412.33763.d5 · Cited by 125
Self-citationOn the optimality of tree-reweighted max-product message-passingPreprint
Kolmogorov, V., & Wainwright, M. J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1395 · Cited by 98
Self-citationSignal-space characterization of iterative decoding
Frey, B. J., Koetter, R., & Vardy, A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910587 · Cited by 83
Wiegerinck, W., & Heskes, T. (2002) · Cited by 69
Upper-bounds for quadratic 0–1 maximization
Boros, E., Crama, Y., & Hammer, P. L. (1990) · Operations Research Letters · doi:10.1016/0167-6377(90)90044-6 · Cited by 56
Minka, T. (2004) · Cited by 49
Multitarget-multisensor data association using the tree-reweighted max-product algorithm
Chen, L., Wainwright, M. J., Çetin, M., & Willsky, A. S. (2003) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.496939 · Cited by 42
Self-citation
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-citation
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.