Instance-dependent Complementary Multi-label Learning

Complementary multi-label learning (CMLL) is a prevalent weakly supervised multi-label classification paradigm where each training instance is annotated with a complementary label set containing only irrelevant labels. Existing CMLL methods commonly assume that complementary labels are selected uniformly. However, this assumption is often violated in real-world scenarios, where the selection of complementary labels naturally depends on the characteristics of individual instances. In this paper, we study instance-dependent CMLL and propose ID-CMLL, a propensity-weighted framework for explicitly modeling and mitigating instance-dependent selection bias. We first formalize the instance-dependent complementary label generation mechanism and derive a selection-weighted unbiased risk estimator. Since the instance-conditioned selection probabilities are unknown, we introduce an identifiable double-logistic model over a fixed representation to factorize the observed complementary label probability, together with a semantic orientation mechanism for reliable propensity estimation. Empirical results demonstrate that ID-CMLL achieves superior performance against state-of-the-art CMLL and partial multi-label learning (PML) baselines.