Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Matthew Blaschko Connect in order to contact the contributor
Submitted on : Friday, June 19, 2015 - 12:23:02 AM
Last modification on : Thursday, February 3, 2022 - 3:01:40 AM
Long-term archiving on: : Tuesday, September 15, 2015 - 7:22:17 PM


Files produced by the author(s)


  • HAL Id : hal-01165337, version 1


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⟩



Record views


Files downloads