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

被引:181
作者
Kleinberg, J [1 ]
Tardos, É [1 ]
机构
[1] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA
关键词
algorithms; theory; approximation algorithms; classification; Markov random fields; metric labeling;
D O I
10.1145/585265.585268
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:616 / 639
页数:24
相关论文
共 31 条
[1]  
[Anonymous], 1994, DIMACS SERIES DISCRE
[2]  
[Anonymous], 1980, Markov Random Fields and Their Applications
[3]  
[Anonymous], 1993, MARKOV RANDOM FIELDS
[4]  
BARTAL Y, 1998, P ACM S THEOR COMP A
[5]  
BARTAL Y, 1996, P IEEE S FDN COMP SC
[6]  
Besag J., 1974, J ROY STAT SOC B, V36
[7]  
BESAG J, 1986, J ROY STAT SOC B, V48
[8]   Fast approximate energy minimization via graph cuts [J].
Boykov, Y ;
Veksler, O ;
Zabih, R .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2001, 23 (11) :1222-1239
[9]  
Boykov Y., 1998, P IEEE C COMP VIS PA
[10]  
BOYKOV Y, 1999, P INT C COMP VIS