DocumentCode :
1452239
Title :
C^4: Exploring Multiple Solutions in Graphical Models by Cluster Sampling
Author :
Porway, Jake ; Zhu, Song-Chun
Author_Institution :
R&D Div., New York Times, New York, NY, USA
Volume :
33
Issue :
9
fYear :
2011
Firstpage :
1713
Lastpage :
1727
Abstract :
This paper presents a novel Markov Chain Monte Carlo (MCMC) inference algorithm called C4-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. C4 is a probabilistic clustering algorithm in the spirit of Swendsen-Wang [34]. By turning the positive edges on/off probabilistically, C4 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, C4 obtains composite ccps (called cccps) with competing ccps connected by negative edges. At each step, C4 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. C4 achieves a mixing rate faster than existing MCMC methods, such as various Gibbs samplers [15], [26] and Swendsen-Wang cuts [2], [34]. It is also more “dynamic” than common optimization methods such as ICM [3], LBP [21], [37], and graph cuts [4], [20]. We demonstrate the C4 algorithm in line drawing interpretation, scene labeling, and object recognition.
Keywords :
Markov processes; Monte Carlo methods; computer graphics; graph theory; image sampling; object recognition; pattern clustering; C4-clustering; Gibbs sampler; MCMC method; Markov Chain Monte Carlo inference algorithm; Markov random field; Swendsen-Wang cut; cluster sampling; competitive constraint; cooperative constraint; graph cut; graph partition; graphical model; line drawing interpretation; object recognition; optimization method; posterior probability; probabilistic clustering algorithm; scene labeling; Algorithm design and analysis; Graphical models; Heuristic algorithms; Labeling; Markov processes; Monte Carlo methods; Probabilistic logic; Markov random fields; Monte Carlo.; computer vision; constraint satisfaction; graph labeling; probabilistic algorithms;
fLanguage :
English
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Publisher :
ieee
ISSN :
0162-8828
Type :
jour
DOI :
10.1109/TPAMI.2011.27
Filename :
5714697
Link To Document :
بازگشت