Efficient inference with cardinality-based clique potentials

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: Yuri Boykov , Vladimir Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1124-1137, September 2004 [doi>10.1109/TPAMI.2004.60]
• 2: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 3: Razvan Bunescu , Raymond J. Mooney, Collective information extraction with relational Markov networks, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.438-es, July 21-26, 2004, Barcelona, Spain [doi>10.3115/1218955.1219011]
• 4: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, ACM SIGMOD Record, v.27 n.2, p.307-318, June 1998
• 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: Jenny Rose Finkel , Trond Grenager , Christopher Manning, Incorporating non-local information into information extraction systems by Gibbs sampling, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.363-370, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219885]
• 7: David Jensen , Jennifer Neville , Brian Gallagher, Why collective inference improves relational classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014125]
• 8: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 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: Vladimir Kolmogorov , Ramin Zabih, What Energy Functions Can Be Minimizedvia Graph Cuts?, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.147-159, January 2004 [doi>10.1109/TPAMI.2004.1262177]
• 12: Vijay Krishnan , Christopher D. Manning, An effective two-stage model for exploiting non-local dependencies in named entity recognition, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.1121-1128, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220316]
• 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: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 15: Pradeep Ravikumar , John Lafferty, Quadratic programming relaxations for metric labeling and Markov random field MAP estimation, Proceedings of the 23rd international conference on Machine learning, p.737-744, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143937]
• 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).
• 18: Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI02), Edmonton, Canada.
• 19: Ben Taskar , Vassil Chatalbashev , Daphne Koller, Learning associative Markov networks, Proceedings of the twenty-first international conference on Machine learning, p.102, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015444]