|
 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 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 multi-way cut problem, and equivalent to a type of uncapacitated quadratic assignment problem.We provide the first non-trivial 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.
CITED BY 33
|
|
|
|
|
Andrei Z. Broder , Robert Krauthgamer , Michael Mitzenmacher, Improved classification via connectivity information, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.576-585, January 09-11, 2000, San Francisco, California, United States
|
|
|
|
|
|
Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
|
|
|
Dragomir Anguelov , Daphne Koller , Hoi-Cheung Pang , Praveen Srinivasan , Sebastian Thrun, Recovering articulated object models from 3D range data, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.18-26, July 07-11, 2004, Banff, Canada
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
Mikhail Bilenko , Sugato Basu , Raymond J. Mooney, Integrating constraints and metric learning in semi-supervised clustering, Proceedings of the twenty-first international conference on Machine learning, p.11, July 04-08, 2004, Banff, Alberta, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David Kempe , Adam Meyerson , Nainesh Solanki , Ramnath Chellappa, Pricing of partially compatible products, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Publisher Site