Meta Objective Guided Disambiguation for Partial Label Learning

Bo-Shi Zou, Ming-Kun Xie, and Sheng-Jun Huang Preprint. Under review.

Abstract

Partial label learning (PLL) is a typical weakly supervised learning framework, where each training instance is associated with a candidate label set, among which only one label is valid. To solve PLL problems, typically methods try to perform disambiguation for candidate sets by either using prior knowledge, such as structure information of training data, or refining model outputs in a self-training manner. Unfortunately, these methods often fail to obtain a favorable performance due to the lack of prior information or unreliable predictions in the early stage of model training. In this paper, we propose a novel framework for partial label learning with meta objective guided disambiguation (MoGD), which aims to recover the ground-truth label from candidate labels set by solving a meta objective on a small validation set. Specifically, to alleviate the negative impact of false positive labels, we re-weight each candidate label based on the meta loss on the validation set. Then, the classifier is trained by minimizing the weighted cross entropy loss. The proposed method can be easily implemented by using various deep networks with the ordinary SGD optimizer. Theoretically, we prove the convergence property of meta objective and derive the estimation error bounds of the proposed method. Extensive experiments on various benchmark datasets and real-world PLL datasets demonstrate that the proposed method can achieve competent performance when compared with the state-of-the-art methods.

Index Terms:

partial label learning, candidate label set, ground-truth label, disambiguation, meta-learning.

I Introduction

With the increasing amounts of carefully labeled data used for training modern machine learning models, model performance has been greatly improved. Nevertheless, collecting a large number of precisely labeled training data is time-consuming and costly in many realistic applications, which imposes a trade-off between the classification performance and the labeling cost.

Partial label learning (PLL) is a commonly used weakly supervised learning framework, where each training example is associated with a set of candidate labels, among which only one corresponds to the ground-truth label[1, 2]. For example, as illustrate in Fig. 1a, in face image recognition (see Fig. 1a)[3, 4, 5], an image with multiple faces is often associated with textual description. One can treat each face detected from the image as an example and those names extracted from the associated textual description consist of the candidate label set of each example. In crowdsourcing image tagging (see Fig. 1b), an image would be assigned with different labels by labelers with different level of expertise. PLL has been successfully applied into numerous realistic applications, such as web mining [6, 7], Ecoinformatics[8], multimedia content analysis[9, 10], etc.

Refer to caption — (a) Automatic face naming

Partial label learning aims to train a multi-class classifier with partially labeled training examples, then utilize the classifier to automatically predict the ground-truth label for an unknown sample. The key challenge of PLL is that the learning algorithms cannot get access to the ground-truth label of training examples [1, 11, 12]. To mitigate this trouble, the most widely used strategy is disambiguation, i.e., identifying the ground-truth label from the candidate label set.

Most existing methods perform disambiguation for candidate labels based on prior knowledge. Among them, some methods utilize the $\ell_{1}$ regularization term to capture the noisy labels based on the sparsity assumption[13]; some methods assume that candidate labels are always instance-dependent (feature-dependent)[14]; some other works recover the ground-truth label matrix by maintaining the local consistency in the label space [15]. The manifold consistency encourages the similar instances to have the same labels.[15, 16]. There exist some other methods exploiting the outputs of model for recovering the true label information. These methods usually use the model outputs as a guidance to progressively identify the ground-truth labels. For instance, the method proposed in [17] re-weights the losses by the confidences of each candidate label. Some methods encourage the model to output a shaper confidence distribution so as to easily identify the most probable class label[18, 19, 20].

Despite the improvement of performance for PLL that these methods have achieved, there still exist two main challenges for learning a multi-class classifier on PLL datasets. On one hand, existing methods rely on prior knowledge, which is often unavailable in practical applications. For instance, the candidate set may not be sparse but composed of many noisy labels in practice, since the training examples may be seriously corrupted in extreme cases. Besides, in high-dimensional feature space, the smoothing assumption may lose effectiveness since it relies on the Euclidean distance. In these cases, the performance of the model often noticeably decreases due to the lack of prior information. On the other hand, the disambiguation methods based on model outputs often suffer from the over-fitting issue of noise labels hidden in the candidate set, particularly when there are a large number of noisy labels. The phenomenon often occurs at the early stage, since the model fails to obtain a desirable disambiguation performance at this time due to its insufficient training.

In this paper, we propose a more reliable and effective approach to perform disambiguation for candidate labels of training examples without any additional auxiliary assumptions. Specifically, we try to recover the true label information by designing a meta-objective on a very tiny validation set (a mini-batch), which can be collected in many practical tasks with small labeling cost. On one hand, we train a classification model by minimizing a confidence-weighted cross entropy loss.. On the other hand, the confidence of each candidate label is adaptively estimated in a meta fashion based on its meta-loss on a tiny validation set. Theoretically, we show that the model learned by the proposed method is always better than directly learning from partial-labeled data, and we further provide the estimation error bounds for the proposed method. Comprehensive experimental results validate that demonstrate that the proposed method shows superiority to the comparing methods on multiple synthetic and real-world datasets.

The rest of this article is organized as follows. Firstly, we overview the related work in the following section. Then the proposed method will be introduced in Section III. Section IV demonstrates theoretical properties of the proposed approach. Section V presents the experimental results, followed by the conclusion in Section VI.

II Related Work

Partial label learning aims to train a classifier model merely using ambiguously labeling training data, thereby reducing labeling cost in practice. The major difficulty of PLL is that the learning algorithms cannot directly get access to the ground-truth label of training examples since it is hidden in the candidate set [1, 11, 12]. To mitigate this issue, a large number of methods have been developed to handle partial labels by adopting the disambiguation strategy, which aims to identify the true label in the candidate set. Existing PLL methods can be roughly divided into three groups: average-based methods, identification-based methods, and disambiguation-free methods.

Averaging-based methods commonly treat all the candidate labels equally and distinguish the ground-truth label by averaging their modeling outputs. Cour et al.[1] proposed to decompose the partial label learning task into a series of binary classification and then employ SVM to solve them, which is a convex optimization approach named CLPL. Hüllermeier and Beringer [21] proposed a k-nearest neighbors method named PL $k$ NN, which distinguishes the ground-truth label by voting among the candidate labels of each neighboring sample. Zhang and Yu [16] proposed an instance-based method called IPAL, which averages the information of the candidate label from the neighboring instances to predict an unknown example. Tang and Zhang [22] proposed to enhance the disambiguation ability by simultaneously utilizing the confidences of candidate label and the weights of training samples. Overall, despite this kind of method can be easily implemented, it has the common drawback that the outputs of false positive labels may mislead the model during the iterative training process and decrease the robustness of learning models.

Identification-based methods progressively estimate the confidence of each candidate label, and then try to recover the ground-truth label from the candidate label set. Specifically, most existing PLL methods typically iteratively refine the confidence of the ground-truth by regarding it as a latent variable. These methods update model parameters by using the iteratively refined expectation maximization techniques, such as maximum likelihood [23, 2, 24], and maximum margin[18, 20, 25]. For instance, Nguyen and Caruana [18] try to maximize the margin between the output of non-candidate labels and the maximal output of candidate label. Feng and An [19] proposed SURE, which imposes the maximum infinity norm regularization on the modeling outputs to conduct pseudo-labeling and train models simultaneously, then automatically identify the ground-truth label with high confidence. The above methods are usually restricted to linear models, which suffers from the lack of strong learning ability. To exploit the powerful fitting ability of the deep neural network, Yao et al. [26] conducted a preliminary study on deep PLL. They proposed a PLL method named $\text{D}^{2}$ CNN [26], they utilize the entropy regularizer to make the prediction more discriminative and employ convolution neural networks (DCNNs) to improve the ability of feature representation. In Yao et al. [27], they proposed to train two networks collaboratively by utilizing a network-cooperation mechanism. Nevertheless, these methods mainly study the discrepancy between the false positive candidate labels and the ground-truth label but neglect the possibility of each candidate label can be the ground-truth label. To mitigate this issue, some methods try to estimate the confidence of each candidate label rather than directly identifying the ground-truth. For example, Lv et al. [17] proposed a progressive identification method named PRODEN, which identifies the true labels according to the output of classifier itself.

Different from aforementioned two disambiguation-based methods, disambiguation-free based methods directly learn from partially labeled data by making modifications to existing techniques. For instance, Zhang et al. [28] proposed a disambiguation-free PLL method called ECOC, which decomposes the PLL problem into many binary classification problems and uses Error-Correcting Output Codes (ECOC) coding matrix [10] to fit partially labeled data.

The proposed method performs disambiguation for candidate labels by designing a meta objective to guide the model training. The idea of using a meta objective to re-weight training examples has been widely applied to train a robust model in many real-world scenarios [29, 30, 31]. Similar to MAML[32], our method takes one gradient descent step on the meta-objective at each iteration. Besides, unlike these meta learning methods, our meta objective guided disambiguation method does not need any extra hyperparameters.

III The Proposed Approach

In this paper, we consider the problem of ordinary $c$ -class classification. Let $\mathcal{X}=\mathbb{R}^{d}$ be the feature space with $d$ -dimensional, $\mathcal{Y}=\{y_{1},y_{2},\dots,y_{c}\}$ be the target space with $c$ class labels. Besides, let $\mathcal{D}=\{(\bm{x}_{i},S_{i})\mid 1\leq i\leq N\}$ be the training set with $N$ partial-labeled instances, where each instance $\bm{x}_{i}\in\mathcal{X}$ is represented by a $d$ -dimensional feature vector $[\bm{x}_{i1},\bm{x}_{i2},\dots,\bm{x}_{id}]^{\top}$ , $S_{i}\subseteq\mathcal{Y}$ is its corresponding candidate label set. Let $\bm{\phi}(\bm{x},\theta)$ be the DNN model, where $\theta$ denotes the parameters.

In the following content, we describe our proposed Meta objective Guided Disambiguation (MoGD) framework for solving PLL problems in detail. Firstly, we develop a confidence-weighted objective function to handle partial-labeled examples; then, we propose to adaptively estimate the confidence of each candidate label in a meta-learning fashion. To reduce the computational cost, we alternatively update the confidences of candidate labels and the parameters of the neural network by using an online approximation strategy.

III-A Confidence-Weighted Objective Function

To solve PLL problems, the pioneer work [1] derives the partial cross entropy (PCE) loss, which computes the cross entropy (CE) loss for each candidate label. Formally, let $\hat{\bm{y}}_{i}=\phi(\bm{x}_{i},\theta)$ denote the model output for instance $\bm{x}_{i}$ , then we define the PCE loss as:

\mathcal{L}(\mathcal{D},\theta)=\frac{1}{N}\sum_{i=1}^{N}\ell_{\text{CE}}(\hat{\bm{y}}_{i},\bm{y}_{i})=-\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{c}y_{ij}\log\hat{y}_{ij},

(1)

where $\bm{y}_{i}=[y_{i1},...,y_{ic}]^{\top}$ denotes the labels vector, $y_{ij}=1$ if $j\in S_{i}$ ; $y_{ij}=0$ , otherwise. For notational simplicity, we denote $\bm{h}_{i}(\theta)=[h_{i1}(\theta),...,h_{ic}(\theta)]$ as the loss vector computed on $\bm{x}_{i}$ . Accordingly, the PCE loss can be rewritten by $\mathcal{L}(\mathcal{D},\theta)=\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{c}h_{ij}(\theta)$ .

Unfortunately, PCE loss regards all candidate labels as ground-truth labels and thus introduces noisy labels into model training. These noisy labels often mislead the model, which leads to a noticeable decrease in generalization performance. To mitigate the negative influence of noise labels, a label confidence vector ${\bm{w}_{i}}=[w_{i1},w_{i2},\dots,w_{ic}]$ is assigned to every example $\bm{x}_{i}$ , where the confidence $w_{ij}\in[0,1]$ is use to estimate the probability that the example $\bm{x}_{i}$ belongs to $j$ -th class. Obviously, if $y_{ij}$ is not a candidate label, then we keep its confidence $w_{ij}$ being 0 due to the fact that it cannot be a ground-truth label for example $\bm{x}_{i}$ .

The confidence-weighted cross entropy loss can be formulated as follows:

\mathcal{L}^{tr}(\mathcal{D},\theta)=\frac{1}{N}\sum_{i=1}^{N}\bm{w}_{i}\bm{h}_{i}(\theta)=\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{c}w_{ij}h_{ij}(\theta),

(2)

In the ideal case, if we can accurately recover the confidences for ground-truth labels, then $\mathcal{L}^{tr}$ would be degenerated into the standard cross entropy, which yields that the disambiguation is achieved for candidate labels.

Nevertheless, it is hard to estimate the confidence precisely without any prior knowledge in many real-world scenarios. To mitigate this issue, we follow a meta-learning paradigm to design a disambiguation strategy based on a meta objective.

III-B Meta Objective Guided Disambiguation

In this subsection, we aim to estimate a optimal confidence distribution for every example in an meta-learning fashion. Towards this goal, we firstly measure the performance of confidence estimation based on a validation set, and then for each candidate label, we use the measurement as a guidance to adaptively estimate its confidence. The only need is a tiny clean validation set (e.g., a mini-batch of examples), which can be collected in many realistic tasks with small labeling cost.

Specifically, we denote $\mathcal{D}_{val}=\{(\bm{x}_{i}^{v},\bm{y}_{i}^{v})\mid 1\leq i\leq M\}$ as a validation set with $M\ (M\ll N)$ examples available during the training phase. Here, for every validation example $(\bm{x}^{v}_{i},\bm{y}^{v}_{i})$ , we use superscript $v$ to distinguish it from training examples. It is noteworthy that every validation example $\bm{x}^{v}_{i}$ has been annotated with its ground-truth label vector $\bm{y}^{v}_{i}$ . Intuitively, the optimal confidences often leads to the best model such that minimizes the validation loss. Based on this intuition, we can treat the objective function on the validation set as guidance to optimize the confidences. The meta objective function can be formulated as follows:

\mathcal{L}^{meta}(\mathcal{D}_{val},\theta^{*}(\bm{w}))=\frac{1}{M}\sum_{i=1}^{M}\ell_{\text{CE}}(\hat{\bm{y}}_{i}^{v},\bm{y}^{v}_{i}),

(3)

where $\mathcal{L}^{meta}$ represents the loss of trained classifier $\theta^{*}(\bm{w})$ on the validation set $\mathcal{D}_{val}$ . In Section V, we discuss that the proposed method is influenced by the size of validation set, and the results show that the performance of MoGD is insensitive to the size of validation set.

Algorithm 1 Meta Objective Guided Disambiguation for Partial Label Learning.

INPUT:

The training set

\mathcal{D}=\{(\bm{x}_{i},S_{i})\mid 1\leq i\leq N\}

;

The validation set

\mathcal{D}_{val}=\{(\bm{x}_{i}^{v},S_{i}^{v})\mid 1\leq i\leq M\}

;

The max iteration

T

;

PROCEDURE:

Initialize the net parameters

\theta

and confidences

\bm{w}

;

for

t=1

T

do:

Sample a mini-batch examples

\mathcal{B}=\{(\bm{x}_{i},S_{i})\}_{i=1}^{b}

from training set

\mathcal{D}

;

Update

\hat{\theta}^{(t)}

according to Eq.(5);

Compute

\mathcal{L}^{meta}

according to Eq.(3);

Update

\bm{w}^{(t)}

according to Eq.(6), Eq.(7), Eq.(8);

Update

\theta^{(t+1)}

according to Eq.(9);

end for;

OUTPUT:

The classifier model

\bm{\phi}

;

We can adopt the alternative strategy to optimize variables $\theta$ and $\bm{w}$ by updating one of the variables while fixing the other. The process continues until both of these two variables converge or exceed the maximum iteration. Unfortunately, it requires two nested loops to obtain optimal parameters, which is unbearable in many realistic tasks, especially when the deep model is used. To improve the training efficiency, inspired by the previous works [30], the online approximation strategy is used to obtain the optimal variables $\theta^{*}$ and $\bm{w}^{*}$ . Specifically, to obtain the $\bm{w}^{*}$ , motivated by the EM algorithm, we can initialize the confidences uniformly as follows:

w_{ij}=\begin{cases}\frac{1}{|S_{i}|}&j\in S_{i}\\ 0,&\text{otherwise}\end{cases}

(4)

Then, at every training iteration $t$ , given a mini-batch training samples $\mathcal{B}=\{(\bm{x}_{i},S_{i})\}_{i=1}^{b}$ , where $b$ denotes the mini-batch size, that satisfies $b\ll N$ . Then we can update the parameters $\theta$ based on the descent direction of the objective function on this mini-batch:

\hat{\theta}^{(t)}(\bm{w})=\theta^{(t)}-\left.\alpha\nabla_{\theta}\mathcal{L}_{tr}(\mathcal{D}_{b},\theta)\right|_{\theta=\theta^{(t)}},

(5)

where $\alpha$ is the step size with respect to $\theta$ .

Next we can seek the optimal confidence $\bm{w}^{*}$ by minimizing the validation loss $\mathcal{L}^{meta}$ .

Based on the $\hat{\theta}^{(t)}$ , we can take a single gradient descent step according to the direction of the meta-objective on the mini-batch validation samples to get a cheap estimate of $\bm{\hat{w}}^{(t)}$ , which can be formally written as:

\bm{\hat{w}}^{(t)}=-\left.\beta\nabla\bm{{}_{w}}\mathcal{L}^{meta}(\mathcal{D}_{val},\hat{\theta}^{(t)}(\bm{w}))\right|_{\bm{w}=0},

(6)

where $\beta$ is the step size with respect to $\bm{w}$ . To make sure the the expect loss non-negative, it requires us to guarantee each $w_{ij}\in\bm{w}$ is non-negative:

\hat{w}_{ij}^{(t)}=\max(\hat{w}_{ij}^{(t)},0),\forall\ i\in[1,m]\text{ and }j\in[1,c].

(7)

In practice, for each training example, we normalize the confidences with respect to every class so that they sum to one:

w_{ij}^{(t)}=\begin{cases}\exp(\hat{w}_{ij}^{(t)})/\sum_{j\in S_{i}}\exp(\hat{w}_{ij}^{(t)}),&j\in S_{i}\\ 0,&\text{otherwise}\end{cases}

(8)

Finally, we can optimize the model parameter $\theta^{(t)}$ by employing the gradient descent based on the latest updated confidences $\bm{w}^{(t)}$ , which is described below:

\theta^{(t+1)}=\theta^{(t)}-\left.\alpha\nabla_{\theta}\mathcal{L}^{tr}(\mathcal{D}_{b},\theta(\bm{w}^{(t)}))\right|_{\theta=\theta^{(t)}}.

(9)

We repeat these procedures until both of them converge or exceed the maximum epoch. The step-by-step pseudo-code of MoGD is shown in Algorithm 1.

IV Theoretical Analysis

In this section, we first analyze the convergence of MoGD, then establish the estimation error bounds.

IV-A Convergence

Different from optimization on a single-level problem, the proposed methods is a optimization problem with two-level objectives including Eq.(6) and Eq.(9). Following the analysis procedure in [30], we obtain the convergence results that both the training and meta objective function converges to the critical points under some mild conditions.

Definition 1

A function $f(x):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is said to be Lipschitz-smooth with constant $L$ if

\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|,\forall x,y\in\mathbb{R}^{d}

Definition 2

$f(x)$ has $\sigma$ -bounded gradients if $\|\nabla f(x)\|\leq\sigma$ for all $x\in\mathbb{R}^{d}$ .

Theorem 1 (convergence)

Suppose that the meta loss function is Lipschitz-smooth with constant $L_{\ell}$ , and for training data $\bm{x}_{i}$ , the training loss function $\ell_{i}$ have $\sigma$ -bounded gradients. Then the validation loss always monotonically decreases with the iteration $t$ by employing our optimization method, i.e.,

\mathcal{L}^{meta}(\theta^{(t+1)})\leq\mathcal{L}^{meta}(\theta^{(t)}).

Note that, the step size $\alpha^{(t)}$ satisfies $\alpha^{(t)}\leq\frac{2nc}{L_{\ell}\sigma^{2}}$ , where $n$ denotes the batch size of training, and $c$ denotes the number of classes.

Furthermore, if the gradient of validation loss becomes $0$ at iteration $t$ , the equality will hold, i.e.,

\mathcal{L}^{meta}(\theta^{(t+1)})=\mathcal{L}^{meta}(\theta^{(t)})

if and only if

\nabla\mathcal{L}^{meta}(\theta^{(t)})=0.

IV-B Comparisons with Ordinary Methods

In the following content, we discuss the effectiveness of the proposed approach compared with ordinary PLL methods.

First, define the empirical risk as:

\hat{R}(\theta)=\frac{1}{N}\sum_{i=1}^{N}\ell(\phi(\bm{x}_{i},\theta),\bm{y}_{i}),

then we have the theorem below.

Theorem 2 (effectiveness)

Define $\theta^{\prime}$ is the model trained without using validation set, i.e.,

\theta^{\prime}=\arg\min_{\theta\in\Theta}\sum_{i=1}^{N}\ell(\bm{\phi}(\bm{x}_{i},\theta),\bm{y}_{i}).

Then the empirical risk of $\hat{\theta}$ that produced by MoGD is never worse than $\theta^{\prime}$ which trained merely utilizes original partial labeled examples, i.e., $\hat{R}(\hat{\theta})\leq\hat{R}(\theta^{\prime})$ .

Proof:

First, we have

\hat{\theta}=\arg\min_{\theta\in\Theta}\sum_{i=1}^{N}\sum_{j=1}^{c}w_{ij}h_{ij}(\theta))

Suppose $\hat{R}(\hat{\theta})>\hat{R}(\theta^{\prime})$ , obviously we can always set the weight of each label to its initial value, e.g., non-candidate label to zero and candidate label to one. Then we can obtain the $\hat{R}(\hat{\theta})=\hat{R}(\theta^{\prime})$ . Therefore, $\hat{R}(\hat{\theta})$ is never worse than $\hat{R}(\theta^{\prime})$ . ∎

TABLE I: Characteristics of Three Image Datasets and Models.

Dataset	# Train	# Test	# Feature	# Class	Model $\phi(x,\theta)$
Fashion-MNIST	60000	10000	784	10	Linear Model
CIFAR-10	50000	10000	3072	10	ResNet, ConvNet
CIFAR-100	50000	10000	3072	100	ResNet, ConvNet

TABLE II: Characteristics of Five Real-World Datasets and Models.

Dataset	# Instance	# Feature	# Avg.Label	# Class	Domain	Model $\phi(x,\theta)$
Lost	1122	108	2.23	16	automatic face naming	Linear Model
BirdSong	4998	38	2.18	13	bird song classification	Linear Model
MSRCv2	1758	48	3.16	23	object classification	Linear Model
Soccer Player	17472	279	2.09	171	automatic face naming	Linear Model
Yahoo! News	22991	163	1.91	219	automatic face naming	Linear Model

IV-C Estimation Error Bounds

In this subsection, we establish the estimation error bounds for the proposed method.

We begin with several useful definitions and lemmas as follows.

Definition 3 ( $\epsilon$ -cover)

For a set $\mathcal{A}$ , if for $\forall\alpha\in\mathcal{B},\exists\alpha^{\prime}\in\mathcal{A}$ satisfies $\left\|\alpha-\alpha^{\prime}\right\|\leq\epsilon$ , then $\mathcal{A}$ is an $\epsilon$ -cover of $\mathcal{B}$ .

Definition 4 (Rademacher Complexity)

Define $p(x,y)$ is the underlying joint density of random variables $(\bm{x},\bm{y})\in\mathcal{X}\times\mathcal{Y}$ . Let $\mathcal{G}=\{g(\bm{x})\}$ be a family of functions for empirical risk minimization, $\sigma_{1},\dots,\sigma_{n}$ be $n$ Rademacher variables, then we can define the Rademacher complexity of $\mathcal{G}$ over $p(x,y)$ with example size $n$ as follows[33]:

\Re_{n}(\mathcal{G})=\mathbb{E}_{\sigma_{1},\dots,\sigma_{n}}\left[\sup_{g\in\mathcal{G}}\frac{1}{n}\sum_{\bm{x}_{i}\in\mathcal{X}}\sigma_{i}g(\bm{x}_{i})\right];

Assume the meta-objective function $\ell$ is upper-bounded by $K$ and Lipschitz-smooth with a constant $L_{\ell}$ , i.e.,

K=\sup_{\bm{x}\in\mathcal{X},\bm{y}\in\mathcal{Y},g\in\mathcal{G}}\ell(g(\bm{x}),\bm{y}).

For notational simplicity, we use $\hat{R}$ and $R$ to denote empirical risk and generalization risk, respectively. Following prior works[17, 30, 34, 35], we summarized two lemmas as follows.

Lemma 1

([17, 35]) For any $\delta>0$ , with a probability at least $1-\delta$ , we have

\sup_{g\in\mathcal{G}}\left|R(g)-\hat{R}(g)\right|\leq 2\Re_{n}(\ell\circ\mathcal{G})+K\sqrt{\frac{\log(2/\delta)}{2n}}.

Lemma 2

([17, 35]) Suppose the loss function $\ell$ is defined as above section, we have

\Re_{n}(\ell\circ\mathcal{G})\leq\sqrt{2}cL_{\ell}\Re_{n}(\mathcal{G}),

where $L_{\ell}$ is the Lipschitz constant of the loss function $\ell$ .

Based on Lemma 1 and 2, we can establish the estimation error bounds as follows.

Theorem 3 (estimation error bounds)

Let $\bm{w}\in\mathbb{B}^{c}$ be the parameter of label confidence of the examples, which is bounded in a $c$ -dimensional unit ball. Let Then, the generalization risk can be defined as:

R(\theta)=\mathbb{E}_{p(\bm{x},\bm{y})}[\ell(\phi(\bm{x};\theta),\bm{y})].

Let $\hat{\bm{w}}=\arg\min_{\bm{w}\in\mathcal{A}}\hat{R}(\hat{\theta}(\bm{w}))$ be the empirically optimal parameter in a candidate set $\mathcal{A}$ , and let $\bm{w}^{*}=\arg\min_{\bm{w}\in\mathbb{B}^{c}}R(\hat{\theta}(\bm{w}))$ be the optimal parameter in the unit ball. Then, with a probability at least $1-\delta$ , we have,

R(\hat{\theta}(\hat{\bm{w}}))-R(\hat{\theta}(\bm{w}^{*}))\leq 4\sqrt{2}cL_{\ell}\Re(\mathcal{G})+K\sqrt{\frac{2\log(2/\delta)}{n}},

where $n$ denotes the number of examples.

Proof:

	$\displaystyle R(\hat{\theta}(\hat{\bm{w}}))-R(\hat{\theta}(\bm{w}^{*}))$	$\displaystyle=\left(\hat{R}(\hat{\theta}(\hat{\bm{w}}))-\hat{R}(\hat{\theta}(\bm{w}^{*}))\right)$
		$\displaystyle+\left(R(\hat{\theta}(\hat{\bm{w}}))-\hat{R}(\hat{\theta}(\hat{\bm{w}}))\right)$
		$\displaystyle+\left(\hat{R}(\hat{\theta}(\bm{w}^{}))-R(\hat{\theta}(\bm{w}^{}))\right)$
		$\displaystyle\leq 0+2\max\|\hat{R}(\hat{\theta}(\alpha))-R(\hat{\theta}(\alpha))\|$
		$\displaystyle\leq 4\sqrt{2}cL_{\ell}\Re(\mathcal{G})+K\sqrt{\frac{2\log(2/\delta)}{n}},$

where we used that $\hat{R}(\hat{\theta}(\bm{w}^{*}))>\hat{R}(\hat{\theta}(\hat{\bm{w}}))$ by the definition of $\bm{w}^{*}$ and $\hat{\bm{w}}$ . ∎

Theorem 3 guarantees that: $n\rightarrow\infty$ , $R(\hat{\theta}(\hat{\bm{w}}))\rightarrow R(\hat{\theta}(\bm{w}^{*}))$ .

TABLE III: Accuracy (Mean

\pm

Std) Comparison Results on Fashion-MNIST with Uniform Partial Labels on Different Ambiguity Levels, the Backbone is Linear Model. The Best Results are Shown in Bold.

Dataset	Method	$q=0.1$	$q=0.3$	$q=0.5$	$q=0.7$
Fashion-MNIST	MoGD	$\mathbf{85.74\pm 0.09\%}$	$\mathbf{85.62\pm 0.15\%}$	$\mathbf{85.13\pm 0.18\%}$	$\mathbf{83.87\pm 0.20\%}$
	VALEN	$82.33\pm 0.24\%$	$81.72\pm 0.13\%$	$80.93\pm 0.36\%$	$78.46\pm 0.32\%$
	LWS	$84.62\pm 0.14\%$	$84.26\pm 0.18\%$	$83.98\pm 0.08\%$	$82.47\pm 0.21\%$
	PRODEN	$84.16\pm 0.08\%$	$83.94\pm 0.12\%$	$83.87\pm 0.06\%$	$82.15\pm 0.26\%$
	RC	$84.53\pm 0.11\%$	$84.16\pm 0.15\%$	$83.95\pm 0.17\%$	$82.64\pm 0.33\%$
	CC	$84.42\pm 0.18\%$	$84.22\pm 0.06\%$	$83.84\pm 0.10\%$	$82.88\pm 0.30\%$
	MSE	$82.21\pm 0.14\%$	$81.02\pm 0.18\%$	$77.25\pm 0.46\%$	$70.47\pm 0.51\%$
	EXP	$83.01\pm 0.15\%$	$80.54\pm 0.23\%$	$79.09\pm 0.37\%$	$71.12\pm 0.65\%$
	Fully Supervised	$86.21\pm 0.13\%$

TABLE IV: Accuracy (Mean

\pm

Std) Comparison Results on CIFAR-10 and CIFAR-100 with Uniform Partial Labels on Different Ambiguity Levels, the Backbone is ConvNet Model. The Best Results are Shown in Bold.

Dataset	Method	$q=0.1$	$q=0.3$	$q=0.5$	$q=0.7$
CIFAR-10	MoGD	$\mathbf{92.67\pm 0.08\%}$	$\mathbf{91.64\pm 0.09\%}$	$\mathbf{88.92\pm 0.07\%}$	$\mathbf{85.11\pm 0.14\%}$
	VALEN	$75.81\pm 0.15\%$	$71.68\pm 0.23\%$	$63.85\pm 0.36\%$	$54.62\pm 0.86\%$
	LWS	$87.63\pm 0.17\%$	$84.65\pm 0.28\%$	$68.29\pm 0.31\%$	$55.57\pm 0.65\%$
	PRODEN	$90.22\pm 0.04\%$	$88.56\pm 0.08\%$	$84.48\pm 0.03\%$	$81.58\pm 0.09\%$
	RC	$88.08\pm 0.05\%$	$86.91\pm 0.10\%$	$79.54\pm 0.12\%$	$70.08\pm 0.17\%$
	CC	$88.24\pm 0.09\%$	$85.72\pm 0.08\%$	$74.14\pm 0.18\%$	$67.26\pm 0.21\%$
	MSE	$78.32\pm 0.13\%$	$71.47\pm 0.30\%$	$65.18\pm 0.16\%$	$60.43\pm 0.24\%$
	EXP	$77.64\pm 0.15\%$	$72.38\pm 0.26\%$	$68.94\pm 0.14\%$	$62.19\pm 0.26\%$
	Fully Supervised	$93.74\pm 0.12\%$
Dataset	Method	$q=0.01$	$q=0.05$	$q=0.1$	$q=0.2$
CIFAR-100	MoGD	$\mathbf{72.14\pm 0.23\%}$	$\mathbf{70.26\pm 0.34\%}$	$\mathbf{65.23\pm 0.41\%}$	$\mathbf{56.84\pm 1.26\%}$
	VALEN	$52.64\pm 0.20\%$	$51.32\pm 0.34\%$	$44.38\pm 0.23\%$	$12.68\pm 0.72\%$
	LWS	$59.74\pm 0.31\%$	$57.21\pm 0.28\%$	$46.52\pm 0.51\%$	$30.26\pm 0.63\%$
	PRODEN	$67.51\pm 0.05\%$	$63.69\pm 0.14\%$	$54.79\pm 0.12\%$	$44.36\pm 0.58\%$
	RC	$61.59\pm 0.15\%$	$53.86\pm 0.23\%$	$44.60\pm 0.38\%$	$33.62\pm 0.84\%$
	CC	$60.72\pm 0.21\%$	$52.94\pm 0.18\%$	$45.85\pm 0.61\%$	$39.73\pm 0.95\%$
	MSE	$46.74\pm 0.15\%$	$43.16\pm 0.21\%$	$40.18\pm 1.24\%$	$6.88\pm 0.16\%$
	EXP	$42.56\pm 0.18\%$	$38.85\pm 0.33\%$	$26.72\pm 2.47\%$	$6.14\pm 0.22\%$
	Fully Supervised	$73.56\pm 0.08\%$

V Experiments

In this section, we conduct experiments on various datasets, and compare it with some state-of-the-art partial label learning algorithms to validate the effectiveness of MoGD.

V-A Experiment Setting

V-A1 Datasets

We perform experiments on three widely used benchmark image datasets, including Fashion-MNIST¹¹1https://github.com/zalandoresearch/fashion-mnist[36], CIFAR-10 and CIFAR-100 ²²2https://www.cs.toronto.edu/~kriz/cifar.html [37] as well as five real-world PLL datasets, including Lost [1], BirdSong [38], MSRCv2 [24], Soccer Player [4], and Yahoo! News [39]. Table I and Table II summarize the detailed characteristics of these datasets, respectively.

Note that it requires to manually generate the candidate label sets for three image datasets, since they are supposed to be used for multi-class classification. We manually generate candidate labels for training examples from these datasets based on two different generation process, i.e., uniform generation process [17] and instance-dependent generation process [14].

Specifically, we generate candidate labels by flipping a negative label $(y=0)$ into false positive label $\tilde{y}$ with a flipping probability $q$ , where $q=P(\tilde{y}=1\mid y=0)$ . In other words, we employ a binomial flipping strategy: for each training example, we conduct $c-1$ independent Bernoulli experiments, and each experiment determines whether a false positive label is generated with probability $q$ . To make sure all training example have two or more candidate labels, for the instance that there is none false positive labels generated, we randomly select a negative label and add it to the candidate label set. Similar to previous works[17, 40], we consider $q\in\{0.1,0.3,0.5,0.7\}$ for Fashion-MNIST and CIFAR-10, and $q\in\{0.01,0.05,0.1,0.2\}$ for CIFAR-100. Generally, a lager value of $q$ indicates a higher level of ambiguity of training examples.

To construct instance-dependent candidate labels, we follow the generating procedure used in [14]. Specifically, for an instance $\bm{x}_{i}$ , let $q_{j}(\bm{x}_{i})=p(\tilde{\bm{y}_{j}}=1|\bm{y}_{j}=0,\bm{x}_{i})$ be the flipping probability of $j$ -th label, where $\bm{y}$ denotes the original label vector. Then we use the prediction probability of a clean network $g$ trained on the clean labels to set the flipping probability of each negative label with $q_{j}(\bm{x}_{i})=\frac{g_{j}(\bm{\bm{x}_{i}})}{\max_{k\in\bar{Y}_{i}}g_{k}(\bm{\bm{x}_{i}})}$ , where $\bar{Y}_{i}$ denotes the negative label set of $\bm{x}_{i}$ . In our experiments, we directly adopt the pre-trained model released by [14] to generate instance-dependent candidate labels.

V-A2 Compared methods

In order to validate the effectiveness of the proposed method, we first compare MoGD against the following five deep PLL methods on three image datasets:

•

VALEN[14]: An instance-dependent method which uses variational inference technique to iteratively estimate the latent label distribution during the training stage.
•

LWS[41]: A discriminative method which imposes a trade-off between losses on non-candidate labels and candidate labels.
•

PRODEN[17]: A progressive identification method which identifies the true labels according to the output of classifier itself.
•

RC[40]: A risk-consistent method which establishes the true risk estimator by employing the importance re-weighting strategy.
•

CC[40]: A classifier-consistent method which establishes the empirical risk estimator by employing the transition matrix and cross entropy loss.

The baseline methods:

•

EXP[42] and MSE[42] are two simple baselines which utilize exponential loss and mean square error as the risks, respectively.
•

Fully Supervised: It trains a multi-class classifier based on ordinary labeled data and can be regarded as an upper bound of performance.

In addition, we also compare MoGD with eight classical PLL methods on five real-world datasets, including GA[43], $\text{D}^{2}$ CNN[26], SURE[19], CLPL[1], ECOC[28], PLSVM[18], PL $k$ NN[21], IPAL[16]. The details of these methods can be found in the related work section. In our experiments, the hyper-parameters are determined based on the recommended parameter settings in their original literature.

TABLE V: Accuracy (Mean

\pm

Std) Comparison Results on CIFAR-10 and CIFAR-100 with Uniform Partial Labels on Different Ambiguity Levels, the Backbone is ResNet Model. The Best Results are Shown in Bold.

Dataset	Method	$q=0.1$	$q=0.3$	$q=0.5$	$q=0.7$
CIFAR-10	MoGD	$\mathbf{86.47\pm 0.07\%}$	$\mathbf{86.31\pm 0.14\%}$	$\mathbf{85.92\pm 0.13\%}$	$\mathbf{83.46\pm 0.09\%}$
	VALEN	$70.52\pm 0.13\%$	$68.37\pm 0.26\%$	$60.85\pm 0.48\%$	$52.73\pm 1.58\%$
	LWS	$82.16\pm 0.12\%$	$80.84\pm 0.16\%$	$63.38\pm 0.26\%$	$54.86\pm 0.26\%$
	PRODEN	$85.39\pm 0.17\%$	$84.74\pm 0.29\%$	$83.79\pm 0.12\%$	$79.88\pm 0.11\%$
	RC	$83.69\pm 0.06\%$	$81.58\pm 0.42\%$	$78.92\pm 0.41\%$	$64.48\pm 1.24\%$
	CC	$82.48\pm 0.08\%$	$80.44\pm 0.39\%$	$76.36\pm 0.47\%$	$65.32\pm 1.61\%$
	MSE	$61.52\pm 0.94\%$	$58.39\pm 0.74\%$	$53.15\pm 0.92\%$	$43.52\pm 2.81\%$
	EXP	$63.24\pm 0.82\%$	$59.32\pm 0.87\%$	$55.35\pm 0.64\%$	$44.48\pm 2.13\%$
	Fully Supervised	$87.32\pm 0.08\%$
Dataset	Method	$q=0.01$	$q=0.05$	$q=0.1$	$q=0.2$
CIFAR-100	MoGD	$\mathbf{68.77\pm 0.34\%}$	$\mathbf{64.85\pm 0.42\%}$	$\mathbf{58.46\pm 0.27\%}$	$\mathbf{50.33\pm 0.56\%}$
	VALEN	$48.82\pm 0.39\%$	$47.65\pm 0.54\%$	$38.66\pm 0.63\%$	$10.45\pm 0.84\%$
	LWS	$53.46\pm 0.27\%$	$52.36\pm 0.23\%$	$40.67\pm 0.43\%$	$28.74\pm 0.85\%$
	PRODEN	$57.71\pm 0.46\%$	$53.16\pm 0.29\%$	$50.62\pm 0.54\%$	$40.78\pm 0.65\%$
	RC	$54.67\pm 0.18\%$	$51.89\pm 0.31\%$	$39.42\pm 0.12\%$	$30.51\pm 0.18\%$
	CC	$51.91\pm 0.34\%$	$51.83\pm 0.56\%$	$41.57\pm 0.34\%$	$35.13\pm 0.23\%$
	MSE	$38.56\pm 0.26\%$	$36.61\pm 0.38\%$	$31.27\pm 0.13\%$	$4.82\pm 0.19\%$
	EXP	$36.37\pm 0.16\%$	$34.73\pm 0.14\%$	$24.45\pm 0.28\%$	$4.25\pm 0.22\%$
	Fully Supervised	$70.08\pm 0.11\%$

V-A3 Implementation Details

We employ multiple basic models, including linear model, 12-layer ConvNet[44] and Wide-ResNet-28[45] to show that the proposed approach is compatible with different learning models. Specifically, for Fashion-MNIST and five real-world datasets, we employ Linear Net as the backbone neural network while using ConvNet and ResNet for CIFAR-10 and CIFAR-100.

To make a fair comparison, we employ the same network architecture as the base model for all methods. For our method, we train the model based on a tiny validation set (a mini-batch). Specifically, before training, we randomly sample a mini-batch precisely labeled instances as the validation set. For the comparing methods, we add the validation examples into training set, which indicates that the classifier is trained on the original training examples and validation examples. Note that the comparing methods directly train the classifier with the validation examples, while MoGD only uses them for auxiliary disambiguation. Furthermore, the parameters are determined as suggested in their original papers. For CIFAR-10 and CIFAR-100, we perform a strong augmentation (containing Cutout [46] and random horizontal flip) for each training image as done in [47] ³³3https://github.com/kekmodel/FixMatch-pytorch. We employ the SGD optimizer [48] with the momentum of 0.9 to train the model for 500 epochs. For all experiments, we repeat $5$ independent experiments (with different random seeds) and report the average results and standard deviation. All experiments are carried on Pytorch ⁴⁴4https://pytorch.org/[49] with GeForce RTX 3080Ti GPUs.

TABLE VI: Accuracy (Mean

\pm

Std) Comparison Results on Fashion-MNIST and CIFAR-10 with Instance-Dependent Partial Labels. We Use ResNet As the Backbone Network.

Method	Fashion-MNIST	CIFAR-10
MoGD	$\mathbf{85.68\pm 0.12\%}$	$\mathbf{80.76\pm 0.17\%}$
VALEN	$83.55\pm 0.21\%$	$66.37\pm 0.18\%$
LWS	$84.36\pm 0.34\%$	$48.82\pm 0.25\%$
PRODEN	$83.12\pm 0.46\%$	$75.43\pm 0.65\%$
RC	$84.74\pm 0.14\%$	$74.14\pm 0.16\%$
CC	$83.88\pm 0.10\%$	$77.45\pm 0.23\%$

TABLE VII: Accuracy (Mean

\pm

Std) Comparison Results on Real-World Datasets with Linear Model. The Best Results are Shown in Bold.

	Lost	MSRCv2	BirdSong	Soccer Player	Yahoo! News
MoGD	$74.65\pm 1.43\%$	$45.38\pm 1.89\%$	$\mathbf{72.69\pm 1.65\%}$	$\mathbf{57.86\pm 0.32\%}$	$\mathbf{68.82\pm 0.44\%}$
VALEN	$72.34\pm 2.26\%$	$47.36\pm 1.82\%$	$72.22\pm 0.36\%$	$55.28\pm 0.62\%$	$67.48\pm 0.26\%$
LWS	$\mathbf{76.54\pm 2.17\%}$	$46.85\pm 1.94\%$	$72.36\pm 1.48\%$	$56.34\pm 2.14\%$	$67.64\pm 0.36\%$
PRODEN	$76.39\pm 1.47\%$	$45.27\pm 1.73\%$	$72.01\pm 0.44\%$	$55.99\pm 0.58\%$	$67.40\pm 0.55\%$
$\text{D}^{2}$ CNN	$69.61\pm 5.48\%$	$40.17\pm 1.99\%$	$66.58\pm 1.49\%$	$49.06\pm 0.15\%$	$56.39\pm 0.89\%$
GA	$48.21\pm 4.44\%$	$22.30\pm 2.71\%$	$29.77\pm 1.43\%$	$51.88\pm 0.44\%$	$34.32\pm 0.95\%$
SURE	$71.61\pm 3.44\%$	$31.57\pm 2.48\%$	$58.04\pm 1.22\%$	$49.16\pm 0.20\%$	$45.73\pm 0.90\%$
CLPL	$76.17\pm 1.81\%$	$43.64\pm 0.24\%$	$67.56\pm 1.12\%$	$49.88\pm 4.29\%$	$53.74\pm 0.95\%$
ECOC	$63.93\pm 5.45\%$	$46.78\pm 2.84\%$	$71.47\pm 1.24\%$	$55.51\pm 0.54\%$	$64.78\pm 0.78\%$
PLSVM	$72.86\pm 5.45\%$	$38.97\pm 4.62\%$	$60.46\pm 1.99\%$	$46.15\pm 1.00\%$	$60.46\pm 1.48\%$
PL $k$ NN	$35.00\pm 4.71\%$	$41.60\pm 2.30\%$	$64.22\pm 1.14\%$	$49.18\pm 0.26\%$	$40.30\pm 0.90\%$
IPAL	$71.25\pm 1.40\%$	$\mathbf{52.36\pm 2.87\%}$	$71.19\pm 1.54\%$	$54.41\pm 0.56\%$	$66.22\pm 0.80\%$

V-B Experiments on Image Datasets

We first report the results of the experiments on three image datasets with uniform candidate labels.

Table III demonstrates the comparison results on Fashion-MNIST with linear models. We consider flipping probability $q\in\{0.1,0.3,0.5,0.7\}$ . As shown in the table, it can be observed that: 1) MoGD consistently outperforms all comparing methods. 2) Even compared to fully supervised learning, the results show that MoGD achieves competitive performance. In particular, with $q=0.1,0.3$ , our method has a very small performance decrease (less than $\bm{1}\%$ ), even with $q=0.5,0.7$ , the performance drop of MoGD is less than $\bm{1.5}\%,\bm{3}\%$ , respectively, when compared to fully supervised learning.

Table IV and Table V report the comparing results on CIFAR-10 and CIFAR-100 with ConvNet and Resnet, respectively. From the results, it can be observed that:

1.

MoGD achieves the best performance on all cases with various flipping probabilities.
2.

MoGD achieves comparable performance compared with fully supervised learning with low flipping probabilities on CIFAR-10 and CIFAR-100, e.g., with the ConvNet backbone, the performance drop of $\bm{1.07}\%$ on CIFAR-10 ( $q=0.1$ ) and $\bm{1.42}\%$ on CIFAR-100 ( $q=0.01$ ).
3.

MoGD outperforms the comparing methods with a large performance gap on CIFAR-100. For example, by using the ConvNet backbone, our method outperforms the second best method PRODEN by $\mathbf{4.63\%}$ , $\mathbf{6.57\%}$ , $\mathbf{10.44\%}$ , and $\mathbf{12.48\%}$ with flipping probabilities $q=0.01,q=0.05,q=0.1,q=0.2$ , respectively.
4.

MoGD achieves a relatively small performance drop as flipping probabilities increase. On the contrary, the comparing methods like LWS, VALEN, MSE and EXP work well on low flipping probabilities, while achieving a significant performance drop with the increase of flipping probabilities.

These experimental results convincingly validate that MoGD can achieve favorable disambiguation ability for candidate labels. The results on CIFAR-100 demonstrate that MoGD show stronger robustness against the comparing methods.

Moreover, we analyze the convergence properties of these methods. Fig. 2 illustrates the performance curves of different methods with regard to test accuracy with the increase of epoch. From the figures, we can see that MoGD can quickly converge with about 40 epochs. Comparing methods like VALEN and LWS converge relatively slowly.

Besides the uniform candidate labels, we also compare these methods on Fashion-MNIST and CIFAR-10 with instance-dependent candidate labels. Table VI shows that the proposed approach achieves the best performance in all cases. In particular, MoGD outperforms the second best method with $\bm{0.94}\%$ and $\bm{3.31}\%$ accuracy on Fashion-MNIST and CIFAR-10, respectively.

V-C Experiments on Real-World Datasets

We also conduct experiments on five real-world PLL datasets to evaluate the practical usefulness of MoGD. Specifically, for all methods, we perform five-fold cross-validation. We use the same Linear model and employ the SGD optimizer [48] with a momentum of $0.9$ to train the model for $500$ epochs. Table VII shows the comparison results between MoGD and comparing methods. From the results, it can observed that our method outperforms all comparing methods on BirdSong, Soccer Player and Yahoo! News. In particular, MoGD outperforms the second best method LWS $\bm{1.52}\%$ and $\bm{1.18}\%$ accuracy on Soccer Player and Yahoo! News, respectively. Although the performance of our method is lower than that of some methods on Lost and MSRCv2, it is still acceptable and higher than that of most comparing methods.

V-D Study On the Size of Validation Set

In this section, we conduct experiments to study the influence of the size of validation data by comparing the performance of our method with different validation set size. Fig. 3 illustrates the test accuracy curves of MoGD as the size of the validation set changes among $\{32,64,128,256\}$ on the CIFAR-10, $\{128,256,384,512\}$ on CIFAR-100 and $\{50,100,150,200,300,400\}$ on the two real-world datasets include Soccer Player and Yahoo! News. From the figures, the performance of MoGD is also satisfactory when the size of the validation set is relatively small, such as 128 for CIFAR-10, 256 for CIFAR-100, 100 for Yahoo! News, and 200 for Soccer Player. In fact, the meta objective on the validation set can encourage the classifier net to precisely estimate the confidence of the candidate label, which is similar to the effect of a regularization term. This phenomenon suggests that, in practical applications, one can precisely annotate a few examples in advance to improve the classification performance.

VI Conclusion

In this paper, we propose a novel framework for partial label learning by achieving disambiguation for candidate labels in a meta-learning manner. Different from the previous methods, we utilize the meta-objective on a tiny clean validation set to adaptively estimate the confidence of each candidate label without extra assumptions of data. Then we optimize the multi-class classifier by minimizing a confidence-weighted objective function. To improve the training efficiency, we iteratively update these two objective functions by using an online approximation strategy. We validate the effectiveness of MoGD both theoretically and experimentally. In theory, we prove that the model trained by MoGD is never worse than merely learning from partial-labeled data. Extensive experiments on commonly used benchmark datasets and real-world datasets demonstrate that MoGD is superior to the state-of-the-art methods. In the future, we will focus on studying other more powerful learning models to further enhance the performance of MoGD algorithm.

References

[1] T. Cour, B. Sapp, and B. Taskar, “Learning from partial labels,” The Journal of Machine Learning Research, vol. 12, pp. 1501–1536, 2011.
[2] R. Jin and Z. Ghahramani, “Learning with multiple labels,” Advances in neural information processing systems, vol. 15, 2002.
[3] M. Guillaumin, T. Mensink, J. Verbeek, and C. Schmid, “Automatic face naming with caption-based supervision,” in 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2008, pp. 1–8.
[4] Z. Zeng, S. Xiao, K. Jia, T.-H. Chan, S. Gao, D. Xu, and Y. Ma, “Learning by associating ambiguously labeled images,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 708–715.
[5] Y.-C. Chen, V. M. Patel, R. Chellappa, and P. J. Phillips, “Ambiguously labeled learning using dictionaries,” IEEE Transactions on Information Forensics and Security, vol. 9, no. 12, pp. 2076–2088, 2014.
[6] L. Feng and B. An, “Partial label learning by semantic difference maximization.” in IJCAI, 2019, pp. 2294–2300.
[7] J. Luo and F. Orabona, “Learning from candidate labeling sets,” Advances in neural information processing systems, vol. 23, 2010.
[8] Y. Zhou, J. He, and H. Gu, “Partial label learning via gaussian processes,” IEEE transactions on cybernetics, vol. 47, no. 12, pp. 4443–4450, 2016.
[9] C.-H. Chen, V. M. Patel, and R. Chellappa, “Matrix completion for resolving label ambiguity,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp. 4110–4118.
[10] T. G. Dietterich and G. Bakiri, “Solving multiclass learning problems via error-correcting output codes,” Journal of artificial intelligence research, vol. 2, pp. 263–286, 1994.
[11] J. Wang and M.-L. Zhang, “Towards mitigating the class-imbalance problem for partial label learning,” in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 2427–2436.
[12] M.-L. Zhang, B.-B. Zhou, and X.-Y. Liu, “Partial label learning via feature-aware disambiguation,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1335–1344.
[13] G. Lyu, S. Feng, Y. Li, Y. Jin, G. Dai, and C. Lang, “Hera: partial label learning by combining heterogeneous loss with sparse and low-rank regularization,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 11, no. 3, pp. 1–19, 2020.
[14] N. Xu, C. Qiao, X. Geng, and M.-L. Zhang, “Instance-dependent partial label learning,” Advances in Neural Information Processing Systems, vol. 34, 2021.
[15] N. Xu, J. Lv, and X. Geng, “Partial label learning via label enhancement,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, 2019, pp. 5557–5564.
[16] M.-L. Zhang and F. Yu, “Solving the partial label learning problem: An instance-based approach,” in Twenty-fourth international joint conference on artificial intelligence, 2015.
[17] J. Lv, M. Xu, L. Feng, G. Niu, X. Geng, and M. Sugiyama, “Progressive identification of true labels for partial-label learning,” in International Conference on Machine Learning. PMLR, 2020, pp. 6500–6510.
[18] N. Nguyen and R. Caruana, “Classification with partial labels,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, 2008, pp. 551–559.
[19] L. Feng and B. An, “Partial label learning with self-guided retraining,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, 2019, pp. 3542–3549.
[20] F. Yu and M.-L. Zhang, “Maximum margin partial label learning,” in Asian conference on machine learning. PMLR, 2016, pp. 96–111.
[21] E. Hüllermeier and J. Beringer, “Learning from ambiguously labeled examples,” Intelligent Data Analysis, vol. 10, no. 5, pp. 419–439, 2006.
[22] C.-Z. Tang and M.-L. Zhang, “Confidence-rated discriminative partial label learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017.
[23] Y. Grandvalet, Y. Bengio et al., “Learning from partial labels with minimum entropy,” CIRANO, Tech. Rep., 2004.
[24] L. Liu and T. Dietterich, “A conditional multinomial mixture model for superset label learning,” Advances in neural information processing systems, vol. 25, 2012.
[25] J. Chai, I. W. Tsang, and W. Chen, “Large margin partial label machine,” IEEE Transactions on Neural Networks and Learning Systems, vol. 31, no. 7, pp. 2594–2608, 2019.
[26] Y. Yao, J. Deng, X. Chen, C. Gong, J. Wu, and J. Yang, “Deep discriminative cnn with temporal ensembling for ambiguously-labeled image classification,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 07, 2020, pp. 12 669–12 676.
[27] Y. Yao, C. Gong, J. Deng, and J. Yang, “Network cooperation with progressive disambiguation for partial label learning,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2020, pp. 471–488.
[28] M.-L. Zhang, F. Yu, and C.-Z. Tang, “Disambiguation-free partial label learning,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 10, pp. 2155–2167, 2017.
[29] M. Ren, E. Triantafillou, S. Ravi, J. Snell, K. Swersky, J. B. Tenenbaum, H. Larochelle, and R. S. Zemel, “Meta-learning for semi-supervised few-shot classification,” arXiv preprint arXiv:1803.00676, 2018.
[30] M. Ren, W. Zeng, B. Yang, and R. Urtasun, “Learning to reweight examples for robust deep learning,” in International conference on machine learning. PMLR, 2018, pp. 4334–4343.
[31] M.-K. Xie, F. Sun, and S.-J. Huang, “Partial multi-label learning with meta disambiguation,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 1904–1912.
[32] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” in International conference on machine learning. PMLR, 2017, pp. 1126–1135.
[33] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of machine learning. MIT press, 2018.
[34] L.-Z. Guo, Z.-Y. Zhang, Y. Jiang, Y.-F. Li, and Z.-H. Zhou, “Safe deep semi-supervised learning for unseen-class unlabeled data,” in International Conference on Machine Learning. PMLR, 2020, pp. 3897–3906.
[35] T. Ishida, G. Niu, W. Hu, and M. Sugiyama, “Learning from complementary labels,” Advances in neural information processing systems, vol. 30, 2017.
[36] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.
[37] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of features from tiny images,” 2009.
[38] F. Briggs, X. Z. Fern, and R. 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, 2012, pp. 534–542.
[39] M. Guillaumin, J. Verbeek, and C. Schmid, “Multiple instance metric learning from automatically labeled bags of faces,” in European conference on computer vision. Springer, 2010, pp. 634–647.
[40] L. Feng, J. Lv, B. Han, M. Xu, G. Niu, X. Geng, B. An, and M. Sugiyama, “Provably consistent partial-label learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 10 948–10 960, 2020.
[41] H. Wen, J. Cui, H. Hang, J. Liu, Y. Wang, and Z. Lin, “Leveraged weighted loss for partial label learning,” in International Conference on Machine Learning. PMLR, 2021, pp. 11 091–11 100.
[42] L. Feng, T. Kaneko, B. Han, G. Niu, B. An, and M. Sugiyama, “Learning with multiple complementary labels,” in International Conference on Machine Learning. PMLR, 2020, pp. 3072–3081.
[43] T. Ishida, G. Niu, A. Menon, and M. Sugiyama, “Complementary-label learning for arbitrary losses and models,” in International Conference on Machine Learning. PMLR, 2019, pp. 2971–2980.
[44] S. Laine and T. Aila, “Temporal ensembling for semi-supervised learning,” arXiv preprint arXiv:1610.02242, 2016.
[45] S. Zagoruyko and N. Komodakis, “Wide residual networks,” arXiv preprint arXiv:1605.07146, 2016.
[46] T. DeVries and G. W. Taylor, “Improved regularization of convolutional neural networks with cutout,” arXiv preprint arXiv:1708.04552, 2017.
[47] K. Sohn, D. Berthelot, N. Carlini, Z. Zhang, H. Zhang, C. A. Raffel, E. D. Cubuk, A. Kurakin, and C.-L. Li, “Fixmatch: Simplifying semi-supervised learning with consistency and confidence,” Advances in Neural Information Processing Systems, vol. 33, pp. 596–608, 2020.
[48] H. Robbins and S. Monro, “A stochastic approximation method,” The annals of mathematical statistics, pp. 400–407, 1951.
[49] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga et al., “Pytorch: An imperative style, high-performance deep learning library,” Advances in neural information processing systems, vol. 32, 2019.

Meta Objective Guided Disambiguation for Partial Label Learning

Abstract

Index Terms:

I Introduction

II Related Work

III The Proposed Approach

III-A Confidence-Weighted Objective Function

III-B Meta Objective Guided Disambiguation

IV Theoretical Analysis

IV-A Convergence

Definition 1

Definition 2

Theorem 1 (convergence)

IV-B Comparisons with Ordinary Methods

Theorem 2 (effectiveness)

Proof:

IV-C Estimation Error Bounds

Definition 3 (ϵ\epsilon-cover)

Definition 4 (Rademacher Complexity)

Lemma 1

Lemma 2

Theorem 3 (estimation error bounds)

Proof:

V Experiments

V-A Experiment Setting

V-A1 Datasets

V-A2 Compared methods

V-A3 Implementation Details

V-B Experiments on Image Datasets

V-C Experiments on Real-World Datasets

V-D Study On the Size of Validation Set

VI Conclusion

References

Definition 3 ( $\epsilon$ -cover)