Learning to Rank and Quadratic Assignment

Thomas Mensink 1, 2, * Jakob Verbeek 1 Tiberio Caetano 3
* Auteur correspondant
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : In this paper we show that the optimization of several ranking-based performance measures, such as precision-at-k and average-precision, is intimately related to the solution of quadratic assignment problems. Both the task of test-time prediction of the best ranking and the task of constraint generation in estimators based on structured support vector machines can all be seen as special cases of quadratic assignment problems. Although such problems are in general NP-hard, we identify a polynomially-solvable subclass (for both inference and learning) that still enables the modeling of a substantial number of pairwise rank interactions. We show preliminary results on a public benchmark image annotation data set, which indicates that this model can deliver higher performance over ranking models without pairwise rank dependencies.
Type de document :
Communication dans un congrès
DISCML 2011 - NIPS Workshop on Discrete Optimization in Machine Learning, Dec 2011, Granada, Spain. 2011
Liste complète des métadonnées

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


https://hal.inria.fr/hal-00645623
Contributeur : Thoth Team <>
Soumis le : jeudi 12 janvier 2012 - 17:13:02
Dernière modification le : mercredi 11 avril 2018 - 01:57:50
Document(s) archivé(s) le : mardi 13 décembre 2016 - 22:53:39

Fichiers

MVC_DISCML2011.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00645623, version 4

Collections

Citation

Thomas Mensink, Jakob Verbeek, Tiberio Caetano. Learning to Rank and Quadratic Assignment. DISCML 2011 - NIPS Workshop on Discrete Optimization in Machine Learning, Dec 2011, Granada, Spain. 2011. 〈hal-00645623v4〉

Partager

Métriques

Consultations de la notice

698

Téléchargements de fichiers

422