Multi-Label Learning with Pairwise Relevance Ordering
Authors: Ming-Kun Xie
Sheng-Jun Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-label learning
pairwise relevance ordering
unbiased estimator
consistency

Abstract: Precisely annotating objects with multiple labels is costly and has become a critical bottleneck in real-world multi-label classification tasks. Instead, deciding the relative order of label pairs is obviously less laborious than collecting exact labels. However, the supervised information of pairwise relevance ordering is less informative than exact labels. It is thus an important challenge to effectively learn with such weak supervision. In this paper, we formalize this problem as a novel learning framework, called multi-label learning with pairwise relevance ordering (PRO). We show that the unbiased estimator of classification risk can be derived with a cost-sensitive loss only from PRO examples. Theoretically, we provide the estimation error bound for the proposed estimator and further prove that it is consistent with respective to the commonly used ranking loss. Empirical studies on multiple datasets and metrics validate the effectiveness of the proposed method.

Multi-Label Learning with Pairwise Relevance Ordering
Ming-Kun Xie and Sheng-Jun Huang"
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, 21 106 {mkxie, juangaj>@nuaa H@nuaa edu. cn
Abstract
Precisely annotating objects with multiple labels is costly and has become crit- ical bottleneck in real-world multi-label classification tasks. Instead, deciding the relative order of label pairs is obviously less laborious than collecting exact labels. However, the supervised information of pairwise relevance ordering is less informative than exact labels. It is thus an important challenge to effectively learn with such weak supervision. learning framework, called multi-label learning with pairwise relevance ordering (PRO). We show that the unbiased estimator of classification risk can be derived with cost-sensitive loss only from PRO examples. Theoretically. the estimation error bound for the proposed estimator and further prove that it is consistent with respect to the commonly used ranking loss. Empirical studies multiple datasets and metrics validate the effectiveness of the proposed method.
this paper, we formalize this problem as a novel
provide
Introduction
Multi-label learning (MLL) solves problems where each object is assigned with multiple class labels simultaneously [Zhang and Zhou| 2013]. For example, an image may be annotated with labels building, street and person. The goal of multi-labe learning predict all the relevant labels for unseen instances. A large number of recent works have witnessed the great successes that MIL. has achieved in many woal-world applications, e.g., image annotation (Chen et al. 2019], human attribute recognition [Li et al. 2016), user profiling [Liu et al.) 202T]. and
train classification model that can
protein function prediction [Elisseeff and Weston 2002]
Traditional multi-label learning studies assume that each instance has been precisely annotated with all of its relevant labels. However, in many real-world scenarios, it is difficult and costly collect the precise annotations. Instead, each instance may be provided with the relative order of label pairs, where each label pair y > y' (or y y²) indicates that label y is more relevant (or irrelevant) than label y to instance x, i.e., p(y = 1|x> > p(y' = 1 1|x) (or p(y = 1|x) < p(y' = 1 1[x)). Generally, deciding the relative order of label pairs would be much easier than collecting the precise annotations and thus less costly. For example, in medical image analysis, only experts with rich experiences accurately identify the disease for patient based the medical image. In contrast, if the question to decide which two given diseases is more likely suffered by the patient, then even medical students with basic knowledge may easily provide the answer. While the annotation cost is significantly reduced with pairwise relevance ordering, the learning task becomes more challenging, since the supervised information of pairwise relevance ordering is much less than exact labels.
We formalize this learning problem as a new framework called multi-label learning with pairwise relevance ordering (PRO). Specifically, PRO attempts to leam a classification model from multi-label
"Correspondence to: Sheng- Jun Huang (huangsj @ nuaa.cdu.en).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

examples with the relative order of label pairs, where each label pair y > y indicates three possible
cases: 1) both y and y are relevant to z, i... y 1, y 1: 1: y is relevant to æ while y/ not, i... y = y, = 0; 3) both y and y' are irrelevant to æ, i.e., y = 0, y 0.
PRO is novel learning framework with significant difference from exiting settings. For example, semi-supervised multi-label learning (SSMLL) learns a classifier by exploiting few of labeled examples as well as large number of unlabeled examples [Liu et al. 2006]; multi-label learning with missing labels (MLML) assumes that only a subset of labels are avai available for each instance (Sun et al. 2010 Yu et al. 2014]; f partial multi-label learning (PML) assigns each instance with a candidate label set Xie and Huang 2018 Zhang and Fang 2020]; multi- learning with noisy labels assumes that multiple class labels may be flipped simultaneously with their respective probabilities [Xie and Huang 2021a]. However, these frameworks do not consider multi-label examples with pairwise relevance ordering, and cannot be employed to solve PRO problems.
To deal with multi-label data with pairwise relevance ordering, we propose a cost-sensitive loss function for learning a multi-label classifier with empirical risk minimization. Theoretically, we show that the unbiased estimator of classification risk can be derived from only PRO examples if the surrogate loss function satisfies a mild condition, i.e., the symmetric condition. The estimation error bound is established for the unbiased estimator, showing that learning with PRO examples can be multi-label consistent to the commonly used ranking loss. Extensive experimental results on multiple datasets and evaluation metrics demonstrate the practical usefulness of the proposed method.
Related Works
There are plenty of literature on multi-label learning. As one of the earliest representative methods, Binary Relevance simply decomposes the multi-label learning task into set of binary classification problems [Zhang and Zhou 2013]. Nevertheless, such method neglects the label correlations, which are regarded as an essential information for multi-label classification. Therefore, there are many studies trying to learn a multi-label classifier by exploiting the label correlations (Read et al. 2011]. Some of these works focus on the pairwise correlation (Elisseeff and Weston 2002 Li et al. 2017 while some others consider the high order correlation among all labels [Chen ct al. 2019).
To solve SSMLL problems, some works attempt to learn a multi-label classifier based on the graph models [Kong et al. 2011] while some others utilize the low-rank assumption (Jing et al. 2015]. In addition to these methods, the co-training strategy (Zhan and Zhang 2017 and matrix factorization
(Liu et al. 2006) are also employed to solve SSMLL problems.
The pioneering MLML study (Sun et al. 2010 tries to construct similarity graph for each label and the manifold regularization term added recover the missing labels. A linear classifier with the low-rank constraint is proposed to deal with large scale data with missing labels (Yu et al. 2014). In (Kanehira and Harada 2016). authors solve the MLML problem by viewing it as a positive-unlabeles learning task. Some other techniques also employ the robust loss [u et al. 2019 or the group lasso regularizer [Bucak et al.] [011] to solve MLML problems.
In order to deal with partial-labeled data, the most commonly used strategy is disambiguation [Cour et al. [0 which recovers ground-truth labeling information for candidate labels. Some methods perform the disambiguation strategy by estimating a confidence for each candidate label [Xie and
Huang 2018 Yu et al. 2018 2020). Other methods utilize the decomposition scheme [Sun et al.
2019] or adversarial training Yan and Guo 2021]. In [Xie and Huang 2021b), authors first solve PML problems by considering the generation process of noisy labels. A recent work utilizes the meta disambiguation strategy to deal with partial-laheled data (Xie et al., (202T]. Although it allows noisy labels hidden the candidate set (e.g., PML) or some labels are missed (e.g. l.g.. SSMLL and MLML), the aforementioned frameworks consider the supervised information of the label-level, i.c., each of labels is relevant or not, which can be still costly. Instead our proposed PRO framework considers pairwise relevance ordering, which can be much easier for annotators and thus less costly. In [Huang et al, 2013), authors propose multi-label active learning framework called AURO which queries the relevance ordering between two labels in every iteration. However, different from the proposed PRO framework, AURO directly asks annotators to provide each label pair with one of three possible cases that have been discussed in Section [] which can be regarded as a stronger supervised information with higher cost. AURO cannot used to solve the PRO problem. Furthermore, authors consider the pairwise supervision of instances and performing binary classification based on similar paired data
2

---

and unlabeled examples [Bao et al. 2018 Shimada et al., 2021 Bao et al. 2020]. Another recent
work trains the binary classifeer under the supervision of pairwise confidence comparisons (Feng et al. 2021J. These methods focus on binary classification and cannot be directly applied to solve the PRO problem.
3 Preliminaries
In this section, before deriving our main results for solving the PRO problem, we introduce some notations and provide the necessary preliminaries.
In traditional multi-label learning task, æ E be feature vector and y S y its corresponding labels, where A' Rd is the feature space and y = {0, 13 is the target space with g possible class
labels. Here, Yj indicates the j-th label is relevant to the instance; yj 0, otherwise. Let D = {x; yi } be the given training examples, where each example is drawn i..d according to the joint distribution p(a, y).
In multi-label learning, many loss functions have been proposed to measure the performance of learning algorithms, such ranking loss, hamming loss, coverage and average precision (Zhang and Zhou 2013). Among them, the ranking loss concerns about label pairs that are ordered reversely for an instance, which naturally considers the pairwise label correlation. Given the decision function f X + Rd, the ranking loss can be defined as follows:
L(f(x),))
Σ 1sicksq
fyy 1, yv 0)((fr, [1y 0, yv = 1)e(fs. fu),
(1)
where
(fj.fa) I (ff ((,=)) (1:
(2)
Here, ʃj is the j-th component of f(x) and I(.) is the indicator function, which outputs if the condition holds while outputs 0 otherwise. The goal of multi-label learning tasks is learn the optimal classifier by minimizing the following expected classification risk:
R(f) Bp(
(T. (T(f(x))
Σ ( ( [T(f(=))
(3)
Σ p(U)
Σ
E pall 1.m 0) [([kk f,) po 0.0. (ff
DEY
1Sicksy
Σ 1gjck$q
10m "ik ") (2)(()) [e(f f3)] + ग
5kc pol (w) [e(J,,fa)]
01
where 5 p(y, = 1, yı 0) (or JR p(y, = yk 1)) denotes the positive-negative (or
negative-positive) label pair prior probability, and (Z) p(aly,
1. y/ 0) (or (x) p(zly, = 0, 5/ 1)) denotes the class-conditional probability density of data given the positive- negative (negative-positiv label pair. Accordingly, we define the minimal risk (also called the Bayes risk) as / i R(f).
However, the loss function L is highly discontinuous and computationally NP-hard, which often makes the corresponding optimization problem hard to solve [Gao and Zhou 2013). In practice, feasible solution is to consider alternatively a surrogate loss function L which can be solved efficiently, Accordingly, the C-risk with respect to (x, y) can defined as:
Re( = Eptæ v) [(f(())
= Σ
10 ( (o(s, fa)) [+)]+ " E
(m)
01
[Ø(f [5)] (4)
15ick5q
where á is surrogate loss function. A common choice is hinge loss d(t) = max(0, 1 t) in Elisseeff and Weston 2002 Accordingly, we define the minimal C-risk (also called the Bayes C-risk) as R inf, Rc(F).
Learning with PRO
In this section, we first formulate the problem of multi-label learning with pairwise relevance ordering (PRO). Then, the unbiased estimator proposed for solving the PRO problem. Due the page limit, most proofs for theorems in Section 4 and Section 5 are provided in the supplementary material.

---

4.1 The PRO Framework
In the PRO framework, each example associated with the relevance ordering of label pairs y = {u, > 1رز where yj > y/ represents the label Vj is more relevant than label z/. i... p(y; 1|x) > p(u/- = 1/x). Note that here v/ represents one out of q - labels (except for label
yÿ) and we can further use y/ to denote y for notational simplicity. As discussed in Section
y1 > yı indicates three possible cases:1) both yj and ys are relevant to z, i.e., Vj 1. yv
2) Mj is relevant to æ while yt is not, i.e., y/j 1, M/ 0; 3) both yjj and ya are irrelevant to az i.e. Y/j 0, yk = The observation tells us that yj = 1, y/s
(or yj 0, y/- = 1) occurs and only if yj ys (or yj < yı)) i.e., the prior probability p(y; 1, = 0lu; < yv) 0 (or ply, = O, y/s = 1/3 > ykk) = 0). We can further utilize the prior to calibrate the ordinary risk E3
Therefore, by taking the prior into consideration, the classification risk Eq(3) can be calibrated as:
R(f)
Σ Isockso
B (/(Ks [[] T B 56 (0( [x)]:
where 1 = ply; = 1, y/ 0ly > y&) (or 1 = p(u, = O, yn 1/1, x yx)) denotes the calibrated negativ- (or vegative-positive) label pair prior probability, and j
10 = p(æ =
1, y/h 0. y ykk (or T p( و = 0, V/x 1, U/j < ykk) denotes the calibrated class-conditional probability density of data given the positive-negative (negative-positive) label pair. Accordingly, the C-risk 4 can be calibrated as:
Re(f) = Σ 15jck$g
THE 100 - fk]] + + go co) - ff)1-
(6)
Our goal is to train multi-label classifier only based on the observed examples D fax; Ve B
drawn i.i.d from the distribution p(z. Øj.. The expected C-risk with respect to p(x, ÿ) can be formulated as follows:
Ea 2) (ft.)/((((( (()()))))
Σ 15icksy
#10 (f - fi)] + -
Rogh (m) [o[S= - [z)]
where 7 p(U; > wk) (or jk = p(y; - yR)) denotes the positive (or negative) ordering label pair prior probability of PRO examples, and P p(z > yk) (or pit p(zly, < yk)) denotes the class-conditional probability density of PRO examples given the positive (negative) ordering label pair. However, directly solving the estimator Eq. obtain the classifier usually suffers the over-fitting issue, which makes the classifier fail to obtain promising generalization performance.
4.2 The Proposed Method
In this section, we derive an unbiased risk estimator for solving the PRO problem.
Based on the aforementioned discussions, each label pair yj > V/ indicates three possible cases, which motivates to derive the following lemma.
Lemma 1. Each PRO example of D is drawn i.i.d. according probability distribution with the following coss-conniiional density:
p(œly; > y&)
11 1 (mly; 11, R/ yj > vk) TJpp(0ly5 = 1, yk 1)
11
(8)
n pfpppar (yg O, yk
0)-
Based on the lemma, we derive the following theorem, which obtains the unbiased estimator of the classification risk only from the PRO examples.
Theorem 1. The classification risk Eq. 5 can be equivalently re-written as
R(f)
Σ
B
((fx:
+ (an),
1
(#l
=To "jk
ToT "jk
15tck59
Proof. According to Eq.
we have
E Egggee fy) = 11 ( [(fa. fu)l + =H) fu)1 + 00

---

Similarly, E Byg (a) [8] [b]] (2) (( + 7 (m)) (0(3) ((m (10
Then, the expected classification risk R()) can expressed as follows:
R(S)
Σ
32 (((,,, ( + B [e{ (
isicksn
Σ Isickso
[K( (2) [((s f3)l E (an fw)] J. " f()
Tik p (f. ([f
00
(m)
E
11 ( fi)l + =oo "jk
(3ik (2)) (((3
11 00
Tikk Tike
1sicksg
where the last equality is due to the fact that {(f), fa) + E(fk: fj) = 1 by the definition
However, discussed in Section 3, it is difficult to optimize the loss function l due to its highly discontinuity. To solve the problem, the following corollary tells us that the unbiased estimator of C-risk with respect to z. y) can be established under mild condition.
Corollary 1. The C-risk Eq. (6) can be equivalently re-written as
Rz(f)= Σ E
THE (2
(o(ss f1ll
1 #3
(TREEgL (0 ffj1-
(9)
TO0
1SIckEa
if is holds, for every t, the loss function e satisfies
(11) + x(-1) 1,
(10)
where, for each label pair Vy yk.
10 π jkk p jo(s ]w]] ]] (or p (o(x is the expected C-risk with respect to p(x, y) and can be directly estimated from PRO training examples with suitable surrogate loss functions. in other weakly supervised learning frameworks (Du Plessis et al. 2014 Ishida et al. 2017].
(z)
noteworthy that the symmetric condition Eq has been widely used
With the theorem, (f) from PRO examples as follows:
train multi-label classifier by minimizing the empirical approximation of
Rg(f) Σ ((f()).))
(11)
where,
((f()))0)= =
Σ 1sickso
1 IT
Mung > vn)) (a( =oT 3j
jk
(12)
Here, it is worthy noting that contrast to previous cost-sensitive methods (Du Plessis et al. 2014 which often requires extra assumptions sophisticated techniques to obtain the cost coefficients, the 10 jk (or ( can be directly estimated from the observed PRO training data.
Theoretical Analysis
In this section, provide the estimation error bound for the proposed unbiased estimator and further prove that it is consistent with respect to ranking loss.
Let a {o1..... ) be Rademacher variables with o; independently uniform variable taking value in --1,+1), Then, the Rademacher complexity with respect function class F and loss function L can be formulated as follows:
R2 (C o F) Ex
sup Σ C(((()))))))) fEF n
(13)
Based on the definition, establish the following lemma.
5

---

Lemma 2. Let R F be the Rademacher complexity of the loss function E and function class
F over D of n training examples drawn from xr Ú), which can be defined as
1 oo.((f(m))
R. o F) F) EEpLE
sup fEF
Then,
Rn F) S 2K CK
where π = maxj,k 1. Vj, & e [q] and Co is the Lipschitz constant of ó.
Based on 2 we can establish the uniform deviation bounds of Rg((f) as follows:
Lemma 3. For the loss function & bounded by O and any ō O, with the probability at least 1 8, we have
In
max
- & 4KTCo KT FEF
2n
Based on Lemma 3] we can derive the estimation error bound as follows, which further shows that learning from PRO examples can be multi-label consistent with respect to ranking loss.
Theorem 2. For any 8 > O, with probability at least 6, we have
In 1
Rf( min Re(f) (F + 2 JEF
2n
where ff is trained by minimizing (
Furthermore, if d is differential and non-increasing function with o' (0) < 0 and ((t) + ((-1)
20) then learning from PRO data with the modified loss function E Eq. 12 is consistent w.r.t ranking loss, iee, there exists a non-negative concave function & with E(O) = 0, such that
R(f) R (((c(ff) - -R2).
Theorem 2 tells us that learning from PRO examples is consistent with respect to ranking loss. As n + oo, R& (f) R2,, then we have the consistency: R(f) = R(f*), since RR, - 0 for all parametric models with bounded norm such as deep networks trained with weight decay (Lu et al. 2018). Based on the above discussion, Sigmoid loss Φ(t) = -+to is suitable surrogate loss function
in our case, since satisfies the symmetric condition Eq. (T) and meanwhile has been proven to be
consistent with respect to ranking loss [Gao and Zhou 2013
6 Experiment
In this section, to validate the effectiveness of the proposed method, we perform the experiments on varied datasets with multiple evaluation metrics.
6.1
Experimental Settings
Datasets evaluate our method on five multi-label datasets: Multi-MNIST Finn et al. 2017). Miii-Kuuuuhii---i (Multi-KMNT) KMNIST for short), Muulii-Fashonn-Min -Onn-MNISSTI Multi-MMNNST for short), VOC2007 Everingham et al. 2010) and MSCOCO [Lin et al. 2014 J. For three Multi- MNIST-style datasets, we randomly sample 6,000 images for trainin and 4,000 images for testing. VOC2007 contains 9,963 images for 20 object categorics, which are divided into train, val and test the trainval set to train the models, and evaluate the
sets. Following [Chen al. 2019 2018
2Sce httpttttt//tgtubbbbbbbb com Baaachuua016MMMlttDiiiggg..
for Multi-MNIST.
"Similar to MuIS. we construct Multi Kuzushiji-MNi MNIST and repsectively. 'See http::/hostt... htwp:/ttttttrrrtts.oooooooooo... ox. ac.ac. ubkppascal/V0C/voc2000// VOC2007.
-NIST for two com-
monly used datasets KuNIshij-MNIIST and Fashion-MNIST,
SSee https://cocoodatasett org for MSCOCO.

---

u-PRO
B-PRO
b-OCMIN
DCCCMN
0.88
0.0
Korkagg
Rauning
0.00
8.52
8.90
224
8:00
0:31
0.54
Narbaa of Label Pains
Nanter of Lubel Pais
Nurba Paid
Natton of Pain
0.803
(aaker 1.30
Herning Zone
1200
1:22
8:500
0405
Nambba of Label Palis
Nanber Labed Paiss
Nathor of Label Paiis
of
0.51
1.25
Houning Lose
0.30
0.53
0.00
0.30
0.99
Nomber Labal Pains
of Labet Pairs
Namber Pains
of
(a) Ranking Loss +
(b) Hamming Loss $
(c) Coverage
(d) Average Precision 1
Figure I: Comparison results with varying number of label pairs on Multi-MNIST, Multi-KMNIST and Multi-FMNIST.
performance on the test set. MSCOCO contains 82,081 images as the training set and 40.504 images as the validation set. We randomly sample 20,000 images from the training set for training and 10,000 randomly sample K pairs of labels and assign their relevance ordering, where K varies among {3, 4, 5, 6, 7, 8} for Multi-MNIST--tyll datasets, {6, 8, 10, 12, 14, 16) for VOC2007 and {5, 10, 15, 20, 25, 30) for MSCOCO. In particular, in the case that two labels are both positive (or negative), we decide their pairwise relevance ordering randomly, i.e., one out of two labels is randomly sampled to be more relevant to the other one. For each dataset, we repeat experiments five times and report their averaging performances.
images from the validation set for testing. For each dataset,
Metrics We evaluate the performance of the proposed method based on multiple standard multi- label criterion: ranking loss, hamming loss, coverage and average precision. For ranking loss, hamming loss and coverage, the smaller value, the better performance; for average precision, the larger value, the better performance. The detail of these criterion can be found in [Zhang and Zhou 2013].
Methods Under the PRO framework, the proposed method that minimizes R&(f) in Eq.11 with Sigmoid loss function is denoted by Unbiased-PRO (u-PRO for short). We compare with the baseline: Biased-PRO (b-PRO for short), which attempts to minimize the empirical approximation of the biased classification risk in Eq(7) with hinge loss function. Note that PRO is new learning framework, and there is method can be directly applied to PRO problems. We employ recently proposed framework called CCMN (Xie and Huang 2021a] to transform the PRO problem into MI.L problem with class-conditional labti noise (CCMN) by regarding as the positive label while y' as the negative label for each label pair > y/. And we compare with the following methods: Biased-CCMN (b-CCMN for short), which directly learns multi-label classifier with noisy labels; Unbiased- CCMM (u-CCMN), which employs the unbiased estimator proposed in (Xie) and Huang 2 to solve the transformed CCMN problem. Note that for u-CCMN, the true noise rates (the probability of the positive (negative) label flipped into the negative (positive) one) are given in experiments.
For experiments on Multi- Malti--NNIS--ttylee datasets, we train a linear model by using Adam [Kingma and Ba 2015) optimizer with learning rate of 0.001. We added an fz-regularization term, with the regularization parameter of 0.0001. For experiments on VOC2007 and MSCOCO,
Implementation
use an Alexnet (Krizhevsky et al. 2012 and Resnet-18 (He et al. 2016 pre-trained with the
7

---

i-PRO
B-PRO
b-OCMIN
BCCMN
0.19
E.9
lonking
9.14
0.11
E.0
Number Lateel Pains
NumborofLabel Pains
Nfnberof Lande
Nombo La Pais
(a) Ranking Loss +
(b) Hamming Loss |
(c) Coverage
(d) Average Precision 1
Figure 2: Comparison results with varying number of label pairs for each instance on VOC2007.
4-PRO
b-PRO
b-CCMN
B-CCMN
Kenking Lan
8.90
R15
0.222
0025
4.00
0.r7
835
Number off Pains
Nantar Nontor ocTabel Park
Nomber Lindl
Number of Labd Parn
(a) Ranking Loss |
(b) Hamming Loss +
(c) Coverage
(d) Average Precision f
Figure 3: Comparison results with varying number of label pairs for each instance on MSCOCO.
ILSVRC2012 dataset on Pytorch platform (Paszke et al., 2019]. The Alexnet and Resnet- 18 are trained by using stochastic gradient descent (SGD) with learning rate of 0.0001. An fz-regularization term is added with the regularization parameter of 0.0001. The batch size for all datasets is set as 200. All the experiments are conducted on GeForce RTX 2080 GPUs
6.2 Performance Comparison
Figure Cilureeillluttttter the performance curve of each comparing method as the number of label pairs for each instance increases in terms of four evaluation metrics on three Multi-MNIST-style datasets. As shown in the figures, we can obtain the following observations: 1) b-PRO and b-CCMN achieve the worst performances, which indicates neither directly minimizing the empirical biased classification risk nor simply conducting binary classification transformation can solve PRO problems, since these two methods may suffer from over-fitting issues due to the biasedness of the risk estimation. 2) Compared to b-CCMN method, u-CCMN achieves promising performance in most cases. This observation demonstrates that CCMN framework is effective for tackling PRO problems in some extent. 3) Our proposed unbiased-PRO method achieves the best performance in almost all cases and significantly outperforms u-CCMN. It is worthy noting that u- u-CCMN utilizes the true noise rates which are usually unavailable practice, and thus the superiority of the proposed method would be more significant in real-world setting.
Figure and Figure 3 jilusttaat the performance curve of each comparing method as the number of label pairs for each instance increases in terms of four evaluation metrics on VOC2007 and MSCOCO, best
respectively. From the figures, it can be observed that our proposed u-PRO method achieves performance in all cases. It seem that u- u-CCMN performs unstable on VOC2007. It even obtains worse results than the baseline b-PRO terms of hamming loss and average precision. One possible reason is that u-CCMN suffers from the over-fitting issue when the complex model is used (in the experiments, Alexnet is used for VOC2007). These results convincingly validate that the proposed unbiased estimator can effectively solve PRO problems.
6.3 Ablation Study
In this section, we conduct some ablation experiments to provide empirical validations for the theoretical analysis proposed in the paper.

---

u- R0-Siggnid
P-PRO-Ramp
U- PRO-Hinge
b-PRO-Hinge
0.14
0.26
Ranking Loss
Ranking Loos
Ranking Loos
0.34
0.24
0.30
0.32
0.28
0.30
0.26
0.20
5
Number of Label Paizs
Number of Label Paizs
Number of Label Pairs
0.27
0.26
0.23
Hamming Loss
Humminng Loss
Humminng Less
0.26
0.25
0.21
0.25
0.34
0.33
0.19
0.23
Number of Label Pairs
Number of Label Pairs
Number of Label Pairs
(a) Multi-MNIST
(b) Multi-KMNIST
(c)
Multi-FMNIST
Figure 4: Comparison results with varying number of label pairs for each instance on Multi-MNIST, and Multi-FMNISS in terms of ranking loss and hamming loss.
We first examine the unbiasedness for the proposed estimator. Based the discussion in Section 4.2 we disclose that the unbiased estimator is composed of two components, i.e., the cost-sensitive estimator Eq. and the symmetric surrogate loss function which satisfies (I). Here, u-PRO-
Sigmoid and u-PRO-Ramp represent the empirical cost-sensitive estimator Eq. (1] with Sigmoid and Ramp losses, respectively, which both satisfy the symmetric condition. U-PRO-Hinge and b-PRO-Hing represent the cost-sensitive estimator Eq.qII) and biased estimator (q. with hinge loss. which does satisfy the symmetric condition.
Due to the page limit, Figure report the performance curves of these four estimators in terms of ranking loss and hamming loss Multi-MNIST, Multi-KMNIS' and Multi-FMNISS FMNIST datasets. From the figures, we can obtain following observations: 1) u-PRO-Sigmoid and u-PRO-Ramp achieve the better performances than u- u-PRO-Hinge and b- b-PRO-Hinge in almost all cases, which indicates both two components, i.e., the cost-sensitive estimator and the symmetric surrogate loss function, certainly contribute obtain the unbiased estimator for solving the PRO problem; 2) U-PRO- Hinge outperforms b-PRO-Hinge with significant superiority, which indicates that the cost-sensitive estimator plays an important role in achieving unbiased risk estimation. The observation tells that even without the symmetric surrogate loss function, we can obtain a promising result by utilizing the cost-sensitive estimator in practice. Finally, from the Figure 4 it can observe that --PO--igmoil generally achieve better performance than u-PRO-Ram Ramp in terms of ranking loss, which provides an empirical validation of Theorem [] since Sigmoid loss has been proven be consistent with respect to ranking loss while Ramp loss not [Gao and Zhou 2013
7 Conclusion
In this paper, we study the problem of multi-label classification with pairwise relevance ordering, where each instance assigned with the relative order of label pairs. To solve PRO problems, we propose an empirical estimator of classification risk based on a cost-sensitive loss. Theoretically, we shows that the proposed estimator can be in an unbiased fashion if the surrogate loss function satisfies the symmetric condition. We derive the estimation error bound for the proposed method, and further prove that learning from PRO examples with the proposed unbiased estimator consistent with respect to ranking loss. Finally, we experimentally examine the effectiveness of the proposed method on multiple datasets and evaluation metrics. the future, we will study PRO problems by considering the data generation process.

---

8 Acknowledgments
This research was supported by the National Key R&D Program of China (2020AAA0107000; Natural Science Foundation of Jiangsu Province of China (BK20211517), and NSFC (62076128. 61732006).
References
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In International Conference on Machine Learning, pages PMLR, 2018.
Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama. Similarity based classifi- cation: Connecting similarity learning to binary classification. arXiv preprint arXiv:2006.06207 2020.
Serhat Selcuk Bucak, Rong Jin, and Anil Jain. Multi-label learning with incomplete class assignments. In CVPR 2011, pages 2801-2808. IEEE, 2011.
Tranhhu Chen, Zhouxia Wang, Guanbin Li, and Liang Lin. Recurrent attentional reinforcement learning for multi- labtl image recognition. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo. Multi-label image recognition with graph convolutional networks. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 5177-5186, 2019.
Timothee Cour, Ben Sapp. and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
Marthinus C Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and
unlabeled data. Advances in neural information processing systems, 27:703-711, 2014.
André Elisseeff and Jason Weston. A kernel method for multi-labelled classification. In Advances in neural information processing systems, pages 681 381-687, 2002.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voe) challenge. International joubaat of computer vision, 88(2): 303-338, 2010.
Lei Feng, Senlin Shu, Nan Lu, Bo Han, Miao Xu, Gang NIu, Bo An, and Masashi Sugiyama. Pointwise binary classification with pairwise confidence comparisons. In International Conference on Machine Learning, pages 3252-3262. PMLR, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostie meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pages 1 1126-112 1135. PMLR, 2017.
Wei Gao and Zhi-Hua Zhou. On the consistency of multi-label learning. Artificial Intelligence, 199 (1):22-44, 2013.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Sheng-Jun Huang, Songean Chen, and Zhi-Hua Zhou. Multi-label active learning: query type matters. In Proceedings of the 24th International Conference on Artificial Intelligence, pages 946-952, 2015.
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. In Proceedings of the 3 Isst International Conference on Neural Information Processing Systems, pages 5644-5654, 2017.
10

---

Liping Jing, Liu Yang, Jian Yu, and Michael K Ng. Semi-supervised low-rank mapping learning for multi-label classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1483-1491, 2015.
Atsushi Kanehira and Tatsuya Harada. Multi-label ranking from positive and unlabeled data. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5138-5146 2016.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Xiangnan Kong, Michael Ng. and Zhi-Hua Zhou. Transductive multilabel learning via label set propagation. IEEE Transactions on Knowledge and Data Engineering, 25(3):704-719 2011.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Yining Li, Chen Huang, Chen Change Loy, and Xiaoou Tang. Human attribute recognition by deep hierarchical contexts. In European Conference on Computer Vision, pages 684-700. Springer, 2016.
Yuncheng Li, Yale Song, and Jiebo Luo. Improving pairwise ranking for multi-label image classifica- tion. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3617-3625, 2017.
Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pages 740-755. Springer, 2014.
Weiwei Liu, Haobo Wang, Xiaobo Shen, and Ivor Tsang. The emerging trends of multi-label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Yi Liu, Rong Jin, and Liu Yang. Supe-sup multi-label learning by constrained non-negative matrix factorization. In AAAI, 2006.
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In International Conference on Learning Representations, 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv: 2019.
Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for multi-label classification. Machine learning, 85(3):333, 2011.
Takuya Shimada, Han Bao, Issei Sato, and Masashi Sugiyama. Classification from pairwise similari- ties/dissimilartiies and unlabeled data via empirical risk minimization. Neural Computation, 33(5): 1264-1268, 2021.
Lijuan Sun, Songhe Feng, Tao Wang, Congyan Lang, and Yi Jin. Partial multi-label learning by low- rank and sparse decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages
2019.
Yu- Yin Sun, Yin Zhang, and Zhi-Hua Zhou. Multi-label learning with weak label. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, 2010.
Ming-Kun Kun Xie and Sheng-Jun Huang. Partial multi-label learning. In Proceedings of the Thirty- Second AAAI Conference on Artificial Intelligence (AAAI-18), pages 4302-4309 2018
Ming- Kun Xie and Sheng-Jun Huang. Cemm: A general framework for learning with class-conditional multi-label noise. arXiv preprint arXiv:2105.073338 2021a.

---

Ming-Kun Kun Xie and Sheng-Jun Huang. Partial multi-label learning with noisy label identification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021b.
Ming-Kun Xie, Feng Sun, and Sheng-Jun Huang. Partial multi-label learning with meta disambigua- tion. In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1904-199 1912, 2021.
Miao Xu, Yu-Feng Li, and Zhi-Hua Zhou. Robust multi-label learning with pro loss. IEEE Transac- fions Knowledge and Data Engineering, 32(8):1610-1224, 2019.
Yan Yan and Yuhong Guo. Adversarial partial multi-label learning with label disambiguation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10568-10576,
2021.
Guoxian Yu, Xia Chen, Carlotta Domeniconi, Jun Wang. Zhao Li, Zili Zhang, and Xindong Wu. Feature-induced partial multi-label learning. In 2018 IEEE International Conference on Data Mining (ICDM), pages 1398-1403. IEEE, 2018
Hsiang-Fu Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit Dhillon. Large-scale multi-label learning with missing labels. In International conference on machine learning, pages 593-601. PMLR, 2014.
Tingting Yu, Guoxian Yu, Jun Wang, Carlotta Domeniconi, and Xiangliang Zhang. Partial multi-label learning using label compression. In 2020 IEEE International Conference Data Mining (ICDM), pages 761-770. IEEF, 2020.
Wang Zhan and Min-Ling Zhang. Inductive semi-supervised multi- learning with co-training. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1305-1314, 2017.
Min-Ling Zhang and Jun-Peng Fang. Partial multi-label learning via credible label elicitation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering, 26(8):1819- 1837, 2013.
12


Reviews:
[{"review_id": "qrw1HqyYINg", "reviewer": "Reviewer_o4Co", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n[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. \n[2] How about the time complexity of the proposed method with a large number of labels for each sample.\n[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.\n ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hour"}, "extra_text": {}}, {"review_id": "YWHWg3ROzOf", "reviewer": "Reviewer_guHb", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n2. The related work can discuss more about learning with pairwise supervision, e.g., \n(a) H. Bao, et al. Classification from pairwise similarity and unlabeled data. In ICML, 2018. \n(b) T. Shimada, et al. Classification from pairwise similarities/dissimilarities and unlabeled data via empirical risk minimization. Neural Computation, 2021. \n(c) H. Bao, et al. Similarity-based Classification: Connecting Similarity Learning to Binary Classification. In arXiv, 2020.\n\n3. 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?\n\n4. 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?  \n\n5. 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)?\n\n6. 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.\n\n7. 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.\n\n8. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "AjnMibdglvx", "reviewer": "Reviewer_d3TV", "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. \n\nTo solve the PRO problems, an unbiased estimator of the classification risk is proposed, whose properties of unbiased, consistency and error bound are theoretically proven.\n\nExperiments are performed on benchmark datasets to show the superiority of the proposed method.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nThe 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.\n\nExtensive experimental results on multiple datasets and evaluation metrics demonstrate the practical usefulness of the proposed method.\n\nThere are some suggestions:\nThe 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.\nThere are some language mistakes. Careful proofreading is needed. Especially, the reference citation is not in the correct form.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6YRJFRNlgLS", "reviewer": "Reviewer_YaKU", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nFor 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.\n\nThe 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.\n\nExperiments are performed on 5 public datasets. Results on commonly used multi-label learning metrics show the superiority of the proposed method.\n\nI think this paper presents a novel problem with effective solution. The contribution is significant from both theoretical and empirical aspects. Overall a solid work.\n\nBelow are some questions and suggestions:\n\nIt 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.\n\nThe 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.\n\nThe consistency is proven with regard to the ranking loss. Can the results be generalized to other loss functions?\n \nThe references are not cited in the right form in the main content. It seems that authors mistakenly used \\shortcite for all citations.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no comment", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

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)