Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Supervised Learning with Similarity Functions

Purushottam Kar and Prateek Jain


We address the problem of general supervised learning when data can only be accessed through an (indefinite) similarity function between data points. Existing work on learning with indefinite kernels has concentrated solely on binary/multi-class classification problems. We propose a model that is generic enough to handle any supervised learning task and also subsumes the model previously proposed for classification. We give a "goodness" criterion for similarity functions w.r.t. a given supervised learning task and then adapt a well-known landmarking technique to provide efficient algorithms for supervised learning using "good" similarity functions. We demonstrate the effectiveness of our model on three important supervised learning problems: a) real-valued regression, b) ordinal regression and c) ranking where we show that our method guarantees bounded generalization error. Furthermore, for the case of real-valued regression, we give a natural goodness definition that, when used in conjunction with a recent result in sparse vector recovery, guarantees a sparse predictor with bounded generalization error. Finally, we report results of our learning algorithms on regression and ordinal regression tasks using non-PSD similarity functions and demonstrate the effectiveness of our algorithms, especially that of the sparse landmark selection algorithm that achieves significantly higher accuracies than the baseline methods while offering reduced computational costs.


Publication typeInproceedings
Published in26th Annual Conference on Neural Information Processing Systems (NIPS)
PublisherNeural Information Processing Systems Foundation

Previous versions

Purushottam Kar and Prateek Jain. Similarity-based Learning via Data driven Embeddings, 2011.

> Publications > Supervised Learning with Similarity Functions