Solving Partial Label Learning Problem with Multi-Agent Reinforcement Learning
Authors: Xinyi Zhang
Xingdong Feng
Fan Zhou
Venue: Submitted to ICLR 2023 (2023)

Abstract: Partial label learning (PLL) deals with classifications when a set of candidate labels instead of the true one is given for each training instance. As a weakly supervised learning problem, the main target of PLL is to discover latent relationships within training samples, and utilize such information to disambiguate noisy labels. Many existing methods choose nearest neighbors of each partially-labeled instance in an unsupervised way such that the obtained instance similarities can be empirically non-optimal and unrelated to the downstream classification task. To address this issue, we propose a novel multi-agent reinforcement learning (MARL) framework which models the connection between each pair of training samples as a reinforcement learning (RL) agent. We use attention-based graph neural network (GNN) to learn the instance similarity, and adaptively refine it using a deterministic policy gradient approach until some pre-defined scoring function is optimized. Different from those two-stage and alternative optimization algorithms whose training procedures are not end-to-end, our RL-based approach directly optimizes the objective function and estimates the instance similarities more precisely. The experimental results show that our method outperforms state-of-the-art competitors with a higher classification accuracy in both synthetic and real examples. 

Under review as a conference paper at ICLR 2023
SOLVING PARTIAL LABEL LEARNING PROBLEM WITH MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Partial label learning (PLL) deals with classifications when set of candidate labels instead of the true one is given for each training instance. As weakly supervised learning problem, the main target of PLL to discover latent relationships within training samples, and utilize such information to disambiguate noisy labels. Many existing methods choose nearest neighbors of each partially-labeled instance an unsupervised way such that the obtained instance similarities can be empirically non-optimal and unrelated to the downstream classification task. To address this issue, we propose novel multi-agent reinforcement learning (MARL) framework which models the connection between each pair of training samples as a reinforce- ment learning (RL) agent. We use prrention-based graph neural network (GNN) learn the instance similarity, and adaptively refine it using a deterministic policy gradient approach until some pre-defined scoring function optimized. Different from those two-stage and alternative optimization algorithms whose training proce- dures are not end-to-end, our RL-based approach directly optimizes the objective function and estimates the instance similarities more precisely. The experimental results show that our method outperforms mate-offthe-ee competitors with higher classification accuracy in both synthetic and real examples.
INTRODUCTION
PLL., also known as superset label learning (Liu & Dietterich 2014: 2012 Gong et al. (017). ), has been extensively studied in the past few decades. As typical -uukly-supervised learning problem, PLL assumes that most of training instances are partially labeled and their ground truth labels are unknown. To be more specific, each instance is associated with small set of candidate labels including the ground truth. PLL has been widely considered in diverse fields, including web mining (Luo & Orabonal 2010)) facial age estimation (Zhang et al., (2066), photograph captioning (Duygulu et al. 2002 Barnard et al., 2003; Berg et al., 2004 Gallagher & Chen 2007) and image annotation (Cour et al. 2011: Zeng et al. 2013). It is usually much easier to get blurry labels than acquiring exact ground truths, and accurately labeling each instance is costly and labor-intensive. For example, the natural photographs collected in the real world may contain multiple human faces and are often tagged ambiguously with several potential names in the captions. The goal is precisely match the persons in each images with the names, and learn a robust classification model which can be generalized unseen instances.
PLL has been widely examined in the past few years. How to distinguish fuzzy labels in training sets and recover their true labels plays an important role in developing efficient and robust PLL methods. One main class of PLL methods, such as LSB-CMM(Lia & Dietterich] 2012). M3PL Zhang 2016) and NNguyen Caruana 2008). directly fits the classifier with traditional machine learning models. These methods ignore the relationships between training instances which leads to unfaithful labelling disambiguation results. Some more advanced methods, such as PL.KKNN (Hüllermeier & Beringer 2006). IPAL (Zhang & Yu 2015) and PL-LEAF (Zhang et al., (2016). utilize the coorelations between training instances provided by some underlying similarity graph learned in an unsupervised manner. These methods have achieved desirable empirical performance, but still suffer from some common issues. For example, the similarity graph generated via some unsupervised approaches may be non-optimal due to its independence of the main classification task. Another weakness of the graph- based methods is that the label prediction of each test example is voted by its neighbors in the training which makes the prediction results highly depend on the selection of

---

Under review as a conference paper at ICLR 2023
neighboring instances. Unfortunately, there is usually guidance of choosing proper size of the neighboring set in practice. The prediction results can be significantly biased when some unrelated or prongly-labelled training instances included voters. Although some more recent studies such as AGGD (Wang et al. 2019) employ supervised methods to model the instance similarities, the neighbor selection issue has not been fully addressed as they initialize the neighboring set in an unsupervised way and only update the similarity measurements at some specific locations in the subsequent optimization step which has great limitations. On the other hand, these methods need to limit the total number of neighbors and thus some training instances that are useful in improving the predicting accuracy are ignored. Furthermore, the complicated optimization problem proposed by these graph-based methods are difficult to solve in practice.
In this work, we propose a novel end-to-end Partial Label learning method using Multi-Agent Reinforcement Learning, called PLRL. Under the MARL setting, each pair of training instances treated as an individual agent and its action is defined as the similarity measurement between these two instances. All the training instances build the node set of an underlying similarity graph, and the learned optimal policy precisely quantifies the closeness between any two nodes, which is the edge weight. Unlike traditional two-stage alternative optimization approaches, our PLRL method directly optimizes a pre-defined score function and adaptively updates the instance similarities in supervised way which makes the learned similarity graph more related to the main classification task. Specifically, we use GNNs to learn the similarity graph which maximizes a total reward shared by all the n² agents. With the similarity graph, an estimated probability distribution over the candidate labels for each test example is obtained through some label propagation strategies. Then we incorporate the estimated probabilities with a kernel ridge regression model to carry out the label disambiguation. The MARL framework together with the classification model is end-to-end trained using policy gradients. The main contributions of this paper are summarized as follows.
We introduce a novel MARL framework to quantify the similarities between training instances and impose no limits on the number of nearest neighbors.
Different from traditional two-stage or alternative optimization methods, we employ an end-to-end approach to jointly implement predictions and labelling disambiguation, which makes the learned instance similarities more related to the main classification task.
We use Policy Gradient to efficiently solve the complicated optimization problem which cannot be easily handled by previous studies.
Experimental results on both synthetic and real datasets show that our method outperforms existing PL. methods with higher classification accuracies in most scenarios, especially in those cases with imbalanced samples.
2 PROBLEM STATEMENT
In PLL, a partially labelled training set D {(x, (Z.t,..., Tid) E X' is a d- dimensional instance and C₁ C y is the candidate label set among which only one label assumed to be valid. y {811 ./., ..., 31y here denotes label space with q classes. Let X [i,,.... x.]] E R nxd be the normalized input data matrix. The target of PLL is to induce a multi-class classifier g(-): X' + y using such fuzzy label information D to precisely classify partially- labelled and unseen instances.
is given, where x,
In this work, we consider an undirected weighted graph g = (V, W) among instances. V = (w; < i S n) is the set of vertices. W = [wiy]nx refers to the non-negative weight adjacency matrix, where Wiy [0, 1] measures how close the two instances x; and x; are to each other with larger value meaning higher correlation. In this work, a novel RL based approach is used to estimate the weighted adjacency matrix W.
For each training example (z,, C,), we aim to generate a normalized real-valued vector f& E R where each fij represents the label confidence of the j-th label being the true label of σ,, The label confidence vector f. satisfies the following constraints: (i) Σj= fij = 1 for any 1 1 i S n, (ii) fiy 2 0 for any Yiy = 1, and (iii) fiy = 0 for any Vi = 0. The second and third constraints indicate the potential ground-truth label resides in the candidate label set. When the label confidence of training set X is generated as F = [f...... ..... fnl'" e Rx based on this disambiguation results.
x, a classifier g(.) X - y can be induced
2

---

Under review as a conference paper at ICLR 2023
3 A MULTI-AGENT RL FRAMEWORK
In this paper, we model the PLL problems via a MARL framework. Each agent learns the similarity Wij between each pair of training instances by fully exploiting the input features and the labelling uncertainty. To be specific, we consider multi-agent extension of partially observable Markov games, which is defined by a set of states S describing the possible configurations of all agents, set of actions A1, Ay and a set of observations II.... ON for each agent. Each agent i chooses the action following a policy n; : O; - A, We use neural networks to parameterize the policy of each agent, which outputs the similarity between two corresponding instances. The private observation of each agent is correlated to the overall state S, such that o, : S - O, Since there are instances, the total number of agents is N n²² All the n² agents are fully cooperative to maximize the total reward r S x A + R. In addition, we define the action-value function (..(s.0.) a) so s, du al. where [a1...,,aN an] and π (TI.....,TT T.) In the context of PLL, we highlight the following specifics:
Q" o1..... aN) E[R(s,
State. The entire state space constructed by the contexts of n training instances, i.c. S (EI....,T,,) Each agent only observes the contexts of the two related instances, i.e. Oij = {a; ).
Action. For each agent, its action aty E [0. 1] measures the similarity between instance 2; and z which represents the edge weight in the similarity graph determined by the policy Tsy (2;; zy). The larger value of (sj implies the higher similarity between æ; and æ,, Specifically, it is much likely that two instances should be categorized into two different classes of y if azj = 0.
For each agent, we employ a neural network to output the action dzy [0, 1] with input being the observation Oij { æj whose parameters are shared by all the N agents. To ensure that the similarity measurement undirected, i.c. aij = ajá. we borrow the idea of attention mechanism (Vaswani et al. (017)) and the action can be obtained as follows,
Wxo(æz) - (i)(0) Tiy (z), x.)) Sigmoid (Wxolx
(I)
where Φ R R encodes each x; p'-dimensional embedding d(x;;) (here we use fully
connected layer with ReLU activation function), and We, WK 129x9' denote the query and key parameter matrices, respectively. 9 includes all the parameters to be learned. It is obvious that the network architecture in (T) is permutation invariant, and the output is independent of the order of the two inputs x; and ıj. With all the N actions taken by the N agents at each training epoch, we can build a normalized weighted adjacency matrix W = [wsg]ax with wij Σe as
a.l All weight values
in W are updated during the optimization, except that the diagonals are set to zero to avoid self self-loops. Different from previous graph-based methods, we allow all the training instances involve in the prediction of each test example and their importance is optimized via the MARL design.
Reward. Since all the N agents are fully cooperative, we define a single reward function to evaluate the learned similarities W between the instances, which is defined as follows,
R Σ
+ Σ g((;)) S 1,11, +n Σ
Ø3
Wiya
log (p(0)
i=1
(i) L.S.. of lahel confidence
(ii): L.S.. of classifier
(ii):: I.S.. of feature
(iv): log- likellhol
(2)
The first three terms in P are similar to those given Wang al. (2019) while the last term is newly raised. Term (iii) measures how each I; is represented by all the n training instance based on W. Term (i) is exploiting the smoothness assumption that the graph structure in the feature space should be preserved in the label space. F here is the label confidence of the n training instances which is a function of W and can be obtained through disambiguation. For term (ii), we expect to minimize the error of the classifier g(.). As shown by Section 4.2 g(-) is determined by F and thus can also be treated as a function of W. In particular, we add a likelihod term (iv) to facilitate the convergence. Ø3 denotes the label prediction of training instance 2, i.e. p(0, x;)) max, f where f is the (j. 1)h element of F. Since the four terms in (2) all depend on the weighted adjacency matrix W. the negative reward can serve as an objective function optimize W.
3

---

Under review as a conference paper at ICLR 2023
4 METHODOLOGY
In this section, we describe the implementation details of the PLRL algorithm. At each training epoch, we apply disambiguation method to obtain the label confidence F which is then used to learn the classifier g(-). With the obtained and g(-), we can compute the reward function in (2).
using policy gradient to train all the N agents and dynamically updating the weighted adjacency matrix W until the optimal reward R is achieved. More details can be found Sections [4. 4.2
4.3 With the optimal adjacency matrix W we can finally predict the class label of each unseen instance using the kernel ridge regression (KRR) with optimal model parameters, which is described in Sections 4.4 The flow chart of PLRL is summarized in Figure I and the detailed algorithm is provided in the Supplement A
Date:
Partiel label.
Mult agant actor
Instance Similarity
Labe confidence matric
Prediction Model
Charsifer g0X)
Disambiguation
Neural Network
Policy gradiant
Reward FOX,
Figure 1: Algorithm architecture of PLRL
4.1 COMPUTING F: DISAMBIGUATION
At each training epoch, we disambiguate the candidate labels of training instances using the obtained W and apply an iterative approach (Zhang Yu 2015) compute the label confidence matrix F through label propagation. To be specific, we initialize the label confidence matrix ((0) P [piglexg based on the partially labelled training set 'D before the iteration process starts, such that
Pr.j {
1/[C,), 0,
if E C otherwise
V1 visign n.
This initialization step equally distributes the label confidence x; over all its candidate classes. Then at the t-th iteration, F is updated by propagating label information along with W, such that
F (4) W ((t-1) PP
(4)
where the hyperparameter a E (0, 1) balances the contribution of the inherited label information W WTF(t-D and the initial label confidence P. Then, F(t) is normalized to get ((t), i..
j00
19
1
Enec, R. 0,
if C₁ otherwise
vI visisn
(5)
After T iterations, we take F(T) the final label confidence and adopt the class mass normalization (CMN) (Zhu & Goldberg 2009) to adjust the disambiguation output towards class prior distribution, which handles unbalanced samples well. We let F = M o (T)) where o denotes the Hadamard product and M (m...., .., m m is composed of the vector defined as
mi
mg
m
(6)
mi
mg
9x1
where m, = Et= Σn
q.
With this disambiguation approach, we get the label confidence matrix which is then used to compute terms (i) and (iv) in the objective function 2 update W.
4

---

Under review as a conference paper at ICLR 2023
4.2 OBTAINING g(-): KERNEL RIDGE REGRESSION MODEL
Now, we introduce the classifier which makes predictions for unlabelled instances by using the label confidence F obtained in Section 4.1 We consider a reproducing kernel Hilbert space (RKHS) and let (-))) IR - Rº denote the (implicit) nonlinear feature mapping that projects the original feature space higher dimensional RKHS space H via a Gaussian kernel function <( F,) exp(-I<æ; æ, / (20")) where a is the averaged pairwise distances of training instances.
We model the classifier via a kernel regression model using generalized ridge penalty. As pointed by Wahba (990), general solution to this problem is finite-dimensional, and can be defined as
( Ei=1 u,n(#, mx) b,
where and u; = .,..., nt are some parameter vectors. Let K 2 (X))(()) be a kernel matrix with each element generated by kernel function kij k( 2ÿ) (x;)) *x(x,) and U = [ui...., u,,] R=* contains the combined weights of all the instances. The classifier can be obtained by fitting the following kernel ridge regression (KRR),
KU 1b - =F( + Atr (U]KU)
min U.b
(8)
where 1 denotes a vector of 1's, || ||e represents the Frobenius norm, and tr(-) the trace. Let the gradients of (8) with respect to U and b be zeros, we can obtain the solution of U and b as follows,
K+ AI 11KK)
F 11 11
71
(9)
b 1 1- (F'I-UKK")
which are then used to compute term (ii) in the objective function
4.3 UPDATING W: POLICY GRADIENT
At each training epoch, the agent i. observes its own observation Oig and outputs the similarity wi; between æ; and æ, With the N obtained w,y's carry out the disambiguation step in Section 4.
and calculate the prediction model given in Section 4.2 Then the reward R can be obtained.
Let the expected reward J (TT)) detailed formulation of R is given by 2 and the computations of F and g()) are described in Sections 4.1 [.2] All the four components which makes the learned similarity graph related to the classification task, and thus the neighboring information can be well utilized to improve the prediction accuracy. The gradient V (TT) is
Saawmo [R] be the objective function of PLRL, where the
? work together and jointly affect the estimation of W,
obtained by the deterministic policy gradient (DPG) algorithm (Silver et al. 2014)
VoJ (TO) VoTo( Vo (8,0)... a...... (xx)),
(10)
where s X, 0H {0,, 3 < i, < n. In practice, can pre-train the model and properly initialize the adjacency matrix W, which helps shorten the training process of the PLRL algorithm. good starting point of the matrix W can be obtained by using some existing unsupervised methods such as k-NN (Zhang & Yu 2015). Then the proposed PIRII algorithm can further improve the prediction accuracy by refining the matrix W in a supervised way.
4.4 PREDICTION
As the DPG algorithm converges, we can get the optimal similarity graph W and the optimal label confidence matrix F*, The finally prediction of each unseen instance x" is given by
y = arg max Σ uijn(x" " xx;) + b7.
(11)
where uf, is the i-th row, j-th column of U and by is the j-th element in b*. Both U and b* here can be obtained by (9) using the optimal W and F*.
5

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTS
In this section, we conduct both synthetic and real-world experiments to demonstrate the advantages of the proposed PLRL algorithm solving PLL problems. PLRL is compared with seven SOTA PLL algorithms, whose parameters these methods are summarized in Table and the details are provided in the Supplement B For PLRL, the optimal choices of the regularization coefficients are Y 1, 0.5 and / 0.05 according to the cross-validation results. More analysis about the parameter sensitivity are in the Supplement E.1 For each method, we perform five-fold cross- validation, and report the mean accuracy together with their standard deviations. In addition, we apply the t-test at 0.05 significance level to assess the performance of the proposed method.
fine-tuned as suggested by the literature. The configurations of
Table 1: Comparing methods
Methods
Graph-based
Configuration
0.95. 7 100, À = 0.05, 1,77
PLRL (Ours)
Yes
0.5, 0.05
AGGD Wang et al.
2019)
10, = 10, 1, 1,7 0.05
IPAL (Zhang & Yu 2015
Yes
== 10, 0.95, = 100
PL-KNN (Hällermeer & Beringer 2006
Yes
== 10
SURE (Feng An 2019a
No
À == 0.5, 0.05
LSB-CMM (Liu Dietterich
2012
o² 1, K = 80, a 0.05
CLPL (Cour et al. (2011)
No
SVM with the squared hinge loss
PL-SVM (Nguyen & Caruana 2008
No
A 0.01
Our implementation is based on PyTorch (Paszke al. 2019) and all the experiments were carried out with NVIDIA Tesla P100 GPUs. When handling large-scale datasets, we employ batch training strategy reduce the influence of the limited memory. To be specific, dataset into several parts and iteratively feed them into the GPUs when training the GNN model. Then we use the trained model to make predictions for all training instances. practice, our PLRL method takes nearly the same computation time as other recently proposed parametric methods including SURE and AGGD. For the small datasets with sample size less than 2000, the whole training procedure takes about I to 10 minuets, and for some large datasets with more than 10000 samples, it takes about to hours. Considering the performance gain of PLRL in practice, the training cost is acceptable.
randomly split the whole
5.1 SIMULATION STUDY
To show that the MARL design can better capture the instance similarities and thus improve the prediction accuracy, design simulation experiment and compare our PLRI. algorithm with three SOTA graph-based methods, AGGD, IPAL. and PL.KNN.
We let the sample size be 110, the dimension of features d be 6, the number of classes g be 5, and the number of wrong labels in each candidate set be r E {1, 2,33. Each of the six instance features binomial distribution. We
generated from Gaussian distribution, an uniform distribution randomly divided the n samples into g classes, and the features of instances belonging to different classes follow different distributions. The detailed distribution settings are summarized in Table 7 of the Supplements. The data generating procedure is given as follows.
1. Randomly assign one of the class labels to each of the instances as the true label
2. For each instance, generate data features X (v) according to Table 7 of the Supplements.
3. We consider an underlying connective graph and simulate the adjacency matrix Á [asy]xxn nn by d.j 1 (y.=,,) (m,,200773 for S i,j S n, which measures the similarities between the n training instances. Kiy here is the Gaussian kernel k(z,, 2.)) exp(- æ, / (2o2)) where is the averaged pairwise distances of all instances.
4. For each instance, simulate the partial labels by randomly selecting r labels from the 1 candidate labels that are not equal to y.

---

Under review as a conference paper at ICLR 2023
We repeat this data generating procedure 40 times and conduct five-fold cross- vols-valioation each time to report the mean prediction accuracy. Due to the small sample size of the generated dataset, we set the total number of training epochs to be 200 for each method.
0.7
Ad00 de C13
Jena 8.33
simu on
900
OVf
(a) Classification accuracy simulation datasets
(b) ROC of graph recovery
Figure 2: Classification and graph recovery performance on simulation datasets
For the three competitors, we plot their prediction results under different choices of k, which is the total number of neighbours of each training instance when building the underlying similarity graph. The prediction performance of all the four methods is visualized in Figure 2(a] where the 40 replicates are sorted in an ascending order according to the classification accuracy. As Figure (()) shows, PLRL performs consistently well while the classification accuracy of the the other three varies lot with the l selections across the 40 replicates. In some cases a small neighbor set is preferred while in other cases denser similarity graph may be helpful. Since the optimal number of k is usually unknown in the real world, the performance of the three graph-base based methods can be highly affected with a improperly selected k. Our method addresses this issue by allowing all the n² edges to have non-zero weights which are optimized by the end-to-end MARL design.
We also show how each method recovers the true underlying graph A. each obtained weighted adjacency matrix into an unweighted one Å = [ā,jax where each d.z 1 [w)y2r and 5 E (0, 1) here represents truncation threshold. In Figure 2(b) draw five ROC curves based on the learned weighted graph obtained by the five methods. It should be noted that both IPAL and PL-KNN estimate the smilarity graph using K Nearest Neighbor and thus
specific, we transform
"KNN" to represent them. As Figure 2(b) shows, PLRL can better estimates the true graph. For both AGGD and KNN, the estimation performance does not improve when a certain TPR is reached.
Table 2 summarizes the graph estimations under т = 0.05. F-norm denotes the Frobenius distance between the true graph A and the estimated graph W. Higher values of NNZ, TPR, and smaller values of FDR, SHD and F norm distance demonstrate that PLRL can discover more true edges than the other three and achieve the best performance in recovering the underlying graph. The simulation study indicates that PLRL can better capture the similarities between training instances which helps improve the final prediction accuracy.
Table 2: Graph recovery performance one simulation dataset
FDR
TPR
SHD
NNZ
F norm
PLRL
0.314
0.212
1052
384
4.74
AGGD(K=5)
0.347
0.157
1101
296
5.66
AGGD(K=10)
0.384
0.174
1110
323
5.30
AGGD(k=50)
0.411
0.174
1126
349
5.28
KNN(A=5)
0.388
0.154
1121
5.48
KNN(K=10)
0.489
0.164
1180
375
4.84
KNN(A=50)
0.681
0.092
1311
334
5.49
5.2 CONTROLLED UCI DATASETS
Following the common design of previous PLL studies, generate artificial partially labelled dataset based on the UCI dataset (Dua Graff 2019). The characteristics of eight UCI datasets are summarized in Table of the Supplements. We set the proportion of PL. examples p across all
7

---

Under review as a conference paper at ICLR 2023
experiments, and vary the number of wrong labels and the probability specific false positive label co-occurs with the true label e. The configuration of the two settings is provided as follows: (I)
p = 1,r = 1, {0.2, 0.3, ..... 0.8). (II) p r {1, 4,5, 7).
The details the experiment performance are shown in Supplement D To clearly illustrate the advantage of the proposed PLRL algorithm, we report the win/tie/loss results between PLRL and each competing method using two-sample t-test. As shows, PLRL significantly outperforms its competitors with win/tie rates greater than 93.0% among 86 set-ups. In particular, for some recently proposed methods such as SURE and AGGD, PLRL is superior or comparable to them in most cases.
Table 3: Win/tie/loss (pairwise f-test at 0.05 significance level) counts on the controlled UCI datasets between PLRL and the comparing algorithms
SURE
AGGD
IPAL
CLPL
PL-SVM
PL-KNN
LSB-CML
conlig (c)
24/27/1
25/26/1
39/9/4
52/0/0
52/0/0
47/5/0
35/12/5
config2(r)
13/21/0
10/24/0
27/5/2
34/0/0
34/0/0
30/4/0
23/11/0
In total
37/48/1
35/50/1
66/14/6
86/0/0
8670/0
77/9/0
58/23/5
PLRL win/tic rate
98.8%
98.8%
93.0%
100.0%
100.0%
100.0%
94.2%
5.3
DATASETS
We use five real-world datasets validate the proposed method, including Lost (Cour al.) 20111. Soccer Player (Zeng et al. (2013). Yahoo! News (Guillaumin et al. (2110). MSRCv2 (Liu & Dietterich 2012) and BirdSong (Briggs al. 2012). The first three are for automatic face naming, the fourth is for object classification, and the last is to classify bird songs. The characteristics of these five datasets are summarized in Table of the Supplements, as well as the average number of candidate labels.
The mean inductive classification accuracy with its standard deviation for each algorithm on unlabelled test data are summarized in Table[4] Pairwise I-tests at 0.05 significance level conducted based on 5-fold cross cross-validation As shown in Table 4 PLRI significantly outperforms the others in four datasets and achieves the second best prediction accuracy in Yahoo! News, which indicates that PLRL is less sensitive to the data structures and performs consistently well in practice.
Table 5 presents the transductive classification accuracy on partially labelled training samples, which reflects the disambiguation capacity of each method in recovering ground-truths from the candidate label set. For PLRL, SURE and AGGD, the generated label confidence vector f. can be used to predict the ground-truth label for each partially labelled training instance æ; such that Ú: = arg max,, EC;; f Other approaches directly make predictions by choosing the most likely V: E Cj-
As shown in Table the performance of PLRL is superior to other algorithms in terms of a higher transductive prediction accuracy. In particular, PLRL significantly outperforms CLPL, IPAL, PL- KNN, and LSB-CMM in all the five real-world datasets. When compared to SURE, AGGD and PL-SVM. PLRL can still achieves the best performance most cases. These results imply that PLRL performs better in disambiguating blurry labels and can extract more useful information which helps to build a more precise prediction model.
Table Inductive classification accuracy (mean&std) of each method on the real- world partial label datasets, where eoo indicates whether the performance of PLRL is statistically superior/inferior the comparing algorithm on each data set (pairwise 1-test at 0.05 significance level)
Lost
MSRCV2
BirdSong
Soccer Player
Yahoo! News
PLRL
0,810 (0.038)
0.585 (0.034)
0.749 (0.013)
0.557 (0.007)
0.652 (0.012)
SURE
0.765 (0.022))
0.463 (0.034)
0.733 (0.020)
0.529 (0.011)
0.628 (0.011)
AGGD
0.758 (0.029)
0.494 (0.024)
0.731 (0.013)
0.538 (0.010)
0.645 (0.009)
IPAL
0.688 (0.033))
0.522 (0.027)
0.708 (0.011)
0.547 (0.006)
0.659 (0.008)
CLPL
0.728 (0.041))
0.412 (0.024)
0.631 (0.010)
0.366 (0.006)
0.461 (0.008)
PL-SVM
0.693 (0.051)
0.467 (0.055)
0.629 (0.051)
0.451 (0.007)
0.544 (0.164)
PL.KNNN
0.342 (0.024)
0.437 (0.018)
0.646 (0.013)
0.493 (0.010)
0.402 (0.003))
L.B-CMM
0.652 (0.033)
0.462 (0.035)
0.684 (0.023)
0.491 (0.011)
0.522 (0.007)
8

---

Under review as a conference paper at ICLR 2023
Table 5: Transductive classification accuracy (mean&std) of each method on the real-world partial
label datasets
Lost
MSRCv2
BirdSong
Soccer Player
Yahoo! News
PLRL
0.907 (0.006)
0.781 (0.005)
0.867 (0.003)
0.708 (0.004)
0.866 (0.002)
SURE
0.828 (0.0T2)
0.608 (0.009)
0.838 (0.016)
0.703 (0.001)
0.8T2 (0.0DT)
AGGD
0.866 (0.004)
0.637 (0.01 )
0.840 (0.004)
0.717 (0.003)
0.850 (0.002)
IPAL
0.834 (0.007)
0.698 (0.013)
0.832 (0.004)
0.679 (0.002)
0.850 (0.001)
CLPL
0.877 (0.002)
0.595 (0.010)
0.762 (0.006)
0.669 (0.005)
0.768 (0.004)
PL-SVM
0,861 (0.020))
0.652 (0.040)
0.778 (0.044)
0.722 (0.004)o
0.790 (0.108)
PL-KNN
0.614 (0.015)
0.598 (0.008)
0.757 (0.008)
0.568 (0.001)
0.689 (0.002)
LSB-CMM
0.797 (0.008)
0.613 (0.016)s
0.814 (0.013)
0.677 (0.003)
0.821 (0.012)
5.4
FURTHER STUDY
To fairly evaluate the contributions of the MARL design, the GNN model used to learn the weighted graph and the KRR model, we carry out an ablation study on four different datasets to quantitatively illustrate their necessity. Specifically, we compare the full PLRL model with the ones removing either GNN&RL or KRR and also the baseline model IPAL, whose detailed architectures are described as follows,
"w/o GNN&RL" represents the prediction method that uses k--N to estimate the underlying graph and make predictions via KRR. In this case, both GNN and RL are removed.
"w/o KRR " refers to the case that the reward obtained by Σ}= ||f, - Σ, wes fi + 1) Eリ= ||, - Σ. wizz;ll2 Since 9(-) is removed, the final prediction of each test instance is voted by it neighbors.
IPAL serves as the baseline of PLRL without KRR and GNN&RL.
Table 6: Prediction accuracy of PLRL and its ablated variants on four partial label datasets
vehicle (r=2)
steel (7=2)
Lost
MSRCv2
PLRL
0.732 (0.042)
0.737 (0.024)
0,810 (0.038)
0.585 (0.034)
w/o GNN&RL
0.710 (0.043)
0.723 (0.018)
0.764 (0.016)
0.543 (0.029)
w/o KRR
0.710 (0.066)
0.684 (0.016)
0.741 (0.022)
0.573 (0.022)
IPAL
0.677 (0.067)
0.686 (0.014)
0.688 (0.033)
0.522 (0.027)
As shown in Table 6 the full PLRL model consistently outperforms the other three in most scenarios with statistically significant f-test results. The prediction accuracy decreases when either the KRR model or the GNN&RL mechanism is removed. Thus, both of these two components are important in improving the bascline performance although their contributions can be varied in different datasets, which validates their effectiveness and indispensability.
We also show that the reward and the classification accuracy on both training and test datasets converge after 1000 epochs. More details can be found in the Supplement E.2
CONCLUSION
In this work, we propose a novel PLL method, called PLRL, which models the instance similarities using an MARI. based GNN model and enhances the disambiguation capacity. Our method takes all training samples into consideration when building the similarity graph and can better utilize the neighboring information. Thanks to the end-to-end design, the graph structure learned by PLRL is more related to the main classification task.
Despite the empirical success PLRL achieves, there are still some open questions to be answered. First, we need to figure out why the improvement of PLRL over baselines is varied across different datasets. Second, the significance of the improvement by PLRL largely lies in the usage of GNN and RL. It may bring some new ideas to other weakly supervised learning problems such as graph estimations and link predictions.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Kobus Barnard, Pinar Duygulu, David Forsyth, Nando De Freitas, David M Blei, and Michael I Jordan. Matching words and pictures. 2003.
Tamara L. Berg. Alexander C Berg, Jaety Edwards, Michael Maire, Ryan White, Yee- Whye Teh, Erik Learned-Miller, and David A Forsyth. Names and faces in the news. In Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004., volume 2, pp. IIIII. IEEE, 2004.
Forrest Briggs, Xiaoli Z. Fern, and Raviv Raich. Rank-loss support instance machines for miml instance annotation. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. $34-542, New York, NY, USA, 2012. Association for Computing Machinery.
Timothee Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12:1501-1536, 2011.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2019. URL http:://ttchii// ics. www.cciccoo www..ce..uuu..mmmm
Pinar Duygulu, Kobus Barnard, Joao FG de Freitas, and David A Forsyth. Object recognition as machine translation: Learning lexicon for fixed image vocabulary. In European conference on computer vision, pp. 97-112. Springer, 2002.
Lei Feng and Bo An. Leveraging latent label distributions for partial label learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI' pp. 2107-2113, USA, 2018. AAAI Press. ISBN 9780999241127.
Lei Feng and Bo An. Partial label learning with self-guided retraining. Proceedings of the AAAI Conference Artificial Intelligence, (3(01))3542-3549 Jul. 2019a.
Lei Feng and Bo An. Partial label learning by semantic difference maximization. In Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, IJCAI-19, pp. 2300, USA, 2019b. International Joint Conferences on Artificial Intelligence Organization.
Andrew C Gallagher and Tsuhan Chen. Using group prior identify people in consumer images. In 2007 IEEE Conference on Computer Vision and Puttern Recognition, pp. 1-8. IEFE, 2007.
Chen Gong, Tongliang Liu, Yuanyan Tang, Jian Yang, Jie Yang, and Dacheng Tao. A regularization approach for instance-based superset label learning. IEEE transactions on cybernetics, 48(3): 967-978, 2017.
Matthieu Guillaumin. Jakob Verbeck, and Cordelia Schmid. Multiple instance metric learning from automatically labeled bags of faces. In Kostas Daniilidis, Petros Maragos, and Nikos Paragios (eds.), Computer Vision ECCV 2010, pp. 634-647, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 3-2-666-15199900
Eyke Hüllermeier and Jürgen Beringer. Learning from ambiguously labeled examples. Intelligent Data Analysis, 10(5):419 4399 2006.
Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In NIPS, volume 2, pp. 897-904, Cambridge, MA, USA, 2002. Citeseer, MIT Press.
Li-Ping Liu and Thomas G. Dietterich. A conditional multinomial mixture model for superset label learning. Proceedings of the 25th International Conference on Neural Information Processing Systems Volume 1, NIPS 12, pp. 548-556, Red Hook, NY, USA, 2012. Curran Associates Inc
Liping Liu and Thomas Dietterich. Learnability of the superset label learning problem. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31 International Conference Machine Learning. volume 32 Proceedings of Machine Learning Research, pp. 1629-1637, Bejing, China, 22-24 Jun 2014. PMLR.
10

---

Under review as a conference paper at ICLR 2023
Jie Luo and Francesco Orabona. Learning from candidate labeling sets. J. Lafferty, C. Williams, Shawe-Taylor, R. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 23, New York, NY, USA, 2010. Curran Associates, Inc.
Nam Nguyen and Rich Caruana. Classification with partial labels. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '08, pp. 551-559, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605581934.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 387-395, Bejing, China, 22-24 Jun 2014. PMLR.
Cai-Zhi Tang and Min-Ling Zhang, Confidence-rated discriminative partial label learning. In Pro- ceedings of the Thirty-Firss AAAI Conference on Artificial Intelligence, AAAI' 17, pp. 2-11-7, USA, 2017. AAAI Press.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31 International Conference on Neural Information Processing Systems. NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964
Grace Wahba. Spline models for observational data. SIAM, Philadelphia, 1990.
Deng-Bao Wang. Li Li, and Min-Ling Zhang. Adaptive graph guided disambiguation for partial label learning. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD '19, pp. 83-91, New York, NY, USA, 2019. Association for Computing Machinery. ISBN
Fei Yu and Min-Ling Zhang. Maximum margin partial label learning. In Geoffrey Holmes and Tie-Yan Liu ), Asian Conference on Machine Learning, volume 45 of Proceedings of Machine Learning Research, pp. 96-111, Hong Kong, 20-22 Nov 2016. PMLR.
Zinan Zeng, Shijie Xiao, Kui Jia, Tsung-Han Chan, Shenghua Gao, Dong Xu, and Ma. Learning by associating ambiguously labeled images. In Proceedings of the 2013 IEEE Conference Computer Vision and Pattern Recognition, pp. 708-715, USA, 2013. IEEE Computer Society. ISBN 9780769549897.
Min Ling Zhang and Fei Yu. Solving the partial label learning problem: An instance-based approach. IJCAI International Joint Conference on Artificial Intelligence, 2015-Janua:4048 4044440044 2015.
Min Ling Zhang, Bin Bin Zhou, and Xu Ying Liu. Partial label learning via feature-aware disam- biguation. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 13-17-Augu: 1335-1344, 2016.
Yu Zhou, Jianjun He, and Hong Gu. Partial label learning via gaussian processes. IEEE transactions on cybernetics, 47(12):4443444 4450, 2016.
Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning, 3(1):1-130, 2009.
11


Reviews:
[{"review_id": "lvy-o0uB_Ak", "reviewer": "Reviewer_cHoo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Partial label learning (PLL) is a typical weakly supervised learning, and there are many solutions. This paper proposes a novel instance-based multi-agent reinforcement learning framework called PLRL, which uses an attention-based graph neural network (GNN) to learn instance similarity. Different from the commonly used two-stage or alternative optimization methods, the authors use the RL-based approach to directly optimize the objective function to improve the accuracy of similarity estimation between instances. Experimental results on the datasets that are frequently used in PLL demonstrate this work is effective.", "summary_of_the_review": "This paper mainly proposes a novel multi-agent reinforcement learning framework to solve PLL. In the instance-based method, The author introduced a more complex and effective similarity calculation model and obtained better results. Experiments show that the proposed method is effective. It is a continuation of research in one or more areas of AI. Marginally above the acceptance threshold.", "strength_and_weaknesses": "Strengths:\n1. Based on instance-based disambiguation, the authors propose a novel learning framework by introducing a multi-agent reinforcement learning approach. Although an additional computational effort is introduced, it is worthwhile from the experimental results.\n2. Technical steps and experimental setup are clearly explained. Easy to reproduce experimental results.\n3. The paper is well-organized and easy to understand.\n\nWeaknesses:\n1. The method proposed in this paper lacks effective theoretical support. Effectiveness is an attempt based on heuristics and experience.\n2. There are a few comparison methods in the experimental part. To my knowledge, many state-of-the-art methods have not appeared in the paper. To demonstrate the effectiveness of the proposed method, experiments should be conducted in this paper to compare with recent methods [1].\n3. Compared with the traditional instance-based PLL, the main contribution of this paper is the improvement in the estimation of the similarity between instances. The article lacks an explanation for the plausibility of this improvement or how it is better than other estimation methods.\n\n[1] PiCO: Contrastive Label Disambiguation for Partial Label Learning. In ICLR, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kLnepvyBoD", "reviewer": "Reviewer_h8m7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Discovering latent relationships within training samples is an important problem that has been studied in depth before. In this work, the authors propose solving the partial label learning (PPL) problem with multi-agent reinforcement learning (RL). Their solution uses an attention-based graph neural network (GNN) to learn the instance similarity, and adaptively refine it using a deterministic policy gradient approach until some pre-defined scoring function is optimized. The empirical results suggest that the new method outperforms existing baselines with higher classification accuracy in both synthetic and real examples.", "summary_of_the_review": "The authors use an interesting idea of applying RL for solving the partial label learning problem. However, I believe there are fundamental flaws with the manuscript, as described above.", "strength_and_weaknesses": "## Strengths\n\n- The idea of using RL for solving partial-label learning is interesting and novel.\n\n## Weaknesses\n\nI think there are some fundamental flaws in this manuscript.\n\n- Firstly, the setting that the authors introduce does not seem to have the notion of time steps. The agent(s) receive a context and then after performing an action, get an immediate return (using the hand-designed reward function). This seems like a contextual multi-armed bandit problem (one-step MDP), rather than an RL problem.\n- Next, I don’t quite understand why the agents try to pose this as a *multi-agent* RL problem. There are no inherent agencies here and neither there is a method here than can be applied to other MARL settings. It seems like the authors artificially decided to call a pair of vertices “agents” and their method, therefore, becomes a multi-agent RL algorithm. There are no restrictions in this problem to make it multi-agent (e.g. partial observability or communication constraints).\n\nI believe this paper requires a major rewriting and to be translated into “Solving Partial Labeling Learning Problem with Multi-Armed Bandit”.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ag-YUOpYhh", "reviewer": "Reviewer_UdWa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an end-to-end solution for partial label learning, in which classification must be done on data which provides a set of labels during training. The main difficulty in existing approaches are that they either treat this as purely classification task (losing any similarity) or apply a  two step approach - of developing a similarity graph first then training over this (non-direct optimisation).\n\nThe authors propose Partial Label learning method using Multi-Agent Reinforcement Learning (PLRL). \n\nThis treats every edge (2 data points) as an agent, with the single (continuous) action of producing the similarity for that edge. These agents are trained in a fully cooperative setting. The reward function is conditioned on a GNN + Kernel Method which is trained in tandem. Each agent is a separate policy and only acts for one action step.\n\nMy generous interpretation is that the GNN+Kernal approach is being distilled in n-agents which are hopefully better at generalising at test time.", "summary_of_the_review": "Paper has strong experimental results but a very unclear method section. The use of multi-agent is not well understood or conveyed. The quality is below the acceptance threshold", "strength_and_weaknesses": "## Strengths\n1) Strong experimental results against established datasets\n2) Really like the statical significance used to evaluate over other methods.\n\n## Weaknesses\n\n1) The authors assert we have $n^2$ agents (where $n$ refers to the number of instances). Doesn't this mean the number of agents groups QUADRATICALLY with the dataset size?\n2) Its unclear if this is MARL? There is some redundancy in your method, if each agent only sees one instance, why  not have a single agent see all instances. The redundancy is clear from the notation in eq1 :$πij(xi,xj)$\n3) Its unclear how this is training end-to-end, the reinforce update for the agent is not done in the same gradient update as that for the GNN", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject