C4: Exploring Multiple Solutions in Graphical Models by Cluster Sampling

This paper presents a novel Markov Chain Monte Carlo (MCMC) inference algorithm called C(4)--Clustering with Cooperative and Competitive Constraints--for computing multiple solutions from posterior probabilities defined on graphical models, including Markov random fields (MRF), conditional random fields (CRF), and hierarchical models. The graphs may have both positive and negative edges for cooperative and competitive constraints. C(4) is a probabilistic clustering algorithm in the spirit of Swendsen-Wang. By turning the positive edges on/off probabilistically, C(4) partitions the graph into a number of connected components (ccps) and each ccp is a coupled subsolution with nodes connected by positive edges. Then, by turning the negative edges on/off probabilistically, C(4) obtains composite ccps (called cccps) with competing ccps connected by negative edges. At each step, C(4) flips the labels of all nodes in a cccp so that nodes in each ccp keep the same label while different ccps are assigned different labels to observe both positive and negative constraints. Thus, the algorithm can jump between multiple competing solutions (or modes of the posterior probability) in a single or a few steps. It computes multiple distinct solutions to preserve the intrinsic ambiguities and avoids premature commitments to a single solution that may not be valid given later context. C(4) achieves a mixing rate faster than existing MCMC methods, such as various Gibbs samplers and Swendsen-Wang cuts. It is also more "dynamic" than common optimization methods such as ICM, LBP, and graph cuts. We demonstrate the C(4) algorithm in line drawing interpretation, scene labeling, and object recognition.