Complementary-Label Learning for Arbitrary Losses and Models
This addresses a practical problem for machine learning practitioners who need to train classifiers when only complementary labels are available, representing a novel methodological advancement rather than an incremental improvement.
The paper tackles the problem of complementary-label learning, where training patterns only specify classes they don't belong to rather than their true class, by developing a framework with an unbiased risk estimator that works for arbitrary losses and models. This enables model/hyper-parameter selection without ordinary labeled validation data and shows improved performance through experiments.
In contrast to the standard classification paradigm where the true class is given to each training pattern, complementary-label learning only uses training patterns each equipped with a complementary label, which only specifies one of the classes that the pattern does not belong to. The goal of this paper is to derive a novel framework of complementary-label learning with an unbiased estimator of the classification risk, for arbitrary losses and models---all existing methods have failed to achieve this goal. Not only is this beneficial for the learning stage, it also makes model/hyper-parameter selection (through cross-validation) possible without the need of any ordinarily labeled validation data, while using any linear/non-linear models or convex/non-convex loss functions. We further improve the risk estimator by a non-negative correction and gradient ascent trick, and demonstrate its superiority through experiments.