Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions
This provides a theoretical foundation for multiclass learning with forgiving loss functions, which is incremental as it extends existing dimensions like the Natarajan Dimension.
The paper tackles the problem of characterizing the learnability of forgiving 0-1 loss functions in multiclass settings with finite labels, and shows that a hypothesis class is learnable if and only if a newly defined Generalized Natarajan Dimension is finite, linking this to set-valued feedback learning.
In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the finite label multiclass setting. 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 a connection to learning with set-valued feedback. Through our results we show that the learnability of a set learning problem is characterized by the Natarajan Dimension.