Hardness Results for Structured Learning and Inference with Multiple Correct Outputs

Abstract : In many domains of structured output prediction , multiple outputs can be considered correct. Several results exist showing that polynomial time computation both at training and test time is possible when a single correct output is present. In this work, we show that such guarantees do not hold when multiple outputs are correct. This is shown through three main results indicating that multiple correct outputs lead to NP-hard computation with existing convex sur-rogates for (i) learning with a supermodular loss function, (ii) learning with a submodular loss function, and (iii) test time inference with a diversity penalty term. These theoretical results highlight the importance of identifying sufficient conditions for tractable learning and inference with multiple correct outputs in practice.
Type de document :
Communication dans un congrès
Constructive Machine Learning Workshop at ICML, Jul 2015, Lille, France
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01165337
Contributeur : Matthew Blaschko <>
Soumis le : vendredi 19 juin 2015 - 00:23:02
Dernière modification le : lundi 1 octobre 2018 - 17:00:03
Document(s) archivé(s) le : mardi 15 septembre 2015 - 19:22:17

Fichier

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

Identifiants

  • HAL Id : hal-01165337, version 1

Citation

Matthew Blaschko, Jiaqian Yu. Hardness Results for Structured Learning and Inference with Multiple Correct Outputs. Constructive Machine Learning Workshop at ICML, Jul 2015, Lille, France. 〈hal-01165337〉

Partager

Métriques

Consultations de la notice

200

Téléchargements de fichiers

428