Complementary Label Learning with Positive Label Guessing and Negative Label Enhancement

Authors: Yuhang Li, Zhuying Li, Yuheng Jia
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Complementary label learning, negative label enhancement, weakly supervised learning

Abstract:
Complementary label learning (CLL) is a weakly supervised learning paradigm that constructs a multi-class classifier only with complementary labels, specifying classes that the instance does not belong to. We reformulate CLL as an inverse problem that infers the full label information from the output space information. To be specific, we propose to split the inverse problem into two subtasks: positive label guessing (PLG) and negative label enhancement (NLE), collectively called PLNL. Specifically, we use well-designed criteria for evaluating the confidence of the model output, accordingly divide the training instances into three categories: highly-confident, moderately-confident and under-confident. For highly-confident instances, we perform PLG to assign them pseudo labels for supervised training. For moderately-confident and under-confident instances, we perform NLE by enhancing their complementary label set at different levels and train them with the augmented complementary labels iteratively. In addition, we unify PLG and NLE into a consistent framework, in which we can view all the pseudo-labeling-based methods from the perspective of negative label recovery. We prove that the error rates of both PLG and NLE are upper bounded, and based on that we can construct a classifier consistent with that learned by clean full labels. Extensive experiments demonstrate the superiority of PLNL over the state-of-the-art CLL methods, e.g., on STL-10, we increase the classification accuracy from 34.96\% to 55.25\%. The source code is available at https://github.com/yhli-ml/PLNL.

Decision: accept (poster)
Reviewer scores: 6, 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730097508280

thread_type:
official_review

<thread_object>
creator: reviewer_zfpu

<content>
summary:
This paper proposes to decompose the CLL problem into multi-class classification problems. The one is to infer the positive label by a positive label guessing method, and another is to infer the negative labels by enhancing the negative labels of the moderately-confident and under-confident instances. Besides, this paper provides the upper bounds for the error rate of positive label guessing method and negative label enhancement method, and the effectiveness of the proposal is demonstrated by several experiments.

strengths:
This paper proposes a new method for CLL, which divides the CLL into two subtasks: PLG and NLE to deal with the high-confident and low-confident instances separately. The authors also verify the effectiveness of the proposal by several experiments and theorems.

weaknesses:
1. This paper attempts to learn a multi-label classifier from CL. However, the difference between CL and partial labels is not clarified. Initially, Ishida proposed complementary label learning, and noted that complementary label y can be regarded as an extreme case of partial labels given to all K −1 classes other than class y. However, in lines 48 and 121 of this paper, the authors claim that CL can be multiple classes that the instance does not belong to, which seems to fundamentally eliminate the difference between partial label and CL.
2. This paper does not well-motivate the proposed method, so that its advantages over existing methods are not clear. It is also not clear what conditions make the proposed method work or fail. Besides, given the strong relevance of this paper and partial label learning, it is not yet clear what advantages the algorithms in this paper have over existing partial label learning algorithms, either motivationally or experimentally.
3. Theorem 2 and Theorem 3 do not give valuable information. For example, the theorem presented in Equation (21) seems to say one thing that a probability value does not exceed 1. Furthermore, the author's discussion of Theorems 2 and 3 is very shallow; they just tell readers that there is an upper bound on the error rate, which is meaningless because any error rate has an upper bound of 1.

questions:
1. What is the difference between partial label learning and the problem addressed in this paper?
2. What are the advantages of the proposed algorithm over other existing algorithms (including CLL and partial label learning)?
3. What are the conditions for the proposed algorithm?
4. What do Theorem 2 and Theorem 3 reveal?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730347692151

thread_type:
official_review

<thread_object>
creator: reviewer_k5te

<content>
summary:
This paper solved the complementary label learning problem by dividing the training instances into three categories: highly-confident, moderately-confident and under-confident. Then, it performed positive label guessing (PLG) and negative label enhancement (NLE) according to the categories of the instances. In addition, it unified PLG and NLE into a consistent framework. It also studied the bounds of the error rates of both PLG and NLE.

strengths:
1. The study of generalization error bound is useful for algorithm evaluation.
2. The improvement in empirical study is significant.

weaknesses:
1. There is no performance reported under biased complementary label learning settings.
2. There is no performance reported under manually annotated datasets, such as CLCIFAR10，CLCIFAR20. In addition, the results on these manually annotated data indicates the performance under instance-depedent CLL.
3. The semi-supervised learning methods used in this paper is not the SoTA ones.
4. There is no deviation reported in Table 3 and Table 4. It is suggested to add standard deviations or confidence intervals for the results, which would help readers better assess the statistical significance and reliability of the reported performance.
5. The study of the separation of moderately-confident and under-confident is not reported in the ablation. It will be helpful for evaluate the idea by comparing the performance when treating these two categories the same versus separately.

questions:
1. Please consider the point 1 and 2 in the weaknesses.
2. How to evaluate the contribution of the separation of moderately-confident and under-confident instances?
3. Assumption 1 should be reconsidered and carefully checked. It assume that the variety of negative labels is large enough in the KNN instances. However, I think this assumption is too strict.
4. Is there any difference between the supervised and complementary learning losses for the high-confident instances? Maybe there are different from the loss gradient perspective.
5. The negative label set size in eq.(15) is fixed at $\tau_i$. However, when the top-$\tau_i$ and the complementary label is largely overlapped in the multiple complementary label setting, the benefit from the complementary label sharing mechanism is largely weakened.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730605775423

thread_type:
official_review

<thread_object>
creator: reviewer_gske

<content>
summary:
The paper introduces PLNL, a new method for complementary label learning that leverages positive label guessing and negative label enhancement based on a confidence-based instances selection module. Through a unified framework and theoretical analysis, it demonstrates the effectiveness of PLNL, achieving state-of-the-art results in CLL.

strengths:
1. This paper is written clear and easy to understand.

2. This paper proposes a new method PLNL for CLL by PLG and NLE.

3. Extensive experiments demonstrate the effectiveness of PLNL over the SOTA CLL methods.

weaknesses:
The contribution of this paper is incremental and using a commonly used confidence based instance selection strategy. Moreover,  only one SOTA method (published in 2023 or 2024) is used and it is too weak to validate the effectiveness of the proposed method.

questions:
1. In the ablation study, it appears that the weak-strong data augmentation strategy is more effective than the proposed confidence-based instance selection strategy.

2. The settings outlined in Table 1 are lacking experimental results for the CIFAR100 dataset.

3.  The number of SOTA methods employed in the experiments is insufficient: only one SOTA method (published in 2023 or 2024) is used, which is inadequate and too weak to validate the effectiveness of the proposed method.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730621618131

thread_type:
official_review

<thread_object>
creator: reviewer_k6zb

<content>
summary:
This paper proposes a new Complementary Label Learning (CLL) method called PLNL (Positive Label Guessing and Negative Label Enhancement), which solves the CLL problem by decomposing the inverse problem into two subtasks, positive label guessing (PLG) and negative label enhancement (NLE). Specifically, PLNL classifies training instances into three categories based on the confidence evaluation of the model output: high confidence, medium confidence, and low confidence, and performs PLG and NNE on them respectively. This paper also proposes a unified framework that considers PLG and NLE as the process of negative label recovery, and theoretically proves that the error rates of PLG and NLE have upper bounds, thus enabling the construction of a model consistent with classifiers learned using clean and complete labels.

strengths:
1.This paper provides a novel solution for the CLL field by transforming the CLL problem into an inverse problem that outputs spatial information and decomposing it into two subtasks, PLG and NLE.
2.This paper also provides a theoretical upper bound proof of error rate, enhancing the credibility and effectiveness of the method.

weaknesses:
1. The performance of PLNL may be sensitive to parameter selection, such as k-NN parameter k and confidence threshold λ, which requires users to make detailed parameter adjustments when using it.
2.Although PLNL has performed well in experiments, its generalization ability on different datasets and tasks of different complexities still needs further validation.
3.The k-NN computation involved in PLNL may have high computational costs on large-scale datasets, which may limit its application in resource-constrained environments.

questions:
Please see the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719451732

thread_type:
official_review

<thread_object>
creator: reviewer_ocgg

<content>
summary:
In this paper, the authors address the complementary label learning problem by performing positive label guessing (PLG) and negative label enhancement (NLE). The authors prove the generalization error bound and the error rates bounds. Extensive experiments demonstrate the superiority of the proposed method.

strengths:
1.	The authors provide theoretical generalization error bound for their proposed method.
2.	The results of the experiments verify the effectiveness of the method.
3.	This paper is well-organized and easy to understand.

weaknesses:
1.	According to Eq.(21), the upper bound of the PLG error rate ranges from 0 to 1, which is too broad and meaningless. And it is not easy to estimate the interval of the error bound in Eq.(22). It would be more meaningful if the authors could show that the upper bounds for these error rates are small numbers close to zero.
2.	Most datasets used in Tables 1 and 2 are relatively easy, it would be better if data set such as 20 Newsgroups is included for comparison.
3.	Some of the experimental results need further explanation, please refer to the questions below.

questions:
1.	In Figure 2(b), the PLG precision decreases as the training progresses, while the NLE precision remains relatively stable, please explain this.
2.	Why do you report the method POCR in Table 4?
3.	Please give the detailed derivation of Eq.(30), especially the first inequality.
4.	There are some typos, e.g., in Eq.(32), “B” is missing, in line 134, “show” should be “shown”, in line 169, ”p” should be “f”, in line 216, “are” should be “is”, and in Figures 2(b) and 2(c), “Precison” should be “Precision”.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732371782748

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

Greetings!

We sincerely thank all reviewers for their efforts and valuable feedback, which have been instrumental in improving the quality of our manuscript. We are delighted that the reviewers have recognized the key contributions of our work, including:

- **Theoretical Contributions:** The introduction of theoretical generalization error bounds and error rate bounds (noted by **all reviewers**) to enhance the soundness and solidness of our method.
- **Methodology:** The novel approach of decomposing the complementary label learning (CLL) problem into positive label guessing (PLG) and negative label enhancement (NLE), effectively addressing the challenges in CLL (highlighted by Reviewers **K6ZB, Gske, and zFpU**).
- **Empirical Results:** The robustness and effectiveness of our method, supported by extensive experiments that demonstrate superior performance compared to state-of-the-art methods (appreciated by **all reviewers**).
- **Presentation and Clarity:** The paper’s clear organization and accessibility, making the methodology and results easy to follow (acknowledged by Reviewers **ocgG, Gske, and zFpU**).

Our manuscript has been updated, and we will tackle the concerns of each reviewer point-by-point.

Thank you once again for your thoughtful and valuable feedback. We are looking forward to further constructive discussions with you!

Best regards,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new complementary label learning method called PLNL, which use positive label guessing and negative label enhancement. It is based on the confidence of the model output, and divide the training into 3 groups and design a way to use each group effectively with techniques such as pseudo labels. The paper also shows theoretical analysis by showing the error rates of both PLG and NLE are upper bounded. Experimental results show the superiority of the proposed method over previous complementary label learning methods.

Reviewers noted that the method is meaningful, and the theoretical contributions provide valuable insights. Reviewers acknowledged that experimental results demonstrate the performance gains of the proposed method, and felt the clarity and presentation of the paper is good. On the other hand, reviewers expressed concerns about bound tightness or assumptions/conditions used, small number and difficulty of dataset, lack of problem setups, lack of comparison with recent methods, lack of investigation of parameter sensitivity and computational costs.

Based on these concerns, the authors have provided a very informative rebuttal and follow-up discussions with new results with more datasets (CLCIFAR10, CLCIFAR20, Tiny ImageNet), more setups (biased complementary labels), more SOTA methods (from 2023,2024), parameter sensitivity investigation (k, lambda), computational cost investigation, more insights and discussions regarding the tightness of bounds and key assumptions/conditions used in the paper, and clarifications about the difference between some similar papers or partial-label learning setup.

Perhaps one remaining unaddressed point is experiments with text datasets due to the difficulty of using data augmentation for text. This may be acceptable if a paper can still contribute to areas where data augmentation is easier.

The reviewer scores are 6,5,5,5,5, where all reviewers feel the paper is borderline. Based on the above, we feel many of the initial concerns were addressed, and we recommend acceptance.