The generalized distributive law

By Srinivas M. Aji, Robert J. McEliece. IEEE Transactions on Information Theory, 2000

823 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/0e8933300a20f3d799dc9f19e352967f41d8efcc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology (1999, neutral): “The belief propagation scheme described here includes as special cases Pearl’s (1988) BP algorithm in directed graphs, the generalized distributive law algorithm of Aji and McEliece (1999), and the factor graph propagation algorithm of Frey et al.”
Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm (1998, methodology): “) Finally, having noticed the similarity between the Gallager–Tanner–Wiberg algorithm and Pearl’s algorithm, Aji and McEliece [1], [2], relying heavily on the post-Pearl improvements and simplifications in the BP algorithm [29], [30], [52], [58], [59] have devised a simple algorithm for distributing”
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs (2001, methodology): “When the potentials are set in this way, it is easy to see that the joint distribution over x in the pairwise Markov graph is exactly g(x) and that the belief propagation algorithm in the Markov graph is equivalent to the GDL algorithm in [1].”
An architecture for parallel topic models (2010, background): “Likewise, the same architecture could be used to perform message passing [1] whenever the junction tree of a graphical model has star topology.”
On trust models and trust evaluation metrics for ad hoc networks (2006, methodology): “The formalism of semirings highlights that our algorithm is a member of a larger family of wellstudied algorithms, collectively described under the term Factor Graphs [5], or Generalized Distributive Law [6].”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, methodology): “The max-sum algorithm belongs to the Generalised Distributive Law (GDL) framework [21], a family of techniques frequently used in information theory for decoding error correcting codes1 [22] and to solve graphical models (e.”
Channel coding: The road to channel capacity (2006, methodology): “= + = = ❅ ❅ ❅ = ❅ ❅ ❅ ... ... Fig. 20. Normal graph of rate-1 3 RA code. Data bits are repeated three times, permuted by a pseudo-random permutationΠ, and encoded by a rate-1/1 convolutional encoder. [129]). He showed that on cycle-free graphs they perform exact ML and APP decoding, respectively. In”
Codes on graphs: normal realizations (2000, methodology): “high degree under the rubrics of “factor graphs” [27] or “the generalized distributive law” [1], and further connections have been made, e.”
Multiresolution Markov models for signal and image processing (2002, methodology): “The computation of the MAP estimate for the entire process involves somewhat different computations but with very much the same structure and spirit, something that has been emphasized in several investigations [294, 295, 7, 169].”
On the solution-space geometry of random constraint satisfaction problems (2006, positive): “In particular, in both papers it is shown that the messages exchanged by SP over the factor graph of the input formula are the messages implied by the Belief Propagation formalism [6] applied to a factor graph encoding the set of all covers.”
Adaptive computation and machine learning (1998, methodology): “But for singly connected graphs (no more than one path between any two nodes in the underlying undirected graph), propagation can be executed in time linear with n, the number of nodes, using a simple message-passing approach [416, 4].”
An introduction to factor graphs (2004, background): “In fact, it was shown in [24] (see also [4]) that even fast Fourier transform (FFT) algorithms may be viewed as instances of the sum-product algorithm.”
Kernel-Based Learning of Hierarchical Multilabel Classification Models (2006, background): “Inference algorithms solving problems of the above form have been well-studied in the literature of probabilistic models, under the names of belief propagation and generalized distributive law (Aji and McEliece, 2000; Kschischang et al., 2001; Wainwright and Jordan, 2003).”
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations (2004, methodology): “Next, we show that the approximate max-marginals computed by max-product are guaranteed to be consistent, in a suitable sense to be defined, over every tree of the graph.”
Graphical Models, Exponential Families, and Variational Inference (2008, background): “More generally, updates of this form apply to arbitrary commutative semirings on tree-structured graphs [232, 211, 62, 2].”
MAP estimation via agreement on trees: message-passing and linear programming (2005, background): “Proposition 1 suggests two different strategies for attempting to ﬁnd a tight upper bound, which are the subjects of the next two sections:”