We propose a novel algorithm for the task of supervised discriminative distance learning by nonlinearly embedding vectors into a low dimensional Euclidean space. We work in the challenging setting where supervision is with constraints on similar and dissimilar pairs while training. The proposed method is derived by an approximate kernelization of a linear Mahalanobis-like distance metric learning algorithm and can also be seen as a kernel neural network. The number of model parameters and test time evaluation complexity of the proposed method are O(dD) where D is the dimensionality of the input features and d is the dimension of the projection space - this is in contrast to the usual kernelization methods as, unlike them, the complexity does not scale linearly with the number of training examples. We propose a stochastic gradient based learning algorithm which makes the method scalable (w.r.t. the number of training examples), while being nonlinear. We train the method with up to half a million training pairs of 4096 dimensional CNN features. We give empirical comparisons with relevant baselines on seven challenging datasets for the task of low dimensional semantic category based image retrieval.
While the distance function learned as above is linear, the problem may be complex and require nonlinear distance function. A popular way of learning a nonlinear distance function is by kernelizing the metric, as inspired by the traditional kernel based methods KPCA and KLDA; invoke representer theorem like condition and write the rows of @math as linear combinations of the input vectors @math (where @math is the matrix of all vectors @math as columns). Noticing that the distance function in Eq. depends only on the dot products of the vectors, allows nonlinearizing the algorithm as follows. Mapping the vectors with a non-linear @math and then using the @math , we can proceed as follows, where, @math is the matrix of @math mapped vectors and is the t @math column of the kernel matrix. Such reasoning was used by Mignon and Jurie @cite_52 recently. While this is a successful way of nonlinearizing the algorithm, it is costly and not scalable as training requires the whole kernel matrix.
@cite_52
2048110836
This paper introduces Pairwise Constrained Component Analysis (PCCA), a new algorithm for learning distance metrics from sparse pairwise similarity dissimilarity constraints in high dimensional input space, problem for which most existing distance metric learning approaches are not adapted. PCCA learns a projection into a low-dimensional space where the distance between pairs of data points respects the desired constraints, exhibiting good generalization properties in presence of high dimensional data. The paper also shows how to efficiently kernelize the approach. PCCA is experimentally validated on two challenging vision tasks, face verification and person re-identification, for which we obtain state-of-the-art results.