Classification with pairwise relationships
by
Éva Tardos
Cornell University

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. We will consider the case 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. Yuri Boykov, Olga Veksler, and Ramin Zabih used a framework of this type to handle a range of problems in computer vision.

Jon Kleinberg and I formulated a general classification problem based on pairwise relationships that we termed the "metric labeling problem''; we showed 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 generalization of certain graph partitioning problems, and equivalent to a type of computationally hard assignment problem. In this talk, I'll describe our model and its origins, and present some efficient algorithms we have obtained that provide provably near-optimal solutions to the general metric labeling problem. The talk is based on joint work with Jon Kleinberg and Anupam Gupta.

Date received: March 22, 2001