Efficient inference with cardinality-based clique potentials

Gupta, Rahul ; Diwan, Ajit A. ; Sarawagi, Sunita (2007) Efficient inference with cardinality-based clique potentials In: 24th international conference on Machine learning.

[img] PDF

Official URL: http://doi.org/10.1145/1273496.1273538

Related URL: http://dx.doi.org/10.1145/1273496.1273538


Many collective labeling tasks require inference on graphical models where the clique potentials depend only on the number of nodes that get a particular label. We design efficient inference algorithms for various families of such potentials. Our algorithms are exact for arbitrary cardinality-based clique potentials on binary labels and for max-like and majority-like clique potentials on multiple labels. Moving towards more complex potentials, we show that inference becomes NP-hard even on cliques with homogeneous Potts potentials. We present a 13/15-approximation algorithm with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 0.5. We perform empirical comparisons on real and synthetic data, and show that our proposed methods are an order of magnitude faster than the well-known Tree-based re-parameterization (TRW) and graph-cut algorithms.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to ACM, Inc
ID Code:128390
Deposited On:20 Oct 2022 04:25
Last Modified:14 Nov 2022 11:12

Repository Staff Only: item control page