  \textit{Complementary label learning} (CLL) requires annotators to give
\emph{irrelevant} labels instead of relevant labels for instances. Currently,
CLL has shown its promising performance on multi-class data by estimating a
transition matrix. However, current multi-class CLL techniques cannot work well
on multi-labeled data since they assume each instance is associated with one
label while each multi-labeled instance is relevant to multiple labels. Here,
we show theoretically how the estimated transition matrix in multi-class CLL
could be distorted in multi-labeled cases as they ignore co-existing relevant
labels. Moreover, theoretical findings reveal that calculating a transition
matrix from label correlations in \textit{multi-labeled CLL} (ML-CLL) needs
multi-labeled data, while this is unavailable for ML-CLL. To solve this issue,
we propose a two-step method to estimate the transition matrix from candidate
labels. Specifically, we first estimate an initial transition matrix by
decomposing the multi-label problem into a series of binary classification
problems, then the initial transition matrix is corrected by label correlations
to enforce the addition of relationships among labels. We further show that the
proposal is classifier-consistent, and additionally introduce an MSE-based
regularizer to alleviate the tendency of BCE loss overfitting to noises.
Experimental results have demonstrated the effectiveness of the proposed
method.
