Pointwise Binary Classification with Pairwise Confidence Comparisons
Authors: Lei Feng
Senlin Shu
Nan Lu
Bo Han
Miao Xu
Gang Niu
Bo An
Masashi Sugiyama
Venue:  (2021)
Keywords: Binary classification
pairwise comparisons
unbiased risk estimator

Abstract: Ordinary (pointwise) binary classification aims to learn a binary classifier from pointwise labeled data. However, such pointwise labels may not be directly accessible due to privacy, confidentiality, or security considerations. In this case, can we still learn an accurate binary classifier? This paper proposes a novel setting, namely pairwise comparison (Pcomp) classification, where we are given only pairs of unlabeled data that we know one is more likely to be positive than the other, instead of pointwise labeled data. Compared with pointwise labels, pairwise comparisons are easier to collect, and Pcomp classification is useful for subjective classification tasks. To solve this problem, we present a mathematical formulation for the generation process of pairwise comparison data, based on which we exploit an unbiased risk estimator (URE) to train a binary classifier by empirical risk minimization and establish an estimation error bound. We first prove that a URE can be derived and improve it using correction functions. Then, we start from the noisy-label learning perspective to introduce a progressive URE and improve it by imposing consistency regularization. Finally, experiments validate the effectiveness of our proposed solutions for Pcomp classification.

Under review as a conference paper at ICLR 2021
POINTWISE BINARY CLASSIFICATION WITH PAIRWISE CONFIDENCE COMPARISONS
Anonymous authors
Paper under double-blind review
ABSTRACT
Ordinary (pointwise) binary classification aims to learn a binary classifier from pointwise labeled data. However, such pointwise labels may not be directly ac- cessible due to privacy, confidentiality. or security considerations. In this case, can we still learn an accurate binary classifier? This paper proposes novel set- given
ting, namely pairwise comparison (Pcomp) classification, where only pairs of unlabeled data that we know one is more likely to be positive than the other, instead of pointwise labeled data. Compared with pointwise labels, pairwise comparisons are easier to collect, and Pcomp classification is useful for subjective classification tasks. To solve this problem, tion for the generation process of pairwise comparison data, based on which we exploit an unbiased risk estimator (URE) train binary classifier by empirical risk minimization and establish an estimation error bound. We first prove that a URE can be derived and improve using correction functions. Then, we start from the noisy-label learning perspective to introduce a progressive URE and im- prove it by imposing consistency regularization. Finally, experiments validate the effectiveness of our proposed solutions for Pcomp classification.
present mathematical formula-
INTRODUCTION
Traditional supervised learning techniques have achieved great advances, while they are demanding for precisely labeled data. In many real-world scenarios. it may be too difficult to collect such data. To alleviate this issue, a large number of weakly supervised learning problems (Zhou, 2018) have been extensively studied, including semi-supervised learning (Zhu & Goldberg, 2009; Niu et al., 2013; Sakai et al., 2018), multi-instance learning (Zhou et al., 2009; Sun et al., 2016; Zhang & Zhou, 2017), noisy-label learning (Han et al., 2018; Xia et al., 2019; Wei et al., 2020), partial-label learning (Zhang et al., 2017; Feng et al., 2020b; Lv et al., 2020), complementary-labe learning (Ishida et al., 2017; Yu et al., 2018; Ishida et al., 2019; Feng et al., 2020a), cositive-ullabled classification (Gong et al., 2019). positive-confidee unlabeled classification (Bao et al., 2018), umlabeled-uulabelee classification (Lu et al., 2019; 2020). and triplet classification (Cui et al., 2020).
classification (Ishida et al., 2018), similar-
This paper considers another novel weakly supervised learning setting called pairwise comparison (Pcomp) classification, where we aim to perform pointwise binary classification with only pairwise comparison data, instead of pointwise labeled data. A pairwise comparison (æx x') represents that the instance æ has larger confidence of belonging to the positive class than the instance x'. Such weak supervision (pairwise confidence comparison) could be much easier for people to collect than full supervision (pointwise label) in practice, especially for applications on sensitive or private mat- ters. For example, it may be difficult to collect sensitive or private data with pointwise labels, as asking for the true labels could be prohibited or illegal. In this case, it could be easier for people to collect other weak supervision like the comparison information between two examples.
is also advantageous to consider pairwise confidence comparisons in pointwise binary classifica- tion with class overlapping, where the labeling task becomes difficult, and even experienced labelers may provide wrong pointwise labels. Let us denote the labeling standard of labeler as p(y [z) and assume that an instance æi is more positive than another instance x2. Facing the difficult labeling task, different labelers may hold different labeling standards, p(y = + +1[z1) > ply = + +1/0>) >
1 1/2, ply +1 (x)) > 1/2 p(y +1 and 1/2 ply + |an) ) > p(u = +1 (ar2), thereby

---

Under review as a conference paper at ICLR 2021
providing different pointwise labels: (+1, +1), (+1, (-) We can find that different la- belers may provide inconsistent pointwise labels, while pairwise confidence comparisons are unan- imous and accurate. One may argue that could aggregate multiple labels of the same instance using crowdsourcing learning methods (Whitehill et al., 2009; Raykar et al., 2010). However, as not every instance will be labeled by multiple labelers, it is not always applicable crowdsourcing learning methods. Therefore, our proposed Peomp classification is useful in this case.
Our contributions in this paper can be summarized follows:
We propose Peomp classification, novel weakly supervised learning setting, and present a mathematical formulation for the generation process of pairwise comparison data.
We prove that unbiased risk estimator (URE) be derived, propose an empirical risk minimization (ERM) based method, and present an improvement using correction functions (Lu al., 2020) for alleviating overftting when complex models are used.
We start from the noisy-label learning perspective to introduce the RankPruning method (Northcutt et al., 2017) that holds progressive URE for solving our proposed Pcomp classification problem and improve it by imposing consistency regularization.
We experimentally demonstrate the effectiveness of our proposed solutions for Peomp clas- sification.
PRELIMINARIES
Binary classification with pairwise comparisons and extra pointwise labels has been studied (Xu al., 2017; Kane al., 2017). Our paper focuses more challenging problem where only pair- wise comparison examples are provided. Unlike previous studies (Xu et al., 2017; Kane et al., 2017) that leverage some pointwise labels to differentiate the labels of pairwise comparisons, our methods are purely based on ERM with only pairwise comparisons. In the next, we briefly introduce some notations and review the related problem formulations of binary classification, positive- positive-unlabeled unlabeled classification, and unlabeled-unlabbled classification.
Binary Classification. Since our paper focuses on how to train a binary classifier from pairwise comparison data, we first review the problem formulation of binary classification. Let the feature space be X' and the label space be y {+1, -1}. Suppose the collected dataset is denoted by D = [xx, y4) ) where each example (z), 34) is independently sampled from the joint distribution with density p(æ, y), which includes an instance æ; X and a label y/8 E y. The goal of binary classification is to train optimal classifier f X R by minimizing the following expected classification risk:
R(F) Ep(ar)) ((((()) = (.) |
π B, (a) [e(f(x),,1))
(1)
where é IR x V R4, denotes a binary loss function, := plu = +1) Tor == ply 1))
denotes the positive (or negative) class prior probability, and p+ (z) p( (or p- (xx
p(zly = 1)) denotes the class-conditions ERM approximates the expectations over P+()) and p=(x) by the empirical averages of positive and negative data and the empirical risk is minimized with respect to the classifier f.
probability density of the positive (or negative) data.
Dositive-Unlabelee (PU) Classification. In some real-world scenarios, it may be difficult to col- lect negative data, and only positive (P) and unlabeled (U) data are available. PU classification aims to train an effective binary classifier in this weakly supervised setting. Previous studies (du Plessis et al., 2014; 2015; Kiryo al., 2017) showed that the classification risk R()) in Eq. (I) can be rewritten only terms of positive and unlabeled data as
(2) where p(x:) = T T4p+ (x) + --p-(xx) (x) denotes the probability density of unlabeled data. This risk expression immediately allows to employ ERM in terms of positive and unlabeled data.
R(F) = Re (f) = x Ep (a) [[f(()), +1) (ff(),, 11] + Ep(a)) [e(f(x), 11)],
Cettablled-nnlabbeee (UU) Classification. The recent studies (Lu et al., 2019; 2020) showed that it is possible to train binary classifier only from two unlabeled datasets with different class priors.
2

---

Under review as a conference paper at ICLR 2021
Lu et al. (2019) showed that the classification risk can be rewritten
(1 - 8") ) ((f(ax), +1) 8'(1 - T+) 0(1-xt) [([(2x), -1)
R()) (f) = (x)
0 0'
0-00
(1- (1- ((f(z')++1) (3) 0(1 - n_) e(f 9 0-
E (xy)
0 0r
where 9 and I' are different class priors of two unlabeled datasets, and (2x) and Per (x') are the densities of two datasets of unlabeled data, respectively. This risk expression immediately allows us to employ ERM only from two sets of unlabeled data. For Ruv(() in Eq. (3), if we set = 1, 0' T and replace (ar( and ptr by (*x) and p(ar) respectively, then we can recover Rf in Eq. (2). Therefore, UU classification could be taken as a generalized framework of PU classification in terms of URE Besides, Eq. (3) also recovers complicated URE of similar- unlabeled classification (Bao et al., 2018) by setting 0 = + and 0' = क.. (2 2T+ + 1).
To solve our proposed Pcomp classification problem, we will present a mathematical formulation for the generation process of pairwise comparison data, based on which we will explore two UREs to train a binary classifier by ERM and establish the corresponding estimation error bounds.
DATA GENERATION PROCESS
In order to derive UREs for performing ERM, we first formulate the underlying generation process of pairwise comparison data', which consists of pairs of unlabeled data that we know which one is more likely to be positive. Suppose the provided dataset is denoted by D = {( > where (æ;, a!)) (with their unknown true labels (yi. v/)) is expected to satisfy p(y: = +1/2,) ply, +1(2)).
It is clear that we could easily collect pairwise comparison data if the positive confidence (i.e.. p(y - +1aa)) )a))) of each instance could be obtained. However, such information is much harder to obtain than class labels in real-world scenarios. Therefore, unlike some studies (Ishida et al., 2018; Shinoda et al., 2020) that assume the positive confidence of each instance is provided by the labeler, we only assume that the labeler has access to the labels of training data. Specifically, we adopt the assumption (Cui et al., 2020) that weakly supervised examples are first sampled from the true data distribution, but the labels are only accessible to the labeler. Then, the labeler would provide us weakly supervised information (i.e., pairwise comparison information) according to the labels of sampled data pairs. That is, for any pair of unlabeled data (æz, x'), the labeler would tell us whether (x, x²) could be collected as a pairwise comparison for Peomp classification, based on the labels (y. s/) rather than the positive confidences (p(y- = +1/x),
+1(x'))
Now, the question becomes: how does the labeler consider x') as a pairwise comparison for Pcomp classification, in terms of the labels (V, As shown in our previous example of bi- nary classification with class overlapping, we could infer that the labels (y. y') of our required pairwise comparison data (æ. x²) for Peomp classification can only be one of the three cases (1),
because the condition p(y = +1[#) 2 p(y' = +1/2²) is defi- nitely violated if (v.y') (-1, Therefore, we assume that the labeler would take (æz, x²) as a pairwise comparison example in the dataset D, if the labels (y, 3/) of (æ, x²) belong to the above three cases. It is also worth noting that for pair of data (x, with labels (y. (-1, +1), the labeler would take (x', x) as a pairwise comparison example. Because by exchanging the positions of (x. x²), (ar, x)) would be associated with labels (+1,-1), which belong to the three cases. In summary, we assume that pairwise comparison data are sampled from those pairs of data whose labels belong to the three cases [(+1,-1) (4,, generation process of pairwise comparison data, we have the following theorem.
(-1, -1)]- Based the above described
Theorem 1. According to the generation process of pairwise comparison data described above, let
9(2, x')
o(z, x')
(4)
1 22 n-
where (2) = (T) (x') + n (x) (x') + (x) Then we have D ((x;,,))) lid. x'x,
'n contrast to Xu et al. (2019) and Xu et al. (2020) which utilized pairwise comparison data to solve the regression problem, we focus binary classification.
3

---

Under review as a conference paper at ICLR 2021
The proof is provided in Appendix A. Theorem provides explicit expression of the probability density of pairwise comparison data.
Next, we would like to extract pointwise information from pairwise information, since our goal is to perform pointwise binary classification. Let = n - + - = स + n =  + т- and we denote the pointwise data collected from D { x=) by breaking the pairwise comparison relation as D+ {= and D_ |
1-1- Then we can obtain the following theorem.
Theorem 2. Pointwise examples in D+ and D_ are independently drawn from p= (x) and p- (x'),
where
7 D+ (x))
P4 (2)
P+ (x)
p- π
px(x,, (x), 8-(x') +
p (x')
The proof is provided in Appendix B. Theorem 2 shows the relationships between the pointwise densities and the class-conditional densities. Besides, indicates that from pairwise comparison data, we can essentially obtain examples that are independently drawn from pa (x) and fr (a').
4 THE PROPOSED METHODS
In this section, we explore two UREs to train a binary classifier by ERM from only pairwise com- parison data with the above generation process.
4.1 CORRECTED PCOMP CLASSIFICATION
As shown in Eq. (1), the classification risk R(f) could be separately expressed the expectations over P+ (x) and (x)). Although we do not have access to the two class- class-conditionall densities p. (x) and p (ar), we can represent them by our introduced pointwise densities p+ (a)) and (wx).
Lemma 1. We can express p. (a)) and (x) in terms P+ and p (x) as
p+(x)= = 1 (p+ (x) - (x),, p-(x) = - (p_(x) (x) -x+++()) π
The proof is provided in Appendix C. As result of Lemma 1, we can express the classification risk R(f) using only pairwise comparison data sampled from p+ (a)) and p- (ar).
Theorem 3. The classification risk R(f) can be equivalently expressed as
1)] + E5 (ar) [ [(((x)))) -1) - ((_((((')++1)) Rpc(f) EE (x) [((f(z), +1) xf((((x), -1]]
(5)
The proof is provided in Appendix D. In this way, we could train binary classifier by minimizing the following empirical approximation of Rro(f):
Pro(S) 1 E"_ "
k=1 ((((()))+1) (-((((m).-)) -1) + {(f())), -
(6)
Estimation Error Bound. Here, we establish estimation error bound for the proposed URE. Let F ( X' + R} be the model class, JPc arg minjee Rto(S)) be the empirical risk minimizer, and f arg min R(f) be the true risk minimizer. Let R (F) and (F, be the Rademacher complexities (Bartlett & Mendelson, 2002) of F with sample size over F+ (æ) and p- (a)) respectively.
Theorem 4. Suppose the loss function is p-Lipschitz with respect to the first argument (0 S p oo), and all functions in the model class F are bounded, i.e., there exists positive constant Cb. such that fIl < Cb for any f E F. Let Ce == sup ((2,t). Then for any with probubility at least 8, we have
log
R(frc) -
s (1+
(1 (F) + 601/
2n
4

---

Under review as a conference paper at ICLR 2021
The proof is provided in Appendix E. Theorem 4 shows that proposed method is consistent, i.e., as a + 0o, R(fpc) + R( since Ri (F), Ri (F) + 0 for all parametric models with a bounded norm such as deep neural networks trained with weight decay (Golowich et al., 2017: Lu et al., 2019). Besides, R and (F) can be normally bounded by Cz/vi for a positive constant Cy. Hence, we can further see that the convergence rate
(1//n) where Op denotes the order in probability. This order is the optimal parametric rate for ERM without additional assumptions (Mendelson, 2008).
Relation to UU Classification. It worth noting that the URE of UU classification Ruu (f) is quite general for binary classification with weak supervision. Hence we also would like to show the relationships between proposed estimator Rec(f) and Ruu(f). We demonstrate by the following corollary that under some conditions, (Vv(S) is equivalent to RPc(S).
Corollary 1. By setting Pur = (x)). per (x),, = T a + m2. and 8' 7 T4 + 7 Eq. (3) is equivalent to Eq. (5), which means that Ruu(f) is equivalent to Rpc(f).
We omit the proof of Corollary since it is straightforward to derive Eq. (5) from Eq. (3) by inserting the required notations.
Empirical Risk Correction. As shown in Lu et al. (2020), directly minimizing Bfc(f) would suffer from overfitting when complex models are used due to the negative risk issue. More specifi- cally, since negative terms are included in Eq. (6), the empirical risk can be negative even though the original true risk can never be negative. To ease this problem, they wrapped the terms in Rfu(f) that cause a negative empirical risk by certain consistent correction functions such as the rectified linear unit (ReLU) function g(z) max(0, 2) and absolute value function g(z) = |z]. This solution could also be applied Rrc. In this way, we could obtain the following corrected empirical risk estimator:
Raro(f)
( (e([(z)), -T =l(((()) +1))
+ + C 1=1 (e(f(x)), -
--((f(()), -1))) -1))). (7)
4.2 PROGRESSIVE PCOMP CLASSIFICATION
Here, we start from the noisy-label learning perspective to solve the Peomp classification prob- lem. Intuitively, we could simply perform binary classification by regarding the data from p+ (æ) as (noisy) positive data and the data from (_(x) as (noisy) negative data. However, this naive solution could be inevitably affected by noisy labels. In this scenario, we denote the noise rates as p- = pl = +1gy = 1) and p+ ply = 1yy = +1), where ÿ is the observed (noisy) label and y is the true label, and the inverse noise rates as Ø+ p(y -17ō +1) and 6_ = p(y = +1 1).. According to the defined generation process of pairwise comparison data, we have the following theorem.
Theorem 5. The following equalities hold:
n²
T +
Φ+
$_
Tē + 2 T4
x7 + 22
P+
2 + TT
p_
2 2
2 TT
The proof is provided in Appendix F.
Theorem 5 shows that the noise rates can be obtained if we regard the Pcomp classification problem as the noisy-label learning problem. With known noise rates for noisy-label learning, was shown (Natarajan et al., 2013; Northeutt et al., 2017) that URE could be derived. Here, adopt the RankPruning method (Northcutt et al., 2017) because it holds a progressive URE by selecting confi- dent examples using the learning model and achieves state-of-the-art performance. Specifically, denote by the dataset composed of all the observed positive data P, i.e., P = { where æ; is independently sampled from (xx). Similarly, the dataset composed of all the observed negative data is denoted by N, i.e., N {ar where af is independently sampled from p_ (æ'). Then,
5

---

Under review as a conference paper at ICLR 2021
confident examples will be selected from P and N by ranking the outputs of the model f. We denote the selected positive data from P as Pacl, and the selected negative data from W Noet:
P sel arg max (1
Eee(pniy f()), Nua
arg min
Eeswnnis f(x).
Then we show that if the model I satisfies the separability condition, i.e., for any true positive instance zp and for any true negative instance Zn. we have f(xp) > f(xa). In other words, the model output of every true positive instance is always larger than that of every true negative instance,
we could obtain URE. We name it progressive URE, as the model f is progressively optimized.
Theorem 6 (Theorem Northcutt et al. (2017)), Assume that the model f satisfies the above separability condition, then the classification risk R(f) can be equivalently expressed as
[f = -1Egi (x) ((1(z))+1)). 1/ E Paal] +Eg (x))
[(f((''), -1) 1a E &Nool] 1 --p-
p+
where [[-] is the indicator function.
In this way, we have the following empirical approximation of RpPC:
RFpC(f) = 1 -", ((f(()))+1) 1- I|2, E Paell+ + ((f(x)))-1) Max E eNaal)
(8)
1 p-
Estimation Error Bound. It worth noting that Northcutt et al. (2017) did not prove the learn- ing consistency for the RankPruning method. Here, establish estimation error bound for this method, which guarantees the learning consistency. Let fppc arg minjer (f) be the empirical risk minimizer of the RankPruning method, then we have the following theorem.
Theorem 7. Suppose the loss function is p- p-Lipschitz with respect to the first argument (0 S < 20). and all functions in the model class are bounded, i.e. there exists positive constant Cp. such that || < Cb for any f E F. Let Ct == supasom E(z,t). Then for any 5 > 0, with probability least 8, we have
R(SPCc) - 1 1
(20Rt + +C
log 4
(2pR, + C.p 2n 1
2
log 1 2n
The proof is provided in Appendix G. Theorem shows that the above method is consistent and this estimation error bound also attains the optimal convergence rate without any additional assumption (Mendelson, 2008), as analyzed in Theorem 4.
Regularization. For the above RankPruning method, its URE is based the assumption that the learning model could satisfy the separability condition. Thus, its performance heavily depends on the accuracy of the learning model. However, the learning model is progressively updated, some of the selected confident examples may still contain label noise during the training process. As result, the RankPruning method would be affected by incorrectly selected data. straightforward improvement could be to improve the output quality of the learning model. Motivated by Mean Teacher used semi-supervised learning (Tarvainen & Valpola, 2017), we also resort to teacher model that is exponential moving average of model snapshots, i.e., Ø a + (1 a)) where O' denotes the parameters of the teacher model, θ denotes the parameters the learning model, the subscript denotes the training step, and is smoothing cocfficient hyper-paree syper-parameter. Such a teacher model could guide the learning model to produce high-quality outputs. To learn from the teacher model, we leverage consistency regularization I((f) = E, []]f((()) fe (æ:) [|2] (Laine & Aila, 2016; Tarvainen Valpola, 2017) to make the learning model consistent with the teacher model for improving the RankPruning method.
EXPERIMENTS
In this section, we conduct experiments to evaluate the practical performance of our proposed meth- ods various datasets.

---

Under review as a conference paper at ICLR 2021
Table 1: Classification accuracy (td) in percentage of each method the four benchmark datasets with different class priors. The best performance is highlighted in bold.
Class Prior
Methods
MNIST
Kuzushiji
Fashion
CIFAR-10
Unbiased
86.52:13344 48
64.47:19.88
91.98:10.35
80.00:10.00
Binary-Biased
27.80+-2.38
18.54+1.13
43.27449.55
49.87++4.38
RankPruning
93.58:10.49
81.58111.33
94.3611.54
84.02:1..51
0.2
AS
89.83+1.49
84.66
91.29+1.69
82.56+00.75
Pcomp-ReLU
93.39110.71
83.76.10.99
94.07-10.49
81.16:10.67
(comp-Unbiasee
80.52:+:.73
60.06++9.28
89.74:+2.27
64.49++2.08
Pcomp-Teacher
94.08
83.82+00.48
94.38+10.53
84.42:10.76
Easy--Unbiased
86.1022
65,4113.48
89.7412.31
62.40:1..08
Binary-Biased
54.10+2.42
60.75+0.54
45.76+1181
48.36++.11
RankPruning
89.64110.21
78.41110.72
92.72.10.34
81.23.10.71
44 0.5
Poomp-ABS
85.90+00.30
74.29+11.42
92.18+0..0
70.71+0.90
Peomp-ReLU
1..8111108
73.88:10.72
12.1311133
74.514:2.26
Pcomp-Unbiased
85.37:14.08
64.84+4.61
91.02:+0.94
1..50:11.78
Pcomp-Teaches
89.85:10.40
78.95:10.66
92.55:10.40
80.21+22.36
Noisy-Unbiased
85.73++3.63
76.60++4.06
88.96++0.557
72.73+-6.92
Binary-Biased
27.12:1:..0
55.72:1
46.7411..19
38.5919.998
RankPruning
93.86:10.72
82.25:12.2
94.6011.22
84.341
44 = 0.8
Poomp-ABS
88 28.06=11.60
82.96++0.54
91.69++1.77
82.87++0.59
Poomp-ReLU
93.63111.03
83.1711.38
93.311:1.44
81.4011..59
Pcomp-Unbiased
80.49:+4.03
67.30+3.57
80,02+4..22
66,48+9.61
Peomp-Teacher
94.96:10.38
84.22++1.21
94.63-10.43
84.86
Datasets. We use four popular benchmark datasets, including MNIST (LeCun et al., 1998), Rashion-MNIST (Xiao al., 2017), Kuzushiji-MND (Clanuwat et al., 2018), and CIFAR- 10 (Krizhevsky et al., 2009). We train multilayer perceptron (MLP) model with three hidden layers of width 300 and ReLU activation functions (Nair & Hinton, 2010) and batch normalization (loffe & Szegedy, 2015) the first three datasets. We train ResNet-34 (He et al., 2016) on the CIFAR-10 dataset. We also use USPS and three datasets from the UCI machine learning repository (Blake & Merz, 1998) including Pendigits, Optdigits, and CNAE-9, We train linear model these datasets, since they are not large-scale datasets. The detailed descriptions of all used datasets with the corresponding models provided in Appendix H. Since these datasets specially used for multi-class classification, we manually transformed them into binary classification datasets (please Appendix H for details). As have shown in Theorem the pairwise comparison examples can be equivalently transformed into pointwise examples, which are more convenient to generate. Therefore, we generate pointwise examples in experiments. Specifically, as Theorem discloses the noise rates in our defined data generation process, we simply generate pointwise corrupted examples according to the noise rates.
For our proposed Peomp classification problem, we propose the following methods: Pcomp-Unbiased, which denotes the proposed method that minimizes RPc(f) in Eq. (6); Pcomp- ReLU, which denotes the proposed method that minimizes R&pC(f) in Eq. (7) with the ReLU function; Pcomp-ABS, which denotes the proposed method that minimizes RepC(f) in Eq. (7) with the absolute value function;
Methods.
which improves the RankPruning method by imposing consistency regularization to make the learning model consistent with teacher model. Besides, compare with the following baselines: Binary-Biased, which conducts binary classification by regarding the data from p. (x)) as positive data and the data from (xx as negative data. This straightforward method handle the Pcomp classification problem. In our setting, Binary- Biased reduces to the BER minimization method (Menon et al., 2015); Noisy-Unbiased which is nobsy learning method that minimizes the empirical approximation of the URE proposed by Natarajan et al. (2013); RankPruning, which is noisy-label learning method (Northcutt et al., 2017) that minimizes (f) in Eq. (8). For all learning methods, take the logistic loss as the binary loss function (i.e., {(2) = In(1 + exp(-2))), for fair comparisons. We implement our methods using Py PoTch (Paszke et al., 2019) and the Adam (Kingma & Ba, 2015) optimization method with mini-bated size set to 256 and the number of training epochs set to 100. All the experiments conducted on GeForce GTX 1080 Ti GPUs.

---

Under review as a conference paper at ICLR 2021
Table 2: Classification accuracy (tta in percentage of each method the four UCI datasets with different class priors. The best performance is highlighted in bold.
Class Prior
Methods
USPS
Pendigits
Optdigits
CNAE-9
Unbiased
88.43:12.99
83.35:10.57
84.63:1..77
83.73::1 1.66
Binary-Biased
79.37+
65.24455.48
65.23+3.48
63.48++1.8
RankPruning
91.93:10.83
78.4315.88
83.61
76.03:15.07
0.2
AS
90.94+00.83
86.14+0.72
85.98+1.82
82,40+1.44
Pcomp-ReLU
91.90110.60
86.35110.80
87.5
1..9
Pcomp-Unie Unbiased
91.88+00.75
85.89+1.500
86.79+1.552
1.71
Pcomp-Teacher
93.18+0.557
86.36.1
8..81+1.54
80.4414.33
Easy--Unbiased
87.57+2..02
83,4712..2
1.,13
76.77:10.95
Binary-Biased
90.78+0..4
79.60+-5.46
81.84+3.998
74.34+1.41
RankPruning
92.28110.26
80.1912.47
82.77
70.65
44 = 0.5
Pcomp-ABS 19.81+1.229
83.32422.38
83.61+1.78
76.32+
Peomp-ReLU
91.10:10.73
84.26:1.2.77
84.43:11.52
7..58:11.17
Pcomp-Unbiased
90.77:+:.87
84.52:12.49
85.43++1.799
1..1
Pcomp-Teaches
92.53:1:0300
82.10:42.26
84.54:11.90
74.89113.60
Noisy-Unbiased
88.49--2.14
85.62+1.29
87.05++1.24
83.78++1.42
Binary-Biased
1..9411..3
63.6314.36
68.83112.70
60.45:10.95
RankPruning
89.02.18.69
84.9411.33
87.2410.87
83.3311.779
44 = 0.8
Poomp-ABS 90.96+00.84
89.20++2.70
88.93+11.12
1..7
Poomp-ReLU
92.09:11.53
89.5912.57
89.13110.67
83.9711.005
Pcomp-Unbiased
1..28=
89.13+2.42
88 1.22
8.,50+
Peomp-Teacher
93.05
87.64
89.30=
83.62+3.62
Experimental Setup. We test the performance of all learning methods under different class prior settings, i.e., 4+ is selected from (0.2, 0.5, 0.8). It is worth noting that we could estimate : according to our described data generation process. Specifically, we can exactly estimate т by counting the fraction of collected pairwise comparison data in all the sampled pairs of data. Since = T-
T we have # = 1/2 - V 3/4 (if π < π-) or π = 1/2 + VT 3/4 (if T 2 J.). Therefore, if we know whether T is larger than т_, we could exactly estimate the true class prior T+. For simplicity, we assume that the class prior क. is known for all the methods. We repeat the sumpling-and-tranne datasets and record the mean accuracy with standard deviation (ttd.
process 5 times for all learning methods all
Experimental Results with Complex Models. Table 1 records the classification performance of each method on the four benchmark datasets with different class priors. From Table I, we have the following observations: 1) Binary-B always achieves the worst performance, which indicates that simply conducting binary classification cannot well solve our Peomp classification problem; 2) Conbased is is inferior to Peomp-ABS and Pcomp Re This observation accords with what we have discussed, i.c., directly minimizing Rpc(f) would suffer from overfitting when com- plex models are used because there are negative terms included in Rec(S) and empirical risk can be negative during the training process. In contrast, Pcomp- ReLU and Pcomp-ABS employ sistent correction functions on Rpc(f) f) so that the empirical risk will never be negative. Therefore, when complex models such as deep neural networks are used, Pcomp-ReLU and Pcomp-ABS are expected to outperform Scomp-Unbiased 3) Pcomp-Teacher achieves the best performance in most cases. This observation verifies the effectiveness of the imposed consistency regularization, which makes the learning model consistent with teacher model, for improving the quality of selected confident examples by the RankPruning method; 4) It is worth noting that the standard deviations of Binary-Biasse Biased, Pcomp-Unbiases
Promp-ReLU
and Noisy-Unbiased are sometimes higher than other meth- ods. This is because the three methods suffer from overfitting when complex models are used, and the performance could be quite unstable in different trials. In addition, Woisy-Unbiase accuracy of 80.00+0.000% Noisy-Unbiase, always simply classifies all examples into the negative class due to the serious overfitting issue complex class-imi iaassimmalanced dataset with complex model ResNet-34.
holds the CIFAR-10 with class prior 0.2. This extreme case happens because
Experimental Results with Simple Models. Table 2 reports the classification performance of each method on the four UCI datasets with different class priors. From Table 2, we have the follow-
8

---

Under review as a conference paper at ICLR 2021
ing observations: 1) Binary-Biased achieves the worst performance in nearly all cases; 2) Peomp- Unbiased slightly better than Pcomp-ReLU and Pcomp-ABS, because Pcomp-Unbiand does not suffer from overfitting when the linear model is used, and it is not necessary to consistent cor- rection functions anymore. Besides, Pcomp-Unbiased becomes comparable to Pcomp-Teacher Teacher and achieves the best performance in half of the cases; 3) Pcomp-Teacher is still better than RankPrun- ing, while it is sometimes inferior to Peomp- Sump--Unbissd... This is because the linear model is not as powerful as neural networks, and the selected confident examples may not be so reliable.
CONCLUSION
In this paper, proposed novel weakly supervised learning setting called pairwise comparison (Pcomp) classification, where we aim to train a binary classifier from only pairwise comparison data, i.e., two examples that know one is more likely to be positive than the other, instead of pointwise labeled data. Peomp classification useful for private classification tasks where we are not allowed directly access labels and subjective classification tasks where labelers have different labeling standards. To solve the Pcomp classification problem, we presented a mathematical for- mulation for the generation process of pairwise comparison data, based on which we explored two unbiased risk estimators (UREs) to train a binary classifier by empirical risk minimization and es- tablished the corresponding estimation error bounds. We first proved that a URE can be derived and improved it using correction functions. Then, we started from the noisy-label learning perspective to introduce a progressive URE and improved it by imposing consistency regularization. Finally, experiments demonstrated the effectiveness of our proposed methods.
In future work, we will apply Pcomp classification to solve some challenging real-world problems like binary classification with class overlapping. In addition, we could also extend Pcomp classi- fication to the multi-class classification setting by using the one-versus-all strategy. Suppose there multiple classes, are given pairs of unlabeled data that know which one is more likely to belong to a specific class. Then, we can use the proposed methods in this paper to train a binary classifier for each class. Finally, by comparing the outputs of these binary classifiers, the predicted class can be determined.
REFERENCES
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In ICML, pp. 452-461, 2018.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3(11):463-482 2002.
Catherine L Blake and Christopher J Merz. Uci repository of machine learning databases, 1998.
URL wwttthtt///t / / aaraaicceee......e ics. uci. wdw/ellll/...... .index.pp........
Tarin Clanuwat, Mikel Nober-Irizan, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature. arXiv preprint 1rXiv:1812.01711 2018.
Zheng-Hane Cui, Nontawat Charoenphakdee, Issei Sato, and Masashi Sugiyama. Classification from triplet comparison data. Neural Computation, 32(3):659-611, 2020.
Marthinus C. du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In NeurIPS, pp. 703-711, 2014.
Marthinus C. du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In ICML., pp. 3386-1394, 2015.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. In ICML, pp. in press, 2020a.
Lei Feng, Jia-Qi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. In NeurlPS, 2020b.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Size-independent sample complexity of 2017.
neural networks. arXiv preprint

---

Under review as a conference paper at ICLR 2021
Chen Gong, Hong Shi, Tong-Liang Liu, Chuang Zhang, Jian Yang, and Da-Cheng Tao. Loss de- composition and centroid estimation for positive and unlabeled learning. TPAMI, 2019.
Bo Han, Quan-Ming Yao, Xing-Rui Rui Yu, Gang Niu, Miao Xu, Wei-Hua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pp. 8527-8537, 2018.
Kai-Ming He, Xiang- Yu Zhang, Shao-Qing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 100201150..03167 2015.
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. In NeurlPS, pp. 5644-5654, 2017.
Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification for positive-confidence data. In NeurIPS, pp. 5917-5928 2018.
Takashi Ishida, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. Complementary-label learning for arbitrary losses and models. In ICML, pp. 2971-2980, 2019.
Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with com- parison queries. In FOCS, pp. 355-366. IEEE, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. In NeurlPS, pp. 1674-1684, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint 1rX1::1610.02242. 2016.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11)2228--2224 1998.
Nan Lu, Gang Niu, Aditya K. Menon, and Masashi Sugiyama. the minimal supervision for training any binary classifier from only unlabeled data. In ICLR, 2019.
Nan Lu, Tian-Yi Yi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In AISTATS, 2020.
Vi-QQ Lx, Miao Xu, Lei Feng. Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identifi- cation of true labels for partial-label learning. ICML. 2020.
Shahar Mendelson. Lower bounds for the empirical minimization algorithm. TIT, 51T3334333377733383 2008
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from cor- rupted binary labels via class-pro estimation. In ICML, pp. 125-134, 2015.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICMI, 2010.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NewrlPS, pp. 1196-1204, 2013.
10

---

Under review as a conference paper at ICLR 2021
Yuval Netzer, Tao Wang. Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Read- ing digits in natural images with unsupervised feature learning. In NeurlPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Gang Niu, Wittawat Jitkrittum, Bo Dai, Hirotaka Hachiya, and Masashi Sugiyama. Squared-loss mutual information regularization: A novel information-theorrtie approach to semi-supervised learning. In ICML, pp. 10-18, 2013.
Curtis G Northcutt, Tailin Wu, and Isaac L Chuang. Learning with confident examples: Rank pruning for robust classification with noisy labels. In UAI, 2017.
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. In NeurlPS, pp. 8026-8037, 2019.
Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. JMLR, 11(4), 2010.
Tomoya Sakai, Gang Niu, and Masashi Sugiyama. supi-supe auc optimization based on positive-unlabeled learning, MLJ, 107(4),767-794, 2018.
Kazuhiko Shinoda, Hirotaka Kaji, and Masashi Sugiyama. Binary classification from positive data with skewed confidence. In IJCAI, pp. 3328-3334, 2020.
Miao Sun, Tony Han, Ming-Chang Liu, and Ahmad Khodayari-Rostamaaad Multiple instance learning convolutional neural networks for object recognition. In ICPR, pp. 3270-3275, 2016.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consis- tency targets improve sumi-supervised deep learning results. In NeurIPS, pp. 1195-1204, 2017.
Hong-Xin Wei, Lei Feng, Xiang-Yo Yu Chen, and Bo An. Combating noisy labels by agreement: A joint training method with co-regularization. In CVPR, pp. 13726-13735 2020.
Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R Movellan, and Paul I. Ruvolo. Whose vote should count more: Optimal integration of labels from labelers unknown expertise. NeurlPS, pp. 2035-2043, 2009.
Xiao-Bo Xia, Tong-Liang Liu, Nan-Nan Wang. Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? In NewrIPS, pp- 6835-6846, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for bench- marking machine learning algorithms. arXiv preprint crXiv:1708.077447 2017.
Li-Yuan Xu, Junya Honda, Gang Niu, and Masashi Sugiyama. Uncoupled regression from pairwise comparison data. In NeurlPS, pp. 3992 4002, 2019.
Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, and Artur Dubrawski. Noise-tolerant interactive learning using pairwise comparisons. In NeurlPS, pp. 2431-2444 2017.
Yichong Xu, Sivaraman Balakrishnan, Aarti Singh, and Artur Dubrawski. Regression with com- parisons: Escaping the curse of dimensionality with ordinal information. JMLR, 21(16)) 2020.
Xi-Yu Yu, Tong-Liang Liu, Ming-Ming Gong, and Da-Cheng Tao. Learning with biased comple- mentary labels. In ECCV, pp. 68-83, 2018.
Min-Ling Zhang, Fei Yu, and Cai-Zhi Tang. Disambiguation-free partial label learning. TKDE, 29 0000:2155-2167 2017.
Ya-Lin Zhang and Zhi-Hua Zhou. Multi-instance learning with key instance shift. In IJCAI. pp. 3441-3447, 2017.
Zhi- Hua Zhou. A brief introduction to weakly supervised learning. National Science Review, 5(1): 44-53, 2018.
11

---

Under review as a conference paper at ICLR 2021
Zhi-Hua Zhou, Yu- Yin Sun, and Yu-Feng Li. Multi-instance learning by treating instances as non-iid samples. In ICML. pp. 1249-1256, 2009.
Xiao-Jin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 3(1):1-130, 2009.
12

---

Under review as a conference paper at ICLR 2021
A PROOF OF THEOREM
is clear that each pair of examples (æ, x²) is independently drawn from the following data distri- bution:
(v.V') E E>) p(2,x))= p(((, =((,=))= (w.5)) p((v,0') E D)
where p((u,v)) v/) E 5) = म + _ + nT and
p( (v.2/) E .
pla, of (v,v')) p(y.
= (x)p (x') (z)p-<x)p t
Finally, let p(x, x') = p((xx, (v. E V). the proof is completed.
B PROOF OF THEOREM
In order decompose the pairwise comparison data distribution into pointwise distribution, marginalize p(æ, æ²) with respect to x or æ'. Then we can obtain
J p(zz, x' x')d' = n (+pp((x) (x)
+ p2) + x π p+ (x))
7²
p+ (x))
p- (xx
T2 +
72 + 14
(x),
and
J p( x'' x')x =
(x 72p_(x') n - (p'))'))
1
72
π - p+ (xx)
p (x¹)
n7 + π
7-(x')
which concludes the proof of Theorem
C PROOF OF LEMMA
Based on Theorem 2, we can obtain the following linear equation:
p+
1
2
p+(x)) (x)
x
p
By solving the above equation, we obtain
1
1
(x)
- -_())
-
(p+(x) -- (x))
T4. π.
π4
1
(=(x)= TT n
T 7-
(z)
म 54 (x))
(ī_(x)
T (x))
which concludes the proof of Lemma 1.
13

---

Under review as a conference paper at ICLR 2021
D PROOF OF THEOREM 3
It is quite intuitive to derive
R(f) = Ep pp(.,)) [((f(x),)))
- R p+ (x) [ar) +1] + -T (_) -1)]
π+
π
B (a) (2) [((f(x)), +1]
x m 1 (00) [(([(z)), +1)]
(Lemma 1)
n -
カー - Bp pp_ (w)) [([(()))
-1) {
TT - E (w) ((f(a)),-1)
(m) [[(())))
(,(( +
(=)) (n) (()()())) -1) ( +1)]
Rpc(S),
which concludes the proof of Theorem
E PROOF OF THEOREM 4
First of all, we introduce the following notations:
(f) = Ex, (a:) [(f(())) x+((((x)) 11),
a
((f(m))) +1) x =+((((a;)) -1)) Rf = Ep_ (a [[(f(2') -1) - =_(((x)) +1))
(f) n
(f) (eff(a)) -1) =((((((()+
In this way, we could simply represent Reo(f) and Rpc(f) as
RPC(f) (f) + Rpo(f), Rec(f) = Rf)(f) + (fc
Then we have the following lemma.
Lemma 2. The following inequality holds:
R(fec) R(f*) < 2 sup
feF RFc(f) R Rtp(()) + +2 sup Rfc(f) Rpo(f)
(9)
fEF
Proof. We could intuitively express R(Fpc) R(({) as
R(Fpc) R((*) = R(Fpc) - (pc()rc)) + RPc( - Rpc(S*) + Rpc( - R(S*)
[pC( Rpp(JPc) + (Pp( R Rpc( Rpc(
< sup SEF
Rpo(S) Rpo(l) +0+ sup RPc(A) Rpo(S)
fEF
= 2 sup SEF
Rpc(S) RPo(S)
< sup feF
[ (P) + sup R
fEF
where the second inequality holds due to Theorem 3.
As suggested by Lemma 2, we need to further upper bound the right hand size of Eq. (9). Before doing that, we introduce the uniform deviation bound, which is useful to derive estimation error bounds. The proof can be found in some textbooks such Mohri et al. (2012) (Theorem 3.1).
14

---

Under review as a conference paper at ICLR 2021
Lemma 3. Let Z be random variable drawn from probability distribution with density μ., H. {h: + [0. M]} (M > 0) be a class of measurable functions, {2,)i=1 be i.i.d. examples drawn
from the distribution with density μ.. Then, for any delto >> O, with probability at least 1 - 8,
log
sup hEH
E EN~Z [b(2)]
Σ h(2i)
29 (H) + M
2n
where Rr (H) denotes the (expected) Rademacher complexity (Bartlett & Mendelson, 2002) of H. with sample size nu over μ.
Lemma 4. Suppose the loss function É is p-Lipschitz with respect the first argument (0 p oc), and all the functions in the model class F are bounded, i.e, there exists a constant Cp such that Ilf Co for any E Let Ct SU E(Cb,t) For any 8 O, with probability 1 6,
log 4 8
RPFlf) Rpo(f) S (1+ +
sup
feF
Proof. By the definition of (f) and (f), we can obtain
E (m) [e(f(x), +1)] , n {(f(z))+1)
sup SeF
Rf - (f) S sup leF
n Σ
R (a) [([(()) -1]] Σ (((())), -1)
+ + sup fet
(10)
By applying Lemma 3, we have for any ō > 0, with probability 1-
log %
_ Σ (f(x). +1)
sup SEF
(p)(())(((()))
s 20 (eo Ctp
(1I)
2n
==1
and for any for any 0, with probability 6, 6,
(p)( -1)] - n
log a
sup
E
Σ ((f(x). S 29 (lo F)+ Cep
(12)
JEF
2n
where l e F means (lo // E F). By Talagrand's lemma (Lemma 4.2 in Mohri al. (2012)),
(e F P (F).
(13)
Finally, by combing Eqs. (10), (11), (12), and (13), have for any 0, with probability least
1 1-5, 6,
log 4 8
sup R Rtc (f) s $1 (F) + (1+ n Cr
(14)
JeF
2n
which concludes the proof of Lemma
Lemma 5. Suppose the loss function É is p-Lisschitz with respect the first argument (0 < p < oc), and all the functions in the model class F are bounded, ie., there exists a constant Cb such that ll Co for any E F. Let Ct sup E(Cb, t). For any 8 O, with probability 1 5,
log
RPo(f) Rpo( (1+ +1+
sup feF
2n
Proof. Lemma can be proved similarly to Lemma 4.
By combining Lemma 2, Lemma 4, and Lemma Theorem 4 is proved.
15

---

Under review as a conference paper at ICLR 2021
F PROOF OF THEOREM 5
Suppose there are pairs of paired data points, which means there are in total 2n data points.
For our Peomp classification problem, we could simply regard æ sampled from p+ (a: as (noisy)
positive data and x' sampled from p_(x') as (noisy) negative data. Given n pairs of examples
{(x,, == for the observed positive examples, there are actually p +1 = +1) true
positive examples; for the observed negative examples, there are actually p(y -1 = -1) true negative examples. From our defined data generation process Theorem 1, is intuitive to obtain
+ FT
plu = +1 y = +1)
$ + -- NTT-
- + -4
p -1
. + -ー_ + ĀĄ
Since o+ = p(u = -1 5 = 11 plu +1 ÿ = +1) and s- = - -1) =
1 pl 1), can obtain
x2
Φ+ = ply = ブ=
77 + + ,イ
#4 + + TT
+
0_ pl -
7 + + -ạオー
#7 x + π π4
In this way, we can further obtain the following noise transition ratios:
P+ = =pÿ 1 y +1) ply +1 5 11)p(= -1)
n 2( + + + x4 π-) 5_
ply = +1)
p_ = p = +1 = -1) ply 1 1 5 +1)p(p==+)
p(u = -1)
2( + n2 T4
where p(ū 1) p(ū 1)
1/4 because have the same number of observed positive
examples and negative examples.
G PROOF OF THEOREM 7
First of all, we introduce the following notations:
(f) = Ep, (m) +1)()) e PP]].
R. (f) = Σ (e(f(z;) e PP]).
π 1m1
(f) Ex (w') [[[]((]), - NNj]
(F)
1
-1)I(a) NŇI)
n
In this way, we could simply represent Rppo(f) (f) and Rppo(f)
1 -- - R ( + 1- p- RT) Ropo(f) -- p+
1 _
1
1
Rppc(f)
(f + --
p_ (f)
Then we have the following lemma.
Lemma 6. The following inequality holds:
R(S(PC)- - (R)T) < 1 p+ feF
2
sup R (t) - ()) + 1-p- feF
2
Rppc(f) n ())
sup
(15)
16

---

Under review as a conference paper at ICLR 2021
Proof. We omit the proof of Lemma 6 since it is quite similar to that of Lemma 2.
As suggested by Lemma 6, we need to further upper bound the right hand size of Eq. (15). According Lemma have the following two lemmas.
Lemma 7. Suppose the loss function & is p-Lipschitz with respect to the first argument (0 < p < oc), and all the functions in the model class F are bounded, i.e., there exists a constant C. such that Ilf Cb for any f E F. Let Ce SUP: [(z,t). For any > O, with probability 1 6,
log
(f) - R (f) - 2p (F) + C.p
sup SEF
2n
Lemma 8. Suppose the loss function E is p-Lipschitz with respect to the first argument (0 < p < oc), and all the functions in the model class F are bounded, i.e., there exists a constant C, such that ll S Coror for any f E F. Let Ce == SuP=SCo.t=11 E(z,t). For any > O, with probability 1 6,
log
(S) Raro(() 2 (F) Ce feF
sup
2m
We omit the proofs of Lemma 7 and Lemma since they are similar that of Lemma By combing Lemma 6, Lemma 7, and Lemma 8, Theorem 7 is proved.
H SUPPLEMENTARY INFORMATION OF EXPERIMENTS
Table 3 reports the specification of the used benchmark datasets and models.
M (LeCun et al., 1998). This is a grayscale image dataset composed of handwritten digits from to 9 where the size of the each image is 28 x 28. It contains 60,000 training images and 10,000 test images. Because the original dataset has 10 classes, regard the even digits as the positive class and the odd digits as the negative class.
-aShion-MNIST
(Xiao al., 2017). Similarly to MNIST, this is also a grayscale image dataset composed of fashion items ('T-shirt', 'trouser', 'pullover', 'dress', 'sandal', ; 'coat', 'shirt', 'sneaker', 'bag'. and 'ankle boot'). It contains 60,000 training examples and 10,000 test examples. It is converted into binary classification dataset as follows:
The positive class is formed by 'T-shirt', 'pullover', 'coat', 'shirt', and 'bag'. The negative class formed by 'trouser', 'dress', 'sandal', 'sneaker', and 'ankle boot'.
Kuzushiji-MNIST- (Netzer al., 2011). This is another grayscale image dataset that is similar to MNIST. It is 10-class dataset of cursive Japanese ("Kuzushiji") characters. consists 60,000 training images and 10,000 test images. It is converted into binary classification dataset follows:
The positive class is formed by 'o', 'na", 'ma', 're.
The negative class formed by 'ki', "tsu", "ha", "wo".
CIFAR-10 (Krizhevsky et al., 2009). This also a color image dataset of 10 different objects ('airplane', 'bird', 'automobile", 'cat', 'deer', 'dog'. 'frog', 'horse", 'ship' and 'truck'), ), where the size of each image is 32 x 32 There are 5,000 training images and 1,000 test images per class. This dataset is converted into binary classification dataset as follows:
The positive class is formed by 'bird', 'deer', 'dog'. 'frog', 'cat', and "oorse".
The negative class formed by 'airplane', 'automobile', 'ship', and 'truck'.
1ecun com www.c//n...o//ee///iiiitetttttt. www.::echhhissiiimimiiimmmm htcppp/s/wwe.....coorttttetettee htm1
17

---

Under review as a conference paper at ICLR 2021
Table 3: Specification of the used benchmark datasets and models.
Dataset
Train
# Test
Features
# Classes
Model
MNIST
60,000
10,000
784
10
MLP (d-300-300-300-300-1
Fashion-MNIST
60,000
10,000
784
10
MLP (d-300-300-330-3300-)
KuzUShiji-NNIST
60,000
10,000
784
10
MLP (d-300-300-330-300--)
CIFAR-10
50,000
10,000
3,072
10
ResNet-34
USPS
7,437
1,861
256
10
Linear Model (d-1)
Pendigits
8,793
2,199
16
10
Linear Model (d-1)
Optdigits
4.495
1,125
62
10
Linear Model (d-1)
CNAE-9
864
216
856
Linear Model (d-1)
USPS, Pendigits, Optdigits. These datasets are composed of handwritten digits from 0 to 9. Be- cause each the original datasets has 10 classes, we regard the even digits as the positive class and the odd digits as the negative class.
CNAE-9, This dataset contains 1,080 documents of free text business descriptions of Brazilian companies categorized into subset of categories cataloged in table called National Classification of Economic Activities.
The positive class is formed by '2', '4', '6' and '8'
The negative class is formed by '1', '3', '5', '7' and '9'.
For MNIST, Kuzushiji-MNIST, and Fashion- -MNIST, we set learning rate to 1e- 1 and weight decay to - 5. For CIFAR-10, we set learning rate to le and weight decay to le We also list the number of pointwise corrupted examples used for model training each dataset: 30,000 for MNIST, Kuzushiji-Min MNISS, Fashion-MNIST, and CIFAR-10; 10; 4,000 for USPS; 5,000 for Pendigits; 2,000 for Optdigits; 400 for CNAE-9.
18


Reviews:
[{"review_id": "iquh89P9Pja", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper: \nThe paper studies binary classification with pairwise comparisons as the supervision. Instead of the traditional pointwise supervision, the paper assumes only access to pairs of examples $x,x'$ where we believe that $p(y=1|x)\\geq p(y=1|x')$. The authors considers two kinds of methods. The first one considers x, x' be sampled from two different distributions, and uses the method from Unlabeled-Unlabeled (UU) classification to obtain an unbiased risk estimator. The second one is the RankPruning method, where a fraction of data with highest confidence is selected and is used to derive a URE on the selected samples. The paper proposes to add a moving-average regularization to RankPruning. The authors performed experiments on 2-class versions of standard benchmark datasets. In general RankPruning with regularization performs the best in most cases, but the first method is also competitive.\n\nReview: \nThe paper studies an important problem of learning classification from pairwise comparisons. I have some doubts though:\n\ta) The paper assumes a generative process of the pairs: Generally, it assumes a rejecting sampling process. If we sample $(x,x')$ with $y=-1,y'=+1$, then we reject it; otherwise we keep it. Why is this correct? Do we have data supporting this process? I may suggest other models: E.g., return $(x',x)$ if $y=-1,y'=+1$, and $(x,x')$ otherwise. Is this also plausible? How can we test what generation method is used?\n\tb) Another bigger problem is that the method ignores the PAIR nature of the problem; the method basically ignores the pairs and just treat list of $x, x'$ as from different distributions. We naturally loses the information that $p(y=1|x)\\geq p(y=1|x')$. Is this a good method? Can we use other methods to utilize the pair information, such as siamese networks? How does the performance compare?\n\tc) In general the paper lacks a bit novelty - the first method is an adaptation of UU estimator, and the second method is just adding a regularization to RankPruning.\n\nMinor Comments:\n\ta) Second paragraph in Sec 3 - the paragraph is a bit unclear to me. Can you state the generation process formally?\n\tb) Classification with pairwise comparisons is also considered in these works:\n\tXu, Y., Zhang, H., Miller, K., Singh, A., and Dubrawski, A. Noise-tolerant interactive learning from pairwise comparisons with near-minimal label complexity. NIPS2017.\n\tD. M. Kane, S. Lovett, S. Moran, and J. Zhang. Active classification with comparison queries. FOCS 2017.\nBoth papers use a small amount of labeled data; but they considers the pair information.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GRFDMUsYrnY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper develops a method to learn a binary classifier based only on pairwise comparison data. For example, the classifier learns to classify pictures of people as \"adult\" versus \"child\" based on pairwise comparisons of the form \"person C is older than person X\". The authors derive their method based on an empirical risk minimization argument. The authors test their methods on four standard data sets (three MNIST variants and one more). They compare to some baselines including binary biased, noisy unbiased, and RankPruning. They try 4 different variations of their method. The Pcomp-Teacher model performs especially well.\n\nThe paper develops some interesting ideas, but the main problem is that the authors say that their pairwise comparison (Pcomp) classification is novel, but it is not. For example, see this blog post: https://blog.ml.cmu.edu/2019/03/29/building-machine-learning-models-via-comparisons/\n\nAnd this paper:\n\nNoise-tolerant interactive learning using pairwise comparisons.\nYichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, Artur W Dubrawski. NIPS'17: Proceedings of the 31st International Conference on Neural Information Processing Systems December 2017 Pages 2428–2437\nhttps://dl.acm.org/doi/10.5555/3294996.3295004\n\nAs the blog post points out, learning to rank is very related and there are hundreds of papers on learning to rank.\n\nUsually pairwise comparisons are motivated as easier for people to do (lower cost labels to obtain). For example, it's easier to tell if one person is older than another than to guess the age of a person. The authors motivate pairwise comparison differently. They say it is better for privacy. Why are pairwise comparisons better for privacy? Given enough pairwise comparisons, the original order can be uncovered, so there are limits to the privacy advantage that the authors don't discuss. In general, the privacy motivation needs to be more clear.\n\nPairwise can sometimes be harder to judge than pointwise, for example which of two pictures of a cat is \"more\" cat than the other? Or which of two laptop computers is \"more cat-like\" than the other?\n\nThe authors must get some small amount of pointwise data, or they have some assumption that I missed, like the base label frequencies are known. For example, what if we try to learn a dog/cat classifier using pairwise comparisons that are 100% cats? How can the classifier possibly know that all the images are cats without *some* pointwise labels? All we know from pairwise comparisons is which cat is the most and least dog-like. There is no way to know how to draw the line without some pointwise labels or other modeling assumption. The blog post above discusses this.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4MLe5eCNRN", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors addressed the problem of 'Pcomp', a weakly supervised binary classification setting where the dataset only includes pairs of unlabeled data with an indicator of which one is more likely to be positive than the other (unlike pointwise labeled data in classical binary classification). The setting could be useful in privacy-preserving applications.\n\nAuthors proposed a generative model for pairwise data comparison, for which unbiased risk estimators could be obtained, and this crucially helps them to obtain a theoretical bound on the empirical risk minimizer.\n\nI have a slight concern about the practicability of the assumed comparison model (Sec 3) which only provides examples like (+1+1), (+1,-1), (-1,-1)? The theoretical proof does not go through without unbiased risk estimators, which in this is obtainable because of Thm 1 and 2, but these are very specific to the above assumption on the generative model? But I think it is an okay assumption and the bare minimum for any practical purpose.\n  \nAlso, can you comment on the tightness of the current bound say Thm. 4 in terms of n (for this specific generative model).\n\nOverall I found the paper is easy to understand and well structured. \n\nTwo interesting follow-up questions:\n- It would interesting if the authors can add some comments about the possibility of extending the work to a multiclass classification setting.\n- Another interesting direction could be to understand the performance limits for the case where instead of two the learner is allowed to see the relative class probabilities of a larger subset of items. Is the current method directly extendable to such a setting and how do we expect to see the estimation error bound varying with the subsetsize?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been evaluated  by three expert reviewers, two of whom recommended rejection and one acceptance. Two of the three reviews are particularly detailed and thorough. Both point out a few points of conceptual issues that leave the reader confused. These key issues have not been addressed sufficiently in the rebuttal to result in changing the reviewers' assessments. One major concern is lacking novelty of the work as presented, which limits its current utility to the ICLR audience. I recommend a rejection.
Decision: Reject