Accumulator networks: Suitors of local probability propagation

One way to approximate inference in richly-connected graphical models is to apply the sum-product algorithm (a.k.a. probabil-ity propagation algorithm), while ignoring the fact that the graph has cycles. The sum-product algorithm can be directly applied in Gaussian networks and in graphs for coding, but for many condi-tional probability functions- including the sigmoid function- di-rect application of the sum-product algorithm is not possible. We introduce "accumulator networks " that have low local complexity (but exponential global complexity) so the sum-product algorithm can be directly applied. In an accumulator network, the probability of a child given its parents is computed by accumulating the inputs from the parents in a Markov chain or more generally a tree. After giving expressions for inference and learning in accumulator net-works, we give results on the "bars problem " and on the problem of extracting translated, overlapping faces from an image.