Learnability of the Superset Label Learning Problem

Liping Liu, Thomas Dietterich
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1629-1637, 2014.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-liug14, title = {Learnability of the Superset Label Learning Problem}, author = {Liu, Liping and Dietterich, Thomas}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1629--1637}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/liug14.pdf}, url = {https://proceedings.mlr.press/v32/liug14.html}, 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.} }
Endnote
%0 Conference Paper %T Learnability of the Superset Label Learning Problem %A Liping Liu %A Thomas Dietterich %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-liug14 %I PMLR %P 1629--1637 %U https://proceedings.mlr.press/v32/liug14.html %V 32 %N 2 %X 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.
RIS
TY - CPAPER TI - Learnability of the Superset Label Learning Problem AU - Liping Liu AU - Thomas Dietterich BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-liug14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1629 EP - 1637 L1 - http://proceedings.mlr.press/v32/liug14.pdf UR - https://proceedings.mlr.press/v32/liug14.html AB - 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. ER -
APA
Liu, L. & Dietterich, T.. (2014). Learnability of the Superset Label Learning Problem. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1629-1637 Available from https://proceedings.mlr.press/v32/liug14.html.

Related Material