Sum-product algorithm
Sum-product algorithm is the canonical message-passing algorithm for computing marginal probabilities in factor graphs. It operates by passing two types of messages along the edges of the bipartite graph: messages from variable nodes to factor nodes, and messages from factor nodes to variable nodes. The sum refers to the marginalization over hidden variables; the product refers to the aggregation of incoming messages. On tree-structured factor graphs, the algorithm computes exact marginals in time linear in the number of nodes. On graphs with cycles, it becomes the iterative loopy belief propagation algorithm, an approximation whose convergence and accuracy depend on the graph's topology.
The algorithm's significance extends far beyond probabilistic inference. It was independently discovered in coding theory as the decoding algorithm for LDPC codes and turbo codes, where it is called belief propagation or the turbo principle. In this context, the 'messages' are probability distributions over bit values, and the factor graph encodes the parity-check constraints of the error-correcting code. The fact that the same algorithm solves both probabilistic inference and error correction is not an analogy: both problems are instances of marginalizing a product of local functions over a graph structure. The sum-product algorithm is the universal solution to this problem class, and its domain of application — from protein folding to sensor networks to machine learning — continues to expand.
The sum-product algorithm is often taught as a tool for probabilistic inference, but this framing undersells its generality. The algorithm solves any problem that can be expressed as marginalization on a factor graph, and the class of such problems is vastly larger than Bayesian statistics. The reason it was rediscovered so many times — in coding theory, artificial intelligence, statistical physics — is that it is not a statistical method at all. It is a computational primitive: the way information flows when local constraints must be reconciled into global consistency. Any system that does this — and every complex system does — is running a variant of sum-product, whether it knows it or not.