Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a new multi-label learning framework called Pairwise Relevance Ordering (PRO). In this setting, the supervised information is given in the form of relevance orders between labels pairs. 

To solve the PRO problems, an unbiased estimator of the classification risk is proposed, whose properties of unbiased, consistency and error bound are theoretically proven.

Experiments are performed on benchmark datasets to show the superiority of the proposed method.

main_review: The paper presents a new framework of PRO for multi-label learning. Because it does not require annotators to precisely assign class labels for each instance, it is expected to be more cost-effective.

The authors propose an unbiased estimator of classification risk, which is shown to be derived with a cost-sensitive loss only from PRO examples. This allows to perform effective multi-label learning with weakly supervised information.

The authors give in-depth theoretical analysis to derive the error bound. They also prove that the estimator is consistent with the commonly used ranking loss.

Extensive experimental results on multiple datasets and evaluation metrics demonstrate the practical usefulness of the proposed method.

There are some suggestions:
The experimental settings are less clear. For example, it is not introduced how to assign relevance ordering information to label pairs given that the standard multi-label datasets are used in the experiments.
There are some language mistakes. Careful proofreading is needed. Especially, the reference citation is not in the correct form.
limitations_and_societal_impact: No potential negative social impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the multi-label classification problem in a weakly supervised setting, where each instance is assigned with the relative order of label pairs. Authors formalize this task as a new framework called pairwise relevance ordering. An empirical estimator of the classification risk based on a cost-sensitive loss is proposed. Then authors theoretically prove that the proposed estimator is unbiased with the symmetric condition of the loss function. The error bound and consistency of the estimator is also proved. In addition to the theoretical results, the paper also validate the effectiveness of the proposed method empirically on multiple datasets.
main_review: The studied problem is interesting and novel. Weakly supervised information in the form of pairwise relevance orders is less costly to obtain compared to precise labeling. The study formalizes a reasonable and practical setting to allow multi-label learning with lower annotation cost.

For this new problem, authors propose a new estimator based on the cost-sensitive loss. The estimator is proved to be an unbiased estimator given a reasonable assumption, i.e., the loss function should be symmetric.

The paper made solid theoretical analysis both on the error bound and the consistency. The results show that learning with PRO examples can be multi-label consistent to the commonly used ranking loss.

Experiments are performed on 5 public datasets. Results on commonly used multi-label learning metrics show the superiority of the proposed method.

I think this paper presents a novel problem with effective solution. The contribution is significant from both theoretical and empirical aspects. Overall a solid work.

Below are some questions and suggestions:

It is not clear to me how the relevance ordering information obtained from the multi-label datasets. I guess it is obtained from the ground-truth labels. Authors stated that they randomly select pairs to assign the relevance order. Then how to decide the order in the case the two labels are both positive or negative? Authors need to make the details clear.

The proposed method shows a large superiority on VOC and MSCOCO datasets. While on MNIST datasets, u-CCMN performs quite well. Authors are suggested to give some detailed discussion on this phenomenon.

The consistency is proven with regard to the ranking loss. Can the results be generalized to other loss functions?
 
The references are not cited in the right form in the main content. It seems that authors mistakenly used \shortcite for all citations.

limitations_and_societal_impact: no comment
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In multi-label learning, the supervised information of pairwise relevance ordering is less informative than exact labels. Hence, it is an important challenge to effectively learn with such weak supervision. In this paper, a multi-label learning with pairwise relevance ordering approach is proposed. Meanwhile, it demonstrates that the unbiased estimator of classification risk can be derived with a cost-sensitive loss only from PRO examples. The theoretical analysis also has been provided. 
main_review: In this paper, a cost-sensitive loss function for learning a multi-label classifier with empirical risk minimization is proposed. To demonstrate the effectiveness of the proposed method, the theoretical analysis is provided to show that learning with PRO examples can be multi-label consistent to the commonly used ranking loss. The experimental results on multiple datasets and evaluation metrics demonstrate the practical usefulness of the proposed method.
limitations_and_societal_impact: 
[1] The recent works are not fully explored. In the reference, the recent works are little. Meanwhile, more state-of-the-art methods should be compared. 
[2] How about the time complexity of the proposed method with a large number of labels for each sample.
[3]The hinge loss is adopted in the paper. In the proposed method, it seems to be used as a ranking loss. It may be not clearly presented.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper attempts to solve the multi-label learning problem with only pairwise relevance ordering. Authors argue that deciding the relative order of label pairs is obviously less laborious than collecting exact labels. A method is also presented to learn multi-label model with only pairwise relevance ordering and experiments shows its superiority.
main_review: 1. As stated in abstract, "deciding the relative order of label pairs is obviously less laborious than collecting exact labels", however, compared with the traditional exact labeling information where we only need to check whether each label belongs to the current instance, we need to annotate each instance many times when annotating it with relevance ordering labeling information (quadratic complexity w.r.t. the number of labels).  Therefore, it is necessary to discuss whether it is really less laborious for the proposed framework, or at least under what conditions, it will be less laborious. Author can also discuss the computational complexity (even the time costs) of the proposed method in Subsection 4.2. Besides, with exact labeling information, we can use binary relevance to learn the multi-label model, however, we can no longer learn such simple model with relevance ordering labeling information. Although binary relevance is usually criticized by not considering label correlations, it can achieve acceptable performance generally.

2. The related work can discuss more about learning with pairwise supervision, e.g., 
(a) H. Bao, et al. Classification from pairwise similarity and unlabeled data. In ICML, 2018. 
(b) T. Shimada, et al. Classification from pairwise similarities/dissimilarities and unlabeled data via empirical risk minimization. Neural Computation, 2021. 
(c) H. Bao, et al. Similarity-based Classification: Connecting Similarity Learning to Binary Classification. In arXiv, 2020.

3. As stated in the last sentence of Section 4, "the $\tilde{\pi}_{jk}^{10}$  can be directly estimated from the observed PRO training data". The estimated values might be affected by the number of label pairs annotated for each instance. Besides, why does the proposed method in Subsection 4.2 correspond to an unbiased estimator?

4. I cannot criticize that the theoretical analyses in Section 5 are useless, but authors should provide some more specific theoretical results rather than some less meaningful ones. For example, for one multi-label learning problem with a total of $q$ labels, how many label pairs are needed for the proposed method to achieve comparable performance with general multi-label classifiers (e.g., binary relevance) learned with exact labeling information? For another example, whether the proposed formulation is robust to noisy label pairs?  

5. The experimental setup is unclear. For example, as stated in Subsection 6.1, "For each dataset, we randomly sample K pairs of labels and assign their relevance ordering", here, how to assign relevance ordering for a pair of labels with the same value (both relevant or irrelevant)?

6. It is better to provide some experimental results of well-established multi-label baselines to know the performance gap between learning with relative order of label pairs and learning with traditional exact labeling information.

7. It is better to annotate a real-world data set for the proposed framework rather than only generating some data sets from existing multi-label data sets. For example, authors can re-annotate the widely-used `scene' multi-label data set which only includes 2407 pictures and 6 labels. With the re-annotated data set, researchers can compare the performance/complexity of learners which are trained with different types of labeling information.

8. This paper is not carefully prepared. For example, Zhang & Zhou (2013) and Xu et al. (2019) are published in 2014 and 2020 respectively instead of 2013 and 2019. For another example, the style of reference citation is not in correct form throughout this paper.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper presents a new framework for multi-label learning that does not require annotators to precisely assign class labels for each instance and thus is cost-effective. The theory part supports the algorithm design and the experiments show good results. The author's responses addressed the questions of the reviewers. 
Decision: Accept (Poster)