Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions
In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the multiclass setting with effectively finite cardinality of the output and label space. To do this, we create a new combinatorial dimension that is based off of the Natarajan Dimension and we show that a hypothesis class is learnable in our setting if and only if this Generalized Natarajan Dimension is finite. We also show how this dimension characterizes other known learning settings such as a vast amount of instantiations of learning with set-valued feedback and a modified version of list learning.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Characterization of List Learnability
A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was set…
Learning TheoryPAC learningSupervised learning through the lens of compression
This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. We first extend the investi…
Binary ClassificationPrivate List Learnability vs. Online List Learnability
This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning. In this setting, a $k$-list learner outputs a list of $k$ potential predictions for an instance…
A Characterization of Multiclass Learnability
A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since th…
Learning TheoryOpen-Ended Question AnsweringPAC learningImpossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniq…