Learnability of the Superset Label Learning Problem
Liping Liu, Thomas G. Dietterich · 2014
In the Superset Label Learning (SLL) problem, weak supervision is provided in the form of a su-perset of labels that contains the true label. If the classifier predicts a label outside of the su-perset, it commits a superset error. Most exist-ing 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 Empiri-cal Risk Minimizing learners that use the super-set error as the empirical risk measure. SLL data can arise either in the form of independent in-stances or as multiple-instance bags. For both scenarios, we give the conditions for ERM learn-ability and sample complexity for the realizable case. 1.