iBet uBet web content aggregator. Adding the entire web to your favor.

Link to original content: https://doi.org/10.1145/1273496.1273538

Efficient inference with cardinality-based clique potentials | Proceedings of the 24th international conference on Machine learning

Article

Efficient inference with cardinality-based clique potentials

Authors:

Sunita SarawagiAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 329 - 336

https://doi.org/10.1145/1273496.1273538

Published: 20 June 2007 Publication History

Abstract

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.

References

[1]

Boykov, Y., & Kolmogorov, V. (September 2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) (pp. 1124--1137).

Digital Library

[2]

Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell., 23, 1222--1239.

Digital Library

[3]

Bunescu, R., & Mooney, R. J. (2004). Collective information extraction with relational markov networks. Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (pp. 439--446).

Digital Library

[4]

Chakrabarti, S., Dom, B., & Indyk, P. (1998). Enhanced hypertext categorization using hyperlinks. SIGMOD Rec., 27, 307--318.

Digital Library

[5]

Duchi, J., Tarlow, D., Elidan, G., & Koller, D. (2007). Using combinatorial optimization within max-product belief propagation. Advances in Neural Information Processing Systems (NIPS 2006).

[6]

Finkel, J. R., Grenager, T., & Manning, C. D. (2005). Incorporating non-local information into information extraction systems by gibbs sampling. ACL.

Digital Library

[7]

Jensen, D., Neville, J., & Gallagher, B. (2004). Why collective inference improves relational classification. Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[8]

Kleinberg, J., & Tardos, E. (2002). Approximation algorithms for classification problems with pairwise relationships: metric labeling and markov random fields. J. ACM, 49, 616--639.

Digital Library

[9]

Kolmogorov, V. (2004). Convergent tree-reweighted message passing for energy minimization (Technical Report MSR-TR-2004-90). Microsoft Research (MSR).

[10]

Kolmogorov, V., & Wainwright, M. J. (2005). On the optimality of tree-reweighted max-product message passing. UAI.

[11]

Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26.

Digital Library

[12]

Krishnan, V., & Manning, C. D. (2006). An effective two-stage model for exploiting non-local dependencies in named entity recognition. ACL-COLING.

Digital Library

[13]

Lu, Q., & Getoor, L. (2003). Link-based classification. Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21--24, 2003, Washington, DC, USA (pp. 496--503).

[14]

Papadimitriou, C., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity, chapter 11, 247--254. Prentice Hall, Englewood Cliffs, NJ.

Digital Library

[15]

Ravikumar, P., & Lafferty, J. (2006). Quadratic programming relaxations for metric labeling and markov random field map estimation. ICML.

Digital Library

[16]

Sutton, C., & McCallum, A. (2004). Collective segmentation and labeling of distant entities in information extraction (Technical Report TR # 04-49). University of Massachusetts. Presented at ICML Workshop on Statistical Relational Learning and Its Connections to Other Fields.

[17]

Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2006). A comparative study of energy minimization methods for markov random fields. In Ninth European Conference on Computer Vision (ECCV 2006) (pp. 16--29).

Digital Library

[18]

Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI02), Edmonton, Canada.

Digital Library

[19]

Taskar, B., Chatalbashev, V., & Koller, D. (2004). Learning associative markov networks. Twenty First International Conference on Machine Learning (ICML04), Banff, Canada..

Digital Library

Cited By

Bauer ANakajima SMüller K(2023)Polynomial-Time Constrained Message Passing for Exact MAP Inference on Discrete Models with Global DependenciesMathematics10.3390/math1112262811:12(2628)Online publication date: 8-Jun-2023
https://doi.org/10.3390/math11122628
Ruiz ARudovic OBinefa XPantic M(2018)Multi-Instance Dynamic Ordinal Random Fields for Weakly Supervised Facial Behavior AnalysisIEEE Transactions on Image Processing10.1109/TIP.2018.283018927:8(3969-3982)Online publication date: Aug-2018
https://doi.org/10.1109/TIP.2018.2830189
Hajimirsadeghi HMori G(2017)Multi-Instance Classification by Max-Margin Training of Cardinality-Based Markov NetworksIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2016.261386539:9(1839-1852)Online publication date: 3-Aug-2017
https://dl.acm.org/doi/10.1109/TPAMI.2016.2613865
Show More Cited By

Efficient inference with cardinality-based clique potentials

Recommendations

Clique-transversal sets and clique-coloring in planar graphs

Let G=(V,E) be a graph. A clique-transversal setD is a subset of vertices of G such that D meets all cliques of G, where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, ...
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcon, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition ...
The clique-perfectness and clique-coloring of outer-planar graphs
Abstract
A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
272
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bauer ANakajima SMüller K(2023)Polynomial-Time Constrained Message Passing for Exact MAP Inference on Discrete Models with Global DependenciesMathematics10.3390/math1112262811:12(2628)Online publication date: 8-Jun-2023
https://doi.org/10.3390/math11122628
Ruiz ARudovic OBinefa XPantic M(2018)Multi-Instance Dynamic Ordinal Random Fields for Weakly Supervised Facial Behavior AnalysisIEEE Transactions on Image Processing10.1109/TIP.2018.283018927:8(3969-3982)Online publication date: Aug-2018
https://doi.org/10.1109/TIP.2018.2830189
Hajimirsadeghi HMori G(2017)Multi-Instance Classification by Max-Margin Training of Cardinality-Based Markov NetworksIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2016.261386539:9(1839-1852)Online publication date: 3-Aug-2017
https://dl.acm.org/doi/10.1109/TPAMI.2016.2613865
Sun TSheldon DOConnor B(2017)A Probabilistic Approach for Learning with Label Proportions Applied to the US Presidential Election2017 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM.2017.54(445-454)Online publication date: Nov-2017
https://doi.org/10.1109/ICDM.2017.54
Ruiz ARudovic OBinefa XPantic M(2017)Multi-Instance Dynamic Ordinal Random Fields for Weakly-Supervised Pain Intensity EstimationComputer Vision – ACCV 201610.1007/978-3-319-54184-6_11(171-186)Online publication date: 10-Mar-2017
https://doi.org/10.1007/978-3-319-54184-6_11
Ahmed FTarlow DBatra D(2015)Optimizing Expected Intersection-Over-Union with Candidate-Constrained CRFsProceedings of the 2015 IEEE International Conference on Computer Vision (ICCV)10.1109/ICCV.2015.215(1850-1858)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.1109/ICCV.2015.215
Hajimirsadeghi HWang Yan Vahdat AMori G(2015)Visual recognition by counting instances: A multi-instance cardinality potential kernel2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR.2015.7298875(2596-2605)Online publication date: Jun-2015
https://doi.org/10.1109/CVPR.2015.7298875
Tarlow DSwersky KZemel RAdams RFrey B(2012)Fast exact inference for Recursive Cardinality ModelsProceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence10.5555/3020652.3020738(825-834)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.5555/3020652.3020738
Shekhovtsov AKohli PRother C(2012)Curvature Prior for MRF-Based Segmentation and Shape InpaintingPattern Recognition10.1007/978-3-642-32717-9_5(41-51)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32717-9_5
Niu FRé CDoan AShavlik J(2011)TuffyProceedings of the VLDB Endowment10.14778/1978665.19786694:6(373-384)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.14778/1978665.1978669
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents