Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields

ABSTRACT

In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of assignment costs---based on the individual choice of label we make for each object---and separation costs---based on the pair of choices we make for two "related" objects.We formulate a general classification problem of this type, the metric labeling problem; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem.We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O(log k log log k)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric---all distances are the same---our methods provide a 2-approximation algorithm.

REFERENCES

• 1: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 2: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 3: Besag, J. 1974. Spatial interaction and the statistical analysis of lattice systems. J. Roy. Stat. Soc. B 36.
• 4: Besag, J. 1986. On the statistical analysis of dirty pictures. J. Roy. Stat. Soc. B 48.
• 5: Y. Boykov , O. Veksler , R. Zabih, Markov Random Fields with Efficient Approximations, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.648, June 23-25, 1998
• 6: Boykov, Y., Veksler, O., and Zabih, R. 1999. Fast approximate energy minimization via graph cuts. In Proceedings of the International Conference on Computer Vision.
• 7: 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]
• 8: Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. 1984. Classification and Regression Trees. Wadsworth & Brooks/Cole.
• 9: Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for multiway cut, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.48-52, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276711]
• 10: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 11: Charikar, M., Chekuri, C., Goel, A., Guha, S., and Plotkin, S. 1998. Approximating arbitrary metrics by O(n log n) trees. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.
• 12: Chellappa, R., and Jain, A. 1993. Markov Random Fields: Theory and Applications. Academic Press, Orlando, Fla.
• 13: Fernand S Cohen, Markov random fields for image modelling and analysis, Modelling and applications of stochastic processes, Kluwer, B.V., Deventer, The Netherlands, 1986
• 14: Cunningham, W. H., and Tang, L. 1994. Optimal 3-terminal cuts and linear programming. In Proceedings of the MPS Conference on Integer Programming and Combinatorial Optimization.
• 15: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 16: Dietterich, T. G. 1997. Machine learning research: Four current directions. AI Mag. 18.
• 17: Dubes, R., and Jain, A. 1989. Random field models in image analysis. J. Appl. Stat. 16.
• 18: Péter L. Erdős , László A. Székely, Evolutionary trees: an integer multicommodity max-flow—min-cut theorem, Advances in Applied Mathematics, v.13 n.4, p.375-389, Dec. 1992 [doi>10.1016/0196-8858(92)90017-Q]
• 19: Ferrari, P., Frigessi, A., and de Sá, P. 1995. Fast approximate maximum a posteriori restoration of multi-color images. J. Roy. Stat. Soc. B 57.
• 20: Geman, S., and Geman, D. 1984. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Patt. Anal. Mach. Intell. 6.
• 21: Greig, D., Porteous, B., and Seheult, A. 1989. Exact maximum a posteriori estimation for binary images. J. Roy. Stat. Soc. B 48.
• 22: H. Ishikawa , D. Geiger, Segmentation by Grouping Junctions, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.125, June 23-25, 1998
• 23: David R. Karger , Philip Klein , Cliff Stein , Mikkel Thorup , Neal E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.668-678, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301430]
• 24: Alexander V. Karzanov, Minimum 0-extensions of graph metrics, European Journal of Combinatorics, v.19 n.1, p.71-101, Jan., 1998 [doi>10.1006/eujc.1997.0154]
• 25: Kinderman, R., and Snell, J. 1980. Markov Random Fields and their Applications. AMS Press.
• 26: S. Z. Li, Markov random field modeling in computer vision, Springer-Verlag, London, 1995
• 27: Pardalos, P., and Wolkowicz, H. 1994. Quadratic assignment and related problems. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16.
• 28: Potts, R. 1952. Some generalized order-disorder transformations. Proc. Cambridge Phil. Soc. 48.
• 29: Queyranne, M. 1986. Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Oper. Res. Lett. 4.
• 30: Sébastien Roy , Ingemar J. Cox, A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem, Proceedings of the Sixth International Conference on Computer Vision, p.492, January 04-07, 1998
• 31: Woods, J. W. 1972. Two-dimensional discrete Markovian fields. IEEE Trans. Inf. Theory 18.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, Markov random fields, classification, metric labeling