Binary Classification with Confidence Difference
Authors: Wei Wang
Lei Feng
Yuchen Jiang
Gang Niu
Min-Ling Zhang
Masashi Sugiyama
Venue: NeurIPS 2023 poster (2023)
Keywords: Weakly supervised learning
binary classification
unbiased risk estimator
TL;DR: The difference of confidence labels on unlabeled data pairs, as a novel type of weak supervision, is sufficient to train binary classifiers with theoretical guarantees.

Abstract: Recently, learning with soft labels has been shown to achieve better performance than learning with hard labels in terms of model generalization, calibration, and robustness. However, collecting pointwise labeling confidence for all training examples can be challenging and time-consuming in real-world scenarios. This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification. Instead of pointwise labeling confidence, we are given only unlabeled data pairs with confidence difference that specifies the difference in the probabilities of being positive. We propose a risk-consistent approach to tackle this problem and show that the estimation error bound achieves the optimal convergence rate. We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven. Extensive experiments on benchmark data sets and a real-world recommender system data set validate the effectiveness of our proposed approaches in exploiting the supervision information of the confidence difference.

Binary Classification with Confidence Difference
Wei Wang 1,, Lei Feng2.?, Yuchen Jiang', Gang Niu", Min-Ling Zhang", Masashi Sugiyama" 2.1
1 'Te University of Tokyo, Chiba, Japan
RIKEN Center for Advanced Intelligence Project, Tokyo. Japan
3 Nanyang Technological University, Singapore
4 Alibaba Group, Beijing, China
Southeast University, Nanjing, China
wangwog ecc tokyoo .p. lfenggaq@gmail. com
j jyc.alibababbbaaaaaaaoaaaa inc. com
gang.nnig ml@gmail.....mmmmmmmmmmmmmmmmm com
zhangml@seu edu, cn sugiōk Fari0k.u-tkyor u-tokyo..c...... Jc.
Abstract
Recently, learning with soft labels has been shown achieve better performance than learning with hard labels terms of model generalization, calibration, and robustness. However, collecting pointwise labeling confidence for all training examples can be challenging and time-consuming in real-world scenarios. This paper delves into novel weakly supervised binary classification problem called confidence-diffrrence (ConfDiff) classification. Instead of pointwise labeling con- fidence, given only unlabeled data pairs with confidence difference that specifies the difference in the probabilities of being positive. We propose a risk- consistent approach to tackle this problem and show that the estimation error bound achieves the optimal convergence rate, We also introduce a risk correction ap- proach to mitigate overfitting problems, whose consistency and convergence rate are also proven. Extensive experiments on benchmark data sets and real-world recommender system data validate the effectiveness of our proposed approaches in exploiting the supervision information of the confidence difference.
Introduction
Recent years have witnessed the prevalence of deep learning and its successful applications. However, the success is built on basis of the collection of large amounts data with unique and accurate labels. However, in many real-world scenarios, it is often difficult to satisfy such requirements. To circumvent the difficulty, various weakly supervised learning problems have been investigated accordingly, including but not limited to semi- superviie learning 2 4. sabel-noise learning (5
6, 7 9. positive-unlabeled learning
10
11 12], partial-label learning 13
14
15
16
unlabeled-unlabeled learning 18 19 and similarity- -hased classification 20 22
Learning with soft labels has been shown to achieve better performance than learning with hard labels in the context of supervised learning [23] 24], where each example is equipped with pointwise labeling confidence indicating the degree to which the labels describe the example. The advantages
have been validated in many aspects, including model generalization 25 26), calibration [27] 28 and
robustness 29 30). For example, with the help of soft labels, knowledge distillation [25 31 transfers
knowledge from large teacher network to a small student network. The student network can be
trained more efficiently and reliably with the soft labels generated by the teacher network [32 33 34
However, collecting large number of training examples with pointwise labeling confidence may be demanding under many circumstances since it challenging describe the labeling confidence for each training example exactly [35] 36 37). Different annotators may give different values of pointwise
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

labeling confidence to the same example due to personal biases, and it has been demonstrated that skewed confidence values can harm classification performance [36.. Besides, giving pointwise labeling information to large-scale data sets is also expensive, laborious, and even unrealistic in many
real-world scenarios [X 39 9.. On the contrary, leveraging supervision information of pairwise comparisons may ameliorate the biases of skewed pointwise labeling confidence and save labeling costs, Following this idea, we investigate a more practical problem setting for binary classification in this paper, where we are given unlabeled data pairs with confidence difference indicating the difference in the probabilities of being positive. Collecting confidence difference for training examples in pairs is much cheaper and more accessible than collecting pointwise labeling confidence for all the training examples.
Take click-throug rate prediction in recommender systems 44 for example. The combinations of users and their favorite/disliked items can be regarded as positive/negative data. Collecting training data takes work to distinguish between positive and negative data. Furthermore, the pointwise labeling confidence of training data may be difficult to be determined due the extraordinarily sparse and class- mass-imbalaacee problems [42]. Therefore, the collected confidence values may be biased. However, collecting the difference in the preference between a pair of candidate items for given user is more accessible and may alleviate the biases. Section 4 will give real-world case study of this problem. Take the disease risk estimation problem for another example. Given a person's 's attributes, the goal is to predict the risk of having some disease. When asking doctors to annotate the probabilities of having the discase for patients, it takes work to determine the exact values of the probabilities. Furthermore, the probability values given by different doctors may differ due to their diverse backgrounds. On the other hand, it is much easier and less biased to estimate the relative difference in the probabilities of having the disease between two patients. Therefore, the problem of learning with confidence difference is of practical research value, but has yet to be investigated in the literature.
As related work, Feng et al. [3 elaborated that a binary classifier can be learned from pairwise comparisons, termed Peomp classification. For a pair of samples, they used a pairwise label of one is being more likely to be positive than the other. Since knowing the confidence difference implies knowing the pairwise label, our method requires stronger supervision than Poomp classification. Nevertheless,
argue that, in many real-world scenarios, may not only know one example is more likely to be positive than the other, but also know how much the difference in confi- dence is, as explained in the above examples. Therefore, the set- ting of the current paper is not restrictive compared with that of Pcomp classification. Furthermore, our setting is more flexi- ble than that of Pcomp classification from the viewpoint of data generation process. Pcomp classification limits the labels of pairs of training data be {(+1, +1), -1), --), To cope with collected data with labels (-1,+1), they either discard them or reverse them as (+1,-11 1). On the contrary, our setting is more general and we take the examples from (-1,+1) also into consideration explicitly in the data distribution assump- tion. Figure| [ shows the results of a pilot experiment. Here, Strategyl denotes Ccomp-Teacher [43] discarding examples from
1.09
alegy2
0.95
stegy22
0.93
0.85
0.90
0.70
MNiST
KuninNi
Fastion
data set
Figure Experimental results for different strategies of handling ex- amples from (-1,+1).
(-1,+1 while Strategy2 denotes Peomp-Teacher reversing examples from (-1,+1) We can observe that both strategies perform ac- tually similarly. Since Strategy1 loses many data, is intuitively expected that Strategy2 works much better, but the improvement is actually marginal. This may be because the training data distribution after reversing differs from the expected one. On the contrary, in this work we take examples from (1) into consideration directly, which is more appropriate way to handle these data.
Learning with pairwise comparisons has been investigated pervasively in the community 44
45
46
47 48 49 50) with applications in information retrieval (51), computer vision (52) regression 53
crowdsourcing [55] (56), and graph learning (57]. It is noteworthy that there exist distinct differences between our work and previous works on learning with pairwise comparisons. Previous works have mainly tried to learn a ranking function that can rank candidate examples according to relevance or preference. In this paper, we try to learn pointwise binary classifier by conducting empirical risk minimization under the binary classification setting.
54
Our contributions are summarized as follows:
2

---

We investigate confidence-differeeee (ConfDiff) classification, novel and practical weakly super- vised learning problem, which can be solved via empirical risk minimization by constructing an unbiased risk estimator. The proposed approach can be equipped with any model, loss function, and optimizer flexibly.
An estimation error bound is derived, showing that the proposed approach achieves the optimal parametric convergence rate. The robustness is further demonstrated by probing into the influence of an inaccurate class prior probability and noisy confidence difference.
To mitigate overfitting issues, a risk correction approach [19] with consistency guarantee is further introduced. Extensive experimental results benchmark data sets and real-world recommender system data set validate the effectiveness of the proposed approaches.
Preliminaries
In this section, we discuss the background of binary classification, binary classification with soft labels, and Peomp classification. Then, we elucidate the data generation process of ConfDiff classification.
2.1 Binary Classification
For binary classification, let X' = Rd denote the d-dimensional feature space and y = {+1, -1} denote the label space. Let p(æ, y) denote the unknown joint probability density over random variables (z, E X x y. The task of binary classification is to learn a binary classifier g X - IR which minimizes the following classification risk:
R(g) = Epte.p/ [[)(()),
where .) is a non-negative binary-class loss function, such as the 0-1 loss and logistic loss. Let T ply +1) and π p'y = -1) denote the class prior probabilities for the positive and negative classes respectively. Furthermore, p. (a)) p(zlyy +1) and p=(x) = p(acy = 1)
denote the class-conditional probability densities of positive and negative data respectively. Then the classification risk in Eq. ( can equivalently expressed as
R(g)= = π Ep (<)) (<)()() +1) + - E.
-1)]
2.2 Binary Classification with Soft Labels
When the soft labels of training examples are accessible to the learning algorithm, taking advantage of them can often improve the generalization performance 23]. First, the classification risk in Eq. ① can be equivalently expressed as
R(g) = px)) ip(y = +( +1) + ply = -1=)\(()))
Then, given training data equipped with confidence { /=) where T4 p(y: = + lx,) is the pointwise positive confidence associated with æ;, we minimize the following unbiased risk estimator to perform empirical risk minimization:
1 E"_ "" (r:((((,))) +1) r:)(((()))) -1)) n
Recat (g)
However, accurate pointwise positive confidence may be hard to be obtained in reality (36
2.3 Pairwise-Comparison (Pcomp) Classification
In principle, collecting supervision information of pairwise comparisons is much easier and cheaper than pointwise supervision information (3) Pcomp classification [43, we are given pairs of unlabeled data where we know which one is more likely to be positive than the other. is assumed that Pcomp data are sampled from labeled data pairs whose labels belong to {(+1, -1) 1), +1),+),(-1,,
Based on this assumption, the probability density of Pcomp data (æ, (x,x") is given as q(x, (=3 + x² + πчオ-) where q(x,x') = nーp+ (x)p+(x') - x"p= (æ)p (x') + -- (--+((x)p- (x'). Then, an unbiased risk estimator for Pcomp classifica-
tion is derived as follows:
R n ""n (E(g(z)), +1) + ((g(2)), -1) - (l(((()))) 1) {_g((()) +1)). (5)
3

---

In real-world scenarios, we may not only know one example is more likely to be positive than the other, but also know how much the difference confidence is. Next, novel weakly supervised learning setting named ConfDiff classification is introduced which can utilize such confidence difference.
2.4 Confidence-Differeeee (ConfDiff) Classification
In this subsection, the formal definition of confidence difference is given firstly. Then, elaborate the data generation process of ConfDiff data. Definition (Confidence Difference). The confidence differrence c( x') between an unlabeled data pair (x, x²) is defined as
c(x, x²) = ply' = -(y +1/x).
(6)
As shown in the definition above, the confidence difference denotes the difference in the class posterior probabilities between the unlabeled data pair, which can measure how confident the pairwise comparison is. In ConfDiff classification, we are only given unlabeled data pairs with confidence difference D (((xx,,))) (.).)))))))))) )= Here, c = c( æ;)) is the confidence difference for the unlabeled data pair (æ;, æ.). Furthermore, the unlabeled data pair (æ;, mx{) is assumed to be drawn from probability density p(æ, x') = (()))((x') This indicates that æ; and a are two i.i.d. instances sampled from p(x)). It is worth noting that the confidence difference e; will be positive the second instance x! has higher probability to positive than the first instance 2;, and will be negative otherwise. During the data collection process, the labeler can first sample two unlabeled data independently from the marginal distribution p(æ), then provide the confidence difference for them.
The Proposed Approach
In this section, we introduce our proposed approaches with theoretical guarantees. Besides, we show the influence an inaccurate class prior probability and noisy confidence difference theoretically. Furthermore, we introduce risk correction approach to improve the generalization performance.
3.1 Unbiased Risk Estimator
In this subsection, show that the classification risk in Eq. ① can be expressed with ConfDiff data in an equivalent way.
Theorem 1. The classification risk R(g) in Eq. i can be equivalently expressed as
RcD(g) pp) (C(x, x') + f(x', x))]
where
C(x,x') (T+ - (x)xx')))(((()) +1) (a_ c(x, (()g(())) -1).
Accordingly, we can derive an unbiased risk estimator for ConfDiff classification:
RCD(O)
1 1
-n (C(ar,, L(xl, m:)).
(8)
2n
Minimum-variance risk estimator. Actually, Eq.
8 one of the candidates of the unbiased risk
estimator. We introduce the following lemma:
Lemma 1. The following expression is also an unbiased risk estimator:
(aL(aa + ((/,))
where a E [0, 1] is an arbitrary weight.
Then, introduce the following theorem:
Theorem 2. The unbiased risk estimator Fg. 8 has the minimum variance among all the candidate unbiased risk estimators in the form of Eq. W.E.t [0, 1).
Theorem indicates the variance minimality of the proposed unbiased risk estimator in Eq. (8) and adopt this risk estimator in the following sections.

---

3.2 Estimation Error Bound
In this subsection, we elaborate the convergence property of the proposed risk estimator RED (g) by giving estimation error bound. Let fg X + R denote the model class. is assumed that there exists some constant Cg such that sup geg supgeg l I Cg and some constant Ce such that sup|siso, {(z, y) I Ct. We also assume that the binary loss function {(2,)) y) is Lipschitz continuous for = and y with a Lipschitz constant Ly. Let 9 = arg mingeg R(g) denote the minimizer of the classification risk in Eq. and ICD arg mingeg RcD(g) denote the minimizer of the unbiased risk estimator in Eq. 8 The following theorem can be derived:
Theorem 3. For any 8 > 0, the following inequality holds with probability at least 1 8:
In 2/8
R(ŌCD) RR(g)) (L) 4Cz/
(10)
where Rr, denotes the Rademacher complexity of 9 for unlabeled data with size n.
From Theorem 3 we can observe that as 7l - o0, R(īcD) - RR(g)) because (g) - 0 for all parametric models with bounded norm, such as deep neural networks trained with weight decay [58). Furthermore, the estimation eπrоr bound converges in O (p(L/vn) where Op denotes the order in probability, which the optimal parametric rate for empirical risk minimization without making additional assumptions [59].
3.3 Robustness Risk Estimator
In the previous subsections, it was assumed that the class prior probability is known in advance. In addition, it was assumed that the ground-truth confidence difference of each unlabeled data pair is accessible. However, these assumptions can rarely be satisfied in real-world scenarios, since the collection of confidence difference is inevitably injected with noise. In this subsection, we theoretically analyze the influence of inaccurate class prior probability and noisy confidence difference on the learning procedure. Later in Section 4.5 we will experimentally verify our theoretical findings.
Let D (((x,,,;)) a)), denote n unlabeled data pairs with noisy confidence difference, where is generated by corrupting the ground-truth confidence difference c; with noise. Besides, let n. denote the inaccurate class prior probability accessible to the learning algorithm. Furthermore, let RgD(g) denote the empirical risk calculated based on the inaccurate class prior probability and noisy confidence difference. Let ICD = arg min yeg ReD (g) denote the minimizer ReD(g). Then the following theorem gives an estimation error bound:
Theorem 4. Based the assumptions above. for any 8 O, the following inequality holds with probability at least 8:
2n
4C En l2 cal +C, 7 -Tl. (11)
- S 16L + SC
2n +
Theorem 4 indicates that the estimation error is bounded by twice the original bound in Theorem with the mean absolute error of the noisy confidence difference and the inaccurate class prior probability. Furthermore, if >i | já - ojl has sublinear growth rate with high probability and the class prior probability is estimated consistently, the risk estimator can be even consistent. It elaborates the robustness of the proposed approach.
3.4 Risk Correction Approach
is worth noting that the empirical risk in Eq. (8) may be negative due to negative terms, which is unreasonable because of the non-negative property of loss functions. This phenomenon will result
severe overfitting problems when complex models are adopted [19 22 43. circumvent this
difficulty, we wrap the individual loss terms in Eq. (8) with risk correction functions proposed in Lu al. [19), such as the rectified linear unit (Rel.U) function f(z) = max(0, 2) and the absolute value
function f(z) = |z]. In this way, the corrected risk estimator for ConfDiff classification can be
5

---

expressed as follows:
RCD(O) 2n
(f (++ -))(()))))))))))))))))))))))) + - (T- c(((g(a)))) 1)) +1))
(T_ ())(g(())) -1)) (12)
Theoretical analysis. We assume that the risk correction function f=) is Lipschitz continuous with Lipschitz constant L. For ease of notation, let A(g) = ( 4: (g)((((())))))) (z) +1)/2n, B(g) (=)(T==))((((()) - 2m, C(g) = (T_
+1) and ((g) = (T=
c)((g(()), From Lemma in Appendix A the values of B[A()) ([)())), E(C(g), and [(D(g)] are non-negative. Therefore, we assume that there exist non son-negative constants a, b, c, and d such that E[A(g)] 2 a, (l)(g) 2 6, B[C(g) 2 C, and E ((D()) 2 d. Besides, let GCD arg migming (g) denote the minimizer of RCD(g). Then, Theorem is provided to elaborate the bias and consistency of RCD(g).
Theorem Based on the assumptions above, the bias of the risk estimator (g) decays exponen- tially as + 0c:
0 S B[Ren(y)) - R(g) < 2 + 1)C,4,
(13)
e where A exp (-2a2n /n/C) + exp (-2b2n/C3 + exp
(-2c2n/ e-
+exp exp Further-
more, with probability at least 1 we have
In 2/2
[RD(g)) RRg)) S
5 2C
+ 2(1, + 1)CCA
(14)
2n
Theorem 5 demonstrates that RoD R(g) in (p(1/ /n). which means that RCD(g) is biased yet consistent. The estimation error bound of JCD analyzed in Theorem 6
Theorem 6. Based on the assumptions above, for any 8 > 0, the following inequality holds with probability at least - 8:
1n2/8
R(āCD) - R(g") < ( + 1)V
- 4(4, 1
(15)
2n
Theorem 6 clucidates that as n + oc, R(GCD) + R(g"), since (9) + 0 for all parametric models with bounded norm 660 and A - Furthermore, the estimation error bound converges in
Op(1/ Vn), which is the optimal parametric rate for empirical risk minimization without additional assumptions (59]
Experiments
In this section, we verify the effectiveness of our proposed approaches experimentally.
4.1 Experimental Setup
We conducted experiments on benchmark data sets, including MNIST 61. KuzushijiMNNIST (22.
Fashion-MNIST (63) and CIFAR-10 (64) In addition, four UCI data sets 65 were used, including Optdigits, USPS, Pendigits, and Letter. Since the data sets were originally designed for multi-class classification, we manually partitioned them into binary classes. For CIFAR-10 10, used ResNet- 34 [66] as the model architecture. For other data sets, we used a multilayer perceptron (MLP) with three hidden layers of width 300 equipped with the ReLU [67] activation function and batch normalization [68] The logistic loss is utilized to instantiate the loss function &.
It is worth noting that confidence difference is given by labelers in real-world applications, while it was generated synthetically in this paper to facilitate comprehensive experimental analysis. We firstly trained probabilistic classifier via logistic regression with ordinarily labeled data and the same neural network architecture. Then, we sampled unlabeled data pairs at random, and generated the class posterior probabilities by inputting them into the probabilistic classifier. After that,

---

Table 1: Classification accuracy (tea of each method on benchmark data sets with different class priors, where the best performance (excluding Oracle) is shown in bold.
Class Prior
Method
MNIST
Kuzushiji
Fashion
CIFAR-10
Peomp-Unbiased
0.761=0.017
0.637=0.052
0.737=0.050
0.776=0.023
Peomp-Rel.U
0.800=00.000
0.800-00.000
0.800=000000
0.800=0.000
Pcomp-ABS
0.800+00.000
0.800+000000
0.800++00000
0.800=00000
Peamp-Teacher
0.965+00.010
0.871+0.046
0.853+0.0017
0.836=000119
4 0.2
Oracle-Hard
0.990-0.000
0.939100000
0.97910.001
0.89410.003
Oracle-Soft
0.989-100001
0.939-10.004
0.97910.001
0.893=0.003
ConIDiff- Unbiased
0.78910.041
0.672:10.053
0.855
0.789
ConfDiff-Raa Reeif
0.968=0.003
0.860=0.017
0.964=0.004
0,844=0.020
ConfDiff-ABB
0.975=00003
0.098=0.003
0.965=0.002
0.862=0.015
Pcomp-Unbiase
0.712:10.020
0.006
0..23
0.703
Pcomp-ReLLU
0.502-10.003
0.502-10.044
0.000
0,602-10032
Pcomp-ABS 0.842=0.012
0.727=0.008
0.851
0.58
Pcomp-Teacher 0.893=0.014
0.782
0.903=0.016
0.779=0.016
T4 = 0.5
Oracle-Hard 0.985+00001
0.906=00000
0.929=00002
0.976=0.001
0.871=0.003
Oracle-Soft
0.928
0.978+00000
0,877=0.002
Cont 0.911+0.006
0.712+0.046
0.896+00003
0.720-0.024
ConfDiff-Rel.U
0.944+0.011
0.805
0.960+00003
0.830=0.007
ConfDiff-ABS
0.96411.0011
0.86710.006
0.007
0.843
Unbiased
0.799110000
0.679
0.81310.029
0.737
Pcomp-ReL.U
0.910=#0031
0.775+0.022
0.897=0.023
0.851=00010
Pcomp-ABS
0.854+00002
0.036
0.921
0.849=0.007
Teapher
0.943+000026
0.814=0.027
0.936=0.014
0,821=0.003
T4 0.8
Oracle-Hard
0.9911100011
0.002
0.909
0.897
Oracle-Soft
0.990-10.002
0.040
0.900
0.004
ConiDDif-Unbiasse
0.792.10.017
0.758
0.810
0.794
ConfDiff-RRad ReLU
0.970=0.004
0.886=00.009
0.970=0.002
0,851=0.012
ConfDiff -AB
0.983=10.002
0.915=0.001
0.975=0.002
0.874=0.011
generated confidence difference for each pair of sampled data according to Definition T To verify the effectiveness of our approaches under different class prior settings, we set π④ E (0.2, 0.5, 0.8) for all the data sets. Besides, we assumed that the class prior T was known for all the compared methods. We repeated the sampling-and and-training procedure for five times, and the mean accuracy as well as the standard deviation were recorded.
We adopted the following variants of our proposed approaches: 1) ConfDiff-Unbiased which denotes the method working by minimizing the unbiased risk estimator; 2) ConfDiff- ReLL,, which denotes the method working by minimizing the corrected risk estimator with the ReLU function as the risk correction function; 3) ConiDiff-ABS, which denotes the method working by minimizing the corrected risk estimator with the absolute value function as the risk correction function. We compared our proposed approaches with several Peomp methods (43), including Pcomp- Unbnp--dbiased,, Pcomp- ReLU, Pcomp-ABS, and Scomp-Teecher. We also recorded the experimental results of supervised learning methods, including Oracle-Hard having access to ground-trute truth hard labels and Oracle-Sor Soft having access to pointwise positive confidence. All the experiments were conducted on NVIDIA GeForce RTX 3090. The number of training epoches was set to 200 and we obtained the testing accuracy by averaging the results in the last 10 epoches. All the methods were implemented in PyTorch [69]. We used the Adam optimizer [70]. To ensure fair comparisons, We set the same hyperparameter values for all the compared approaches, where the details can be found in Appendix
4.2 Experimental Results
Benchmark data sets. Trepots detailed experimental results for all the compared methods on four benchmark data sets. Based on Table [] we can draw the following conclusions: a) On all the cases of benchmark data sets, our proposed ConfDiff-ABS method achieves superior performance against all of the other compared approaches significantly, which validates the effectiveness of our approach in utilizing supervision information of confidence difference; b) Pcomp- -eacher achieves
7

---

Table 2: Classification accuracy (mean=istd) of each method UCI data sets with different class priors, where the best performance (excluding Oracle) is shown in bold.
Class Prior
Method
Optdigits
USPS
Pendigits
Letter
Coomp-Unbiased
0.771=0.016
0.721=0.046
0.743=0.057
0.757=0.028
Peomp-Rel.U
0.800+000000
0.800+00.000
0.800=00.000
0.800=0.000
Pcomp-ABS
0.800+0.0011
0.800+000000
0.800++0.000
0.800=000000
Peamp-Teacher
0.901+0..03
0.894+000233
0.928+0.0119
0.883+0.006
0.2
Oracle-Hard
0.990-0.002
0.98410.002
0.99710.000
0,97810,003
Oracle-Soft
0.990-10.003
0.984
0.00810.001
0.971
ConiDiff- Unbiased
0.83110.008
0.840
0.86510.077
0.732-10.053
ConfDiff-Raa ReEif
0.953=00014
0.957=0.007
0.987=0.003
0.929=0.008
ConfDiff-ABB
0.963=0.009
0.960=0.005
0.988=0.002
0.942=0.007
Pcomp-Unbiase
0.651110.112
0.0090
0,748 10.038
0.632.10.019
Pcomp-ReLLU
0.630-10.076
0.55410.008
0.514
0.005
Pcomp-ABS 0.787=#0031
0.814=0.018
0.793=0.017
0.748=0.031
Pcomp-Teacher
0.890=0.009
0.860=0.012
0.883=0.018
0.864=0.024
74 = 0.5
Oracle-Hard 0.988=00003
0.980=0.003
0.997=0.001
0.975=0.001
Oracle-Soft 0.987+-0.03
0.980+00.003
0.997+000001
0.967=0.006
Cont 0.917+00006
0.936+0.010
0.945+00052
0.755=0.041
ConfDiff-Rel.U
0.921+0.011
0,945+000009
0.981+0.004
0.895
ConfDiff-ABS
0.002
0.959-1.004
0.088
0.003
Unbiased
0.765110.023
0.746110011
0.043
0.694
Pcomp-ReL.U
0.902=000017
0.89140.024
0.913+0.023
0.827=0.025
Pcomp-ABS
0.894+00011
0.879+00000
0.911
0.870=0.006
Teapher
0.918+0.007
0.933+0.023
0.903
0,872=0.011
T4 0.8
Oracle-Hard
0.987110000
0.98310.002
0.99710.001
0.976_100004
Oracle-Soft
0.986
0.905
0.000
0.965
ConlDiit-Unbiasse
0.886-10.037
0.803
0.892.10.0%
0.708
ConfDiff ReLU
0.949=0.007
0.958=000008
0,000
0.927=0,008
ConfDiff -AB
0.064=:0.005
0.964=0.003
0.987=0.002
0.945=0.007
superior performance against all of the other Pcomp approaches by large margin. The excellent performance benefits from the effectiveness of consistency regularization for weakly supervised learning problems 17 [1]; c) It is worth noting that the classification results of ConfDiff ReLU and ConíDiff-A ABS have smaller variances than ConfDiff- Unbiased. demonstrates that the risk correction method can enhance the stability and robustness for ConfDiff classification.
UCI data sets. Table reports detailed experimental results on four UCI data sets as well. From Table 2 we can observe that: a) On all the UCI data sets under different class prior probability settings, our proposed ConfDiff-ABS. method achieves the best performance among all the compared approaches with significant superiority, which verifies the effectiveness of our proposed approaches again; b) The performance of our proposed approaches is more stable than the compared Peomp approaches under different class prior probability settings, demonstrating the superiority of our methods in dealing with various kinds of data distributions.
4.3 Experiments a Real-world Recommender System Data Set
We also conducted experiments on a recommender system data demonstrate our approach's ''s usefulness and promising applications in real-world scenarios. We used the KuaiRec [72] data set, real-world recommender system data set collected from well-known short-video mobile app. In this data set, user-item interactions are represented by watching ratios, i.e.. the ratios of watching time to the entire length of videos. Such statistics could reveal the confidence of preference, and we regarded them as pointwise positive confidence. We generated pairwise confidence difference between pairs of items for given user. We adopted the NCF (73 model as backbone.
Table 3: Experimental results on the KuaiRec data set.
Method
HR
NDCG
BPR MRL Oracle-Hard
0.464
0.256
0.476
0.271
0.469
0.283
Oracle-Soft
0.534
0.380
Peomp-Teacher
0.179
0.066
ConDDiff-ABS
0.570
0.372

---

6.
the hit ratio (HR) and normalized discounted cumulative gain Derding V0
Contint cata
cara
dita
(a) Kuzushiji
(b) Fashion
(c) USPS
(d) Letter
0431
Puray
(c) Optdigits
(f) Pendigits
R
MNIST
(h) CIFAR-10
Figure 2: Classification performance ConfDiff-ReLU and ConfDiff-ABS given a fraction of training data well Pcomp-
Pcomp-Teacher Teacher given 100% of training data (T4 0.5).
Details of the experimental setup and the data set can be found in Appendix H We employed compared methods, including BPR (74), Margin Ranking Loss (MRL), Oracle-Hard, Oracle-Soft, and Peomp-Teacher. Table (NDCG) results. Our approach performs comparably against Oracle in terms of NDCG and performs better in terms of HR. On the contrary, Pcomp-Teache does not perform well on this data It validates the effectiveness of our approach in exploiting the supervision information of the confidence difference.
4.4 Performance with Fewer Training Data
We conducted experiments by changing the fraction of training data for ConiDiff-ReLU and ConfDiff- ABS (100% indicated that all the ConIDiff data were used for training). For comparison, we used 100% of training data for Peomp-Teacher during the training process. Figure 2 shows the results with π 0.5, and more experimental results can be found in Appendix || We can observe that the classification performance of our proposed approaches still advantageous given fraction of training data. Our approaches can achieve superior or comparable performance even when only 10% of training data are used. It elucidates that leveraging confidence difference may more effective than increasing the number of training examples.
4.5 Analysis on Robustness
In this subsection, we investigate the influence of an inaccurate class prior probability and noisy confidence difference on the generalization performance of the proposed approaches. Specifically, let Ā <T denote the corrupted class prior probability with being a real number around 1. Let c/ denote the noisy confidence difference where e is sampled from normal distribution (1, o²) Figure shows the classification performance our proposed approaches on MNIST and Pendigits (T+ 0.5) with different and It is demonstrated that the performance degenerates with 0.8 or e = 1.2 on some data sets, which indicates that it is important to estimate the class prior accurately.
5 Conclusion
In this paper, we dived into novel weakly supervised learning setting where only unlabeled data pairs equipped with confidence difference were given. To solve the problem, an unbiased risk estimator was derived to perform empirical risk minimization. An estimation error bound was established to show that the optimal parametric convergence rate can achieved. Furthermore, a risk correction approach was introduced to alleviate overfitting issues. Extensive experimental results validated the superiority our proposed approaches. In future, it would be promising to apply our approaches in real-world scenarios and multi-class classification settings.

---

socurscy
26
0.
00
0.11
(a) ConfDiff-Unbiase
(b) ConIDiff-ReLU
(c) ConfDift-ABS
08
64.
ocoumbyy
00
0.6
006
(d) ContDiff-Unbiased
(e) ConfDiff-ReLU
(1) ContDiff-ABS
Figure Classification accuracy on MNIST (the first row) and Pendigits (the second row) with T 0.5 given an inaccurate class prior probability and noisy confidence difference.
Acknowledgments and Disclosure of Funding
The authors wish thank the anonymous reviewers for their helpful comments and suggestions. The research was partially supported by the SGU MEXT Scholarship, the Junior Research Associate (JRA) program of RIKEN, Microsoft Research Asia, the National Science Foundation of China (62176055), and Basic Research Grant (Super AI) of Institute for Al and Beyond of the University of Tokyo.
References
[1] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A. Raffel. MixMatch: A holistic approach to semi-supervised learning. In Advances in Neural Information Processing Systems 32, pages 5050-5060, 2019.
[2] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-Supervised Learning. The MIT Press, 2006.
[3] Xiaojin Zhu and Andrew B. Goldberg. Introduction semi-supervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 3(1):1-130, 2009.
[4] Yu-Feng Li and Zhi-Hua Zhou. Towards making unlabeled data never hurt. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(1):175-188 2015.
[5] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems 31, pages 8536 05668556, 2018.
[6] Junnan Li, Caiming Xiong, and Steven C. H. Hoi. MoPro: Webly supervised learning with momentum prototypes. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[7] Giorgio Patrini, Alessandro Rozza, Aditya K. Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the 2017 IEEE Conference Computer Vision and Pattern Recognition, pages 1944-1952, 2017.
10

---

[8] Deng-Bat Bao Wang, Yong Wen, Lujia Pan, and Min-Ling Zhang. Learning from noisy labels with complementary loss functions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 10111-101 19, 2021.
[9] Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In Proceedings of the 10th International Conference on Learning Representations, 2022.
[10] Marthinus C. du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in Neural Information Processing Systems 27, pages 703-711, 2014.
[11] Guangxin Su, Weitong Chen, and Miao Xu. Positive-unlabeled learning from imbalanced data. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pages 2995-3001, 2021.
[12] Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Gang Niu, Masashi Sugiyama, and Dacheng Tao. Rethinking class-prior estimation for positive-unlabeled learning. In Proceedings of the 10th International Conference on Learning Representations, 2022.
[13] Haobo Wang, Ruixuan Xiao, Sharon Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. PiCO: Contrastive label disambiguation for partial label learning. In Proceedings of the 10th International Conference on Learning Representations, 2022.
[14] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12(May):1001-1536 2011.
[15] Wei Wang and Min-Ling Zhang. Semi-supervised partial label learning via confidence-rated margin maximization. In Advances in Neural Information Processing Systems 33, pages 6982-6993, 2020.
[16] Hongwei Wen, Jingyi Cui, Hanyuan Hang. Jiabin Liu, Yisen Wang, and Zhouchen Lin. Lever- aged weighted loss for partial label learning. In Proceedings of the 38th International Conference on Machine Learning, pages 1091-11100, 2021.
[17] Dong-Dong Wu, Deng- Deng-Bao Wang, and Min-Ling Zhang. Revisiting consistency regularization for deep partial label learning. In Proceedings of the 39th International Conference on Machine Learning, pages 24212 2222222,2 2022.
[18] Nan Lu, Gang Niu, Aditya K. Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In Proceedings of the 7th International Conference Learning Representations, 2019.
[19] Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 1115-1125. 2020.
[20] Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In Proceedings of the 35th International Conference on Machine Learning. pages 461-470, 2018
[21] Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama. Pairwise supervision can provably elicit decision boundary. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 2-18- 2022.
[22] Yuzhou Cao, Lei Feng, Yitian Xu, Bo An, Gang Niu, and Masashi Sugiyama. Learning from similarity-coffidence data. In Proceedings of the 38th International Conference Machine Learning, pages 1272-1282, 2021.
[23] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition, pages 2818-2826 2016.
11

---

[24] Hua Yuan, Ning Xu, Yu Shi, Xin Geng, and Yong Rui. Learning from biased soft labels. In Advances Neural Information Processing Systems 36, 2023, press.
[25] Li Yuan, Francis EH Tay, Guilin Li, Tao Wang, and Jiashi Feng. Revisiting knowledge distillation via label smoothing regularization. In Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3903-3911, 11, 2020.
[26] Takashi Ishida, Ikko Yamane, Nontawat Charoenphaklee, Gang Niu, and Masashi Sugiyama. Is the performance of my deep network too good to be true? A direct approach to estimating the bayes error in binary classification. In Proceedings of the 11th International Conference on Learning Representations, 2023.
[27] Rafael Müller, Simon Korblithh, and Geoffrey E. Hinton. When does label smoothing help? In Advances in Neural Information Processing Systems 32, pages 4696-4705, 2019.
[28] Deng-Bac Bao Wang, Lei Feng. and Min-Ling Zhang. Rethinking calibration of deep neural networks: Do not be afraid overconfidence. In Advances in Neural Information Processing Systems 34, pages 11809-11820 1820, 2021.
[29] Michal Lukasik. Srinadh Bhojanapalli, Aditya Menon, and Sanjiv Kumar. Does label smoothing mitigate label noise? In Proceedings of the 37th International Conference on Machine Learning. pages 6448 6458, 2020.
[30] Tianyu Pang, Xiao Yang, Yinpeng Dong, Hang Su, and Jun Zhu. Bag of tricks for adversarial training. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[31] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint trXiv:1503.0553 2015.
[32] Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In Proceedings of the 36th International Conference Machine Learning, pages 1152-5151, 2019.
[33] Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. In Proceedings of the 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 3967-3976, 2019.
[34] Jianping Gou, Baosheng Yu, Stephen J. Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129-1789-1819 2021.
[35] Katherine M. Collins, Umang Bhatt, and Adrian Weller. Eliciting and learning with soft labels from every annotator. In Proceedings of the 10th AAAI Conference on Human Computation and Crowdsourcing, pages 20-52, 2022.
[36] Kazuhiko Shinoda, Hirotaka Kaji, and Masashi Sugiyama. Binary classification from positive data with skewed confidence. In Proceedings of the 29th International Joint Conferences Artificial Intelligence, pages 3328-3322333 3334, 2020.
[37] Ilia Sucholutsky, Ruairidh M. Battleday, Katherine M. Collins, Raja Marjieh, Joshua Peterson, Pulkit Singh, Umang Bhatt, Nori Jacoby, Adrian Weller, and Thomas L. Griffiths. On the informativeness of supervision signals. In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, pages 2036-2046, 2023.
[38] Davood Karimi, Haoran Dou, Simon K. Warfield, and Ali Gholipour. Deep learning with noisy labels: Exploring techniques and remedies in medical image analysis. Medical Image Analysis, 65:101759, 2020.
[39] Alexander J. Ratner, Christopher M. De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. In Advances in Neural Information Processing Systems 29, pages 3567-3575, 2016.
[40] Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: survey and new perspectives. ACM Computing Surveys, 52(1):1-38, 2019.
12

---

[41] Yuchen Jiang, Qi Li, Han Zhu, Jinbei Yu, Jin Li, Ziru Xu, Huihui Dong, and Bo Zheng. Adaptive domain interest network for multi-domain recommendation. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, page 3212-3221, 2022.
[42] Tiansheng Yao, Xinyang Yi, Derek Zhiyuan Cheng, Felix Yu, Ting Chen, Aditya Menon, Lichan Hong, Ed H. Chi, Steve Tjoa, Jieqi (Jay) Kang, and Evan Etringer. Self-supervised learning for large-scale item recommendations. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, page 4321 4330, 2021.
[43] Lei Feng, Senlin Shu, Nan Lu, Bo Han, Miao Xu, Gang Niu, Bo An, and Masashi Sugiyama. Pointwise binary classification with pairwise confidence comparisons. In Proceedings of the 38th International Conference on Machine Learning, pages 1252-3262. 2021.
[44] Christopher J. C. Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Gregory N. Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd International Conference on Machine Learning, pages 89-96, 2005.
[45] Zhe Cao, Tao Qin, Tie- Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: From pairwise approach to listwise approach. In Proceedings of the 24th International Conference on Machine Learning, pages 129-136, 2007.
[46] Kevin G. Jamieson and Robert D. Nowak. Active ranking using pairwise comparisons. In Advances in Neural Information Processing Systems 24, pages 2240-2248, 2011.
[47] Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science, pages 355-366 2017.
[48] Dohyung Park, Joe Neeman, Jin Zhang, Sujay Sanghavi, and Inderjit S. Dhillon. Preference completion: Large-scale collaborative ranking from pairwise comparisons. In Proceedings of the 32nd International Conference Machine Learning, pages 1907-1916, 2015.
[49] Nihar B. Shah, Sivaraman Balakrishnan, and Martin J. Wainwright. Feeling the bern: Adap- tive estimators for bernoulli probabilities of pairwise comparisons. IEEE Transactions on Information Theory, 65(8):8854 4874, 2019.
[50] Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, and Artur Dubrawski. Noise-tolerant interactive learning using pairwise comparisons. In Advances in Neural Information Processing Systems 30, pages 2428 0018-2437,22 2017.
[51] Tic- Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011.
[52] Yanwei Fu, Timothy M. Hospedales, Tao Xiang, Jiechao Xiong, Shaogang Gong, Yizhou Wang. and Yuan Yao. Robust subjective visual property prediction from crowdsourced pairwise labels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3803):663-577.215
[53] Liyun Xu, Junya Honda, Gang Niu, and Masashi Sugiyama. Uncoupled regression from pairwise comparison data. In Advances in Neural Information Processing Systems 32, pages 3992-4002, 2019.
[54] Yichong Xu, Sivaraman Balakrishnan, Aarti Singh, and Artur Dubrawski. Regression with comparisons: Escaping the curse of dimensionality with ordinal information. Journal of Machine Learning Research, 21(1):6480-6533, 2020.
[55] Xi Chen, Paul N. Bennett, Kevyn Collins-Thompsen and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining, pages 193-202, 2013.
[56] Shiwei Zeng and Jie Shen. Efficient PAC learning from the crowd with pairwise comparisons. In Proceedings of the 39th International Conference on Machine Learning, pages 25973-25993 2022.
13

---

[57] Yixuan He, Quan Gan, David Wipf, Gesine D. Reinert, Junchi Yan, and Mihai Cucuringu. GNNRank:
Learning global rankings from pairwise comparisons via directed graph neural networks. In Proceedings of the 39th International Conference Machine Learning, pages 8581-8612, 2022.
[58] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 31st Conference On Learning Theory, pages 297-299, 2018.
[59] Shahar Mendelson. Lower bounds for the empirical minimization algorithm. IEEE Transactions on Information Theory, 54(8):3797-3803, 2008.
[60] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. The MIT Press, 2012.
[61] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-2)) 2324,, 1998.
[62] Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature. arXiv preprint arXiv:1812.0177 2018.
[63] Han Xiao, Kashif Rasul, and Roland Vollgraf. Masiion-MNIST: A novel image dataset for benchmarking machine learning algorithms. arXiv preprint (00.:/700.07000 2017.
[64] Alex Krizhevsky and Geoffrey E. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[65] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[66] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the 2016 IEEE Conference on Computer Vision and Putlern Recognition, pages 770-778, 2016.
[67] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning, pages 807-814, 2010.
[68] Sergey loffe and Christian Szegedy. Batch Normalization: Accelerating deep network training by reducing internal covariate shift. Proceedings of the 32nd International Conference on Machine Learning, pages 448-456, 2015.
[69] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. PyTorchh: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8026-8037, 2019.
[70] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
[71] Junnan Li, Richard Socher, and Steven C. H. Hoi. DivideMix: Learning with noisy labels as semi-supervised learning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[72] Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. KuaiRec: A fully-observed dataset and insights for evaluating recommender systems. In Proceedings of the 3 ACM International Conference on Information Knowledge Munagement, pages 540-550, 2022.
[73] Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th International Conference on World Wide Web, pages 173-182, 2017.
[74] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thiene BPR: Bayesian personalized ranking from implicit feedback. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages 452-461, 2009.
14

---

A Proof of Theorem 1
Before giving the proof of Theorem 1, we begin with the following lemmas:
Lemma 2. The confidence difference c(x, can be equivalently expressed as
- - -
(16)
p(z)p(('')
--p- (x)_("))("') - (appp(a)j~__ppppp100
(17)
p(z)p(<')
Proof. On one hand,
c(xx x') =pu'' = +1(x²) p(u = +1/-))
p(x', 3/ = +1) p(xx y +1)
p(x²)
p(x)
-+p+ (+)+(xx)
p(x') p(x:)
_+p((=)p+ (ax) + (ar ((=)))
p(x))((x')
On the other hand,
cx=, x') p(y' = +1/=²) plu +1
(1 p(y' 0|z')) (1 pvv 0|z))
plu = 0|æ²) ply' 0/z')
p(ær, y = 0) p(a', 0)
p(x)
p(x')
r-p-(a) (x)
π p- (x))
p(x)
p(x')
x -- (x) (p((')
n p (x')
((x))p(x')
which concludes the proof.
Lemma 3. The following equations hold:
Pp(a,x')((T++ - (((/)---( E (()
(18)
c(z, (T=
( Fp (w) ((((())) -1)],
(19)
[ (() = ( (()()))
(20)
-
(T_
(21)
15

---

Proof. Firstly, the proof of Eq. 18 is given:
pp ar (( da, ((,
= - (p00))(('))=-ppaaa) (.. (m)=(())(a)) [(g(z),+1)p(z x') dæ dæ'
p(z)p(('))
{ ( - (agp
da'
/ T+pl))(((())) +1 +1) plaa' da' - / ग. =_) pppppptii px((')) da
f
(z))))) +1) do p(x') do'
(=pl)) dx
T+p(Z))(((zZ) +1) dx + (+p+(2))((((x) +1) dz
T+P+ (x)
= (z) ((g(()) +1)]
After that, the proof of Eq. is given:
E pp w [ + = 11]
= -
- ((((()) 1 (2, x²) dæ day
+ T- (x))
/ / (t) (2))) - dx dæ
=
x- - do / p(z' dx' (= de / p(x') dx
(=)())(((()) 1) dæ pp-
(())))((()). 11 dæ T-P- -1) - =
m ==p()))(((())) -1) da
7 p- (z))) - 1) da
(e0000)))) -1]]
It can be noticed that c(æ,, x²) - c((x', .)) and p(æ, x²) = p(x'(( x). Therefore, it can be deduced
naturally that (pp(a,=')((T - c(ar, x ))(((()) (((((()(+))))) +1)] Eppaa' .x) . [ + c(a' ax) )((()))) +1)]. Be-
cause and x' are symmetric, we can swap them and deduce Eq. (0 Eq. (21) can be deduced in the same manner, which concludes the proof.
Based on Lemma] the proof of Theorem I is given.
Proof of Theorem 7 To begin with, it can be noticed that Ep (ar) [((g()), +1]]
Ep (x') ( [((g(='), + and Ep (x) [((g()), -1] ] = Fp_((e (x) [[(g(='), -1)]. Then, by summing up all
the equations from Eq. (18) to Eq. (1). we can get the following equation:
E Ep( [C (g(x), g(x')) + C- (g(x))
2n (e) +1]] 2n En (((g(()) -1))
After dividing each side of the equation above by 2, obtain Theorem I
16

---

B Analysis on Variance of Risk Estimator
B.1 Proof of Lemma
Based on Lemma
3 it can be observed that
Ep(a,xx) (L
- -(4, (--
(T_ clo, ())(((()))
Ba (()(0) + (=)(((g(x'),-11) -1]]
(o)))))))) + (1))(((()) -1)]
-R(g)
and
= pp 20 ( + +| (m_ ( 2)) -1)]
= (m)) (a) - 1)] ग. pp (a)) [(g((z))++1
= p_ (2z) ((g((r)) 1)] क (()(())
-R(g).
Therefore, for an arbitrary weight E [0,
R(g) =a((g)) + (1-a)) (((
pa. x/)
( [[(x, x') + (1 a) () p( (C(('' x)],
which indicates that
(aL 2²) + (1 - a)) x:))
is also an unbiased risk estimator and concludes the proof.
B.2 Proof of Theorem 2
In this subsection, we show that Eq. (8) in the main paper achieves the minimum variance of
S(g; ax) 1
n Σ (aL(a,, σ() (1 a)(())
w.r.t. any a E [0, 1]. To begin with, introduce the following notations:
An a E E
az)
L(x,, xf{)) = Expcer,' xeee
Σ
Caa, a.)) {?,,)
n2 1=1
1
n
n C(x,, a Σ C(x), ax)]]
P2 A ) Furthermore, according to Lemma in the main paper, we have
n
Ep(e. (S(r;))) = R(g).
Then, we provide the proof of Theorem as follows.
Proof of Theorem
_
Var(S(g;a) a))
E Ep
(S(g);) R(g))
= Epla, [S(g:a) R(g)²
a
=a B Eple, 11
C(x;, xz)) (1 1p ) n
L(x xx
+ 2a Eppepa))
1
C(x,, x.)) Σ 1=1
L1x,,, 2r - R(g)²
12 1=1
=pia² + (1 - a)² + 2112a a)) R(gg)
1
=(2p1 - 2/22) 2
+ 2
(M) + +2)) - R(g)²
17

---

Besides, it can be observed that
2/11 2/12 = Bp(x (()) C(rl, ((),), a;)))
0.
Therefore, Var(S(g::)) a)) achieves the minimum value when a = 1/22, which concludes the proof.
C Proof of Theorem
To begin with, we give the definition of Rademacher complexity.
Definition 2 (Rademacher complexity). Let X₂ = [21, ... Fn denote n. i.i.d. random variables drawn from a probability distribution with density p(æ), 9 9= {g X + R.] denote class of
measurable functions, and a = (01, 02.-.. ,n) denote Rademacher variables taking values from {+1,-1} uniformly. Then, the (expected) Rademacher complexity of 9 is defined
1 sup DEG nt
(G) = Ex, E.
ozg(
(22)
Let Dn ~ p(x, x²) denote n pairs of ConfDiff data and LeD(g; = then we introduce the following lemma.
Lemma 4.
Rr (CD o 9) (9).
where LCD o og= = (SoD glg E 9) and (.) is the Rademacher complexity over ConfDiff data pairs Dr of size n.
Proof.
Hi (CCD og)=E2 -Ep,
Eg Ssup gEg n
o, oc
1
n
=Ep, Eo Isup
- ())((())())))))))))))))))))))))) (1) + + - -1)
gEG 2n
+ + ())
+ -1)]].
Then, we can induce that
[VLcD(g 2,, 2
-/VV T+ (()))(((((())))))))))))))))))))) +1 + (r) 1)
2
(T4 + cc)e(((z()) +1) (T- +c)el(((x)) -1) )|12
(++ ()) +1)
|ll + || ( c))((((()); -1) )ll2
<||V(
2
|| (++ ())(g(a))) +1)
( ())((((2))) -1) )
)||2 + ||
2
2
Ca Le
- GLLe
| c Le
T Le
+
(23)
2
2
Suppose म. 2 v., the value of RHS of Eq. (3) can determined as follows: when e; E [-1, - n ) the value is -2c; Le; when C; E [-T++ - π the value is (π++ (;) Ly; when E {--x-,
the
value is T,g when e E [T=, 74). the value (#+ + 0;) e.)T.; T4; when 6; [m 1). the value is 2c, I.g. To
sum up, when T4 2 T_, the value of RHS of Eq. 23 is less than 2 When π. I T_, we can
18

---

deduce that the value of RHS of Eq. 23 is less than 2L in the same way. Therefore,
RR (CDD g) S2 Eg /su geg 7
[g([)]]]
1
=2,,Ex E /sup gEg n2
ogg()))]
-9),
which concludes the proof.
After that, introduce the following lemma.
Lemma 5, The inequality below hold with probability at least -
In 2/8
sup R(g) RcD(g)) (L) +2))) SEG
2n
Proof. To begin with, we introduce Φ sup (R(g) - ReD (g)) and + supgeg (R(g))
RcD(g)), where RcD(g) and RcD(g) denote the empirical risk
sets of training examples
with exactly one different point {(x; xx), ai and { o(), c( o{)} respectively. Then we have
4 S sup (RcD (g) - RCD(g))
DEG
Cep u,, 2t) LCD (g. 2y)
< sup
gE0
2Ca
n
Accordingly, - can be bounded in the same way. The following inequalities holds with probability at least 1 - 6/2 by applying McDiarmid's inequality:
2n2
sup (R(g) - RcD(a)) < ED, [sup - RCD(g))) +20, gEg
gEG
2n
Furthermore, we can bound Ep., Jsup R(g) ReD(g))) with Rademacher complexity. is routine work to show by symmetrization [60] that
ED, (usp R(g) - ReD (g))) 29R, (CeD o 9) < (9),,.()), SEg
where the second inequality is from Lemma 4 Accordingly, sup (CD((g) R(g)) has the same bound. By using the union bound, the following inequality holds with probability least 8:
2/8
sup R(g) Rg)( 4L,R,, 20,
gEG
2n
which concludes the proof.
Finally, the proof of Theorem is provided.
Proof of Theorem 3
R(ğcD) R(g") (R(ğcD) ReD (ĀD)) + (ReD( RcD(g")) (Rco(g") R(g"))
< (R(ğcD) - Rep (CD)) + (Rc - R(g"))
s R(ğcD) - ReD (DD )l + ReD(o") - R(g")
s 2sup [R(g) RRc(())
geg
2n2/8
< SL + 4C2/
2n
19

---

The first inequality is derived because ICD is the minimizer of (oD The last inequality is derived according to Lemma [
which concludes the proof.
D Proof of Theorem
To begin with, we provide the following inequality:
RcD(()) - RC)(
1
- + - +a -1)
2n ==1
+ (++ - 4 + -
1 8
(T - ++
-1)1
2n
[(T+
k4 + + -- (1000 1)))
1
u + - - - -1)
2n
i=1
+ |
#4 + 0. - - -1))
n
(1 - -++1+ + 14 - C, ( (()();))) +1) - (l=_---11) le - 2/ {)))((((()) 1)
2n
+ (| - .+| + j2 - ()) +1) + (1=_ - - جū - - -1)
1 n
Σ (( -+ + la 2. ) (1)) +1) - ((m+ #+| lcs c: ([(((())))))))))))))) -1)
2n
(1T++
.4| + [2 - 0: (1))(((()))))))))))))))))) (z)) +1) + (|= - -- + l0 cl))(((a;)). -1))
2C
Ex= 10 cal
+ 2C + x+1.
π
Then, we deduce the following inequality:
R(ğoD) R(g") =RR(gcD) - RCD (ReD - RCD (CD()) (Red - RCD (õCD))
+ +ReD ((CD) - RoD (āCD)) + (ReD(CeD) - R(ĀcD)) + (R(ōen) - ))
<2sup RR(g) (g) + sup RCD(g) ( + (R(ĀcD) -(("))
.Eg
9Eg
<usup RR(g) Rc)( + sup RcD(g) - -RD((g)) 9Eg
969
(16L + 8C2
In 2/8 2n
+
4C
Σ i7, cal + 4C// x4|-
1i=1
n
The first inequality is derived because ICD is the minimizer of R(g). The second and third inequality are derived according to the proof of Theorem 3 and Lemma respectively
E Proof of Theorem 5
To begin with, let (g) = (D,(A()) 2 80 2 20nc()) 2n 2 0} and D,, (g)
(())A(g) < O B(g) s (() < OU D(g) < 0). Before giving the proof of Theorem 5 we
give the following lemma based on the assumptions in Section 3
Lemma 6. The probability measure of D,, (g) can be bounded as follows:
22n2n
2b2mm
-2c2 + exp(
-2d2n
P(2, S exp
+ exp
+ exp
(
(24)
C
C2
C
C2
20

---

Proof. It can be observed that
p(Dr)) - p((1, .. p(ann
- p((x)) ... p( ((()))) ... p((())))))))))))))))))))))))))))
Therefore, the probability measure P(2 (g)) can be defined as follows:
(9)7 DDDDD (s)
p(D.) dD,
(DD,) dæ dæ,, day ... doy
D.ED
When exactly one ConfDiff data pair in S, is replaced, the change of A(g), B(g), C(g) and D(g)
will be no more than Cz/n. By applying McDiarmid's inequality, we can obtain the following inequalities:
-2a2n
P(E[A(g) A(g) 2 a) S exp
C2
-26ºn
P(E[B()) B(g) 2 b) $ exp
C2
20
P(E[C(()] ((6) 20 S exp
C7
-2d
P(E[(() D60 2 d) s exp
C²
Furthermore,
(9),
004000555HH000000000000000000000 0
P(E[A(()) - -(( B(g) 2
+ +(EE(((0)] - 2
- P(E - D(g) 2 d)
2a
-2b n
2ctn
2nd
exp C2
+ exp
exp
+ exp
C2
C2
C/
which concludes the proof.
Then, the proof of Theorem 5 is given.
Proof of Theorem
To begin with, we prove the first inequality in Theorem 5
B(Ren(g) - R(g)
R (g) RCD(g))
(ReD(g) RcD(g))p(D.))dD dD,
(..eD!())
f (Rcv(g) ReD(g))p(D,)) dD,
(Rc((g) RcD) 2 0,
(.E
21

---

where the last inequality is derived because RcD(9) is an upper bound of RCD(g). Furthermore,
E[RcD - R(g)
=1 (ReD(g)- (cD,)))
(..E27(0))
< sup (RcD(g) RcD(O)) (.ED.(0) dD, (,)
sup (Reb(o) (cD(4))P(97(1))
D.EDi(0)
(f(A(g)) + f
f(D(g)
= sup
(.)
-A(g) - B(g) O()) (()))((),
< sup (I,r)A()) + ++,1 1
D.EDT())
A(g) + |B(g)) + +((())++ (00))(000)))000000
+
+++ c))((((x)))))))))))))))))))))))) +1)1 + Σ TT- c;){(((())))))))))))))))))))){)) -1)1
sup
2n
D.ED7 (1)
Σ (++ + ())(g(=)),, +1)1 +
TT_ + (c))(()))), -11)))))))1)1))))0000
L 1 "
(T+ - ())(g(())))))))))))))))))){))))) +1)1 + Σ -c)((())))))
sup D., P..EN (1)
2n
Σ (T+ ())(((()))) +1)1 + Σ
(m- +
L, +1 1
= sup
Σ
- -(((4=a))(((1
(1)) -()
2n
D.EDT (g)
1=1
+ +I( + ())(((())))))))))))))))))))))))) +1) + ( -1) (g))
(L, + 1)C(
S sup
(|T 0: + - + + + cil + m + cs)) (g))
2n
D,ED. (n)
Similar to the proof of Theorem
3 we can obtain
T+
Cal + |T- - cal + | + czl + |T= + +al S 4.
Therefore, we have
B(RcD(g) - R(g) , 1)C2A
which concludes the proof of the first inequality in Theorem 5 Before giving the proof of the second inequality, we give the upper bound of (R) E[RCD When exactly one ConfDiff data pair D, replaced, the change of RCD(g) no more than 2C,L, nn. By applying McDiarmid's inequality, we have the following inequalities with probability at least 1 - 8/2:
In 2/5
RCD(g) E[Rcl())] & 2C V
2n
In 2/8
B[RcD())) (gn(g) < 2C,T..
2n
Therefore, with probability least 8, we have
In 2/0
(R)((g) ((Re s 2C
22

---

Finally, we have
(gn(g) R(g)) = (CD( ([ -( R(g)
ReD(g) E[Rcn + |B(cD R(g)
Rc)(g) E[RcD + E()c(()) R(g)
2/66
s V
+ 2 1)C,A.
2n
with probability at least 1 - 6, which concludes the proof.
F
Proof of Theorem 6
With probability at least 1 - 5, we have
R(GCD) R(gg)) -R(CCD)) (āCD)) (Ren(TeD) ReD(CCD))
+ (Ren(TeD) - R(Cn)) + (R(āen) - R(g"))
<|R(OcD) RCD( + (CD( R(ŌcD) (R(īcD) R(g"))
In 2/5 + 4(Ls + 1)CA + (L)
<4C,(L, +1
2n
The first inequality derived because ICD is the minimizer of RcD(g). The second inequality is derived from Theorem 5 and Theorem The proof is completed.
G Limitations and Potential Negative Social Impacts
G.1 Limitations
This work focuses binary classification problems. To generalize multi-class problems, we need to convert multi-class classification to set of binary classification problems via the one-versus-rew or the one- versus--u- strategies. In the future, developing methods directly handling multi-class classification problems is promising.
G.2 Potential Negative Social Impacts
This work is within the scope of weakly supervised learning, which aims to achieve comparable performance while reducing labeling costs. Therefore, when this technique is very effective and prevalent in society, the demand for data annotations may be reduced, leading to the increasing unemployment rate of data annotation workers.
H Additional Information about Experiments
In this section, the details of experimental data sets and hyperparameters provided.
H.1 Details of Experimental Data Sets
The detailed statistics and corresponding model architectures are summarized in Table 4 The basic information of data sets, sources and data split details are elaborated follows.
For the four benchmark data sets,
MNIST 61] It is grayscale handwritten digits recognition data set. It is composed of 60,000 training examples and 10,000 test examples. The original feature dimension is 28*28, and the label space is ()-. The even digits are regarded as the positive class while the odd digits are regarded as the negative class. sampled 15,000 unlabeled data pairs as training data. The data can be downloaded from /attp://yanm lecun. com/ exdb/mnist/
23

---

Table 4: Characteristics of experimental data sets.
Data Set
# Train
# Tess
Features
# Class Labels
Model
MNIST
60,000
10,000
784
10
MLP
Kuzushiji
60,000
10,000
784
MLP
Fashion
60,000
10,000
784
10
MLP
CIFAR-10
50,000
10,000
3,072
ResNet-34
Optdigits
4,495
1,125
62
10
MLP
USPS
7,437
1,861
256
MLP
Pendigits
8,793
2,199
16
10
MLP
Letter
16,000
4,000
26
MLP
KuzushijiMMNIST [62] It is a grayscale Japanese character recognition data set. is composed of 60,000 training examples and 10,000 test examples. The original feature dimension is 28*28, and the label space ('o', "n'' "ma', 're', 'ki', 'tsu', "'s'',haa,, 'ya', 'wo'), ). The positive class is
composed of "o', 'su', 'na', 'ma', and 're' while the negative class is composed of 'ki', "tsu', 'ha', 'ya', and 'wo'. We sampled 15,000 unlabeled data pairs as training data. The data set can be downloaded from https: http//ttttt....../e/ com/rois ceciiisccocc/ae mrodh/kmniss
Fashion-MNIST 633 It is grayscale fashion item recognition data set. It is composed of 60,000 training examples and 10,000 test examples. The original feature dimension 28*28, and the label space is "T-ssirr', 'trouser', 'pullover', 'dress", 'sandal', "coat', 'shirt', 'sneaker', 'bag'. "ankle boot'), The positive class is composed of 'T-shirt', 'pullover'. 'coat', 'shirt', and 'bag' while the negative class is composed of 'trouser', 'dress', 'sandal', 'sneaker', and 'ankle boot'. We sampled 15,000 unlabeled data pairs as training data. The data set can be downloaded from /ittp:://githu thub. com/ zal andoresear cawaarhicfofaaoooooo Fashion- mnist. CIFAR-10 [64] examples and 10,000 test examples. The original feature dimension is 32*32*3, and the label space ('airplane', 'bird', 'automobile', 'cat', 'deer', 'dog', 'frog'. 'horse', 'ship', "truck"). The positive class is composed of "bird', 'deer', 'dog', 'frog', 'cat', and 'horse' while the negative class is composed of "airplane", 'automobile', 'ship', and 'truck'. We sampled 10,000 unlabeled data pairs training data. The data set can be downloaded from https: //wp:://wwwww./ toronto edu/ "rriz/ 'kriz/cifar" cifar. html]
a colorful object recognition data set. It is composed of 50,000 training
For the four UCI data sets, they can be downloaded from Dua and Graff [65]
Optdigits, USPS, Pendigits [65] They are handwritten digit recognition data set. The train-test split can be found in Table The feature dimensions are 62, 256, and 16 respectively and the label space 0-9. The even digits are regarded as the positive class while the odd digits are regarded the negative class. We sampled 1, 1,200, 2,000, and 2,500 unlabeled data pairs for training respectively.
Letter [65]: It is letter recognition data set. It is composed of 16,000 training examples and 4,000 test examples. The feature dimension is 16 and the label space is the 26 capital letters the English alphabet. The positive class is composed of the top 13 letters while the negative class is composed of the latter 13 letters. We sampled 4,000 unlabeled data pairs for training.
H.2 Details of Experiments on the KuaiRec Data Set
We used the small matrix of the KuaiRec 72 data set since it has dense confidence scores. It has 1,411 users and 3,327 items. We clipped the watching ratio above 2 and regarded the examples with watching ratio greater than positive examples. Following the experimental protocol of He et al. [3 we regarded the latest positive example foe each user as the positive testing data, and sampled 49 negative testing data to form the testing set for each user. The HR and NDCG were calculated at top 10. The learning rate was set to le-3 and the dropout rate was set to 0.5. The number of epochs was set to 50 and the batch size was set to 256. The number MIP layers was and the embedding dimension was 128. The hyperparameters the same for all the approaches for fair comparison.

---

H.3 Details of Hyperparameters
For MNIST, Kuzushiji-MNi -NNIST and Fashion- -MISST, the learning rate was set to 1e-3 and the weight decay was set to le-5. The batch size was set to 256 data pairs. For training the probabilistic classifier to generate confidence, the batch size was set to 256 and the epoch number was set to 10.
For 10, the learning rate was set to 5e-4 and the weight decay was set to le-5. The batch size was set to 128 data pairs. For training the probabilistic classifier generate confidence, the batch size was set to 128 and the epoch number was set to 10.
For all the UCI data sets, the learning rate was set to 1e-3 and the weight decay was set to le-5. The batch size was set to 128 data pairs. For training the probabilistic classifier to generate confidence, the batch size was set to 128 and the epoch number was set to 10.
The learning rate and weight decay for training the probabilistic classifier were the same as the setting for each data set correspondingly.
I More Experimental Results with Fewer Training Data
Figure 3 shows extra experimental results with fewer training data on other data sets with different class priors.
(a) Kuzushiji
(b) Fashion
(c)
USPS
(d) Letter
(e) Optdigits
Pendigits
(g) MNIST
(h) CIFAR-10
Puary Teader
0.04
Contiit
dant
60%
Mt date
20%
Carli data
Kuzushiji
Fashion
(k) USPS
(I Letter
Ta
ContD cata
CarDD if data
(m) Optdigits
(n) Pendigits
(0) MNIST
(p) CIFAR-10
Figure 4: Classification performance of ConfDifi- ReLU and ConfDiff-ANe -BS given fraction of training data as well as Ccomp-Teacher given 100% of training data with different prior settings (T_ 0.2 for the fist and the second row and म = 0.8 for the third and the fourth row).
25


Reviews:
[{"review_id": "7pEABJ5psd", "reviewer": "Reviewer_Qs9H", "summary": "The paper proposes to solve a classification problem using weakly supervised learning problem called confidence-difference (ConfDiff)\nclassification, where unlabeled data pairs are equipped with confidence difference specifying the difference in the probabilities of being positive. The authors further develop a risk-consistent approach to tackle this problem and show that the estimation error bound achieves the optimal convergence rate. They provide additional analysis for noisy labels.  The authors empirically show the effectiveness of their suggested technique on several classification benchmarks such as MNIST, CIFAR-10 and FASHION datasets (TABLE 1), where they show that they approach performs better compared to PComp methods. They further show effectiveness of their method  in leveraging the supervision information of the confidence difference on a real-world recommender system data set.", "questions": "Please add performance of regular classification for your experiments if such is possible to benchmark.\nAre there any other methods applicable for the Recommendation systems you can compare against? Providing more comparisons will help to strengthen your experimental section. ", "limitations": "I feel there are not so many applications that will have relative comparison between two samples. The two applications provided in the motivation are well-suited for such approach, but unfortunately the method is only benchmarked on one application. The authors might want to benchmark against additional application that benefits from relative comparison.     ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is relatively clear and presents an interesting take on classification approach. Instead of an exact label the paper proposes to use relative confidence and provides theory to establish the performance bounds. The paper further validates the effectiveness  on a real world recommender dataset, surpassing PComp teacher. The authors also investigate what happens when the volume of the labeled data is reduced and show that the suggested approach achieves superior or comparable performance even when only 10% of training data are used. It elucidates that leveraging confidence difference may be more effective than increasing the number of training examples.", "weaknesses": "My main concern is that there is no comparison to a performance based on regular labels. Such comparison can at least show the gap in case regular classification performs better (and labels can be provided). Also the authors mention medical application in motivation, however they do not provide experiments with similar data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank you for your time and effort in reviewing our submission. Next, we would like to respond to the main concerns raised in the comments.\n***\n**Q1: Comparison with supervised learning based on ordinary labels.**\n\n**A1:** We agree with you and list the performance of the supervised learning method.\nHere are the experimental results on the four benchmark data sets:\n\n| Class Prior   | Method     | MNIST       | Kuzushiji   | Fashion     | CIFAR-10    |\n| ------------- | ---------- | ----------- | ----------- | ----------- | ----------- |\n| $\\pi_{+}=0.2$ | Supervised | 0.990±0.000 | 0.939±0.001 | 0.979±0.001 | 0.894±0.003 |\n| $\\pi_{+}=0.5$ | Supervised | 0.986±0.000 | 0.929±0.002 | 0.976±0.001 | 0.871±0.003 |\n| $\\pi_{+}=0.8$ | Supervised | 0.991±0.001 | 0.942±0.003 | 0.979±0.000 | 0.897±0.002 |\n\nHere are the experimental results on the four UCI data sets:\n\n| Class Prior   | Method     | Optdigits   | USPS        | Pendigits   | Letter      |\n| ------------- | ---------- | ----------- | ----------- | ----------- | ----------- |\n| $\\pi_{+}=0.2$ | Supervised | 0.990±0.002 | 0.984±0.002 | 0.997±0.001 | 0.978±0.003 |\n| $\\pi_{+}=0.5$ | Supervised | 0.988±0.003 | 0.980±0.003 | 0.997±0.001 | 0.975±0.001 |\n| $\\pi_{+}=0.8$ | Supervised | 0.987±0.003 | 0.983±0.002 | 0.997±0.001 | 0.976±0.004 |\n\nIn particular, the performance is comparable to the Pconf method, which can be used as a reference for performance comparisons.\n***\n**Q2: Additional compared approaches for the recommender system application.**\n\n**A2:** Yes, adding more compared approaches will greatly strengthen the paper. Therefore, we add the following compared approaches 1) Binary Cross Entropy Loss (BCE), which uses the assigned hard labels as the target and applies the cross entropy loss; 2) Bayesian Personalised Ranking (BPR) (Rendle et al., 2009), which uses the logistic loss to rank a pair of items; 3) Margin Ranking Loss (MR), which ranks a pair of items by using the margin loss. The hyperparameters are the same as those in Appendix I. The experimental results are summarised as follows:\n\n| Method        | HR    | NDCG  |\n| ------------- | ----- | ----- |\n| BCE           | 0.469 | 0.283 |\n| BPR           | 0.464 | 0.256 |\n| MR            | 0.476 | 0.271 |\n| Pcomp-Teacher | 0.179 | 0.066 |\n| Pconf         | 0.534 | 0.380 |\n| ConfDiff-ABS  | 0.570 | 0.372 |\n\nIt is worth noting that BCE did not perform well because the heuristic labeling method can introduce a lot of label noise. Based on the experimental results, we can see that ConfDiff-ABS achieves the best performance in terms of HR and achieves comparable performance to Pconf. This confirms the effectiveness of our method in tackling this problem in recommender systems.\n***\n**Q3: Experiments on the medical data sets.**\n\n**A3:** We agree that adding additional experiments on the medical application benchmarks will better motivate the setting. In the introduction, we pointed out a promising application of our setting and method in the medical domain. However, collecting data for medical applications is demanding because it requires a lot of domain knowledge and may involve privacy-sensitive issues. Therefore, we have not yet found such public data sets. We will consider collecting similar data sets as our future work. For example, we will consider collecting such data sets using a crowdsourcing platform (e.g. MTurk) by asking annotators to give the confidence difference between two examples. We are very grateful for your valuable suggestions.\n\n***\nReference:\n\n- Rendle et al., BPR: Bayesian personalized ranking from implicit feedback, UAI 2009."}, {"review_id": "MZUdVoSkEo", "reviewer": "Reviewer_DX8U", "summary": "- This work proposes a confidence label based training approach called _ConfDiff_ for binary classification models as an improvement over traditional hard labels. Specifically, authors argue that obtaining hard labels for traditional supervised learning paradigm, or confidence metrics around positive labels for weakly supervised learning paradigm is expensive and at times infeasible process. Therefore, they propose training such classification models on pairwise comparisons between confidence in positive labeling of training data example.\n\n- Authors prove error bounds, and demonstrate the robustness of the proposed approach theoretically.\n\n- Authors evaluate the proposed approach on benchmark classification datasets and a real world recommender system.\n\n", "questions": "- Could you address the weakness/include discussions about the same in the manuscript?", "limitations": "In the Appendix section, authors have addressed limitations of the approach being currently limited to binary classification and potential negative societal impact in terms of loss of annotation work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Motivation**\nAuthors make a strong technical as well as intuitive case in support of their approach, _ConfDiff_, in comparison to prevalent approaches in the related work such as _Pconf_. Similar to traditional supervised learning paradigm where approaches such as _soft labeling_, _pairwise loss_, etc. have provided benefits over pointwise models utilizing hard labels in the form of increased robustness and robustness, it is intuitive that pairwise confidence differences should outperform methods like _Pconf_, as demonstrated by the paper.\n\n**Technical Presentation**\nThe work is very well presented and easy to digest. The Preliminaries section sets up the reader very well equipped to compare/contrast the proposed approach with existing classification approaches. Specifically, the authors do a great job at using formal notations with perfect granularity required to compare different approaches, without being overwhelming to the reader.\n\n**Experiments**\nAuthors evaluate their proposed approach on multiple benchmark datasets as well one real world recommender system dataset. All the details as well as source code required for reproducibility are available in the Appendix section of the work. The observed evaluation metrics clearly favors the proposed approach against the baseline comparisons. Authors further analyze the sample efficiency and robustness of the proposed approach and provide empirical evidence supporting the theoretical analysis in the prior sections.", "weaknesses": "**Choice of comparative baselines**\nWhile the authors clearly position their work as an improvement over the existing approaches in weakly supervised learning domain, they make a case throughout the introductory as well as technical sections regarding benefits over traditional hard label supervised learning. Given that _ConfDiff_ was evaluated using backbones such as ResNet-34, I believe it would help the work to include inside Table 1 the metrics corresponding to vanilla ResNet-34 or logistic regressions. \n\n**Generalizability of proposed approach**\nTheoretical contributions not withstanding, it is not entirely clear how generalizable the proposed approach is in terms of obtaining confidence difference values. Authors present the real world evaluation on  KauiRec dataset where _watching ratio_ i.e., ratio of watching time of short video and total length of short video, has an intuitive relationship with $p(y=1|x)$. \n> We clipped the watching ratio above 2 and regarded the examples with watching ratio greater than 2 as positive examples. Following the experimental protocol of [8], we regarded the latest positive example for each user as the positive testing data, and sampled 49 negative testing data to form the testing set for each user. \n\nAs I understand, based on the above text in the Appendix, even in this example, the authors had to resort to assigning hard labels to training data using a heuristic based approach. I am not sure what would be a similar intuitive approach to compute $c(x, x^{\\prime})$ in a more common user-item recommender system where purchase labels/click labels are by nature hard labels, and the priors are heavily biased by the fact that only limited number of recommendations can be shown to a user?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we are very grateful for your time and effort in reviewing this submission. We are encouraged that you agree with the contributions of our paper. Below are the responses to your comments.\n***\n**Q1: Add experimental results from the vanilla ResNet.**\n\n**A1:** We agree with you that adding experimental results of logistic regression (LR) will strengthen the paper. We will add the following experimental results to Table 1 and Table 2.\n\n| Class Prior   | Method     | MNIST       | Kuzushiji   | Fashion     | CIFAR-10    |\n| ------------- | ---------- | ----------- | ----------- | ----------- | ----------- |\n| $\\pi_{+}=0.2$ | Supervised | 0.990±0.000 | 0.939±0.001 | 0.979±0.001 | 0.894±0.003 |\n| $\\pi_{+}=0.5$ | Supervised | 0.986±0.000 | 0.929±0.002 | 0.976±0.001 | 0.871±0.003 |\n| $\\pi_{+}=0.8$ | Supervised | 0.991±0.001 | 0.942±0.003 | 0.979±0.000 | 0.897±0.002 |\n\n| Class Prior   | Method     | Optdigits   | USPS        | Pendigits   | Letter      |\n| ------------- | ---------- | ----------- | ----------- | ----------- | ----------- |\n| $\\pi_{+}=0.2$ | Supervised | 0.990±0.002 | 0.984±0.002 | 0.997±0.001 | 0.978±0.003 |\n| $\\pi_{+}=0.5$ | Supervised | 0.988±0.003 | 0.980±0.003 | 0.997±0.001 | 0.975±0.001 |\n| $\\pi_{+}=0.8$ | Supervised | 0.987±0.003 | 0.983±0.002 | 0.997±0.001 | 0.976±0.004 |\n\nThe performance of LR is comparable to the Pconf method, which can serve as a reference for performance comparisons.\n***\n**Q2: The application to common recommender system tasks even with biased class priors.**\n\n**A2:** Currently, our approaches require supervision information of *confidence labels*. Therefore, if there are only 0-1 interactions without any other side information, it may be difficult to directly apply our methods without *confidence labels*. We will include this limitation of our applications in our paper. However, we can still obtain such confidence labels by using an auxiliary probabilistic classifier that outputs the probability of being positive, which is often used for many recommender system problems, such as click-through rate (CTR) prediction (Zhou et al., 2018). In addition, for many real-world recommender system applications, such as news recommendation, short video recommendation, and movie recommendation, we can often collect some real-value *confidence labels*, such as watching ratios and user ratings. We have also discussed the influence of inaccurate confidence values on our approach in Section 3.3. Therefore, our method is promising to be applied to more recommender system problems.\n\nWe agree with you that the class prior may be biased from the training data to the testing data. Such a problem is the well-known *label shift* problem in the distribution shift literature (Lipton et al., 2018). In this paper, we only consider that the ordinally labelled training data and testing data are sampled from the same distribution. We will consider the development of approaches that address label shift as our future work. Furthermore, if the class prior is the same for training and testing and the estimated class prior is biased, we have discussed its influence with theoretical analysis in Section 3.3. It is shown that a more accurate estimation of the class prior will reduce the upper bound of the estimation error and facilitate model training.\n\n***\n\nReference:\n\n- Zhou et al., Deep interest network for click-through rate prediction, KDD 2018.\n- Lipton et al., Detecting and correcting for label shift with black box predictors, ICML 2018.\n"}, {"review_id": "e2uw6MjITP", "reviewer": "Reviewer_XYQ6", "summary": "The paper discusses weak supervised learning for binary classification, specially in the setting where labeled data is not available. Based on pairwise-comparison (Pcomp) confidence, where we are given data pair $(x_1, x_2)$ and binary label {+1, -1} of $x_1$ being more or less probable of being positive compared to $x_2$, this paper suggests the novel problem setting of ConfDiff, where we are given $((x_1, x_2), P(y = 1 | x_2) - P(y = 1 | x_1))$. The paper then proceeds to provide risk estimators and error bounds for this new problem setting. Experimental results on curated benchmarks and one real benchmark shows the usefulness of the paper’s theoretical results and motivated algorithm.", "questions": "1. Based on the weakness mentioned, are there prior works that suggests this problem setup is more meaningful?\n2. Line 233, “Since the data sets were originally designed for multi-class classification, we manually partitioned them into binary classes.”, how is this manual partitioning done for each dataset? Referencing to the appendix would be fine here.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is well written and organized.\n2. The theoretical results in the paper are non-trivial and well done.\n3. Good experiments and ablation studies.\n", "weaknesses": "My main complain with the paper is that the problem setting does not feel well justified. Since the main goal of the paper is to suggest a novel problem setting, this is a big weakness.\n\nFor example, in line 39, the paper makes the claim that $P(y = 1 | x_2) - P(y = 1 | x_1)$ values might be less biased than individual $P(y = 1 | x_2)$ and  $P(y = 1 | x_1)$ estimates by human labelers. I do not think this claim is well justified. \n\nSimilarly, line 51 claims that section 4 will give a real world case study of this problem. While section 4 does present a real world problem where the paper’s algorithm works better, it is not clear that this is due to the problem setup being more useful/ideal. More study would need to establish that this problem setup has indeed lower bias then the case of pointwise confidence value, possibly with collecting a large scale dataset with human annotators.\n\nFinally, if someone is unconvinced of the problem setting, the paper seems **tautological**, i.e., defining a custom problem where a modified risk estimator works (which, while the proof being involved, is not hard to see).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we are very grateful for your time and effort in reviewing this paper. Below are the responses to your questions and comments.\n\n***\n**Q1: The claim that the confidence difference has a lower bias is not well justified.**\n\n**A1:** Thank you for your comment. As discussed in the Introduction section, the confidence difference can be less biased in *some applications*. Take the problem of disease risk estimation as an example. Different doctors with different backgrounds and experience will give different confidence scores given a person's attributes. Some are confident and tend to assign high confidence, while others are relatively conservative and tend to assign low confidence. As a result, considering them all together in the training set may have negative effects. In such cases, using the confidence difference may be a more objective statistic by describing the relative difference between two examples for a doctor. We agree with you that using more large real-world data sets will better motivate. We will consider collecting more large-scale data sets using crowdsourcing platforms (e.g. MTurk) as our future work.\n\n***\n**Q2: Are the advantages in the experimental results of the recommender system task the result of better settings? Is there any prior work suggesting that the setting is more meaningful?**\n\n**A2:** In this experiment, our approach performs better in terms of HR and achieves comparable performance in terms of NDCG compared with the Pconf method. Since our approach uses less supervision information, the Pconf method should have performed better than ours. Therefore, we suspect that this is because Pconf is affected by biased pointwise confidence values, while ConfDiff can deal with this problem in a better way. \n\nAs positive-confidence classification is a relatively new problem, there is no previous work on this setting. Therefore, the setting is new to the literature. We agree with you that more case studies will further support our setting. We will dedicate ourselves to collecting more large-scale real-world data sets to further validate the superiority of our setting.\n***\n**Q3: Partition of data sets.**\n\n**A3:** We have listed the details of the data set partition in Appendix I. We will add the reference to our paper.\n"}, {"review_id": "GASoTvs5jW", "reviewer": "Reviewer_G7aZ", "summary": "This paper studies binary classification problems. A new data type is introduced, where each observation consists of two input instances, together with the \"confidence difference,\" defined as the difference of the conditional probabilities (output=1|input) of the two input instances. New loss functions are introduced and the excess risk bound is derived with probability. To extend the research, the author(s) also studied the case when the confidence difference is contaminated by noise, and the idea of rectifying the empirical loss function by dropping the negative summands. Empirical tests are done on benchmark datasets where the proposed algorithm consistently outperforms the competitors.", "questions": "1. Table 2 has a structure similar to Table 1 in [11]. In particular, the methods Pcomp-*** have different values from those reported in Table 1 in [11]. Would it be possible for the author(s) to take a look at Table 1 in [11] and briefly explain the difference in experiment design or other conditions that leads to such a difference in the values in these two tables? Same question for Table 2 of this manuscript, and Table 3 in [11].\n2. It seems that the density (or probability mass function?) tilde-p defined in Eq. (4) is not used elsewhere. Is that true? Is there any insight into this density?\n3. Since x and x' are drawn from the same probability distribution, what is the relation between x_i and x_i'? Is the sample in Line 137 just n independent copies? Would the analysis still work if n=m^2 is the square of some integer, so that x_i and x_i's are obtained by the full combination of some sample points u_1,...,u_m?\n4. Is the definition (6) and (8) newly introduced, or cited from the literature? It would be better if the author(s) could specify the facts around these equations.", "limitations": "This is theoretical research, and I have not identified any limitations.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "To my knowledge, the proposed data type (based on confidence difference) is new. The presented research is original. The high quality of the research is guaranteed by solid theoretical analysis, and the definition of a new class of classification data that captures more possible application scenarios. This paper is written clearly and is easy to follow. The broad application scenarios support the significance of the research.", "weaknesses": "I have no major concerns about this work. Some minor issues are listed in the \"Questions\" section below, for the author(s) to clarify.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We are encouraged that you agree with the novelty and contributions of our paper. Below are the answers to your questions.\n\n***\n**Q1: Difference in experimental design between this paper and [11].**\n\n**A1:** In [11], they only used examples from ${(+1, +1),(+1, -1),(-1, -1)}$, while ours also used examples from $(-1, +1)$. Because the training data is different, the experimental results are different. In order to make a fair comparison, we adapted the Pcomp methods to our problem settings. In particular, the input to Pcomp methods can be data pairs where the first example is more likely to be positive. Therefore, when the confidence difference was greater than zero, we used this data pair directly. If the confidence difference was less than zero, we swapped them. We will include the details of the experimental settings in the final version of our paper.\n\n***\n**Q2: The density in Eq.(4) is not used and what is the insight?**\n\n**A2:** Yes, we only used Eq.(4) to elaborate the data distribution assumption of the Pcomp methods. As discussed in the Introduction section, Pcomp methods only consider examples from ${(+1, +1),(+1, -1),(-1, -1)}$. To handle training data with labels $(-1, +1)$, they have to discard them or reverse them to $(+1, -1)$. On the contrary, our data distribution assumption is more general, because we explicitly consider the examples from $(-1, +1)$ in the data distribution assumption. \n\n***\n**Q3: The relationship between $(x, x')$ and whether the analysis will still work for data pairs of size $m^2$ obtained from combining unlabeled data of size $m$.**\n\n**A3:** First, we assume that $x$ and $x'$ in an unlabeled data pair are i.i.d. and both sampled from $p(x)$. Therefore, based on our assumption, any two unlabeled data pairs are also *mutually independent*. If we use all pairwise combinations of an unlabeled data set, some of the resulting data pairs may not be i.i.d. For example, we may have two unlabeled data pairs $(x_1, x_2)$ and $(x_1, x_3)$ both in the training set. Because they contain the same example $x_1$, I am afraid that they are *dependent*. Therefore, our theoretical analysis may not apply to this setting, and we need to investigate new theories that formulate non-i.i.d. training data. Thank you for the insightful question and we will include the discussion in our paper.\n\n***\n**Q4: Are Equations (6) and (8) newly introduced and what are the facts about them?**\n\n**A4:** The two equations are new. Eq.(6) is the definition of confidence difference and Eq.(8) is the empirical approximation of Eq.(7), also known to be an *unbiased risk estimator*. We introduced Eq.(6) to specify the confidence difference between two unlabeled examples, which can also measure how confident the pairwise comparison is. Eq.(8) is a natural result of using training data to estimate the expected value. In Theorem 3, we discussed the estimation error bound by using the unbiased risk estimator. We will add this discussion to our paper."}]

Author rebuttal:
First of all, we sincerely thank all the reviewers for their great efforts in reviewing this submission and providing helpful and valuable comments. Since we cannot revise our paper during the rebuttal period, we plan to make the following revisions in our paper:

- According to Reviewer Qs9H and Reviewer DX8U, we will include the performance of the supervised learning method in Tables 1 and 2.
- According to Reviewer Qs9H, we will include the results of additional compared approaches for the recommender system problem.
- According to Reviewer XYQ6, we will introduce a reference to the details of data sets in the paper.
- According to Reviewer G7aZ, we will add the details of the experimental setting for the Pcomp methods and the facts about Equations (6) and (8) to the paper. We will also discuss more about our data distribution assumption.

Besides, as suggested by Reviewer Qs9H and Reviewer XYQ6, we will consider collecting more real-world data sets for our problem as future work.

Meta-review: Reviewers were unanimously supportive of this paper, which provides a consistent algorithm for learning from pairs of samples which are annotated with the difference of their probability of being positive. One recurring comment was that the practical applications of this framework are a little unclear; this appears to be fair comment that the authors may wish to remedy. Nonetheless, as a formal study of a statistical learning problem, the paper still appears to be above the acceptance threshold.
Decision: Accept (poster)