The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
A New Class of Upper Bounds on the Log Partition Function
Abstract
We introduce a new class of upper bounds on the log partition function of a Markov random field (MRF). This quantity plays an important role in various contexts, including approximating marginal distributions, parameter estimation, combinatorial enumeration, statistical decision theory, and large-deviations bounds. Our derivation is based on concepts from convex duality and information geometry: in particular, it exploits mixtures of distributions in the exponential domain, and the Legendre mapping between exponential and mean parameters. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe variational problem, but distinguished by the following desirable properties: i) they are convex, and have a unique global optimum; and ii) the optimum gives an upper bound on the log partition function. This optimum is defined by stationary conditions very similar to those defining fixed points of the sum-product algorithm, or more generally, any local optimum of the Bethe variational problem. As with sum-product fixed points, the elements of the optimizing argument can be used as approximations to the marginals of the original model. The analysis extends naturally to convex combinations of hypertree-structured distributions, thereby establishing links to Kikuchi approximations and variants.
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
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
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
Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
Onsager, L. (1944) · Physical Review · doi:10.1103/physrev.65.117 · Cited by 6,510
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×
“, [23], [30] can be formulated as a method for attempting to solve this Bethe variational problem.”
MethodStanley, R. P., & Rota, G.-C. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511805967 · Cited by 6,025
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
Exactly Solved Models in Statistical Mechanics
Moore, M. A. (1983) · Physics Bulletin · doi:10.1088/0031-9112/34/4/045 · Cited by 4,413
An Introduction to Variational Methods for Graphical Models
Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., & Saul, L. K. (1999) · Machine Learning · doi:10.1023/a:1007665907178 · Cited by 3,791
Self-citationBollobás, B. (1998) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0619-4 · Cited by 3,772
Cited by
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-citationInformation, 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-citationConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850085 · Cited by 1,617
Advances in Variational Inference
Zhang, C., Butepage, J., Kjellstrom, H., & Mandt, S. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2889774 · Cited by 671
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
Self-citationDiscrete temporal models of social networks
Hanneke, S., Fu, W., & Xing, E. P. (2010) · Electronic Journal of Statistics · doi:10.1214/09-ejs548 · Cited by 587
Learning Deep Generative Models
Salakhutdinov, R. (2015) · Annual Review of Statistics and Its Application · doi:10.1146/annurev-statistics-010814-020120 · Cited by 436
Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures
Hershey, J. R., Roux, J. L., & Weninger, F. (2014) · arXiv · doi:10.48550/arxiv.1409.2574 · Cited by 412
“This is because rather than optimizing an objective function at test time, we instead optimize the parameters according to a discriminative objective function at training time, such that the inference algorithm implemented by the network obtains the best result on training data.”
BackgroundMethodOn the quantitative analysis of deep belief networks
Salakhutdinov, R., & Murray, I. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390266 · Cited by 411
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
Message Passing Algorithms for Scalable Multitarget Tracking
Meyer, F., Kropfreiter, T., Williams, J. L., Lau, R., Hlawatsch, F., Braca, P., & Win, M. Z. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2789427 · Cited by 355
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
Wiebe, N., Kapoor, A., & Svore, K. M. (2016) · Quantum Information and Computation · doi:10.26421/qic16.7-8-1 · Cited by 85
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
Visual Semantic Information Pursuit: A Survey
Liu, D., Bober, M., & Kittler, J. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2019.2950025 · Cited by 39
Wiebe, N., Kapoor, A., & Svore, K. M. (2014) · arXiv · doi:10.48550/arxiv.1412.3489 · Cited by 5
Metadata
- Authors
- Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2005-07
- Volume
- 51
- Issue
- 7
- Pages
- 2313-2335
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2135094946
- Cited by
- 381
- References
- 42
- FWCI
- 23.70
- 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.