HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Learning to Rank and Quadratic Assignment

Thomas Mensink 1, 2, * Jakob Verbeek 1 Tiberio Caetano 3
* Corresponding author
1 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

Contributor : Thoth Team Connect in order to contact the contributor
Submitted on : Thursday, January 12, 2012 - 5:13:02 PM
Last modification on : Thursday, January 20, 2022 - 5:28:06 PM
Long-term archiving on: : Tuesday, December 13, 2016 - 10:53:39 PM


Publisher files allowed on an open archive


  • HAL Id : hal-00645623, version 4



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. ⟨hal-00645623v4⟩



Record views


Files downloads