F. DiMaio & J. Shavlik (2006).
Improving the Efficiency of Belief Propagation in Large Highly Connected Graphs. Department of Computer Sciences, University of Wisconsin, Machine Learning Research Group Working Paper 06-1.

This publication is available in PDF.

Abstract:

We describe a part-based object-recognition framework, specialized to mining complex 3D objects from detailed 3D images. Objects are modeled as a collection of parts together with a pairwise potential function. The algorithm's key component is an efficient inference algorithm, based on belief propagation, that finds the optimal layout of parts, given some input image. Belief Propagation (BP) - a message passing method for approximate inference in graphical models - is well suited to this task. However, for large objects with many parts, even BP may be intractable. We present AggBP, a message aggregation scheme for BP, in which groups of messages are approximated as a single message, producing a message update analogous to that of mean-field methods. For objects consisting of N parts, we reduce CPU time and memory requirements from O(N^2) to O(N). We apply AggBP to both real-world and synthetic tasks. First, we use our framework to recognize protein fragments in three-dimensional images. Scaling BP to this task for even average-sized proteins is infeasible without our enhancements. We then use a synthetic ''object generator'' to test our algorithm's ability to locate a wide variety of part-based objects. These experiments show that our improvements result in minimal loss of accuracy, and in some cases produce a more accurate solution than standard BP.

Return to the publications of the Univ. of Wisconsin Machine Learning Research Group.