Reduction based similarity learning for high dimensional problems

Abstract

The problems of learning a good similarity function between objects naturally arise in machine learning, pattern recognition and data mining such as clustering, community detection or metric learning as well. We focus on the special case of this problem, where similarity function is completely determined by the hidden object classes. But we assume that no information about object labels is accessible on a training stage. The main contribution of the paper is two-stage algorithm assigns to each object its class label and provides a similarity function based on this assignment. We provide risk bounds and empirical evaluation in support of our algorithm. As a consequence of our analysis we provide a new tradeoff between empirical error of a multi-class classifier and its generalization error.