Similarity Learning for High-Dimensional Sparse Data

Abstract : A good measure of similarity between data points is crucial to many tasks in machine learning. Similarity and metric learning methods learn such measures automatically from data, but they do not scale well respect to the dimensionality of the data. In this paper, we propose a method that can learn efficiently similarity measure from high-dimensional sparse data. The core idea is to parameterize the similarity measure as a convex combination of rank-one matrices with specific sparsity structures. The parameters are then optimized with an approximate Frank-Wolfe procedure to maximally satisfy relative similarity constraints on the training data. Our algorithm greedily incorporates one pair of features at a time into the similarity measure, providing an efficient way to control the number of active features and thus reduce overfitting. It enjoys very appealing convergence guarantees and its time and memory complexity depends on the spar-sity of the data instead of the dimension of the feature space. Our experiments on real-world high-dimensional datasets demonstrate its potential for classification, dimensionality reduction and data exploration.
Type de document :
Communication dans un congrès
International Conference on Artificial Intelligence and Statistics (AISTATS 2015), May 2015, San Diego, United States. 〈http://www.aistats.org/aistats2015/〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01430854
Contributeur : Aurélien Bellet <>
Soumis le : mardi 10 janvier 2017 - 12:47:57
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : mardi 11 avril 2017 - 14:34:47

Fichier

aistats15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01430854, version 1

Citation

Kuan Liu, Aurélien Bellet, Fei Sha. Similarity Learning for High-Dimensional Sparse Data. International Conference on Artificial Intelligence and Statistics (AISTATS 2015), May 2015, San Diego, United States. 〈http://www.aistats.org/aistats2015/〉. 〈hal-01430854〉

Partager

Métriques

Consultations de la notice

90

Téléchargements de fichiers

33