Discriminative Complementary-Label Learning with Weighted Loss

Complementary-label learning (CLL) deals with the weak supervision scenario where each training instance is associated with one complementary label, which specifies the class label that the instance does not belong to. Given the training instance x, existing CLL approaches aim at modeling the generative relationship between the complementary label ȳ, i.e. P (ȳ | x), and the ground-truth label y, i.e. P (y | x). Nonetheless, as the ground-truth label is not directly accessible for complementarily labeled training instance, strong generative assumptions may not hold for real-world CLL tasks. In this paper, we derive a simple and theoretically-sound discriminative model towards P (ȳ | x), which naturally leads to a risk estimator with estimation error bound at O(1/ √ n) convergence rate. Accordingly, a practical CLL approach is proposed by further introducing weighted loss to the empirical risk to maximize the predictive gap between potential groundtruth label and complementary label. Extensive experiments clearly validate the effectiveness of the proposed discriminative complementary-label learning approach.