Search Machine Learning Repository: Learnability of the Superset Label Learning Problem
Authors: Liping Liu and Thomas Dietterich
Conference: Proceedings of the 31st International Conference on Machine Learning (ICML-14)
Year: 2014
Pages: 1629-1637
Abstract: In the Superset Label Learning (SLL) problem, weak supervision is provided in the form of a {\it superset} of labels that contains the true label. If the classifier predicts a label outside of the superset, it commits a {\it superset error}. Most existing SLL algorithms learn a multiclass classifier by minimizing the superset error. However, only limited theoretical analysis has been dedicated to this approach. In this paper, we analyze Empirical Risk Minimizing learners that use the superset error as the empirical risk measure. SLL data can arise either in the form of independent instances or as multiple-instance bags. For both scenarios, we give the conditions for ERM learnability and sample complexity for the realizable case.
[pdf] [BibTeX]

authors venues years
Suggest Changes to this paper.
Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).