Rethinking One-vs-the-Rest Loss for Instance-dependent Complementary Label Learning

TL;DR — We propose to leverage the one-vs-the-rest loss to deal with instance-dependent complementary label learning.

Abstract

Complementary Label Learning (CLL) is a typical weakly supervised learning protocol, where each instance is associated with one complementary label, which specifies the class that the instance does not belong to. Existing CLL methods assume that the complementary label is sampled uniformly from all non-ground-truth labels, or from a biased probability depending on the ground-truth label. However, these assumptions are normally unrealistic, for example, an annotator tends to choose a label that is largely irrelevant to the instance to avoid mistaking the ground-truth label as the complementary one. Therefore, in this paper, we introduce instance-dependent CLL (IDCLL), where non-ground-truth labels that are less relevant to the instances are more likely to be selected as the complementary ones. Accordingly, we present our generation process for instance-dependent complementary label and observe that directly applying existing CLL methods to IDCLL results in poor performance. We further empirically analyze this phenomenon and identify: Existing methods exhibit a decline in their capacity to share complementary labels under the instance-dependent setting, resulting in small logit margins, thus difficult to identify ground-truth labels. To address this problem, we introduce complementary logit margin loss (CLML) and demonstrate CLML can enhance the capacity to share complementary labels. Additionally, we propose a novel form of the complementary one-vs-the-rest loss (COVR) as the surrogate loss for CLML, and provide theoretical proof that COVR can decrease CLML to a greater extent compared to existing CLL methods. The estimation error bound of COVR is also theoretically characterized. Extensive experiments conducted on benchmark datasets demonstrate the superiority of the proposed method compared to the existing CLL methods under our instance-dependent setting.