Learning with Pairwise Constraints

In many application fields, ranging from bioinformatics to computer vision, prior knowledge on pairwise relationships among a given set of objects is available. Even if the information that they describe has different semantic meanings among a variety of problems, it specifically indicates that two entities are expected to fulfill a certain property, such as, for example, belonging to the same, but unknown, class. These relationships can be formalized as a set of constraints on the learning problem, and, for this reason, they are commonly referred to as pairwise constraints in the scientific literature. Given a set of pairwise constraints that are provided by a supervisor or that are intrinsically available from problem-specific assumptions and prior knowledge, how can we efficiently tackle a learning task that involves them? This is the main point that we investigate in this dissertation, focusing on many instances of this problem. We analyze the “learning with pairwise constraints framework” in a hierarchical manner, progressively increasing the abstraction level of the constraints and of the entities that they include. In particular, we focus on: binary relationships between data points; relationships between values of a function evaluated on them; relationships between functions defined in different domains. The nature of the pairwise constraints changes among these three settings. Sometimes they are the only information supporting the learning task, whereas in some situations we have the use of additional supervision.At first, we investigate the popular scenario of similarity learning, where the back- ground information on the problem is expressed by binary relationships between data points. A set of similarity and dissimilarity links is available, and the goal is to learn a function that predicts the similarity score between two patterns. Since class labels are not provided, the learned measure is used to appropriately group data in a semi- supervised clustering setting. We propose a neural model, Similarity Neural Network (SNN), that is guaranteed to learn symmetric and non negative functions from pairwise supervisions. Moreover, it can compute the representative of a group of data coher- ently with the learned measure, allowing the user to define a hierarchical organization to speedup data access. Second, we consider pairwise constraints that involve values of a function evaluated on the data points. In particular, constraints do not come from a supervisor but from specific assumptions on the proximity of each data point. We focus on semi-supervised classification, where the information supporting the learning task is constituted by class labels of a few training points, while constraints also involve a wider set of unlabeled data. The classification function is constrained to change smoothly its value when evaluated on two nearby points, leading to an instance of the geometrical framework of manifold regularization. We investigate the Laplacian Support Vector Machine (LapSVM) algorithm, showing how we can efficiently solve the primal formulation of the regularized learning problem. The effect of the pairwise constraints becomes intangible when the decision of the classifier is stable, so that we can significantly speedup the training algorithm by a stability-based early stop that leads to approximate solutions with equivalent quality to the optimal one. Finally we consider a higher level of representation where the constraints involve functions defined on different domains. In this setting, the structure of the problem itself suggests the pairwise relationships. Following the previously described scenario, we keep focusing on semi-supervised kernel machines, and we investigate the problem of multi-view object recognition, where pictures of an input object are acquired from different view points. Given a set of single view classifiers, pairwise constraints define relationships that must hold between the corresponding views of the same object. Each classification function operates in its own domain, and an interaction is established within the training stage of the classifiers. Thanks to the pairwise constraints, the shape of each function is adjusted accordingly to the shape of the other ones, even in those space regions where class labels are not available.