On the value of pairwise constraints in classification and consistency

Abstract

In this paper we consider the problem of classification in the presence of pairwise constraints, which consist of pairs of examples as well as a binary variable indicating whether they belong to the same class or not. We propose a method which can effectively utilize pairwise constraints to construct an estimator of the decision boundary, and we show that the resulting estimator is sign-insensitive consistent with respect to the optimal linear decision boundary. We also study the asymptotic variance of the estimator and extend the method to handle both labeled and pairwise examples in a natural way. Several experiments on simulated datasets and real world classification datasets are conducted. The results not only verify the theoretical properties of the proposed method but also demonstrate its practical value in applications.