Candidate-Label Learning: A Generalization of Ordinary-Label Learning and Complementary-Label Learning

A supervised learning framework has been proposed for a situation in which each training data is provided with a complementary label that represents a class to which the pattern does not belong. In the existing literature, complementary-label learning has been studied independently from ordinary-label learning, which assumes that each training data is provided with a label representing the class to which the pattern belongs. However, providing a complementary label should be treated as equivalent to providing the rest of all labels as candidates of the one true class. In this paper, we focus on the fact that the loss functions for one-versus-all and pairwise classifications corresponding to ordinary-label learning and complementary-label learning satisfy additivity and duality, and provide a framework that directly bridges the existing supervised learning frameworks. We also show that the complementary labels generated from a probabilistic model assumed in the existing literature is equivalent to the ordinary labels generated from a mixture of ground-truth probabilistic model and uniform distribution. Based on this finding, the relationship between our work and the existing work can be naturally derived. Further, we derive the classification risk and error bound for any loss functions that satisfy additivity and duality.