Learnability with Partial Labels and Adaptive Nearest Neighbors
This work addresses the challenge of partial label learning for machine learning practitioners, providing a general solution with theoretical and empirical validation, though it builds incrementally on prior methods.
The paper tackles the problem of learning with partial labels, where each instance has a bag of labels, by mathematically characterizing when it is feasible and introducing an adaptive nearest-neighbors algorithm called PL A-kNN. The result shows that PL A-kNN outperforms state-of-the-art methods in general scenarios, with experimental results supporting its strong performance guarantees.
Prior work on partial labels learning (PLL) has shown that learning is possible even when each instance is associated with a bag of labels, rather than a single accurate but costly label. However, the necessary conditions for learning with partial labels remain unclear, and existing PLL methods are effective only in specific scenarios. In this work, we mathematically characterize the settings in which PLL is feasible. In addition, we present PL A-$k$NN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-$k$NN can outperform state-of-the-art methods in general PLL scenarios.