A Revolution: Belief Propagation in Graphs with Cycles

Until recently, artificial intelligence researchers have frowned upon the application of probability propagation in Bayesian belief net(cid:173) works that have cycles. The probability propagation algorithm is only exact in networks that are cycle-free. However, it has recently been discovered that the two best error-correcting decoding algo(cid:173) rithms are actually performing probability propagation in belief networks with cycles. Our increasingly wired world demands efficient methods for communicating bits of information over physical channels that introduce errors. Examples of real-world channels include twisted-pair telephone wires, shielded cable-TV wire, fiber-optic cable, deep-space radio, terrestrial radio, and indoor radio.