Multi-Label Learning with Pairwise Relevance Ordering
Year: 2021

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 respect to the commonly used ranking loss. Empirical studies on multiple datasets and metrics validate the effectiveness of the proposed method.

heading: 1 Introduction
text: 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-label learning is to train a classification model that can predict all the relevant labels for unseen instances. A large number of recent works have witnessed the great successes that MLL has achieved in many real-world applications, e.g., image annotation [Chen et al., 2019], human attribute recognition [Li et al., 2016], user profiling [Liu et al., 2021], and 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 to 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|x) (or p(y = 1|x) < p(y′ = 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 can accurately identify the disease for a patient based on the medical image. In contrast, if the question is to decide which of 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 learn a classification model from multi-label
∗Correspondence to: Sheng-Jun Huang (huangsj@nuaa.edu.cn).
35th Conference on Neural Information Processing Systems (NeurIPS 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 x, i.e., y = 1, y′ = 1; 2) y is relevant to x while y′ is not, i.e., y = 1, y′ = 0; 3) both y and y′ are irrelevant to x, i.e., y = 0, y′ = 0.
PRO is a novel learning framework with significant difference from exiting settings. For example, semi-supervised multi-label learning (SSMLL) learns a classifier by exploiting a few of labeled examples as well as a large number of unlabeled examples [Liu et al., 2006]; multi-label learning with missing labels (MLML) assumes that only a subset of labels are available for each instance [Sun et al., 2010, Yu et al., 2014]; partial multi-label learning (PML) assigns each instance with a candidate label set [Xie and Huang, 2018, Zhang and Fang, 2020]; multi-label 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.

heading: 2 Related Works
text: 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 a 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 et 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 a similarity graph for each label and the manifold regularization term is added to 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-unlabeled learning task. Some other techniques also employ the robust loss [Xu et al., 2019] or the group lasso regularizer [Bucak et al., 2011] to solve MLML problems.
In order to deal with partial-labeled data, the most commonly used strategy is disambiguation [Cour et al., 2011], 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-labeled data [Xie et al., 2021]. Although it allows noisy labels hidden in the candidate set (e.g., PML) or some labels are missed (e.g., SSMLL and MLML), the aforementioned frameworks consider the supervised information of the label-level, i.e., 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., 2015], authors propose a 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 1, which can be regarded as a stronger supervised information with higher cost. AURO cannot be used to solve the PRO problem. Furthermore, authors consider the pairwise supervision of instances and performing binary classification based on similar paired data
and unlabeled examples [Bao et al., 2018, Shimada et al., 2021, Bao et al., 2020]. Another recent work trains the binary classifier under the supervision of pairwise confidence comparisons [Feng et al., 2021]. These methods focus on binary classification and cannot be directly applied to solve the PRO problem.

heading: 3 Preliminaries
text: 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, let x ∈ X be a feature vector and y ⊆ Y its corresponding labels, where X = Rd is the feature space and Y = {0, 1}q is the target space with q possible class labels. Here, yj = 1 indicates the j-th label is relevant to the instance; yj = 0, otherwise. Let D = {xi,yi}ni=1 be the given training examples, where each example is drawn i.i.d. according to the joint distribution p(x,y).
In multi-label learning, many loss functions have been proposed to measure the performance of learning algorithms, such as 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),y) = ∑
1≤j<k≤q
I(yj = 1, yk = 0)`(fk, fj) + I(yj = 0, yk = 1)`(fj , fk), (1)
where `(fj , fk) = I(fj > fk) + 1
2 I(fj = fk). (2)
Here, fj is the j-th component of f(x) and I(·) is the indicator function, which outputs 1 if the condition holds while outputs 0 otherwise. The goal of multi-label learning tasks is to learn the optimal classifier f by minimizing the following expected classification risk:
R(f) = Ep(x,y)[L(f(x),y))] = ∑ y∈Y p(y)Ep(x|y)[L(f(x),y))], (3)
= ∑ y∈Y p(y) ∑ 1≤j<k≤q Ep(x|yj=1,yk=0)[`(fk, fj)] + Ep(x|yj=0,yk=1)[`(fj , fk)],
= ∑
1≤j<k≤q
π10jkEp10jk(x)[`(fk, fj)] + π 01 jkEp01jk(x)[`(fj , fk)],
where π10jk = p(yj = 1, yk = 0) (or π 01 jk = p(yj = 0, yk = 1)) denotes the positive-negative (or negative-positive) label pair prior probability, and p10jk(x) = p(x|yj = 1, yk = 0) (or p01jk(x) = p(x|yj = 0, yk = 1)) denotes the class-conditional probability density of data given the positivenegative (negative-positive) label pair. Accordingly, we define the minimal risk (also called the Bayes risk) as R∗ = inff 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, a feasible solution is to consider alternatively a surrogate loss function L which can be solved efficiently. Accordingly, the L-risk with respect to p(x,y) can be defined as: RL(f) = Ep(x,y)[L(f(x),y))] =
∑ 1≤j<k≤q π10jkEp10jk(x)[φ(fj−fk)]+π 01 jkEp01jk(x)[φ(fk−fj)], (4)
where φ is a surrogate loss function. A common choice is hinge loss φ(t) = max(0, 1 − t) in [Elisseeff and Weston, 2002]. Accordingly, we define the minimal L-risk (also called the Bayes L-risk) as R∗L = inff RL(f).

heading: 4 Learning with PRO
text: In this section, we first formulate the problem of multi-label learning with pairwise relevance ordering (PRO). Then, the unbiased estimator is proposed for solving the PRO problem. Due to the page limit, most proofs for theorems in Section 4 and Section 5 are provided in the supplementary material.

heading: 4.1 The PRO Framework
text: In the PRO framework, each example x is associated with the relevance ordering of K label pairs ỹ = {yj y′j}Kj=1, where yj y′j represents the label yj is more relevant than label y′j , i.e., p(yj = 1|x) > p(y′j = 1|x). Note that here y′j represents one out of q − 1 labels (except for label yj) and we can further use yk to denote y′j for notational simplicity. As discussed in Section 1, yj yk indicates three possible cases:1) both yj and yk are relevant to x, i.e., yj = 1, yk = 1; 2) yj is relevant to x while yk is not, i.e., yj = 1, yk = 0; 3) both yj and yk are irrelevant to x, i.e., yj = 0, yk = 0. The observation tells us that yj = 1, yk = 0 (or yj = 0, yk = 1) occurs if and only if yj yk (or yj ≺ yk), i.e., the prior probability p(yj = 1, yk = 0|yj ≺ yk) = 0 (or p(yj = 0, yk = 1|yj yk) = 0). We can further utilize the prior to calibrate the ordinary risk Eq(3). Therefore, by taking the prior into consideration, the classification risk Eq(3) can be calibrated as:
R(f) = ∑
1≤j<k≤q
Π10jkEτ10jk (x)[`(fk, fj)] + Π 01 jkEτ01jk (x)[`(fj , fk)], (5)
where Π10jk = p(yj = 1, yk = 0|yj yk) (or Π01jk = p(yj = 0, yk = 1|yj ≺ yk)) denotes the calibrated positive-negative (or negative-positive) label pair prior probability, and τ10jk = p(x|yj = 1, yk = 0, yj yk) (or τ01jk = p(x|yj = 0, yk = 1, yj ≺ yk)) denotes the calibrated class-conditional probability density of data given the positive-negative (negative-positive) label pair. Accordingly, the L-risk Eq(4) can be calibrated as:
RL(f) = ∑
1≤j<k≤q
Π10jkEτ10jk (x)[φ(fj − fk)] + Π 01 jkEτ01jk (x)[φ(fk − fj)]. (6)
Our goal is to train a multi-label classifier only based on the observed examples D̃ = {xi, ỹi}ni=1, drawn i.i.d. from the distribution p̃(x, ỹ). The expected L-risk with respect to p̃(x, ỹ) can be formulated as follows:
Ep̃(x,ỹ)[L(f(x), ỹ)] = ∑
1≤j<k≤q
π̃10jkEp̃10jk(x)[φ(fj − fk)] + π̃ 01 jkEp̃01jk(x)[φ(fk − fj)], (7)
where π̃10jk = p(yj yk) (or π̃01jk = p(yj ≺ yk)) denotes the positive (or negative) ordering label pair prior probability of PRO examples, and p̃10jk = p(x|yj yk) (or p̃01jk = p(x|yj ≺ yk)) denotes the class-conditional probability density of PRO examples given the positive (negative) ordering label pair. However, directly solving the estimator Eq.(7) to obtain the classifier usually suffers the over-fitting issue, which makes the classifier fail to obtain a promising generalization performance.

heading: 4.2 The Proposed Method
text: In this section, we derive an unbiased risk estimator for solving the PRO problem.
Based on the aforementioned discussions, each label pair yj yk indicates three possible cases, which motivates us to derive the following lemma.
Lemma 1. Each PRO example of D̃ is drawn i.i.d. according a probability distribution with the following class-conditional density:
p(x|yj yk) = Π10jkp(x|yj = 1, yk = 0, yj yk) + π11jkp(x|yj = 1, yk = 1) (8) + π00jkp(x|yj = 0, 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) = ∑
1≤j<k≤q
1
π̃10jk
( π̃10jkEp̃10jk(x)[`(fk, fj)] ) + 1
π̃01jk
( π̃01jkEp̃01jk(x)[`(fj , fk)] ) .
Proof. According to Eq.(8), we have
Ep̃10jk(x)[`(fk, fj)] = Π 10 jkEτ10jk (x)[`(fk, fj)] + π 11 jkEp11jk(x)[`(fk, fj)] + π 00 jkEp00jk(x)[`(fk, fj)].
Similarly,
Ep̃01jk(x)[`(fj , fk)] = Π 01 jkEτ01jk (x)[`(fj , fk)] + π 11 jkEp11jk(x)[`(fj , fk)] + π 00 jkEp00jk(x)[`(fj , fk)].
Then, the expected classification risk R(f) can be expressed as follows: R(f) = ∑
1≤j<k≤q
Π10jkEτ10jk (x)[`(fk, fj)] + Π 01 jkEτ01jk (x)[`(fj , fk)],
= ∑
1≤j<k≤q
Ep̃10jk(x)[`(fk, fj)] + Ep̃01jk(x)[`(fj , fk)]− π 11 jkEp11jk(x)[`(fk, fj) + `(fj , fk)]
− π00jkEp00jk(x)[`(fk, fj) + `(fj , fk)], = ∑
1≤j<k≤q
1
π̃10jk
( π̃10jkEp̃10jk(x)[`(fk, fj)] ) + 1
π̃01jk
( π̃01jkEp̃01jk(x)[`(fj , fk)] ) − π11jk − π00jk ,
where the last equality is due to the fact that `(fj , fk) + `(fk, fj) = 1 by the definition of `.
However, as discussed in Section 3, it is difficult to optimize the loss function ` due to its highly discontinuity. To solve the problem, the following corollary tells us that the unbiased estimator of L-risk with respect to p̃(x, ỹ) can be established under a mild condition. Corollary 1. The L-risk Eq.(6) can be equivalently re-written as
RL̃(f) = ∑
1≤j<k≤q
1
π̃10jk
( π̃10jkEp̃10jk(x)[φ(fj − fk)] ) + 1
π̃01jk
( π̃01jkEp̃01jk(x)[φ(fk − fj)] ) , (9)
if it holds, for every t, the loss function φ satisfies
φ(t) + φ(−t) = 1, (10)
where, for each label pair yj , yk, π̃10jkEp̃10jk(x)[φ(fj − fk)] (or π̃ 01 jkEp̃01jk(x)[φ(fk− fj)]) is the expected L-risk with respect to p̃(x, ỹ) and can be directly estimated from PRO training examples with suitable surrogate loss functions. It is noteworthy that the symmetric condition Eq(10) has been widely used in other weakly supervised learning frameworks [Du Plessis et al., 2014, Ishida et al., 2017].
With the theorem, we can train a multi-label classifier by minimizing the empirical approximation of RL̃(f) from PRO examples as follows:
R̂L̃(f) = 1
n n∑ i=1 L̃(f(x), ỹ), (11)
where, L̃(f(x), ỹ) = ∑
1≤j<k≤q
1
π̃10jk I(yij yik)φ(fj(xi)−fk(xi))+
1
π̃01jk I(yij ≺ yik)φ(fk(xi)−fj(xi)).
(12) Here, it is worthy noting that in contrast to previous cost-sensitive methods [Du Plessis et al., 2014], which often requires extra assumptions or sophisticated techniques to obtain the cost coefficients, the π̃10jk (or π̃ 01 jk) can be directly estimated from the observed PRO training data.

heading: 5 Theoretical Analysis
text: In this section, we provide the estimation error bound for the proposed unbiased estimator and further prove that it is consistent with respect to ranking loss.
Let σ = {σ1, ..., σn} be n Rademacher variables with σi independently uniform variable taking value in {−1,+1}. Then, the Rademacher complexity with respect to function class F and loss function L can be formulated as follows:
Rn(L ◦ F) = Ex,y,σ [ sup f∈F 1 n n∑ i=1 σiL(f(xi),yi) ] . (13)
Based on the definition, we can establish the following lemma.
Lemma 2. LetRn(L̃ ◦ F) be the Rademacher complexity of the loss function L̃ and function class F over D̃ of n training examples drawn from p̃(x, ỹ), which can be defined as
Rn(L̃ ◦ F) = ED̃Eσ [ sup f∈F 1 n n∑ i=1 σiL̃(f(xi), ỹi) ] .
Then, Rn(L̃ ◦ F) ≤ 2KπCφRn(F),
where π = maxj,k 1π10jk ,∀j, k ∈ [q] and Cφ is the Lipschitz constant of φ.
Based on Lemma 2, we can establish the uniform deviation bounds of R̂L̃(f) as follows: Lemma 3. For the loss function φ bounded by Θ and any δ > 0, with the probability at least 1− δ, we have
max f∈F |R̂L̃(f)−RL̃(f)| ≤ 4KπCφRn(F) +KπΘ √ ln 1δ 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 δ > 0, with probability at least 1− δ, we have
RL(f̂)−min f∈F RL(f) ≤ 8KπCφRn(F) + 2KπΘ √ ln 1δ 2n .
where f̂ is trained by minimizing R̂L̃(f). Furthermore, if φ is a differential and non-increasing function with φ′(0) < 0 and φ(t) + φ(−t) = 2φ(0), then learning from PRO data with the modified loss function L̃ Eq.(12) is consistent w.r.t ranking loss, i.e., there exists a non-negative concave function ξ with ξ(0) = 0, such that
R(f̂)−R∗ ≤ ξ(RL(f̂)−R∗L).
Theorem 2 tells us that learning from PRO examples is consistent with respect to ranking loss. As n→∞, if RL(f̂) = R∗L, then we have the consistency: R(f̂) = R(f∗), sinceRn(F)→ 0 for all parametric models with a bounded norm such as deep networks trained with weight decay [Lu et al., 2018]. Based on the above discussion, Sigmoid loss φ(t) = 11+et is a suitable surrogate loss function in our case, since it satisfies the symmetric condition Eq.(10) and meanwhile has been proven to be consistent with respect to ranking loss [Gao and Zhou, 2013].

heading: 6 Experiment
text: In this section, to validate the effectiveness of the proposed method, we perform the experiments on varied datasets with multiple evaluation metrics.

heading: 6.1 Experimental Settings
text: Datasets We evaluate our method on five multi-label datasets: Multi-MNIST2 [Finn et al., 2017], Multi-Kuzushiji-MNIST (Multi-KMNIST for short), Multi-Fashion-MNIST 3 (Multi-FMNIST for short), VOC2007 4 [Everingham et al., 2010] and MSCOCO 5 [Lin et al., 2014]. For three MultiMNIST-style datasets, we randomly sample 6,000 images for training and 4,000 images for testing. VOC2007 contains 9,963 images for 20 object categories, which are divided into train, val and test sets. Following [Chen et al., 2019, 2018], we use the trainval set to train the models, and evaluate the
2See https://github.com/shaohua0116/MultiDigitMNIST for Multi-MNIST. 3Similar to Multi-MNIST, we construct Multi-Kuzushiji-MNIST and Multi-Fashion-MNIST for two com-
monly used datasets Kuzushiji-MNIST and Fashion-MNIST, repsectively. 4See http://host.robots.ox.ac.uk/pascal/VOC/voc2007/ for VOC2007. 5See https://cocodataset.org for MSCOCO.
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 images from the validation set for testing. For each dataset, we randomly sample K pairs of labels and assign their relevance ordering, where K varies among {3, 4, 5, 6, 7, 8} for Multi-MNIST-style 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.
Metrics We evaluate the performance of the proposed method based on multiple standard multilabel 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̂L̃(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 no method can be directly applied to PRO problems. We employ a recently proposed framework called CCMN [Xie and Huang, 2021a] to transform the PRO problem into a MLL problem with class-conditional multi-label noise (CCMN) by regarding y as the positive label while y′ as the negative label for each label pair y y′. And we compare with the following methods: Biased-CCMN (b-CCMN for short), which directly learns a multi-label classifier with noisy labels; Unbiased-CCMN (u-CCMN), which employs the unbiased estimator proposed in [Xie and Huang, 2021a] 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.
Implementation For experiments on Multi-MNIST-style datasets, we train a linear model by using Adam [Kingma and Ba, 2015] optimizer with learning rate of 0.001. We added an `2-regularization term, with the regularization parameter of 0.0001. For experiments on VOC2007 and MSCOCO, we use an Alexnet [Krizhevsky et al., 2012] and a Resnet-18 [He et al., 2016] pre-trained with the
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 `2-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

heading: 6.2 Performance Comparison
text: Figure 1 illustrates 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 a 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-CCMN utilizes the true noise rates which are usually unavailable in practice, and thus the superiority of the proposed method would be more significant in real-world setting.
Figure 2 and Figure 3 illustrate 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, respectively. From the figures, it can be observed that our proposed u-PRO method achieves the best performance in all cases. It seem that u-CCMN performs unstable on VOC2007. It even obtains worse results than the baseline b-PRO in 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.

heading: 6.3 Ablation Study
text: In this section, we conduct some ablation experiments to provide empirical validations for the theoretical analysis proposed in the paper.
We first examine the unbiasedness for the proposed estimator. Based on the discussion in Section 4.2, we disclose that the unbiased estimator is composed of two components, i.e., the cost-sensitive estimator Eq.(9) and the symmetric surrogate loss function which satisfies Eq.(10). Here, u-PROSigmoid and u-PRO-Ramp represent the empirical cost-sensitive estimator Eq.(11) with Sigmoid and Ramp losses, respectively, which both satisfy the symmetric condition. U-PRO-Hinge and b-PRO-Hinge represent the cost-sensitive estimator Eq.(11) and biased estimator Eq.(7) with hinge loss, which does not satisfy the symmetric condition.
Due to the page limit, Figure 4 only report the performance curves of these four estimators in terms of ranking loss and hamming loss on Multi-MNIST, Multi-KMNIST and Multi-FMNIST datasets. From the figures, we can obtain following observations: 1) u-PRO-Sigmoid and u-PRO-Ramp achieve the better performances than u-PRO-Hinge and 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 to obtain the unbiased estimator for solving the PRO problem; 2) U-PROHinge 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 be observe that u-PRO-Sigmoid generally achieve better performance than u-PRO-Ramp in terms of ranking loss, which provides an empirical validation of Theorem 2, since Sigmoid loss has been proven to be consistent with respect to ranking loss while Ramp loss is not [Gao and Zhou, 2013].

heading: 7 Conclusion
text: In this paper, we study the problem of multi-label classification with pairwise relevance ordering, where each instance is 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 is consistent with respect to ranking loss. Finally, we experimentally examine the effectiveness of the proposed method on multiple datasets and evaluation metrics. In the future, we will study PRO problems by considering the data generation process.

heading: 8 Acknowledgments
text: 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).

Review summaries:
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.

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. 

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.

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.