Learning From Multi-Dimensional Partial Labels

1 Introduction

Multi-dimensional classification (MDC) aims to assign each instance to multiple classes, which has been seen in a variety of real-world applications, including but not limited to, text categorization [Ortigosa-Hern´andez et al., 2012], gene function prediction [Barutc¸uoglu et al., 2006] and image annotation [Read et al., 2014; Batal et al., 2013; Arias et al., 2016]. In order to train an effective MDC model, it is typically desirable to obtain a large number of precisely annotated data. Unfortunately, obtaining fully labeled data in MDC tasks is usually intractable. As a result, it is non-trivial to learn multidimensional classifiers from partially labeled data.

Weakly-supervised learning has been explored to deal with partially labeled data in various settings. For example, semi-supervised learning (SSL) [Chapelle et al., 2002] learns from both labeled and unlabeled data. In positiveunlabeled learning (PUL) [Denis, 1998; Kiryo et al., 2017], there are only positive labeled data and unlabeled data available. In partial label learning (PLL) [Cour et al., 2011;

∗Corresponding Author.

Liu and Dietterich, 2012; Wu and Zhang, 2018], the groundtruth label is concealed in a set of candidate labels. Recently, there are also some works that address the weakly-supervised learning problem in multiple-label setting, such as semisupervised multi-label learning [Zhan and Zhang, 2017], partial multi-label learning (PML) [Fang and Zhang, 2019; Wang et al., 2019] and semi-supervised multi-dimensional classification [Ortigosa-Hern´andez et al., 2012].

In this work, we consider a new weakly-supervised MDC scenario where the ground-truth labels of each instance are concealed in multiple candidate label sets, i.e. MultiDimensional Partial Label Learning (MDPL). Take the image [Khosla et al., 2011] in Table ?? as an example, it is associated with four class variables {Place, Tree, Dog Breeds, Weather}. It is hard for the annotators to identify all the correct labels, but they can provide some candidate labels with much less effort. Label disambiguation and label correlation extraction pose the serious challenges in MDPL. The noisy information will decrease the generalization performance of

tional semantic information to disambiguate the noisy labels. For example, since there exist some trees in the image, it is more likely to be a Mountain instead of a Glacier.

Our main contributions in this paper are to formulate the MDPL problem and provide an empirical risk minimization (ERM) framework. In particular, we propose a partial hamming loss that incurs a large loss if the predicted labels are not included in candidate label sets. Theoretically, we rigorously present the conditions for ERM learnability of MDPL in both independent and dependent cases. Moreover, we instantiate two MDPL algorithms under our empirical risk minimization framework. Extensive experiments on both synthetic and real-world datasets demonstrate that our proposed methods can effectively handle MDPL tasks.

2 RelatedWork

2.1 Multi-Dimensional Classification

In multi-dimensional classification (MDC), each object is associated with multiple class variables. It is a generalization of multi-label learning [Liu and Tsang, 2017; Shen et al., 2018; Liu et al., 2019] that allows each class variable to have more than two values. Compared to MLL problems, the label correlations in MDC are more sophisticated, because the intraclass labels are exclusive, while inter-class labels may still correlate to each other. One popular strategy for MDC is binary relevance (BR) [Read et al., 2014] that decomposes the original problem into several multi-class classification problems. Despite its computational efficiency, BR neglects the label dependencies and hence the predictive performance is limited. To cope with this shortcoming, many works are proposed, including probabilistic graph model based algorithms [Batal et al., 2013; Benjumeda et al., 2018], classifier chains [Zaragoza et al., 2011], instance-based approaches [Jia and Zhang, 2019] and so on. Nevertheless, all of them require the training data to be precisely labeled, which is demanding and time-consuming.

Consequently, some weakly-supervised multiple-label problems have been studied, such as semi-supervised multilabel learning [Zhao and Guo, 2015; Zhan and Zhang, 2017], partial multi-label learning (PML) [Fang and Zhang, 2019; Wang et al., 2019], semi-supervised multi-dimensional classification [Ortigosa-Hern´andez et al., 2012] and so on. However, most of these learning paradigms explore only multilabel setting where the labels are restricted to be binary and it is non-trivial to study the generalized weakly-supervised MDC problems.

2.2 Partial Label Learning

The partial label learning (PLL) setting is between fully supervised and unsupervised learning setting, but is quantitively different from SSL [Chapelle et al., 2002; Zhan and Zhang, 2017] and PUL [Denis, 1998; Kiryo et al., 2017]. In PLL, each instance is equipped with a set of candidate labels. The ground-truth label is guaranteed to be included and the remaining labels are termed as distractor labels or false positive labels. The biggest challenging issue in PLL is to disambiguate the ground-truth label from the distractor labels and many papers [Cour et al., 2011; Liu and Dietterich, 2012; Wu and Zhang, 2018; Feng and An, 2019; Lv et al., 2020] are presented to address this problem. There are also some works [Fang and Zhang, 2019; Wang et al., 2019] studying partial multi-label learning, which extends PLL problem to the multiple-label learning field. Nonetheless, PML restricts the labels to be binary and thus is unpractical in many realworld tasks [Read et al., 2014].

To bridge this gap, we propose a novel learning paradigm: multi-dimensional partial label learning where the groundtruth labels of each instance are concealed in multiple candidate label sets.

3 Learning Framework

We first formulate the problem of MDPL and introduce an empirical risk minimization framework.

Consider a standard setting of MDC problem with an input space X ⊆ Rm and an output space Y = C1 × C2 × ... × Cd. Here Ci = {li1, li2, ..., liki } is the i-th class space and Y is their Cartesian product. The ultimate goal of MDC is to induce a mapping from X to Y that captures the dependence of the outputs on inputs. To this end, based on a training dataset Q = {(xi, Yi)|xi ∈ X, Yi ∈ Y, 1 ≤ i ≤ n}, a learner chooses an optimal hypothesis h∗ from a given hypothesis space H to minimize the prediction loss. Specifically, common choices of prediction loss (or risk) for MDC include hamming loss and global loss [Read et al., 2014].

In MDPL tasks, we are interested in the case where the correct labels are adulterated by false positive labels. To be more specific, the ground-truth labels are invisible and only a collection of candidate label sets S = {s1, s2, ..., sd} ∈ S is given, where S = (2C1 - ∅) × (2C2 - ∅) × ... × (2Cd - ∅) is the candidate class space and si ⊆ Ci is the i-th candidate label set for the corresponding class space. We denote a complete example by (x, Y, S), where only instance vector x and candidate label collection S are accessible. The goal of MDPL is to learn a multi-dimensional classifier h : X ↦→ Y from multi-dimensional partially labeled data by minimizing the expected hamming loss: LHD (h) = E(x,Y,S)∼D[ 1d ∑di=1 I(hi (x) ̸= yi)], where D is the underlying data distribution, hi (x) is the i-th predicted label and yi denotes the i-th ground-truth label. Since the correct labels are invisible in the training dataset, we can not minimize the standard hamming loss directly. Inspired by partial 0/1 loss [Cour et al., 2011], we introduce a multi-dimensional version named expected partial hamming loss,

An obvious observation is that expected partial hamming loss is an underestimate of the true expected hamming loss. Thus, it is not a surrogate and we have to explore some conditions where minimizing the partial loss can also bound the true loss. Moreover, a large loss will incur if the predicted labels are not included in candidate label sets. It motivates us to employ the VC-dimension of the inside-out set binary classification task as a bridge to complete our theoretical proof.

In summary, based on our proposed expected partial hamming loss, we propose an empirical risk minimization framework for MDPL, and each hypothesis h will be evaluated by average partial hamming loss,

where Z = {(xi, Si)|xi ∈ X, Si ∈ S, 1 ≤ i ≤ n} is the partially labeled training dataset and sij is the j-th candidate label set of i-th training example.

4 Learnability of MDPL

In this section, we will discuss how to bound the true loss using expected partial hamming loss. In this paper, we only investigate the realizable case where an optimal hypothesis h∗ makes the risk LHD (h∗ ) = 0.

4.1 Independent Case

We first consider the independent case, i.e. the labels are independent to each other. Then we can simply decompose the MDPL problem to a set of partial label learning problems.

Many works have studied PLL problems based on minimizing the upper-bound of risk LDp , usually, the expected 0/1 loss [Cour et al., 2011]: LDp (hp) = E(x,y,s)∼Dp [I(hp(x) ̸= y)], where Dp is the underlying distribution of a PLL task. Based on this risk, we obtain the following lemma.

Lemma 1. Assume that the labels in an MDPL problem are independent to each other. Then if a PLL problem adopts the expected 0/1 loss as risk and it is PAC-learnable with sample complexity n0(Hp, δ, ϵ), the MDPL problem is also PAC-learnable with sample complexity as follows,

where Hip is the i-th PLL hypothesis space.

Proof. If a PLL problem is PAC-learnable [Shalev-Shwartz and Ben-David, 2014], then for every ϵ, δ ∈ (0, 1), when the training set has size n ≥ n0(Hp, δ, ϵ), there exists an ERM learner Ap that returns a hypothesis hp ∈ Hp with expected 0/1 loss LDp (hp) ≤ ϵ. Since the labels in this MDPL problem are independent to each other, the MDPL task can be decomposed to d PLL problems. By running an ERM learner Aip on each single PLL problem, and aggregating the hypothesises hi = Aip (Z ip ), we can obtain an MDPL classifier h = [hi ]d, where Z ip is the i-th PLL training dataset. When the training set has size n ≥ n1(H, δ, ϵ) ≥ n0(Hip , δ, ϵ), for every ϵ, δ ∈ (0, 1), the following inequality holds with probability no less than 1 - δ,

We conclude that the MDPL problem is PAC-learnable with sample complexity n1(H, δ, ϵ).

The learnability of partial label learning can refer to many works [Cour et al., 2011; Ishida et al., 2017]. For instance, the small ambiguity degree condition, proposed by [Cour et al., 2011], is one of the most popular assumptions in PLL problems.

4.2 Dependent Case

During the past decades, a variety of works [Zaragoza et al., 2011; Read et al., 2014; Shen et al., 2018] have proved that neglecting label correlations may achieve degenerated performance in multiple-label problems. Thus, it is crucial to study the problem in what condition can MDPL tasks be learned in the dependent case.

Here we propose a sufficient condition for the PAClearnability of MDPL tasks.

Theorem 1. In an MDPL problem, if there exists a positive constant γ > 0 such that,

then in realizable case, the MDPL problem is PAC-learnable.

We first introduce an MDC algorithm, Class Powerset (CP) [Read et al., 2014], into MDPL scenario. The basic idea is to transform the MDC problem to a multi-class classification problem by regarding each label combination as a new class. Then it learns a multi-class classifier f : X ↦→ ˜ Y where ˜ Y is the new label space with size ∏di=1 ki. Since all the label combinations are considered, we can fully explore the label correlations across the class space.

Specifically, we call an ERM learner Acp that returns a hypothesis minimizing the multi-class risk, i.e. expected 0/1 loss. Nonetheless, in MDPL setting, the learner does not have direct access to the precise data. To deal with this issue, we involve a surrogate loss called global loss LG with corresponding partial global loss LGP , which are defined as,

We can immediately obtain their relation,

The last step is to design a CP algorithm Acp that minimizes the empirical partial global loss,

In traditional MDC setting, it is a typical multi-class learning problem. Let Hcp b be a binary hypothesis class with VCdimension τ = VCdim(Hcp b ), e.g., Hcp b is linear with τ =m.

Suppose that the multi-class hypothesis space Hmc is constructed above Hcp b using one-versus-all strategy. According to Lemma 29.5 in [Shalev-Shwartz and Ben-David, 2014], the Natarajan dimension [Natarajan, 1989] of Hmc enjoys an upper-bound of,

where Ndim(·) denotes the Natarajan dimension of a hypothesis space. Nevertheless, in MDPL setting, our learning problem is no longer a multi-class task and the Natarajan dimension can not directly yield the sample complexity.

Our strategy is to construct a binary classification task from the problem above. Given a partial example (x, S), the binary classifier should predict whether there exist some predicted labels yi outside their corresponding candidate label sets, i.e. returning I(∃i, yi /∈ si). We observe that the binary classification loss is the partial global loss. Therefore, we can design an ERM learner Ab that calls Acp and then transforms the prediction to binary output space. Compared with class powerset method, it is unpractical but provides good theoretical results. Now our task is to explore the VC-dimension of the binary classifier.

Denote the hypothesis space of this binary classification task by Hb. We have the following lemmas.

Lemma 2. Let K = ∏di=1 ki. The VC-dimension of Hb can be bounded by,

Proof. Let ν = VCdim(Hb) and µ = Ndim(Hmc). Then, the maximum size of a set that Hb can shatter is ν. In other words, there are 2ν different dichotomies (i.e., labelings) induced by Hb over these ν instances. Based on Lemma 29.4 in [Shalev-Shwartz and Ben-David, 2014], we can conclude that,

Taking the natural logarithm of both sides yields that,

To bound ν, we involve a function g(x) = e logx - x. Its maximum value g(x) = 0 is obtained when g′ (x) = 0, i.e. x = e. Hence, g(x) ≤ 0 holds for all x > 0. Choosing x = νµ gives that log ν ≤ ν eµ + log µ. Hence,

Combining Eq. (9) and Eq (13), we obtain the desired result.

Lemma 3. For every δ, ϵ ∈ (0, 1), every distribution D over X, and the binary classification task defined above, if the realizable assumption holds, when running algorithm Ab on a training set of size n satisfying

then the algorithm returns a hypothesis h such that with probability of at least 1 - δ, LGP D (h) ≤ ϵ.

The proof can be found in [Shalev-Shwartz and Ben-David, 2014].

Now recalling Eq. (5) and Eq. (7), when Ab runs on a training set of size n2(Hb, δ, ϵγ ), the hamming loss has the following bound,

Taking the corresponding multi-class hypothesis h as our solution, we obtain a provable algorithm that ensures the MDPL problems to be PAC-learnable with a finite sample complexity n2(Hb, δ, ϵγ ). Therefore, Theorem 1 is proved.

4.3 Further Discussion

Remark of the Proposed Condition

Suppose we know the distribution of partial examples. We can design a Bayesian optimal classifier with zero partial hamming loss. In realizable case, our goal is to find a hypothesis h∗ that satisfies LHD (h∗ ) = 0. Denote the optimal hypothesis set by H∗ . If there exists a hypothesis ˆh /∈ H∗ such that LPD (ˆh) = 0, even the Bayesian optimal classifier can not guarantee to return an optimal solution. Hence, our sufficient condition actually ensures the ERM learner to return an optimal hypothesis from H∗ .

Relation to PML

Another observation is that the recently popularized task of partial multi-label learning also benefits from our theoretical analysis. In a typical PML problem, the ground-truth binary labels are adulterated with some irrelevant labels. If we regard each candidate label as a two-element candidate label set, it can be categorized into MDPL problems. In independent case, each positive label is accompanied by a negative label. Thus, it should be treated as a positive-unlabeled learning problem instead of a PLL problem, whose learnability can be referred to [Denis, 1998]. In the dependent case, PML enjoys the same PAC-learnability as MDPL. In reality, PML is an untypical branch of MDPL, because only positive labels will be partially labeled.

Practical Implementation

According to our theoretical analysis, two MDPL algorithms are instantiated under our ERM framework. In independent case, we propose MDPL-BR that reduces an MDPL problem to multiple PLL tasks, which can be solved by any off-theshelf PLL method. And we present the MDPL-CP method for dependent case. Note that by Eq. (7), partial hamming loss is also a surrogate loss to partial global loss. Therefore, we unify the two algorithms by minimizing the proposed partial hamming loss. To validate the theoretical results, we consider all the label combinations in the experiments. However, such a strategy may decrease the scalability of MDPLCP. This problem can be alleviated by an ensemble technique [Tsoumakas et al., 2011]. Due to the page limitation, we leave it for future work.

Table 2: Results of hamming accuracy on all datasets (mean±standard deviation). The best ones are in bold.

5 Experiments

In this section, we evaluate the performance of our proposed methods on both synthetic and real-world dataset. All the computations are performed on a workstation with an i75930K CPU, a TITAN Xp GPU and 64GB main memory running Linux platform.

5.1 Dataset

Synthetic Datasets

We follow the experimental setting in [Wang et al., 2019] and synthesize a total of 20 MDPL datasets from 5 realworld MDC datasets. The MDC datasets are collected from UCI repository [Dheeru and Karra Taniskidou, 2017]: 1) Bridges estimates bridge properties from specific constraints; 2) WQplant and WQanimals determine the plant and animal species in Slovenian rivers; 3) Flare predicts number of times that certain types of solar flare occurred within 24 hours period; 4) Thyroid determines types of thyroid problems based on patient information. For each class variable of an example, we randomly select some negative labels and aggregate them with the ground-truth label to obtain a candidate label set. Different configurations are controlled by the number of average candidate labels in each class space. The detailed information is reported in Table 3.

Puppy Dataset

Because the MDPL is a new learning setting, there is no publicly available MDPL dataset yet. To further boost our empirical studies, this paper builds one real-world MDPL dataset Puppy. A total of 102 dog images are collected and categorized to 4 class variables {Place, Tree, Dog Breeds, Weather}. We manually tagged all the data examples by ground-truth labels. The candidate label sets are collected by crowdsourcing. Moreover, we extract 1000-dimensional fc-8 feature of these images using a pre-trained VGG-19 [Simonyan and Zisserman, 2015] model.

All the datasets are randomly split in to 80% training and 20% testing. We run five times on each dataset and the mean hamming accuracy with standard deviation are reported.

5.2 Baselines

We compared the proposed algorithms with three state-ofthe-art baselines: 1) P-VLS: PARTICLE [Fang and Zhang, 2019] is an effective PML method that integrates the label propagation and calibrated label ranking techniques. By regarding each nominal label as a binary label, the MDPL problem can be transformed to a PML problem and solved by PARTICLE. In this work, we choose the virtual label splitting based version, i.e. P-VLS. 2)CoH: CoH [Shen et al., 2018] is a label embedding based multi-label algorithm that jointly compresses the input and output to a latent space by co-hashing. We employ it to deal with MDPL tasks by treating all the candidate labels as valid ones. Note that P-VLS and CoH will return a group of positive labels in an uncertain size. Hence, we take the label with maximum score in its class space as our prediction. 3) MDPL-kNN: we induce a knearest neighbor model from MDPL data and the prediction is made by voting in each class space.

We use CLPL [Cour et al., 2011] as the base PLL predictor in MDPL-BR method. For MDPL-CP, we choose linear classifier as the base hypothesis. In practice, we also adopt a naive convex surrogate loss in [Jin and Ghahramani, 2002] to implement MDPL-CP. For our methods, the empirical risk is optimized by stochastic gradient algorithm. We also add an l2 regularization term. The learning rate and the regularization parameters are fine-tuned by cross-validation. The number of nearest neighbors is set as k = 10 for all the kNN-based approaches. Following the experimental setting in [Fang and Zhang, 2019], we set thr = 0.9 and α = 0.95 for P-VLS. Finally, following [Shen et al., 2018], the parameters of CoH are set as α = 100 and d = 10.

5.3 Results

Table 2 lists the results of hamming accuracy of all the methods on Puppy and 20 synthetic MDPL datasets. Figure 1 shows some real predictive results on some test examples from Puppy dataset.

From the results, we can see that: 1) MDPL-CP algorithm achieves the best performance, which verifies our theoretical analysis. For instance, on Puppy dataset, MDPL-CP algorithm improves the best result of the baselines by 4.3%. By considering all the label combinations, it fully explores the label correlations with theoretically guaranteed disambiguation ability. 2) MDPL-BR works well on some datasets such as Thyroid. However, it generally underperforms MDPL-CP because of neglecting the correlations, which also further effects its disambiguating ability. 3) P-VLS and CoH are inferior to MDPL-CP method. Since they are designed for partial multi-label tasks, they will wrongly learn the label correlations of intra-class labels due to the false positive labels, which leads to degenerated performance. 4) Without considering both correlations and ambiguity, MDPL-kNN underperforms MDPL-CP and MDPL-BR. By these observations, we conclude that our proposed methods can effectively tackle the MDPL problems.

6 Conclusion

In this paper, we propose a novel learning paradigm named Multi-Dimensional Partial Label Learning (MDPL), where each data instance is equipped with multiple candidate label sets. Based on our proposed partial hamming loss, we present an empirical risk minimization framework for MDPL. Theoretically, we rigorously prove the ERM learnability of MDPL in specific conditions. We further provide two effective MDPL algorithms under our ERM framework. In independent case, we propose MDPL-BR that decomposes the original task to a series of partial label learning problems. In dependent case, we propose MDPL-CP which fully explores the label correlations. Extensive experiments on both synthetic and real-world datasets validate our theoretical studies and the effectiveness of our proposed methods.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 61976161) and Key R&D Program of Zhejiang Province (Grant No. 2020C01024).