The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Tree-based reparameterization framework for analysis of sum-product and related algorithms
Abstract
We present a tree-based reparameterization (TRP) framework that provides a new conceptual view of a large class of algorithms for computing approximate marginals in graphs with cycles. This class includes the belief propagation (BP) or sum-product algorithm as well as variations and extensions of BP. Algorithms in this class can be formulated as a sequence of reparameterization updates, each of which entails refactorizing a portion of the distribution corresponding to an acyclic subgraph (i.e., a tree, or more generally, a hypertree). The ultimate goal is to obtain an alternative but equivalent factorization using functions that represent (exact or approximate) marginal distributions on cliques of the graph. Our framework highlights an important property of the sum-product algorithm and the larger class of reparameterization algorithms: the original distribution on the graph with cycles is not changed. The perspective of tree-based updates gives rise to a simple and intuitive characterization of the fixed points in terms of tree consistency. We develop interpretations of these results in terms of information geometry. The invariance of the distribution, in conjunction with the fixed-point characterization, enables us to derive an exact expression for the difference between the true marginals on an arbitrary graph with cycles, and the approximations provided by belief propagation. More broadly, our analysis applies to any algorithm that minimizes the Bethe free energy. We also develop bounds on the approximation error, which illuminate the conditions that govern their accuracy. Finally, we show how the reparameterization perspective extends naturally to generalizations of BP (e.g., Kikuchi (1951) approximations and variants) via the notion of hypertree reparameterization.
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
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
$I$-Divergence Geometry of Probability Distributions and Minimization Problems
Csiszar, I. (1975) · The Annals of Probability · doi:10.1214/aop/1176996454 · Cited by 1,645
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-citationGraphical 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
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
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
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-citationAn Introduction to Conditional Random Fields
Sutton, C., & McCallum, A. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000013 · Cited by 564
Nonparametric belief propagation for self-localization of sensor networks
Ihler, A. T., Fisher, J. W., Moses, R. L., & Willsky, A. S. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.843548 · Cited by 537
Self-citationCorrectness of Local Probability Propagation in Graphical Models with Loops
Weiss, Y. (2000) · Neural Computation · doi:10.1162/089976600300015880 · Cited by 452
Nonparametric belief propagation
Sudderth, E. B., Ihler, A. T., Freeman, W. T., & Willsky, A. S. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211409 · Cited by 413
Self-citationPhylogenetic Estimation of Context-Dependent Substitution Rates by Maximum Likelihood
Siepel, A. (2003) · Molecular Biology and Evolution · doi:10.1093/molbev/msh039 · Cited by 383
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-citationA 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
Stereo Correspondence by Dynamic Programming on a Tree
Veksler, O. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.334 · Cited by 295
Loopy Belief Propagation: Convergence and Effects of Message Errors
Ihler, A., Fischer, J. W., & Willsky, A. S. (2005) · doi:10.5555/1046920.1088703 · Cited by 286
Self-citation
Metadata
- Authors
- Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2003-05
- Volume
- 49
- Issue
- 5
- Pages
- 1120-1146
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2160988325
- Cited by
- 232
- References
- 3
- FWCI
- 14.84
- 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.