Jon Kleinberg
Éva Tardos
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.
- bartal Y. 1996. Approximations of metric spaces, and its algorithmic applications. In Proc. IEEE Symposium on Foundations of Computer Science. Google Scholar
- Bartal, Y. 1998. On approximating arbitrary metrics by tree metrics. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. Google Scholar
- Besag, J. 1974. Spatial interaction and the statistical analysis of lattice systems. J. Roy. Stat. Soc. B 36.Google Scholar
- Besag, J. 1986. On the statistical analysis of dirty pictures. J. Roy. Stat. Soc. B 48.Google Scholar
- Boykov, Y., Veksler, O., and Zabih, R. 1998. Markov random fields with efficient approximations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE computer Society Press, Los Alamtos, Calif. Google Scholar
- Boykov, Y., Veksler, O., and Zabih, R. 1999. Fast approximate energy minimization via graph cuts. In Proceedings of the International Conference on Computer Vision.Google Scholar
- Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Patt. Anal. Mach. Intel. 23, 11 (Nov.), 1222--1239. Google Scholar
- Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. 1984. Classification and Regression Trees. Wadsworth & Brooks/Cole.Google Scholar
- Calinescu, G., Karloff, H., and Rabani, Y. 1998. Improved approximation algorithms for multiway cut. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. Google Scholar
- Chakrabarti, S., Dom, B., and Indyk, P. 1998. Enhanced hypertext categorization using hyperlinks. In Proceedings of ACM SIGMOD. ACM, New York. Google Scholar
- 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.Google Scholar
- Chellappa, R., and Jain, A. 1993. Markov Random Fields: Theory and Applications. Academic Press, Orlando, Fla.Google Scholar
- Cohen, F. S. 1986. Markov random fields for image modeling and analysis. In Modeling and Application of Stochastic Processes, U. B. Desai, Ed. Kluwer. Google Scholar
- 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.Google Scholar
- Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., and Yannakakis, M. 1994. The complexity of multi-terminal cuts. SIAM J. Comput. 23. Google Scholar
- Dietterich, T. G. 1997. Machine learning research: Four current directions. AI Mag. 18.Google Scholar
- Dubes, R., and Jain, A. 1989. Random field models in image analysis. J. Appl. Stat. 16.Google Scholar
- Erdös, P. L., and Székely, L. A. 1992. Evolutionary trees: An integer multicommodity max-flow min-cut theorem. Adv. Appl. Math 13. Google Scholar
- 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.Google Scholar
- Geman, S., and Geman, D. 1984. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Patt. Anal. Mach. Intell. 6.Google Scholar
- Greig, D., Porteous, B., and Seheult, A. 1989. Exact maximum a posteriori estimation for binary images. J. Roy. Stat. Soc. B 48.Google Scholar
- Ishikawa, H., and Geiger, D. 1998. Segmentation by grouping junctions. In IEEE Conference on Computer Vision Pattern Recognition. pp. 125--131. Google Scholar
- Karger, D. R., Klein, P., Stein, C., Thorup, M., and Young, N. E. 1999. Rounding algorithms for a geometric embedding of multiway cut. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. Google Scholar
- Karzanov, A. V. 1998. Minimum 0-extension of graph metrics. Europ. J. Combinat. 19. Google Scholar
- Kinderman, R., and Snell, J. 1980. Markov Random Fields and their Applications. AMS Press.Google Scholar
- Li, S. 1995. Markov Random Field Modeling in Computer Vision. Springer-Verlag. New York. Google Scholar
- Pardalos, P., and Wolkowicz, H. 1994. Quadratic assignment and related problems. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16.Google Scholar
- Potts, R. 1952. Some generalized order-disorder transformations. Proc. Cambridge Phil. Soc. 48.Google Scholar
- Queyranne, M. 1986. Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Oper. Res. Lett. 4.Google Scholar
- Roy, S., and Cox, I. 1998. A maximum-flow formulation of the n-camera stereo correspondence problem. In Proceedings of the 6th International Conference on Computer Vision. Google Scholar
- Woods, J. W. 1972. Two-dimensional discrete Markovian fields. IEEE Trans. Inf. Theory 18.Google Scholar
Index Terms
- Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields
Recommendations
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields
FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer ScienceIn 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 ...
The Hardness of Metric Labeling
The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set $L$ of labels and a weighted graph $G=(V,E)$. Additionally, a metric distance ...
Semi-supervised genetic programming for classification
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationLearning from unlabeled data provides innumerable advantages to a wide range of applications where there is a huge amount of unlabeled data freely available. Semi-supervised learning, which builds models from a small set of labeled examples and a ...
Comments