Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles

In Until recently, artificial intelligence researchers have frowned upon the application of probability propagation in Bayesian belief networks 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 algorithms are actually performing probability propagation in belief networks with cycles. 1 Communicating over a noisy channel 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. Engineers attempt to correct the errors introduced by the noise in these channels through the use of channel coding which adds protection to the information source, so that some channel errors can be corrected. A popular model of a physical channel is shown in Fig. 1 . A vector of K information bits u = (Ut, ... ,UK), Uk E O, I is encoded, and a vector of N codeword bits x = (Xl! ... ,XN) is transmitted into the channel. Independent Gaussian noise with variance (12 is then added to each codeword bit, .