Abstract:

The problem of dimensionality reduction given some domain knowledge on the data is considered. Here the domain knowledge denotes additional supervision information other than the data, e.g. the class labels of data or more weakly, the pairwise similarity or dissimilarity constraints. The focus is on the latter because it is more general than the former. Given class labels of data, corresponding pairwise similarity or dissimilarity constraints can be generated, but not vice versa. Also in real world application such as image retrieval, obtaining pairwise constraints is much easier than obtaining labels.A simple algorithm called constraint preserving embedding (COPE) was presented, which can effectively use the pairwise constraints for better embedding. The algorithm is formulated under a unified spectral graph embedding framework and  the relationship between it and existing related methods is indicated. Moreover,  COPE  is extended to semisupervised and kernel cases, in order to include unlabeled data and capture the nonlinear relationships between data. The performance of the  proposed algorithms is evaluated through a series of experiments including face image recognition and retrieval and semisupervised clustering. Experimental results show that the algorithms are effective and promising in learning from pairwise constraints.

Key words: pairwise constraint；domain knowledge,  semi-supervised dimensionality reduction