Learnability in “Learning from Fuzzy Labels”

Learning from fuzzy labels (LFL) refers to a generalization of supervised learning in which supervision is represented as a (epistemic) fuzzy set over the collection of possible classification labels: this represents the uncertainty of the annotating agent with respect to the true class label to be assigned to the data instances, using a possibility distribution. The two most popular LFL algorithmic approaches are either based on generalized risk minimization (GRM) or nearest-neighbor (NN) methods: while both methods have been applied successfully with promising empirical results, theoretical characterizations of these approaches, in the framework of learning theory, have been lacking. In this article we address this gap and study the LFL problem from the perspective of statistical learning theory, providing a theoretical analysis of both GRM and NN, in terms of sample complexity and risk bounds.