PerspectivePHYSICS/COMPUTER SCIENCE

Passing Messages Between Disciplines

See allHide authors and affiliations

Science  19 Sep 2003:
Vol. 301, Issue 5640, pp. 1685-1686
DOI: 10.1126/science.1086309

Complex behaviors can emerge in systems in which many “atoms”—such as real atoms, economic agents, logical variables, or neurons—locally exchange messages. Recent independent studies of such systems in different subject areas have shown that message passing is extremely powerful as an algorithmic framework, as well as a conceptual one. Three archetypal problems illustrate this utility: error correction in information theory, satisfiability in discrete optimization, and spin glasses in statistical physics.

Error correction is important for the transmission of information. To transmit a signal—for example, a string of 0's and 1's—through a noisy channel, one first encodes the signal by adding some redundant bits to it. These bits enable the decoding of the received string even if it has been degraded by errors during transmission.

In the 1940s, Claude Shannon predicted that, for a given degree of redundancy, there exist error-correcting codes that can correct all distortions induced by a channel below a threshold noise level. However, practical codes coming close to Shannon's prediction have only recently been found. The main difficulty was to find fast decoding procedures. A clever message-passing procedure called belief propagation (BP) [a name borrowed from computer science studies of inference problems (1)] recently allowed these problems to be overcome (2).

In low-density parity check codes (3, 4), redundancy is added through a number of parity checks (see the first figure). These checks are constraints such that, for instance, the sum of bits B1, B2, B3, and B5 is even. If the received string does not satisfy this constraint, at least one of these four bits has been corrupted. With several such checks one can identify the bits of the received string that have been corrupted during transmission. The more noisy the channel, the more checks are required.

Graphical representation of a decoding device.

The circles represent the bits transmitted through the channel. The squares are the parity check constraints; for instance, constraint C1 requires that the sum of bits B1, B2, B3, and B5 should be even. Along each edge of this graph two messages are exchanged, one in each direction. These messages give the “belief” of the sending node on the state of the bit. This same message exchange also applies to satisfiability problems and spin glasses.

This decoding process can be very slow, because an N-bit message can be garbled in 2N ways. This is where the BP algorithm comes to the rescue. It works by exchanging messages along a graph (5) in which the vertices, or nodes, are bits and parity checks. The edges of the graph connect each check to the bits that it involves (see the first figure).

In such a graph, two messages transmit along the edge that connects a check C to a bit B. C sends to B its “belief” on the state of B. This belief is a probability estimated by C based on all the messages it receives from the bits distinct from B. Similarly, B computes its probability to be in a given state if C were absent, using the beliefs it receives from other checks, and sends this information to C. These messages propagate through the network of bits and checks in an iterative procedure. In well-designed low-density parity check codes, each check involves a small number of bits, and the propagation converges rapidly to fixed belief values (2), from which corrupted bits are easily identified.

The decoding problem is just one example of constraint satisfaction with discrete variables. Another is the satisfiability problem. Consider N Boolean variables. Each of them can be assigned to true or false, but they are subject to some constraints. In satisfiability, each constraint forbids one specific assignment of some subset of the variables (for example, x1 = true, x2 = false can be forbidden). The question is whether there exists an assignment of each variable such that all constraints are satisfied.

This problem is important, because any logical statement between Boolean variables can be transformed into a set of constraints of the satisfiability type. It is generally considered unlikely that an algorithm able to solve all satisfiability instances efficiently (with a running time that grows as the power of N) exists: It would imply that many familiar hard optimization problems, like the traveling salesman problem, could be solved efficiently (6).

However, randomly generated instances of satisfiability are often easy to solve: For large N, they exhibit a threshold phenomenon at a critical value, αc, of the number of constraints per variable, α. Problems with α < αc are almost always satisfiable (SAT), whereas those with α > αc are almost always unsatisfiable (UNSAT) (7). The really difficult problems are “critically constrained,” with α close to αc (8, 9). In such cases, the BP procedure can only find solutions in an easy regime where α is smaller than αc and not too close to it.

How clusters defy satisfiability.

The clustering phenomenon is typical of the onset of a glassy phase. In satisfiability, the set of solutions is connected if there are not too many constraints per variable (left). It splits into disconnected clusters when the number of constraints per variable α crosses the clustering threshold αd. The clusters shrink further when α increases, and finally disappear at the satisfiability threshold αc. The full space, depicted here as a sphere, is an N-dimensional hypercube.

Methods from statistical physics have helped to understand the performance and limitations of BP, and have led to substantial improvements. The threshold phenomena exhibited by the above computational problems—the satisfiability threshold at αc or Shannon's threshold—are nothing but phase transitions, typical of macroscopic materials that switch abruptly from one phase to another as a result of a small change in a control parameter. This happens, for example, when ice changes to water at temperatures above 0°C. In physics, phase diagrams are typically studied using “mean field” or more accurate “Bethe” approximations in which some correlations between variables are neglected. It turns out that BP message passing is a Bethe approximation (10).

The closest physical analogs of the above computational problems are disordered magnetic materials called spin glasses. In these materials, magnetic moments (spins) interact locally through interactions that can be ferromagnetic (two interacting spins tend to be aligned) or antiferromagnetic (the two spins tend to point in opposite directions). A given spin will thus be subject to conflicting interactions. At low temperatures, these materials have a glass phase in which the spins tend to freeze in random directions.

In experiments, this freezing transition is continuous (the magnetization of a spin vanishes when one reaches the transition temperature). However, recent theoretical studies using mean field theory predict the existence of an alternative, discontinuous, glass transition scenario. The discontinuous transition is unusual in that it takes place in two stages and exhibits a “clustering” phenomenon.

Let us describe this clustering scenario in the case of satisfiability. There exist two phase transitions when one increases α (the ratio of constraints to variables). If α is small, there are few constraints and many solutions (assignments satisfying all constraints). One can go from one solution to another by changing the assignment of a few variables, and the space of solutions consists of one big connected cluster. When α increases, there are more constraints, and the number of solutions decreases. At αd, the cluster of solutions separates into smaller clusters, and the solutions in different clusters differ in the assignments of many variables. Above αc, there are too many constraints to satisfy all of them, and the clusters disappear. Thus, the threshold between SAT and UNSAT phases at αc is preceded by a clustering phase transition at α = αd < αc.

This clustering fools the BP algorithm, because the beliefs exchanged locally in the graph can convey information only about solutions in one cluster. Beliefs in distant parts of the graph typically deal with different clusters, and the algorithm cannot get this global information.

Theoretical studies of model spin glasses have solved this problem by introducing the statistics of beliefs (11). For each cluster of solutions, there exists a set of beliefs exchanged along the graph. Instead of trying to compute the beliefs associated with one cluster, one sends a more complicated message along each edge of the graph. This message contains a full survey of all beliefs that pass along this edge when the various clusters of solutions are explored.

Recently, this idea has been turned into an efficient algorithm, the survey propagation, where the messages that are exchanged are surveys of the usual beliefs (12, 13). Survey propagation can solve random satisfiability problems with up to 107 variables very near to αc in a region where BP does not converge, opening up a whole new direction in this field.

The discontinuous phase transition scenario seen in theoretical spin glasses is at work also in generic low-density parity check codes: When one increases the noise level n of the transmitting channel, a clustering effect at a noise threshold nd, smaller than the real capacity nc of the code, prevents the convergence of BP decoding (2, 14, 15). The spectacular progress in finding low-density parity check codes that approach Shannon's bound has been thanks to an optimization of the connectivities, which maximizes nd (2).

Some of the recent breakthroughs discussed above, both algorithmically and conceptually, were obtained through clever use of sophisticated message-passing procedures. Message passing is likely to play a central role in many complex systems. The methods and concepts of statistical physics—developed in studies of physical materials—now prove to be useful for various computational problems, ranging from those in information theory and computer science discussed here to some problems in economics and biology.

References

  1. 1.
  2. 2.
  3. 3.
  4. 4.
  5. 5.
  6. 6.
  7. 7.
  8. 8.
  9. 9.
  10. 10.
  11. 11.
  12. 12.
  13. 13.
  14. 14.
  15. 15.
View Abstract

Navigate This Article