2012/10/22 by Purushottam Kar, Prateek Jain, Kar, Purushottam +1 · 1 citation
Computer Science · Engineering · Mathematics · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1210.5840
To appear in the proceedings of NIPS 2012, 30 pages
arxiv created 2012/10/22 · openalex publication_date 2012/10/22 · arxiv updated 2012/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 super-vised 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.