An O(n log n) Cutting Plane Algorithm for Structured Output Ranking

Abstract : In this work, we consider ranking as a training strategy for structured output prediction. Recent work has begun to explore structured output prediction in the ranking setting, but has mostly focused on the special case of bipartite preference graphs. The bipartite special case is computationally efficient as there exists a linear time cutting plane training strategy for hinge loss bounded regularized risk, but it is unclear how to feasibly extend the approach to complete preference graphs. We develop here a highly parallelizable O(n log n) algorithm for cutting plane training with complete preference graphs that is scalable to millions of samples on a single core. We explore theoretically and empirically the relationship between slack rescaling and margin rescaling variants of the hinge loss bound to structured losses, showing that the slack rescaling variant has better stability properties and empirical performance with no additional computational cost per cutting plane iteration. We further show generalization bounds based on uniform convergence. Finally, we demonstrate the effectiveness of the proposed family of approaches on the problem of object detection in computer vision.
Type de document :
Communication dans un congrès
German Conference on Pattern Recognition, Sep 2014, Münster, Germany. Springer, 2014, 〈10.1007/978-3-319-11752-2_11〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01020943
Contributeur : Matthew Blaschko <>
Soumis le : mardi 15 juillet 2014 - 16:54:44
Dernière modification le : vendredi 6 avril 2018 - 13:32:01
Document(s) archivé(s) le : vendredi 16 octobre 2015 - 14:47:16

Fichier

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

Identifiants

Collections

Citation

Matthew Blaschko, Arpit Mittal, Esa Rahtu. An O(n log n) Cutting Plane Algorithm for Structured Output Ranking. German Conference on Pattern Recognition, Sep 2014, Münster, Germany. Springer, 2014, 〈10.1007/978-3-319-11752-2_11〉. 〈hal-01020943〉

Partager

Métriques

Consultations de la notice

450

Téléchargements de fichiers

509