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
Probabilistic Reasoning in Intelligent Systems
(1988) · Elsevier eBooks · doi:10.1016/c2009-0-27609-4 · Cited by 3,321
Mangasarian, O. L. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971255 · Cited by 3,220
Lauritzen, S. L. (1996) · doi:10.1093/oso/9780198522195.001.0001 · Cited by 2,976
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-citationBiggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940
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
Approximating discrete probability distributions with dependence trees
Chow, C., & Liu, C. (1968) · IEEE Transactions on Information Theory · doi:10.1109/tit.1968.1054142 · Cited by 1,720
Constructing 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
Understanding belief propagation and its generalizations
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2003) · Cited by 1,288
van Lint, J. H., & Wilson, R. M. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511987045 · Cited by 1,185
A family of algorithms for approximate bayesian inference
Minka, T. P., & Picard, R. W. (2001) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 882
Matroids and the greedy algorithm
Edmonds, J. (1971) · Mathematical Programming · doi:10.1007/bf01584082 · Cited by 866
An Introduction to Variational Methods for Graphical Models
Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., & Saul, L. K. (1998) · Learning in Graphical Models · doi:10.1007/978-94-011-5014-9_5 · Cited by 551
Self-citationPolynomial-Time Approximation Algorithms for the Ising Model
Jerrum, M., & Sinclair, A. (1993) · SIAM Journal on Computing · doi:10.1137/0222066 · Cited by 548
Information 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
Fundamentals of Statistical Exponential Families
Brown, L. D. (1987) · Cited by 393
Differential Geometry of Curved Exponential Families-Curvatures and Information Loss
Amari, S.-I. (1982) · The Annals of Statistics · doi:10.1214/aos/1176345779 · Cited by 373
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
Self-citationTree-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-citationWainwright, M. J., Jaakkola, T., & Willsky, A. S. (2003) · Cited by 167
Self-citationGraphs, Networks and Algorithms
Jungnickel, D. (1999) · Algorithms and computation in mathematics · doi:10.1007/978-3-662-03822-2 · Cited by 136
Learning Markov networks: maximum bounded tree-width graphs
Karger, D. R., & Srebro, N. (2001) · doi:10.5555/365411.365486 · Cited by 104
Approximate Inference and Constrained OptimizationPreprint
Heskes, T., Albers, K., & Kappen, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.2480 · Cited by 87
Wiegerinck, W., & Heskes, T. (2002) · Cited by 69
Computing Upper and Lower Bounds on Likelihoods in Intractable NetworksPreprint
Jaakkola, T., & Jordan, M. I. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.3586 · Cited by 57
Self-citationBelief Propagation on Partially Ordered Sets
McEliece, R. J., & Yıldırım, M. A. (2003) · The IMA volumes in mathematics and its applications · doi:10.1007/978-0-387-21696-6_10 · Cited by 42
Variational Inference in Graphical Models: The View from the Marginal Polytope
Wainwright, M. J., & Jordan, M. I. (2003) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 34
Self-citationRecursive Algorithms for Approximating Probabilities in Graphical Models
Jaakkola, T., & Jordan, M. I. (1996) · Cited by 33
Self-citationStochastic approximation algorithms for partition function estimation of Gibbs random fields
Potamianos, G., & Goutsias, J. I. (1997) · IEEE Transactions on Information Theory · doi:10.1109/18.641558 · Cited by 32
A Tighter Bound for Graphical Models
Leisink, M. A. R., & Kappen, H. J. (2001) · Neural Computation · doi:10.1162/089976601750399344 · Cited by 22
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
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.